Loading... 持续更新中...... <!--more--> # 第 1 天 栈与队列(简单) ## [剑指 Offer 09. 用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/) <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-357052f85c2b59a29b13c0d886fdc1f993" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-357052f85c2b59a29b13c0d886fdc1f993" class="collapse collapse-content"><p></p> ```cpp class CQueue { public: CQueue() { } stack<int>s1,s2; void appendTail(int value) { s1.push(value); } int deleteHead() { if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } if(s2.empty()) return -1; int tmp=s2.top(); s2.pop(); return tmp; } }; /** * Your CQueue object will be instantiated and called as such: * CQueue* obj = new CQueue(); * obj->appendTail(value); * int param_2 = obj->deleteHead(); */ ``` <p></p></div></div></div> ## [剑指 Offer 30. 包含min函数的栈](https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/) <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-a2c869fbc38f905f1d25db1aab328c8718" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-a2c869fbc38f905f1d25db1aab328c8718" class="collapse collapse-content"><p></p> 构造一个辅助栈,使辅助栈顶元素始终为当前栈内元素的最小值 ```cpp class MinStack { public: /** initialize your data structure here. */ MinStack() { } stack<int>st; stack<int>m; void push(int x) { st.push(x); if(m.empty()||m.top()>=x) m.push(x); } void pop() { if(st.top()==m.top()) m.pop(); st.pop(); } int top() { return st.top(); } int min() { return m.top(); } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->min(); */ ``` <p></p></div></div></div> # 第 2 天 链表(简单) ## [剑指 Offer 06. 从尾到头打印链表](https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/) 存入数组中然后反转一下 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-4f58e052213f91c4e1807bd658f2c20d36" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-4f58e052213f91c4e1807bd658f2c20d36" class="collapse collapse-content"><p></p> ```cpp /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: vector<int> reversePrint(ListNode* head) { vector<int>v; while(head) { v.push_back(head->val); head=head->next; } reverse(v.begin(),v.end()); return v; } }; ``` <p></p></div></div></div> ## [剑指 Offer 24. 反转链表](https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/) 让当前节点的下一个节点指向上一个节点,使用一个临时的指针来实现 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-5438aead8a0ee7604e839b8a6c4cf1ac100" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-5438aead8a0ee7604e839b8a6c4cf1ac100" class="collapse collapse-content"><p></p> ```cpp /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *cnt=head,*ans=NULL; while(cnt) { ListNode *tmp=cnt->next; cnt->next=ans; ans=cnt; cnt=tmp; } return ans; } }; ``` <p></p></div></div></div> ## [剑指 Offer 35. 复杂链表的复制](https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/) 待补 # 第三天 字符串(简单) ## [剑指 Offer 05. 替换空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/) 直接遍历 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-9a0e31da034925300c663ec2b0051c9e60" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-9a0e31da034925300c663ec2b0051c9e60" class="collapse collapse-content"><p></p> ```cpp class Solution { public: string replaceSpace(string s) { string ans; for(auto i:s) { if(i==' ') ans+="%20"; else ans+=i; } return ans; } }; ``` <p></p></div></div></div> ## [剑指 Offer 58 - II. 左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/) <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-6b8210d7fcb2e2473f5134b0c967feca93" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-6b8210d7fcb2e2473f5134b0c967feca93" class="collapse collapse-content"><p></p> ```cpp class Solution { public: string reverseLeftWords(string s, int n) { string ans=""; ans+=s.substr(n,s.size()); ans+=s.substr(0,n); return ans; } }; ``` <p></p></div></div></div> # 第 4 天 查找算法(简单) ## [剑指 Offer 03. 数组中重复的数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/) 构建元素的索引和值为一对一的关系,如果当前索引已经有值并且和当前值相同,则出现多次 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-8e0940f2b7ada0cb0655865e7798be226" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-8e0940f2b7ada0cb0655865e7798be226" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int findRepeatNumber(vector<int>& nums) { int l=nums.size(); int i=0; while(i<l) { if(nums[i]==i) { i++; continue; } if(nums[nums[i]]==nums[i]) return nums[i]; swap(nums[i],nums[nums[i]]); } return -1; } }; ``` <p></p></div></div></div> ## [剑指 Offer 53 - I. 在排序数组中查找数字 I](https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/) `lower_bound`和`upper_bound`的使用 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-ebf0eb81571921ea829b8f99db2f91905" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-ebf0eb81571921ea829b8f99db2f91905" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int search(vector<int>& nums, int target) { int l_place=lower_bound(nums.begin(),nums.end(),target)-nums.begin(); int r_place=upper_bound(nums.begin(),nums.end(),target)-nums.begin(); return r_place-l_place; } }; ``` <p></p></div></div></div> ## [剑指 Offer 53 - II. 0~n-1中缺失的数字](https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/) ### 遍历 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-1778eb04dec6912a819b4e29ec1f1f5a71" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-1778eb04dec6912a819b4e29ec1f1f5a71" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int missingNumber(vector<int>& nums) { int l=nums.size(); for(int i=0;i<l;i++) { if(nums[i]!=i) return i; } return l; } }; ``` <p></p></div></div></div> ### 二分 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-81dd949e49478f6cf68a152172b9845b17" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-81dd949e49478f6cf68a152172b9845b17" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int missingNumber(vector<int>& nums) { int l=0,r=nums.size()-1; while(l<=r) { int mid=(l+r)/2; if(nums[mid]>mid) r=mid-1; else l=mid+1; } return l; } }; ``` <p></p></div></div></div> # 第 5 天 查找算法(中等) ## [剑指 Offer 04. 二维数组中的查找](https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/) ### 二分 对每一行进行二分,时间复读$O(n \log(m))$ <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-4209a6f6969459e7c517746df69737cc24" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-4209a6f6969459e7c517746df69737cc24" class="collapse collapse-content"><p></p> ```cpp class Solution { public: bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) { for(auto i:matrix) { int place=lower_bound(i.begin(),i.end(),target)-i.begin(); if(place!=i.size()&&i[place]==target) return true; } return false; } }; ``` <p></p></div></div></div> ### 线性查找 从右上角开始,如果当前元素比target大,往左走;如果比target小,向下走。时间复杂度为$O(n+m)$ <span style='color:red'>注意数组为空的情况</span> <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-40bf10b4bdc7841fa382a0f7a06f630d4" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-40bf10b4bdc7841fa382a0f7a06f630d4" class="collapse collapse-content"><p></p> ```cpp class Solution { public: bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) { int n=matrix.size(); if(!n) return false; int m=matrix[0].size(); int i=0,j=m-1; while(i<n&&j>=0) { if(matrix[i][j]<target) i++; else if(matrix[i][j]>target) j--; else return true; } return false; } }; ``` <p></p></div></div></div> ## [剑指 Offer 11. 旋转数组的最小数字](https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/) ### 遍历 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-5152063ef4a493e15b88402a73bbd3e960" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-5152063ef4a493e15b88402a73bbd3e960" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int minArray(vector<int>& numbers) { int ans=numbers[0]; for(auto i:numbers) ans=min(ans,i); return ans; } }; ``` <p></p></div></div></div> ### 二分 注意相等的情况,需要遍历 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-4bde82bb7ef28c9807dc2f38614393e639" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-4bde82bb7ef28c9807dc2f38614393e639" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int minArray(vector<int>& numbers) { int l=0,r=numbers.size()-1; int ans=10000000; while(l<r) { int mid=(l+r)/2; if(numbers[mid]>numbers[r]) l=mid+1; else if(numbers[mid]<numbers[r]) r=mid; else { for(int i=l;i<=r;i++) ans=min(ans,numbers[i]); return ans; } } return numbers[l]; } }; ``` <p></p></div></div></div> ## [剑指 Offer 50. 第一个只出现一次的字符](https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/) 直接用`map`存就行,可以把字符去一下重优化时间 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-124a55f9f993a505953fd62e892650ff11" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-124a55f9f993a505953fd62e892650ff11" class="collapse collapse-content"><p></p> ```cpp class Solution { public: char firstUniqChar(string s) { unordered_map<char,int>mp; char ans=' '; vector<char>v; for(auto i:s) { if(!mp[i]) v.push_back(i); mp[i]++; } for(auto i:v) { if(mp[i]==1) return i; } return ans; } }; ``` <p></p></div></div></div> # 第 6 天 搜索与回溯算法(简单) ## [剑指 Offer 32 - I. 从上到下打印二叉树](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/) <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-c5bffd64d1ff6f332b2585e5b260126e6" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-c5bffd64d1ff6f332b2585e5b260126e6" class="collapse collapse-content"><p></p> ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> levelOrder(TreeNode* root) { queue<TreeNode*>que; que.push(root); vector<int>ans; if(!root) return ans; while(!que.empty()) { TreeNode *tmp=que.front(); que.pop(); if(tmp->left) que.push(tmp->left); if(tmp->right) que.push(tmp->right); ans.push_back(tmp->val); } return ans; } }; ``` <p></p></div></div></div> ## [剑指 Offer 32 - II. 从上到下打印二叉树 II](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/) 在当前节点的下一层放入队列之前,把当前节点存下来 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-77382a3b11e570a4e7530132d6c9274393" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-77382a3b11e570a4e7530132d6c9274393" class="collapse collapse-content"><p></p> ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { if(!root) return {}; queue<TreeNode*>que; que.push(root); vector<vector<int> >ans; while(!que.empty()) { vector<int>tmp; int sz=que.size(); for(int i=0;i<sz;i++) { TreeNode *now=que.front(); tmp.push_back(now->val); que.pop(); if(now->left) que.push(now->left); if(now->right) que.push(now->right); } ans.push_back(tmp); } return ans; } }; ``` <p></p></div></div></div> ## [剑指 Offer 32 - III. 从上到下打印二叉树 III](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/) 和上一题一样,只不过在存入到最终结果之前需要判断一下当前在第几层,翻转一下 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-745214afba876156931c8ad75482673442" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-745214afba876156931c8ad75482673442" class="collapse collapse-content"><p></p> ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { if(!root) return {}; queue<TreeNode*>que; que.push(root); vector<vector<int> >ans; while(!que.empty()) { vector<int>tmp; int sz=que.size(); for(int i=0;i<sz;i++) { TreeNode *now=que.front(); tmp.push_back(now->val); que.pop(); if(now->left) que.push(now->left); if(now->right) que.push(now->right); } if(ans.size()%2) reverse(tmp.begin(),tmp.end()); ans.push_back(tmp); } return ans; } }; ``` <p></p></div></div></div> # 第 7 天 搜索与回溯算法(简单) ## [剑指 Offer 26. 树的子结构](https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/) 先从A开始往下遍历,如果出现了与B的根节点相等的节点,开始A和B同时向下递归 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-3db389486415fde0656c83eb357d37ad29" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-3db389486415fde0656c83eb357d37ad29" class="collapse collapse-content"><p></p> ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSubStructure(TreeNode* A, TreeNode* B) { if(!A||!B) return false; if(dfs(A,B)) return true; return isSubStructure(A->left,B)||isSubStructure(A->right,B); } bool dfs(TreeNode *A,TreeNode *B) { if(!B) return true; if(!A) return false; if(A->val!=B->val) return false; return dfs(A->left,B->left)&&dfs(A->right,B->right); } }; ``` <p></p></div></div></div> ## [剑指 Offer 27. 二叉树的镜像](https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/) ### BFS 用栈辅助遍历来实现二叉树的镜像 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-820c9d8f193fd4c3c3457adc08c036a375" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-820c9d8f193fd4c3c3457adc08c036a375" class="collapse collapse-content"><p></p> ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* mirrorTree(TreeNode* root) { if(!root) return root; stack<TreeNode*>st; st.push(root); while(!st.empty()) { TreeNode *node=st.top(); st.pop(); if(node->left) st.push(node->left); if(node->right) st.push(node->right); TreeNode *tmp=node->left; node->left=node->right; node->right=tmp; } return root; } }; ``` <p></p></div></div></div> ### DFS <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-12afe02e73cd1113d0405b836b0d17c087" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-12afe02e73cd1113d0405b836b0d17c087" class="collapse collapse-content"><p></p> ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* mirrorTree(TreeNode* root) { if(!root) return root; TreeNode *node=root->left; root->left=mirrorTree(root->right); root->right=mirrorTree(node); return root; } }; ``` <p></p></div></div></div> ## [剑指 Offer 28. 对称的二叉树](https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/) 对左子树和右子树同时向下遍历 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-a664d9f30ac716b0e1e0d1871baee5f778" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-a664d9f30ac716b0e1e0d1871baee5f778" class="collapse collapse-content"><p></p> ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSymmetric(TreeNode* root) { if(!root) return true; return dfs(root->left,root->right); } bool dfs(TreeNode *A,TreeNode *B) { if(!A&&!B) return true; if((!A||!B)||A->val!=B->val) return false; return dfs(A->left,B->right)&&dfs(A->right,B->left); } }; ``` <p></p></div></div></div> # 第 8 天 动态规划(简单) ## [剑指 Offer 10- I. 斐波那契数列](https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/) 别用递归写就行了 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-9cd82856b985834e2d4992c6e1748e0f59" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-9cd82856b985834e2d4992c6e1748e0f59" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int a[3]; const int mod=1e9+7; int fib(int n) { if(n<2) return n; a[0]=0;a[1]=1; for(int i=2;i<=n;i++) { a[2]=(a[1]%mod+a[0]%mod)%mod; a[0]=a[1];a[1]=a[2]; } return a[2]; } }; ``` <p></p></div></div></div> ## [剑指 Offer 10- II. 青蛙跳台阶问题](https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/) $dp[i]=dp[i-1]+dp[i-2]$ <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-98c226bb05d13b6ea6e205f116b0bf6d38" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-98c226bb05d13b6ea6e205f116b0bf6d38" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int dp[101]; const int mod=1e9+7; int numWays(int n) { dp[0]=1; dp[1]=1; dp[2]=2; for(int i=2;i<=n;i++) dp[i]=(dp[i-1]+dp[i-2])%mod; return dp[n]; } }; ``` <p></p></div></div></div> ## [剑指 Offer 63. 股票的最大利润](https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/) 不断更新当前元素与当前最小值的差值就行了 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-3ffd950972b0a1d67f77ebf59b901e39100" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-3ffd950972b0a1d67f77ebf59b901e39100" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int maxProfit(vector<int>& prices) { int sz=prices.size(); if(!sz) return 0; int m=prices[0]; int ans=0; for(int i=1;i<sz;i++) { m=min(prices[i],m); ans=max(ans,prices[i]-m); } return ans; } }; ``` <p></p></div></div></div> # 第 9 天 动态规划(中等) ## [剑指 Offer 42. 连续子数组的最大和](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/) <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-0b59ce604cd66c360e3e294b6a36b9e546" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-0b59ce604cd66c360e3e294b6a36b9e546" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int maxSubArray(vector<int>& nums) { int ans=nums[0]; int tmp=0; for(auto i:nums) { tmp=max(tmp+i,i); ans=max(ans,tmp); } return ans; } }; ``` <p></p></div></div></div> ## [剑指 Offer 47. 礼物的最大价值](https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/) $dp[i][j]=\max\{dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j],dp[i][j] \}$ <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-364e446f860e65a5870dfc116da7fa9670" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-364e446f860e65a5870dfc116da7fa9670" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int dp[202][202]; int maxValue(vector<vector<int>>& grid) { int n=grid.size(),m=grid[0].size(); dp[0][0]=grid[0][0]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(!i&&!j) continue; if(!i) dp[i][j]=max(dp[i][j-1]+grid[i][j],dp[i][j]); else if(!j) dp[i][j]=max(dp[i-1][j]+grid[i][j],dp[i][j]); else dp[i][j]=max({dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j],dp[i][j]}); } } return dp[n-1][m-1]; } }; ``` <p></p></div></div></div> # 第 10 天 动态规划(中等) ## [剑指 Offer 46. 把数字翻译成字符串](https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/) $dp[i]$表示在位置$i$有多少种方案,如果$i$和$i-1$位置能够在一起翻译成字母,则$dp[i]=dp[i-1]+dp[i-2]$,否则$dp[i]=dp[i-1]$ <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-5c792d9f36383f413ce03ac69abeab5896" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-5c792d9f36383f413ce03ac69abeab5896" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int dp[20]; int translateNum(int num) { if(num<10) return 1; vector<int>v; while(num) { v.push_back(num%10); num/=10; } reverse(v.begin(),v.end()); int sz=v.size(); dp[0]=1; if(v[0]*10+v[1]<26) dp[1]=2; else dp[1]=1; for(int i=2;i<sz;i++) { if(v[i-1]*10+v[i]<26&&v[i-1]*10+v[i]>=10) dp[i]=dp[i-1]+dp[i-2]; else dp[i]=dp[i-1]; } return dp[sz-1]; } }; ``` <p></p></div></div></div> ## [剑指 Offer 48. 最长不含重复字符的子字符串](https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/) 向后遍历,保证遍历过程中子字符串包含的字符只出现了一次。当出现第二次时,让子字符串开始的位置变成该字符出现第二次的位置。 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-ede2d7cb1b15cd25bc2bf13f22ebfd480" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-ede2d7cb1b15cd25bc2bf13f22ebfd480" class="collapse collapse-content"><p></p> ```cpp class Solution { public: int lengthOfLongestSubstring(string s) { int l=s.length(); map<char,int>mp; int ans=0; int place=0; for(int i=0;i<l;i++) { if(mp[s[i]]) place=max(place,mp[s[i]]); ans=max(i-place+1,ans); mp[s[i]]=i+1; } return ans; } }; ``` <p></p></div></div></div> # 第 11 天 双指针(简单) ## [剑指 Offer 18. 删除链表的节点](https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/) 设置一个当前节点的前驱结点,如果当前节点为删除节点,停止查找,让前驱结点的下一个节点变成当前节点的下一个节点,即可实现删除 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-cb187bf72bc4a00b70b6c40e54a67eb721" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-cb187bf72bc4a00b70b6c40e54a67eb721" class="collapse collapse-content"><p></p> ```cpp /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* deleteNode(ListNode* head, int val) { if(head->val==val) return head->next; ListNode *pre=head,*now=head->next; while(now->val!=val&&now) pre=now,now=now->next; if(now) pre->next=now->next; return head; } }; ``` <p></p></div></div></div> ## [剑指 Offer 22. 链表中倒数第k个节点](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/) 设置两个所指位置不同的指针,保证在前面的指针和在后面的指针相差$k$个节点,当在前面的指针指向链表末尾时,在后面的指针恰好指向倒数第$k$个节点 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-a1e38fda947e42bd5dafed547c81eda570" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-a1e38fda947e42bd5dafed547c81eda570" class="collapse collapse-content"><p></p> ```cpp /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* getKthFromEnd(ListNode* head, int k) { ListNode *slow=head,*fast=head; for(int i=0;i<k;i++) { if(!fast) return NULL; fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } return slow; } }; ``` <p></p></div></div></div> # 第 12 天 双指针(简单) ## [剑指 Offer 25. 合并两个排序的链表](https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/) 同时遍历两个链表,每次添加两个链表中较小的那个节点,知道有一个链表遍历结束 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-07fb5fc883f908cedc73f433c1d6a34136" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-07fb5fc883f908cedc73f433c1d6a34136" class="collapse collapse-content"><p></p> ```cpp /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode *head=new ListNode(0,NULL); ListNode *tmp=head; while(l1&&l2) { if(l1->val>l2->val) { tmp->next=l2; l2=l2->next; } else { tmp->next=l1; l1=l1->next; } tmp=tmp->next; } if(l2) tmp->next=l2; if(l1) tmp->next=l1; return head->next; } }; ``` <p></p></div></div></div> ## [剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/) 双指针,[官方题解](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/liang-ge-lian-biao-de-di-yi-ge-gong-gong-pzbs/)有证明 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-f2ea787496b8c110f299b752287c920974" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-f2ea787496b8c110f299b752287c920974" class="collapse collapse-content"><p></p> ```cpp /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(!headA||!headB) return NULL; ListNode *nodeA=headA,*nodeB=headB; while(nodeA!=nodeB) { nodeA=nodeA?nodeA->next:headB; nodeB=nodeB?nodeB->next:headA; } return nodeA; } }; ``` <p></p></div></div></div> # 第 13 天 双指针(简单) ## [剑指 Offer 21. 调整数组顺序使奇数位于偶数前面](https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/) 两个指针分别指向数组的开头和结尾,如果左边的数为偶数,右边的数为奇数,交换两数的位置;如果左边为奇数,左指针右移;如果右边为偶数,右指针左移 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-dec2ae1023e45343caf3150d169e6ca287" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-dec2ae1023e45343caf3150d169e6ca287" class="collapse collapse-content"><p></p> ```cpp class Solution { public: vector<int> exchange(vector<int>& nums) { int l=0,r=nums.size()-1; while(l<r) { if(!(nums[l]%2)&&nums[r]%2) swap(nums[l++],nums[r--]); else if(nums[l]%2) l++; else if(!(nums[r]%2)) r--; } return nums; } }; ``` <p></p></div></div></div> ## [剑指 Offer 57. 和为s的两个数字](https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/) ### 哈希 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-be44047a7d20afbd0f32b78aaa606e4b14" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-be44047a7d20afbd0f32b78aaa606e4b14" class="collapse collapse-content"><p></p> ```cpp class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int,int>mp; for(auto i:nums) { if(mp[target-i]) return {i,target-i}; mp[i]++; } return {}; } }; ``` <p></p></div></div></div> ### 双指针 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-378c9c701cf13c08f99dadde690d9a1d49" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-378c9c701cf13c08f99dadde690d9a1d49" class="collapse collapse-content"><p></p> ```cpp class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int l=0,r=nums.size()-1; while(l<r) { if(nums[l]+nums[r]<target) l++; else if(nums[l]+nums[r]>target) r--; else return {nums[l],nums[r]}; } return {}; } }; ``` <p></p></div></div></div> ## [剑指 Offer 58 - I. 翻转单词顺序](https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/) 直接py cpp的话用栈来做吧,挺麻烦的 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-99952aab7102688e1fa436d7059b956e76" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-99952aab7102688e1fa436d7059b956e76" class="collapse collapse-content"><p></p> ```python class Solution: def reverseWords(self, s: str) -> str: s=s.strip().split() s.reverse() return ' '.join(s) ``` <p></p></div></div></div> Last modification:January 2, 2022 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 如果觉得我的文章对你有用,请随意赞赏