二叉樹重建(給定前序司倚、中序遍歷的結(jié)果)
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){};
};
TreeNode* rebuild(vector<int> preOrder, vector<int> inOrder){
if(preOrder.empty()||inOrder.empty()){
return NULL;
}
// vector<int>::iterator it;
// // cout<<"pre"<<endl;
// for(it=preOrder.begin();it!=preOrder.end();it++){
// cout<<*it<<" ";
// }
// cout<<endl<<"in"<<endl;
// for(it=inOrder.begin();it!=inOrder.end();it++){
// cout<<*it<<" ";
// }
// cout<<endl;
int idx_find = 0;
for(idx_find=0;idx_find<inOrder.size();idx_find++){
if(inOrder[idx_find]==preOrder[0]) break;
}
// cout<<"idx:"<<idx_find<<endl;
// cout<<"val:"<<inOrder[idx_find]<<endl;
TreeNode* root = new TreeNode(preOrder[0]);
vector<int> preLeft(preOrder.begin()+1,preOrder.begin()+idx_find+1);//(begin,end) end is not in vector
vector<int> preRight(preOrder.begin()+idx_find+1,preOrder.end());
vector<int> inLeft(inOrder.begin(),inOrder.begin()+idx_find);
vector<int> inRight(inOrder.begin()+idx_find+1,inOrder.end());
root->left = rebuild(preLeft,inLeft);
root->right = rebuild(preRight,inRight);
return root;
}
int main(){
int pre[] = {1,2,4,7,3,5,6,8};
int in[] = {4,7,2,1,5,3,8,6};
vector<int> preOrder(pre,pre+sizeof(pre)/sizeof(int));
vector<int> inOrder(in,in+sizeof(in)/sizeof(int));
TreeNode* reBiTree=rebuild(preOrder,inOrder);
}
要對比兩個序列，找到根篓像，劃分為左右子樹动知，再遞歸建立左右子樹
注意用iterator生成vector時第二個參數(shù)的指向的元素不進入vector
注意無左右子樹時返回NULL
2 stacks mock queue
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
int ret = stack2.top();
stack2.pop();
while(!stack2.empty()){
stack1.push(stack2.top());
stack2.pop();
}
return ret;
}
private:
stack<int> stack1;
stack<int> stack2;
};
push沒啥特別，隊列的pop在頭上员辩，把stack的元素倒到另一個棧盒粮，然后pop然后倒回。相當于彈出棧底元素
旋轉(zhuǎn)數(shù)組找最小值
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾屈暗，我們稱之為數(shù)組的旋轉(zhuǎn)拆讯。
輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素养叛。
例如數(shù)組[3,4,5,1,2]為[1,2,3,4,5]的一個旋轉(zhuǎn)种呐，該數(shù)組的最小值為1。
NOTE：給出的所有元素都大于0弃甥，若數(shù)組大小為0爽室，請返回0
暴力法不考慮。使用改進二分法
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int first=0,last=rotateArray.size()-1,mid;
while(first<last){
mid = (first+last)/2;
if(rotateArray[mid]>rotateArray[last]){
first = mid+1;
//mid = (first+last)/2;
}
else if(rotateArray[mid]<rotateArray[last]){
last = mid;
}
else{
last--;
}
}
return rotateArray[last];
}
};
旋轉(zhuǎn)前數(shù)組可以是0淆攻，0阔墩，1，1瓶珊，1啸箫，2，4
比較難理解mid 和target處數(shù)字相等的情況
青蛙跳臺階問題
519966841.jpg
二進制問題
正數(shù)右移最終為0
負數(shù)右移伞芹，保持負數(shù)(首位為1)最終為-1
正數(shù)左移不保持正數(shù)(1左移31變最小負數(shù))
負數(shù)左移不保持負數(shù)忘苛，有正有負
求double base 的整數(shù)次方
注意指數(shù)為負數(shù)的時候
c++ STL copy()
copy(iterator start, iterator end, container.begin())
求鏈表倒數(shù)第k個元素
普通解法：遍歷求長度蝉娜，再減k再循環(huán)定位到目標位置
優(yōu)化：使用快慢指針方法，讓快指針先走k步扎唾，然後快慢指針同時走直到快指針到達尾部
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(!pListHead) return NULL;
ListNode* p=pListHead, *q=pListHead;
while(k--){
if(p){
p = p->next;
}
else return NULL;
}
//if(p!=NULL||k!=0) return NULL;
while(p){
p = p->next;
q = q->next;
}
return q;
}
反轉(zhuǎn)鏈表
普通解法：通過開辟新vector
優(yōu)化：不開辟新空間召川。用一個指針正向遍歷鏈表，將每個元素拉出來加入到反轉(zhuǎn)鏈表的頭部胸遇。ret指針指向反轉(zhuǎn)鏈表(tmp)頭部荧呐，一個指針指向正向遍歷指針的下一個元素，因為否則取走之后找不到頭了纸镊。
ListNode* ReverseList(ListNode* pHead) {
ListNode *ret, *node, *nextNode;
ret = NULL;
node = pHead;
nextNode = pHead->next;
while(node){
node->next = ret;
ret = node;
node = nextNode;
nextNode = nextNode->next;
}
return ret;
}
合并兩個有序鏈表
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
// if(!pHead1){
// return pHead2;
// }
// if(!pHead2){
// return pHead1;
// }
// ListNode* ret, *p;
// bool flag = true;
// while(pHead1&&pHead2){
// int less;
// if((pHead1->val) <= (pHead2->val)){
// less = pHead1->val;
// pHead1 = pHead1->next;
// }
// else{
// less = pHead2->val;
// pHead2 = pHead2->next;
// }
//int less = pHead1->val <= pHead2->val ? pHead1->val : pHead2->val;
// ListNode* t = new ListNode(less);
// if(flag){
// ret = t;
// p = ret;
// flag = false;
// }
// else{
// p->next = t;
// p = p->next;
// }
// }
// if(pHead1){
// p->next = pHead1;
// }else if(pHead2){
// p->next = pHead2;
// }
// return ret;
}
};
很自然的解法倍阐。
還有遞歸方法，我沒寫逗威，先貼著
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if (!pHead1) return pHead2;
if (!pHead2) return pHead1;
if (pHead1->val <= pHead2->val) {
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
}
else {
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
}
};
很簡潔收捣，我什么時候才能如此簡潔..
24 Sep
判斷樹b是否為樹a的子樹
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool dfs(TreeNode* r1, TreeNode* r2){
if(!r2) return true;
if(!r1) return false;
return r1->val==r2->val && dfs(r1->left,r2->left) && dfs(r1->right,r2->right);
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot1==NULL||pRoot2==NULL) return false;
if (HasSubtree(pRoot1->left, pRoot2)) return true;
if (HasSubtree(pRoot1->right, pRoot2)) return true;
return dfs(pRoot1,pRoot2);
}
};
官方解釋，在hasSubtree中庵楷，返回深度遍歷的結(jié)果||左子樹判斷||右子樹判斷，heuristic楣颠。我的if-if-return其實是靠dfs在return 吧
return dfs(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) ||
HasSubtree(pRoot1->right, pRoot2);
25 Sep
順時針打印矩陣
做了半天尽纽，原來還能打印矩形的矩陣。童漩。寫不動了弄贿，看看答案吧
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
int r = matrix.size(), c = matrix[0].size();//行和列
vector<int> result;
if (r == 0 || c == 0)
return result;
int left = 0, right = c - 1;
int top = 0, bottom = r - 1;
while (left <= right && top <= bottom)
{
//從左到右輸出第一行
for (int i = left; i <= right; i++)
{
//將一個新的元素添加到最后面
result.push_back(matrix[top][i]);
}
//從上到下，不包括第一行最后一個數(shù)矫膨，即top+1
for (int i = top + 1; i <= bottom; i++)
{
result.push_back(matrix[i][right]);
}
//從右到左差凹，不包括最后一行最后一個數(shù)，即right-1
if (top != bottom)
for (int i = right - 1; i >= left; i--)
{
result.push_back(matrix[bottom][i]);
}
//從下到上侧馅，不包括最后一行最后一個數(shù)和第一行第一個數(shù)
if (left != right)
for (int i = bottom - 1; i >= top + 1; i--)
{
result.push_back(matrix[i][left]);
}
left++, top++, right--, bottom--;
}
return result;
}
};
尋找棧中最小元素危尿，且時間復雜度為1
看解答才知道怎么回事，用一個輔助棧存normal棧更新時最小元素馁痴，查詢min時彈出輔助棧的棧頂即可谊娇。
class Solution {
public:
stack<int> normal,minval;
void push(int value) {
normal.push(value);
if(minval.empty()) minval.push(value);
else if(value<minval.top()){
minval.push(value);
}
}
void pop() {
if(normal.top()==minval.top()){
minval.pop();
}
normal.pop();
}
int top() {
return normal.top();
}
int min() {
return minval.top();
}
};
輔助棧真是
判斷出棧順序是否正確
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
vector<int>::iterator it,pre;
stack<int> normal;
it = find(pushV.begin(),pushV.end(),popV[0]);
if(it==pushV.end()){
return false;
}
pushV.erase(it);
pre = it-1;
for(int i=1;i<popV.size();i++){
// if(popV[i]!=(*pre)&&popV[i]!=(*it)) return false;
if(popV[i]!=(*pre)){
bool hasAfter = false;
while(it!=pushV.end()){
if(*it == popV[i]) {
hasAfter = true;
break;
}
it++;
}
if(!hasAfter)return false;
pushV.erase(it);
pre = it-1;
}
else {
it = find(pushV.begin(),pushV.end(),popV[i]);
pushV.erase(it);
if(it-pushV.begin()==0){
pre = it+1;
continue;
}
pre = it-1;
}
}
return true;
}
};
按層從左到右打印二叉樹節(jié)點
vector<int> PrintFromTopToBottom(TreeNode* root) {
deque<TreeNode *> q;
vector<int> ret;
if(!root) return ret;
q.push_back(root);
while(!q.empty()){
TreeNode* tmp=q.front();
ret.push_back(tmp->val);
if(tmp->left) q.push_back(tmp->left);
if(tmp->right) q.push_back(tmp->right);
q.pop_front();
}
return ret;
}
將根節(jié)點加入到隊列q中，取隊列頭罗晕，將其左右子樹加入隊列济欢，隊列頭加入返回向量中
判斷一個序列是不是二叉搜索樹后序遍歷結(jié)果
bool VerifySquenceOfBST(vector<int> sequence) {
int n=sequence.size();
if(n==0) return false;
int j=0;
for(int i=n-1;i>0;i--)
{
while(sequence[j]<sequence[i]) j++;
while(sequence[j]>sequence[i]) j++;
if(j<i) return false;
j=0;
}
return true;
}
這是什么騷操作，看不懂
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size()==1) {
return true;
}
int root = sequence.back();
int idx=0;
for(idx;idx<sequence.size();idx++){
if(sequence[idx]>root) break;
}
if(idx==0) return true;
for(int i=0;i<idx;i++){
if(sequence[i]>root) return false;
}
for(int i=idx;i<sequence.size();i++){
if(sequence[i]<root) return false;
}
vector<int> left(sequence.begin(),sequence.begin()+idx);
vector<int> right(sequence.begin()+idx,sequence.end());
if(VerifySquenceOfBST(left)&&VerifySquenceOfBST(right)) return true;
return false;
}
我寫的小渊，平臺報內(nèi)存超了不通過
