剑指week3 剑指week3

1.反转链表 【剑指week3】迭代版本:

class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* pre=NULL,*cur=head; while(cur) { auto next=cur->next; cur->next=pre; pre=cur; cur=next; } return pre; } };

递归版本:注意这个函数的意义即可，他的操作是将链表反转过来，并且返回的是尾结点

class Solution { public: ListNode* reverseList(ListNode* head) { while(!head||!head->next) return head; auto tail=reverseList(head->next); head->next->next=head; head->next=NULL; return tail; } };

2.合并两个链表采用归并排序的思想，逐个比较然后添加

class Solution { public: ListNode* merge(ListNode* l1, ListNode* l2) { auto dummy=new ListNode(-1); auto cur=dummy; while(l1&&l2) { if(l1->valval) { cur->next=l1; cur=l1; l1=l1->next; } else { cur->next=l2; cur=l2; l2=l2->next; } } if(l1)cur->next=l1; else if(l2)cur->next=l2; return dummy->next; } };

3.树的子结构

class Solution { public: bool hasSubtree(TreeNode* pRoot1,TreeNode* pRoot2) { if(!pRoot1||!pRoot2)return false; if(ispart(pRoot1,pRoot2))return true; return hasSubtree(pRoot1->left,pRoot2)||hasSubtree(pRoot1->right,pRoot2); } bool ispart(TreeNode* pRoot1,TreeNode* pRoot2) { if(!pRoot2)return true; if(!pRoot1||pRoot1->val!=pRoot2->val) return false; return ispart(pRoot1->left,pRoot2->left)&&ispart(pRoot1->right,pRoot2->right); } };

4.二叉树的镜像

class Solution { public: void mirror(TreeNode* root) { if(!root)return ; mirror(root->left); mirror(root->right); swap(root->left,root->right); } };

5.对称的二叉树

class Solution { public: bool isSymmetric(TreeNode* root) { if(!root)return true; return dfs(root->left,root->right); } bool dfs(TreeNode* p,TreeNode* q) { if(!p||!q)return !p&&!q; if(p->val!=q->val)return false; return dfs(p->left,q->right)&&dfs(p->right,q->left); } };

6.顺时针打印矩阵

class Solution { public: vector printMatrix(vector > matrix) { vectorvt; if(matrix.empty()||matrix[0].size()==0)return vt; int n=matrix.size(),m=matrix[0].size(); int book[n+5][m+5]; memset(book,0,sizeof book); int tol=1,x=0,y=0; book[0][0]=1; vt.push_back(matrix[0][0]); while(tol=0&&book[x][y-1]==0) { vt.push_back(matrix[x][--y]); tol++; book[x][y]=1; } while(x-1>=0&&book[x-1][y]==0) { vt.push_back(matrix[--x][y]); tol++; book[x][y]=1; } } return vt; } };

7.包含main的栈

class MinStack { public: stackstk,min_stk; /** initialize your data structure here. */ MinStack() {}void push(int x) { if(stk.empty()|| min_stk.top()>=x)min_stk.push(x); stk.push(x); }void pop() { if(stk.top()==min_stk.top())min_stk.pop(); stk.pop(); }int top() { return stk.top(); }int getMin() { return min_stk.top(); } };

8.栈的压入、弹出序列

class Solution { public: bool isPopOrder(vector pushV,vector popV) { if(pushV.size()!=popV.size())return false; stackst; int i=0; for(auto x:pushV) { st.push(x); while(st.size()&&st.top()==popV[i]) { st.pop(); i++; } } return st.empty(); } };

9.不分行从上往下打印二叉树层序遍历板子题

class Solution { public: vector printFromTopToBottom(TreeNode* root) { queueq; vectorvt; if(!root)return vt; q.push(root); while(!q.empty()) { TreeNode* top=q.front(); q.pop(); vt.push_back(top->val); if(top->left)q.push(top->left); if(top->right)q.push(top->right); } return vt; } };

10.分行从上往下打印二叉树通过记录队列长度达到分层的目的

class Solution { public: vector> printFromTopToBottom(TreeNode* root) { queueq; vector>res; if(!root)return res; q.push(root); while(!q.empty()) { vectorcur; int n=q.size(); //每次统计队列中的个数来做到分层 for(int i=0; ival); if(top->left)q.push(top->left); if(top->right)q.push(top->right); } res.push_back(cur); } return res; } };

11.之字形打印二叉树

class Solution { public: vector> printFromTopToBottom(TreeNode* root) { int book=1; queueq; vector>res; if(!root)return res; q.push(root); while(!q.empty()) { int n=q.size(); vectorvt; for(int i=0; ival); if(top->left) q.push(top->left); if(top->right) q.push(top->right); } if(book==1) res.push_back(vt); else { reverse(vt.begin(),vt.end()); res.push_back(vt); } book=-book; } return res; } };