双栈法：用两个栈分别存奇数层和偶数层，入栈的顺序需要注意：奇数层从右往左，偶数层从左往右 class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { int n = 1; stack<TreeNode*> s1; stack<TreeNode*> s2; vector<vector<int>> res; if(!pRoot) re...

这题有点像跳箱子（一次跳一格或者两格） 如果按照跳箱子的做法，dp[n] = dp[n-2] + dp[n-1],从后往前递归，会超时（递归时间和空间都会超）； 那么可以用从前往后的动态规划： 从前往后遍历，分类讨论当前元素i： 如果i == 0，那么前一个字符必须为1或者2，此时dp[i] = dp[i - 2],否则无法译码，直接返回0； 如果i != 0，考虑i-1: 如果i - 1 == 0，那么当前i只能单独译码，则dp[i] = dp[i - 1]； 如果i - 1 != 0,那么看string(i - 1, i)是否在10~26之间，在的话dp[i] = dp[i - ...

贪心+排序：等于数组中任意两个字符串a,b，如果a + b < b + a, 显然我们希望a排在b的前面，因为a排在前面可以使结果更小。那么可以用内排序（插入，冒泡等）的方法，让局部的字符串最小（贪心）。 初始代码： public: string PrintMinNumber(vector<int> numbers) { string res = ""; vector<string> strs; for(int i = 0; i < numbers.size(); i ++) s...

1.初始化：快指针fast指向头结点， 慢指针slow指向头结点 2.让fast一次走两步， slow一次走一步，第一次相遇在C处，停止 3.然后让fast指向头结点，slow原地不动，让后fast，slow每次走一步，当再次相遇，就是入口结点。 如上解释： （为了便于分析，上图所展示的是假设快指针只比慢指针多走了一圈就相遇的情况，也即快指针所走过的路程为A->B->C->D->B->C，而慢指针所走过的路程为A->B->C） 假设慢指针slow从头结点A第一次走到了环的入口结点B处时所走过的路程为X，且设环的入口结点B到达快慢指针相遇结点C处的路程...

√双指针法： 将两个链表的非公共部分加成一样长（b+a=a+b） public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode *ta = pHead1, *tb = pHead2; while (ta != tb) { ta = ta ? ta->next : pHead2;//能在第一遍遍历时检测链表是否在头部重合 tb = tb ? tb->next : pHead1;//否则能在...

1.如果不限制空间大小，直接遍历一遍链表，把数据拿出来排好序后再放回原链表。空间O（n），时间可以到O（nlgn）2.如果限制空间大小O（1）,那么可以直接在链表上进行排序，选择排序比较好写，但是时间上得到O（n*n），这道题过不了 注意：哨兵的设置，可以有效的减少不必要的操作 class Solution { public: /** * * @param head ListNode类 the head node * @return ListNode类 */ ListNode* sortInList(ListNode* head) { ...

先排序，再合并注意几个细节：1.快排的时候利用填坑的思想，base是第一个坑，先从后往前填一个坑，再从前往后填一个坑最后把base放到最后一个坑，填坑时注意判断 i < j int i = start, j = end; while(i < j) { while(j > i && v[j].start > base.start) j --; if(j > i) { v[i] = v[j]; ...

1.暴力统计直接用map或者set统计数字出现次数即可，注意一旦数字出现两次即可从集合中删除该数字，遍历完剩下的就是要找的数字。 vector<int> FindNumsAppearOnce(vector<int>& array) { // write code here map<int,int> m; for(int i : array) { if(m.count(i)) { m.erase(i); } else{...