博客搬至，cnblogs不再更新。
新的题解会更新在：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
LeetCode OJ 题解
LeetCode OJ is a platform for preparing technical coding interviews.
LeetCode OJ 是为与写代码有关的技术工作面试者设计的训练平台。
LeetCode OJ:
默认题目顺序为题目添加时间倒叙，本文题解顺序与OJ题目顺序一致（OJ会更新，至少目前一致。。。），目前共152题。
另外，做了Python版的题解：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
Maximum Product Subarray
&维护当前位置连续乘积的最大值 tmpp 和最小值 tmpn ，最大值和最小值都可能由三种情况得到：上一个数的 tmpp*A[i]，上一个数的 tmpn*A[i]，A[i]本身。
不断更新答案，最终输出。
1 class Solution {
int maxProduct(int A[], int n) {
int tmpp = A[0], tmpn = A[0], tmp, ans = A[0];
for(int i = 1; i & i ++)
tmpp = max(max(A[i], A[i] * tmpp), A[i] * tmpn);
tmpn = min(min(A[i], A[i] * tmp), A[i] * tmpn);
ans = max(ans, tmpp);
&先翻转整个字符串，然后从前往后一个单词一个单词地再翻转一次，同时去除多余空格，等于是扫描两遍，O(n)。
1 class Solution {
void reverseWords(string &s) {
reverse(s.begin(), s.end());
int start = 0, end = 0, j = 0;
while(start != s.length())
while(start != s.length() && s[start] == ' ') start ++;
for(end = end != s.length() && s[end] != ' '; end ++);
if(j != 0 && start &= end - 1) s[j ++] = ' ';
for(int i = end - 1; start & start ++, i --)
swap(s[i], s[start]), s[j ++] = s[start];
while(start & end) s[j ++] = s[start ++];
s.resize(j);
逆波兰表达式计算四则运算。用栈。
1 class Solution {
int evalRPN(vector&string& &tokens) {
stack&int&
for(int i = 0; i & tokens.size(); i ++)
if(isdigit(tokens[i][0]) || tokens[i].length() & 1)
s.push(atoi(tokens[i].c_str()));
a = s.top();s.pop();
b = s.top();s.pop();
switch(tokens[i][0])
case '+': s.push(b + a); break;
case '-': s.push(b - a); break;
case '*': s.push(b * a); break;
case '/': s.push(b / a); break;
return s.top();
&平面上一条直线最多穿过多少点。乍一看好熟悉的问题，做了这么久计算几何。。。却还真没做过这个小问题。
第一反应当然不能O(n^3)枚举了，枚举圆周好像也不行，毕竟是考察所有点，不是某个点。那么应该就是哈希斜率了吧。
肯定少不了竖直的线，哈希斜率这不像是这类OJ让写的题吧。。忘了map这回事了。
确定思路之后，还是看看别人博客吧，少走点弯路，然后就学习了还有unordered_map这么个东西，的思路挺好，避免double问题，把斜率转化成化简的x、y组成字符串。
再另外就是重叠的点了，想让题目坑一点，怎能少得了这种数据，单独处理一下。
* Definition for a point.
* struct Point {
Point() : x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
10 class Solution {
11 public:
int maxPoints(vector&Point& &points) {
int ans = 0;
for(int i = 0; i & points.size(); i ++)
unordered_map&string, int&
int tmpans = 0, same = 0;
for(int j = i + 1; j & points.size(); j ++)
int x = points[j].x - points[i].x, y = points[j].y - points[i].y;
int g = gcd(x, y);
if(g != 0) x /= g, y /=
else {same ++; continue;}
if(x & 0) x = -x, y = -y;
string tmp = to_string(x) + " " + to_string(y);
if(!mp.count(tmp)) mp[tmp] = 1;
else mp[tmp] ++;
tmpans = max(tmpans, mp[tmp]);
ans = max(tmpans + 1 + same, ans);
int gcd(int a, int b)
return a ? gcd(b % a, a) :
&又长见识了，原来链表也可以O(nlogn)排序的。没往下想就查了一下，看到人说用归并，于是才开始想能不能实现。。。
O(n)找到中点，把中点的next变成NULL，对两部分递归。递归结束后对两部分归并，先找到newhead，即两部分的头部val较小的那个，然后归并就把小的从newhead往后续。
把最后的next赋值NULL，返回newhead。
又有空数据@_@.
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
ListNode *sortList(ListNode *head) {
int n = 0;
ListNode *p =
while(p != NULL)
n ++, p = p-&
if(n &= 1) return
while(-- n)
ListNode *tmp = p-&
p-&next = NULL;
ListNode *nl = sortList(head);
ListNode *nr = sortList(tmp);
ListNode *
if(nl-&val & nr-&val)
while(nl != NULL && nr != NULL)
if(nl-&val & nr-&val) p-&next = nl, p = p-&next, nl = nl-&
else p-&next = nr, p = p-&next, nr = nr-&
while(nl != NULL) p-&next = nl, p = p-&next, nl = nl-&
while(nr != NULL) p-&next = nr, p = p-&next, nr = nr-&
p-&next = NULL;
&指针操作很烦啊。。暴力枚举插入位置，注意细节就能过了。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
ListNode *insertionSortList(ListNode *head) {
ListNode *newhead =
if(head == NULL) return NULL;
head = head-&
newhead-&next = NULL;
while(head != NULL)
if(head-&val & newhead-&val)
ListNode *tmp = head-&
head-&next =
ListNode *pre = newhead, *p = newhead-&
while(p != NULL && p-&val & head-&val)
pre = pre-&
pre-&next =
head = head-&
pre = pre-&
pre-&next =
新建数据类class Val，保存key、val和访问自增标记updatecnt。
用unordered_map更新数据，增加updatecnt，并把更新的数据放入队列，最关键是处理capacity满了的时候，队列依次出队，map中不存在的和updatecnt和最新数据不相等的项目都忽略，直到发现updatecnt和map中存的最新状态相等，则为&最近未使用&数据，出队后在map中erase。思路有点像STL队列实现版本的Dijkstra。
的方法更好，map中存的是链表的节点指针，链表顺序表示访问情况，这样就把map内容和链表的每个节点一一对应了，没有冗余节点，且更新操作也是O(1)的。
1 class Val{
7 class LRUCache{
unordered_map&int, Val&
queue&Val&
LRUCache(int capacity) {
int get(int key) {
if(mp.count(key))
mp[key].updatecnt ++;
q.push(mp[key]);
return mp[key].
return -1;
void set(int key, int value) {
if(mp.count(key))
mp[key].val =
mp[key].updatecnt ++;
q.push(mp[key]);
if(mp.size() == cap)
while(!q.empty())
tmp = q.front();
if(mp.count(tmp.key) && tmp.updatecnt == mp[tmp.key].updatecnt)
mp.erase(mp.find(tmp.key));
mp[key].key =
mp[key].val =
mp[key].updatecnt = 0;
q.push(mp[key]);
mp[key].key =
mp[key].val =
mp[key].updatecnt = 0;
q.push(mp[key]);
&二叉树的非递归后序遍历，考研的时候非常熟悉了，现在写又要想好久。重点是关于右子树遍历时候需要一个标记，或者标记根节点出栈次数，或者标记右子树是否访问。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&int& postorderTraversal(TreeNode *root) {
vector&int&
if(root == NULL) return
stack&TreeNode*&
TreeNode *
while(root != NULL || !s.empty())
while(root != NULL)
s.push(root), root = root-&
root = s.top();
if(root-&right == NULL || visited == root-&right)
ans.push_back(root-&val);
root = NULL;
root = root-&
&前序遍历的非递归就容易多了。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&int& preorderTraversal(TreeNode *root) {
stack&TreeNode*&
vector&int&
if(root == NULL) return
s.push(root);
while(!s.empty())
root = s.top();
ans.push_back(root-&val);
if(root-&right != NULL) s.push(root-&right);
if(root-&left != NULL) s.push(root-&left);
找到中间位置，把中间之后的链表反转，两个指针一个从头一个从尾开始互插，奇偶和指针绕得有点晕，理清就好了。。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
void reorderList(ListNode *head) {
int n = 0;
ListNode *pre, *p =
n ++, p = p-&
if(n & 3) return;
while(n --) p = p-&next, pre = pre-&
while(p != NULL)
ListNode *tmp = p-&
ListNode *tail =
while(true)
ListNode *tmp1 = p-&next, *tmp2 = tail-&
tail-&next = tmp1;
if(p == tail || p == tmp2) break;
tail = tmp2;
p-&next = NULL;
设置两个指针slow和fast，从head开始，slow一次一步，fast一次两步，如果fast能再次追上slow则有圈。
设slow走了n步，则fast走了2*n步，设圈长度m，圈起点到head距离为k，相遇位置距离圈起点为t，则有：
n = k&+ t + (1)
2*n = k + t +(2)
这里p和q是任意整数。（不过fast速度是slow二倍，则肯定在一圈内追上，p就是0了）
2 * (1) - (2) 得k = lm -(l = q - 2 * p)
&即 k 的长度是若干圈少了 t 的长度。
因此这时候，一个指针从head开始，另一个从相遇位置开始，都每次只走一步，当从head开始的指针走到圈开始位置时，两指针刚好相遇。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
ListNode *detectCycle(ListNode *head) {
if(head == NULL) return NULL;
ListNode *slow, *
slow = fast =
int n = 0;
if(slow == NULL || fast == NULL) return NULL;
slow = slow-&
fast = fast-&
if(fast == NULL) return NULL;
fast = fast-&
if(fast == NULL) return NULL;
}while(slow != fast);
while(slow != fast)
slow = slow-&next, fast = fast-&
&呃，时间逆序做的结果。。。成买一送一了。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
bool hasCycle(ListNode *head) {
if(head == NULL) return false;
ListNode *slow, *
slow = fast =
int n = 0;
if(slow == NULL || fast == NULL) return NULL;
slow = slow-&
fast = fast-&
if(fast == NULL) return NULL;
fast = fast-&
if(fast == NULL) return NULL;
}while(slow != fast);
return true;
&先递推，dp[i] == true 表示 s 中前 i 个字符的串是符合要求的，枚举位置 i ，对于 i 枚举位置 j & i，如果 dp[j] == true且 j ~ i的串在字典中，则dp[i] = true。
同时对于这样的 j, i，site[i].push_back(j)，即在 i 位置的可行迭代表中增加位置 j。
完成site之后，从尾部倒着DFS过去就得到了所有串。
1 class Solution {
vector&string& DFS(const string &s, vector&int& *site, int ith)
vector&string&
for(int i = 0; i & site[ith].size(); i ++)
vector&string&
string str = s.substr(site[ith][i], ith - site[ith][i]);
if(site[site[ith][i]].size() == 0)
res.push_back(str);
tmp = DFS(s, site, site[ith][i]);
for(int j = 0; j & tmp.size(); j ++)
res.push_back(tmp[j] + " " + str);
vector&string& wordBreak(string s, unordered_set&string& &dict) {
vector&int& *site = new vector&int&[s.length() + 1];
bool *dp = new bool[s.length() + 1];
memset(dp, 0, sizeof(bool) * s.length());
dp[0] = true;
for(int i = 1; i &= s.length(); i ++)
for(int j = 0; j & j ++)
if(dp[j] == true && dict.count(s.substr(j, i - j)))
site[i].push_back(j), dp[i] = true;
return DFS(s, site, s.length());
&参考Word Break II，对于dp标记，当dp[i]为true时候可以停止枚举后面的 j，优化一下常数。
1 class Solution {
bool wordBreak(string s, unordered_set&string& &dict) {
bool *dp = new bool[s.length() + 1];
memset(dp, 0, sizeof(bool) * (s.length() + 1));
dp[0] = true;
for(int i = 1; i &= s.length(); i ++)
for(int j = 0; j & j ++)
dp[i] = dp[i] || dp[j] && dict.count(s.substr(j, i - j));
return dp[s.length()];
第一次遍历，把每个节点复制一份放到对应节点的下一个，即组成二倍长的链表：ori1-&copy1-&ori2-&copy2-&....
第二次遍历，利用&复制节点总是对应节点的下一个节点&特性，将每个ori-&next-&random指向ori-&random-&next，中间判断一下空指针。
第三次遍历，把两个链表拆开，恢复原链表。
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
RandomListNode *next, *
RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
9 class Solution {
10 public:
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode *p = head, *newhead = NULL, *
if(p == NULL) return NULL;
while(p != NULL)
tmp = new RandomListNode(p-&label);
tmp-&next = p-&
newhead = head-&
while(p != NULL)
tmp-&random = p-&random == NULL ? NULL : p-&random-&
while(p != NULL)
p-&next = tmp-&
tmp-&next = p == NULL ? NULL : p-&
方法一：设置cnt[32]记录&32个比特位的1的个数，出现3次的数的对应位的1总数为3的倍数，则统计之后每个位对3取模，剩下的位为1的则对应个数为1的那个数。
1 class Solution {
int singleNumber(int A[], int n) {
int cnt[32] = {0};
for(int i = 0; i & i ++)
int tmp = A[i];
for(int j = 0; j & 33; tmp &&= 1, j ++)
cnt[j] += tmp & 1;
int ans = 0;
for(int i = 0; i & 32; i ++)
ans |= (cnt[i] % 3) &&
方法二：设置int one, two模拟两位二进制来统计各比特位1次数，每当one和two对应二进制位都为1的时候把one和two都清零，最后剩下的one就是要求的数。
1 class Solution {
int singleNumber(int A[], int n) {
int one = 0, two = 0;
for(int i = 0; i & i ++)
two |= one & A[i];
one ^= A[i];
int tmp = one &
&一路异或过去就可以了。
1 class Solution {
int singleNumber(int A[], int n) {
int tmp = 0;
for(int i = 0; i & i ++)
tmp ^= A[i];
时间复杂度&O(n)的方法还是容易想了，优化为空间复杂度O(1)的话也不难，只是思考代码的时候会有点绕。
上坡一步步来，下坡走个等差数列，波峰位置比较一下上坡时候记录的最大值和下坡求的的最大值，取较大的，具体看代码：
1 class Solution {
int candy(vector&int& &ratings) {
int cnt = 0, i, j, start,
for(i = 0; i & ratings.size(); i ++)
if(i == 0 || ratings[i] == ratings[i - 1])
nownum = 1;
else if(ratings[i] & ratings[i - 1])
nownum ++;
if(i + 1 & ratings.size() && ratings[i + 1] & ratings[i])
start = 1;
for(j = i + 1; j & ratings.size() && ratings[j] & ratings[j - 1]; start++, j ++);
if(start & nownum)
cnt += (start + 1) * start && 1;
cnt += ((start - 1) * start && 1) +
nownum = 1;
i = j - 1;
一、如果从 i 到 j 的时候理论计算气量刚好为负数，则 i ~ j 的加气站都不可以作为起点。
反证一下，从前往后去掉站，如果去掉的站能增加气，即正数，则结果更糟。如果去掉的站是负数，那么负数如果抵消了之前的正数，则在到 j 之前已经负数了，如果不能抵消之前的正数，那么结果还是更糟。
二、判断是否能成行，一个环的和为非负就可以。
假设环为正， 0 ~ j 刚好为负， j + 1 ~ k 刚好为负数，k + 1 之后为正，则 k + 1 为答案。
也反证一下，k + 1 出发，到gas.size() - 1都为正，则转回来到 j - 1 都会为正。如果到 j 时候为负，则整个环不可能为正，所以到 j 的时候也为正，剩下的一样。这样就能够成功转一圈。
1 class Solution {
int canCompleteCircuit(vector&int& &gas, vector&int& &cost) {
int i, ans, sum,
for(i = ans = sum = all = 0; i & gas.size(); i ++)
sum += gas[i] - cost[i];
all += gas[i] - cost[i];
if(sum & 0)
ans = i + 1;
return all &= 0 ? ans : -1;
&label是唯一的，递归，用unordered_map标记。
* Definition for undirected graph.
* struct UndirectedGraphNode {
vector&UndirectedGraphNode *&
UndirectedGraphNode(int x) : label(x) {};
9 class Solution {
10 public:
unordered_map&int, UndirectedGraphNode *&
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(node == NULL || mp.count(node-&label)) return NULL;
UndirectedGraphNode *tmp = new UndirectedGraphNode(node-&label);
mp[node-&label] =
for(int i = 0; i & node-&neighbors.size(); i ++)
cloneGraph(node-&neighbors[i]);
tmp-&neighbors.push_back(mp[node-&neighbors[i]-&label]);
O(n^2)的动态规划。
cutdp[i] 表示前 i 个字符最小切割几次。
paldp[i][j] == true 表示 i ~ j 是回文。
在枚举 i 和 i 之前的所有 j 的过程中就得到了 paldp[j][i] 的所有回文判断，而对于 i + 1，paldp[j][i + 1]可由 s[j]、s[i + 1]、dp[j + 1][i]在O(1)判断。
cutdp[i]为所有 j (j & i)，当paldp[j + 1][i] == true的 cutdp[j] + 1的最小值。注意一下边界。
1 class Solution {
int minCut(string s) {
bool paldp[s.length()][s.length()];
int cutdp[s.length()];
for(int i = 0; i & s.length(); i ++)
cutdp[i] = 0x3f3f3f3f;
for(int j = i - 1; j &= -1; j --)
if(s.at(j + 1) == s.at(i) && (j + 2 &= i - 1 || paldp[j + 2][i - 1]))
paldp[j + 1][i] = true;
cutdp[i] = min(cutdp[i], (j &= 0 ? (cutdp[j] + 1) : 0));
paldp[j + 1][i] = false;
return cutdp[s.length() - 1];
&O(n^2)动态规划，paldp[i][j]& == true表示 i ~ j 是回文。这里DP的方法是基本的，不再多说。
得到paldp之后，DFS一下就可以了。因为单字符是回文，所以DFS的终点肯定都是解，所以不必利用其他的结构存储答案信息。
1 class Solution {
vector&vector&string& &
vector&string&
void DFS(string s, int ith)
if(ith == s.length())
res.push_back(tmp);
for(int i = i & s.length(); i ++)
if(paldp[ith][i])
tmp.push_back(s.substr(ith, i - ith + 1));
DFS(s, i + 1);
tmp.pop_back();
vector&vector&string& & partition(string s) {
paldp = new bool*[s.length()];
for(int i = 0; i & s.length(); i ++)
paldp[i] = new bool[s.length()];
for(int i = 0; i & s.length(); i ++)
for(int j = j &= 0; j --)
paldp[j][i] = s.at(i) == s.at(j) && (j + 1 &= i - 1 || paldp[j + 1][i - 1]);
DFS(s, 0);
&周围四条边的O做起点搜索替换为第三种符号，再遍历所有符号把O换成X，第三种符号换回O。
1 class Solution {
typedef pair&int, int&
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
queue&pii&
void solve(vector&vector&char& & &board) {
if(board.size() == 0) return;
int width = board[0].size();
int height = board.size();
for(int i = 0; i & i ++)
if(board[0][i] == 'O')
board[0][i] = '#', q.push(pair&int, int&(0, i));
if(board[height - 1][i] == 'O')
board[height - 1][i] = '#', q.push(pii(height - 1, i));
for(int i = 1; i & height - 1; i ++)
if(board[i][0] == 'O')
board[i][0] = '#', q.push(pii(i, 0));
if(board[i][width - 1] == 'O')
board[i][width - 1] = '#', q.push(pii(i, width - 1));
while(!q.empty())
pii now = q.front();
for(int i = 0; i & 4; i ++)
int ty = now.first + dx[i];
int tx = now.second + dy[i];
if(tx &= 0 && tx & width && ty &= 0 && ty & height && board[ty][tx] == 'O')
board[ty][tx] = '#';
q.push(pii(ty, tx));
for(int i = 0; i & i ++)
for(int j = 0; j & j ++)
if(board[i][j] == 'O') board[i][j] = 'X';
else if(board[i][j] == '#') board[i][j] = 'O';
&遍历一遍加起来。。。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
void DFS(TreeNode *now, int tmp)
if(now-&left == NULL && now-&right == NULL)
ans += tmp * 10 + now-&
if(now-&left != NULL)
DFS(now-&left, tmp * 10 + now-&val);
if(now-&right != NULL)
DFS(now-&right, tmp * 10 + now-&val);
int sumNumbers(TreeNode *root) {
if(root == NULL) return 0;
DFS(root, 0);
&方法一：一开始竟然想了并查集，其实绕弯了，多此一举。哈希+并查集，把每个数哈希，枚举每个数看相邻的数在不在数组里，并查集合并，只是并查集的复杂度要比O(1)大一些。
1 class Solution {
unordered_map&int, int& mp,
int ans = 1;
int fa(int i)
i == mp[i] ? i : (mp[i] = fa(mp[i]));
int longestConsecutive(vector&int& &num) {
for(int i = 0; i & num.size(); i ++)
mp[num[i]] = num[i], cnt[num[i]] = 1;
for(int i = 0; i & num.size(); i ++)
if(mp.count(num[i] + 1) && fa(num[i]) != fa(num[i] + 1))
cnt[fa(num[i] + 1)] += cnt[fa(num[i])];
ans = max(cnt[fa(num[i] + 1)], ans);
mp[fa(num[i])] = fa(num[i] + 1);
方法二：哈希+枚举相邻数。相邻的数在数组里的话，每个数之多访问一次；相邻的数不在数组里的话，枚举会中断。所以设哈希复杂度为O(1)的话，这个方法是严格的O(n)。
其实这个题的数据挺善良，如果出了, -，那还是用long long 稳妥些。
1 class Solution {
unordered_map&int, bool&
int longestConsecutive(vector&int& &num) {
int ans = 0;
for(int i = 0; i & num.size(); i ++)
vis[num[i]] = false;
for(int i = 0; i & num.size(); i ++)
if(vis[num[i]] == false)
int cnt = 0;
for(int j = num[i]; vis.count(j); j ++, cnt ++)
vis[j] = true;
for(int j = num[i] - 1; vis.count(j); j --, cnt ++)
vis[j] = true;
ans = max(ans, cnt);
&用数组类型的队列，BFS过程中记录pre路径，搜完后迭代回去保存路径。
似乎卡了常数，用queue队列，另外存路径的方法超时了。
想更快就双向广搜吧。让我想起了POJ那个八数码。
1 class Node
Node(string s, int pa, int pr)
15 class Solution {
16 public:
vector&vector&string&&
vector&vector&string&& findLadders(string start, string end, unordered_set&string& &dict) {
vector&Node&
q.push_back(Node(end, 1, -1));
unordered_map&string, int&
dis[end] = 1;
for(int i = 0; i & q.size(); i ++)
Node now = q[i];
if(dis.count(start) && now.pace &= dis[start]) break;
for(int j = 0; j & now.str.length(); j ++)
string tmp = now.
for(char c = 'a'; c &= 'z'; c ++)
if((dict.count(tmp) || tmp == start) && (!dis.count(tmp) || dis[tmp] == now.pace + 1))
dis[tmp] = now.pace + 1;
q.push_back(Node(tmp, now.pace + 1, i));
for(int i = q.size() - 1; i &= 0 && q[i].pace == dis[start]; i --)
if(q[i].str == start)
vector&string&
for(int j = j != -1; j = q[j].pre)
tmp.push_back(q[j].str);
ans.push_back(tmp);
&直接BFS。
1 class Solution {
int ladderLength(string start, string end, unordered_set&string& &dict) {
typedef pair&string, int&
unordered_set&string&
queue&pii&
q.push(pii(start, 1));
while(!q.empty())
pii now = q.front();
for(int i = 0; i & now.first.length(); i ++)
string tmp = now.
for(char j = 'a'; j &= 'z'; j ++)
if(tmp == end) return now.second + 1;
if(dict.count(tmp) && !flag.count(tmp))
q.push(pii(tmp, now.second + 1));
flag.insert(tmp);
&做过刘汝佳 白书的人想必都知道ctype.h和isdigit(), isalpha, tolower(), toupper()。
1 class Solution {
bool valid(char &x)
x = tolower(x);
return isdigit(x) || isalpha(x);
bool isPalindrome(string s) {
if(s.length() == 0) return true;
for(int i = 0, j = s.length() - 1; i & i ++, j --)
while(!valid(s[i]) && i & s.length()) i ++;
while(!valid(s[j]) && j &= 0) j --;
if(i & j && s[i] != s[j]) return false;
return true;
后续遍历，子问题为子树根节点向叶子节点出发的最大路径和。
即&l = DFS(now-&left), r = DFS(now-&right)。
此时，ans可能是 now-&valid,可能是左边一路上来加上now-&valid，可能是右边一路上来，也可能是左边上来经过now再右边一路下去，四种情况。
四种情况更新完ans后，now返回上一层只能是 now-&valid或左边一路上来或右边一路上来，三种情况。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
int DFS(TreeNode *now)
if(now == NULL) return 0;
int l = max(DFS(now-&left), 0);
int r = max(DFS(now-&right), 0);
ans = max(ans, l + r + now-&val);
return max(l + now-&val, r + now-&val);
int maxPathSum(TreeNode *root) {
if(root == NULL) return 0;
ans = -0x3f3f3f3f;
DFS(root);
&前缀pre[i]处理 0 ~ i 买卖一次最优解，后缀suf[i]处理 i ~ prices.size() - 1 买卖一次最优解。
所有位置pre[i] + suf[i]最大值为答案O(n)。
处理最优解的时候是维护前（后）缀prices最小（大）值，与当前prices做差后和前（后）缀最优解比较取最优，O(n)。
总复杂度O(n)。
1 class Solution {
int maxProfit(vector&int& &prices) {
int ans = 0;
vector&int& pre(prices.size()), suf(prices.size());
for(int i = 0, mtmp = 0x3f3f3f3f; i & prices.size(); i ++)
mtmp = i ? min(mtmp, prices[i]) : prices[i];
pre[i] = max(prices[i] - mtmp, i ? pre[i - 1] : 0);
for(int i = prices.size() - 1, mtmp = 0; i &= 0; i --)
mtmp = i != prices.size() - 1 ? max(mtmp, prices[i]) : prices[i];
suf[i] = max(mtmp - prices[i], i != prices.size() - 1 ? suf[i + 1] : 0);
for(int i = 0; i & prices.size(); i ++)
ans = max(ans, pre[i] + suf[i]);
&可以买卖多次，把所有上坡差累加即可。
1 class Solution {
int maxProfit(vector&int& &prices) {
int ans = 0;
for(int i = 1; i & prices.size(); i ++)
if(prices[i] & prices[i - 1])
ans += prices[i] - prices[i - 1];
&维护前（后）缀最小（大）值，和当前prices做差更新答案。
1 class Solution {
int maxProfit(vector&int& &prices) {
int ans = 0;
for(int i = prices.size() - 1, mtmp = 0; i &= 0; i --)
mtmp = max(mtmp, prices[i]);
ans = max(mtmp - prices[i], ans);
竟然遇到了ACM递推入门题，想必无数ACMer对这题太熟悉了。
从下往上递推，一维数组滚动更新即可。这里懒省事，直接把原数组改了。
1 class Solution {
int minimumTotal(vector&vector&int& & &triangle) {
for(int i = triangle.size() - 2; i &= 0; i --)
for(int j = 0; j & triangle[i].size(); j ++)
triangle[i][j] = min(triangle[i][j] + triangle[i + 1][j], triangle[i][j] + triangle[i + 1][j + 1]);
return triangle.size() == 0 ? 0 : triangle[0][0];
&滚动数组递推，从后往前以便不破坏上一层递推数据。
1 class Solution {
vector&int& getRow(int rowIndex) {
vector&int& ans(rowIndex + 1, 0);
ans[0] = 1;
for(int i = 0; i &= rowI i ++)
for(int j = j &= 0; j --)
ans[j] = (i == 0 || j == 0 || j == i ? 1 : ans[j] + ans[j - 1]);
1 class Solution {
vector&vector&int& & generate(int numRows) {
vector&vector&int& &
for(int i = 0; i & numR i ++)
vector&int&
for(int j = 0; j &= j ++)
tmp.push_back(i == 0 || j == 0 || j == i ? 1 : v[i - 1][j] + v[i - 1][j - 1]);
v.push_back(tmp);
&题目要求空间复杂度O(1)，所以递归、队列等传统方法不应该用。
本题可以利用生成的next指针来横向扫描，即得到一层的next指针之后，可以利用这一层的next指针来给下一层的next指针赋值。
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
TreeLinkNode *left, *right, *
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
9 class Solution {
10 public:
TreeLinkNode *findNext(TreeLinkNode *head)
while(head != NULL && head-&left == NULL && head-&right == NULL)
head = head-&
void connect(TreeLinkNode *root) {
if(root == NULL) return;
TreeLinkNode *head, *last, *
for(head = head != NULL; head = nexhead)
head = findNext(head);
if(head == NULL) break;
if(head-&left != NULL) nexhead = head-&
else nexhead = head-&
for(last = NULL; head != NULL; last = head, head = findNext(head-&next))
if(head-&left != NULL && head-&right != NULL)
head-&left-&next = head-&
if(last == NULL) continue;
if(last-&right != NULL)
last-&right-&next = head-&left != NULL ? head-&left : head-&
last-&left-&next = head-&left != NULL ? head-&left : head-&
&不用考虑连续的空指针，就不用额外实现找下一个子树非空节点，比Populating Next Right Pointers in Each Node II 容易处理。
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
TreeLinkNode *left, *right, *
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
9 class Solution {
10 public:
void connect(TreeLinkNode *root) {
if(root == NULL) return;
TreeLinkNode *head, *nexhead, *
for(head = head-&left != NULL; head = nexhead)
nexhead = head-&
last = NULL;
while(head != NULL)
head-&left-&next = head-&
if(last != NULL) last-&right-&next = head-&
head = head-&
&典型动态规划。dp[i][j] 表示 T 的前 j 个字符在 S 的前 i 个字符中的解。
对于dp[i + 1][j + 1]，由两部分组成：
一、 j + 1 对应到 S 前 i 个字符中的解，忽略 S 的第 i + 1 个字符。
二、判断 S 的第 i + 1 个字符是否和 T 的第 j + 1 个字符相同，如果相同，则加上dp[i][j]，否则不加。
1 class Solution {
int numDistinct(string S, string T) {
if(S.length() & T.length()) return 0;
vector&vector&int& & dp(S.length() + 1, vector&int&(T.length() + 1, 0));
for(int i = 0; i & S.length(); i ++) dp[i][0] = 1;
dp[0][1] = 0;
for(int i = 0; i & S.length(); i ++)
for(int j = 0; j & T.length(); j ++)
dp[i + 1][j + 1] = dp[i][j + 1];
if(S[i] == T[j]) dp[i + 1][j + 1] += dp[i][j];
return dp[S.length()][T.length()];
&题意是优先左子树靠前，且排成一列用右子树指针，不管val的大小关系。
后序遍历一遍即可，递归返回子树中尾节点指针，注意各种条件判断。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
TreeNode *DFS(TreeNode *now)
if(now-&left == NULL && now-&right == NULL) return
TreeNode *leftok = NULL, *rightok = NULL;
if(now-&left != NULL) leftok = DFS(now-&left);
if(now-&right != NULL) rightok = DFS(now-&right);
if(leftok != NULL)
leftok-&right = now-&
now-&right = now-&
now-&left = NULL;
return rightok ? rightok :
else return
void flatten(TreeNode *root) {
if(root == NULL) return;
DFS(root);
&传统递归，把路径上的数字插入vector，终点判断是否插入答案。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&vector&int& &v;
vector&int&
void DFS(TreeNode *now, int cursum)
curv.push_back(now-&val);
if(now-&left == NULL && now-&right == NULL)
if(cursum + now-&val == goal)
v.push_back(curv);
curv.pop_back();
if(now-&left != NULL) DFS(now-&left, cursum + now-&val);
if(now-&right != NULL) DFS(now-&right, cursum + now-&val);
curv.pop_back();
vector&vector&int& & pathSum(TreeNode *root, int sum) {
if(root == NULL) return
DFS(root, 0);
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
bool DFS(TreeNode *now, int cursum)
if(now-&left == NULL && now-&right == NULL)
return cursum + now-&val ==
if(now-&left != NULL && DFS(now-&left, cursum + now-&val)) return true;
if(now-&right != NULL && DFS(now-&right, cursum + now-&val)) return true;
bool hasPathSum(TreeNode *root, int sum) {
if(root == NULL) return false;
return DFS(root, 0);
&还是遍历。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
int minDepth(TreeNode *root) {
if(root == NULL) return 0;
if(root-&left == NULL) return minDepth(root-&right) + 1;
else if(root-&right == NULL) return minDepth(root-&left) + 1;
else return min(minDepth(root-&left), minDepth(root-&right)) + 1;
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
int maxDepth(TreeNode *now)
if(now == NULL) return 0;
int l = maxDepth(now-&left) + 1;
int r = maxDepth(now-&right) + 1;
return abs(l - r) & 1 || l & 0 || r & 0 ? -2 : max(l, r);
bool isBalanced(TreeNode *root) {
return maxDepth(root) &= 0;
每次找中点作为根节点，将两边递归，返回根节点指针作为左右节点。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
18 class Solution {
19 public:
TreeNode *sortedListToBST(ListNode *head) {
if(head == NULL) return NULL;
ListNode *p, *mid, *
for(p = mid = head, pre = NULL; p-&next != NULL; mid = mid-&next)
if(p-&next == NULL) break;
TreeNode *root = new TreeNode(mid-&val);
if(pre != NULL) pre-&next = NULL, root-&left = sortedListToBST(head);
else root-&left = NULL;
root-&right = sortedListToBST(mid-&next);
if(pre != NULL) pre-&next =
&递归做，比链表的容易些。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
TreeNode *convert(vector&int& &num, int left, int right)
if(right == left) return NULL;
int mid = right + left && 1;
TreeNode *root = new TreeNode(num[mid]);
root-&left = convert(num, left, mid);
root-&right = convert(num, mid + 1, right);
TreeNode *sortedArrayToBST(vector&int& &num) {
return convert(num, 0, num.size());
&宽搜和深搜都可以，找对层数就行了。
本以为这题亮点是如何一遍实现从底向上顺序的vector，AC之后上网一查也全是最后把vector翻转的。。。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&vector&int& &v;
void DFS(TreeNode *now, int depth)
if(v.size() &= depth) v.push_back(vector&int&(0));
v[depth].push_back(now-&val);
if(now-&left != NULL) DFS(now-&left, depth + 1);
if(now-&right != NULL) DFS(now-&right, depth + 1);
vector&vector&int& & levelOrderBottom(TreeNode *root) {
if(root == NULL) return
DFS(root, 0);
for(int i = 0, j = v.size() - 1; i & i ++, j --)
swap(v[i], v[j]);
数据结构经典题。后序遍历的结尾是根节点 Proot，在中序遍历中找到这个节点 Iroot，则 Iroot两边即为左右子树。根据左右子树节点个数，在后序遍历中找到左右子树分界（左右子树肯定不交叉），则几个关键分界点都找到了，对左右子树递归。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
TreeNode *build(vector&int& &inorder, int ileft, int iright, vector&int& &postorder, int pleft, int pright)
if(iright == ileft)
return NULL;
for(root = inorder[root] != postorder[pright - 1]; root ++);
TreeNode *node = new TreeNode(inorder[root]);
node-&left = build(inorder, ileft, root, postorder, pleft, pleft + root - ileft);
node-&right = build(inorder, root + 1, iright, postorder, pleft + root - ileft, pright - 1);
TreeNode *buildTree(vector&int& &inorder, vector&int& &postorder) {
return build(inorder, 0, inorder.size(), postorder, 0, postorder.size());
&和上一题Construct Binary Tree from Inorder and Postorder Traversal方法一样，前序和后序的信息作用相同。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
TreeNode *build(vector&int& &inorder, int ileft, int iright, vector&int& &preorder, int pleft, int pright)
if(iright == ileft)
return NULL;
for(root = inorder[root] != preorder[pleft]; root ++);
TreeNode *node = new TreeNode(inorder[root]);
node-&left = build(inorder, ileft, root, preorder, pleft + 1, pleft + root - ileft);
node-&right = build(inorder, root + 1, iright, preorder, pleft + root - ileft + 1, pright);
TreeNode *buildTree(vector&int& &preorder, vector&int& &inorder) {
return build(inorder, 0, inorder.size(), preorder, 0, preorder.size());
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
int maxDepth(TreeNode *root) {
if(root == NULL) return 0;
if(root-&left == NULL) return maxDepth(root-&right) + 1;
if(root-&right == NULL) return maxDepth(root-&left) + 1;
return max(maxDepth(root-&left), maxDepth(root-&right)) + 1;
&BFS，奇偶层轮流走，一层左到右，一层右到左。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&vector&int& &
vector&vector&int& & zigzagLevelOrder(TreeNode *root) {
if(root == NULL) return
vector&TreeNode*& q1, q2;
q1.push_back(root);
int depth = 0;
while(!q1.empty() || !q2.empty())
ans.push_back(vector&int&(0));
for(int i = q1.size() - 1; i &= 0; i --)
ans[depth].push_back(q1[i]-&val);
if(q1[i]-&left != NULL) q2.push_back(q1[i]-&left);
if(q1[i]-&right != NULL) q2.push_back(q1[i]-&right);
q1.clear();
if(q2.empty()) continue;
ans.push_back(vector&int&(0));
for(int i = q2.size() - 1; i &= 0; i --)
ans[depth].push_back(q2[i]-&val);
if(q2[i]-&right != NULL) q1.push_back(q2[i]-&right);
if(q2[i]-&left != NULL) q1.push_back(q2[i]-&left);
q2.clear();
&懒省事直接在上一题Binary Tree Zigzag Level Order Traversal的代码上改了一下。
只用一个队列的话，增加个层数信息存队列里即可。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&vector&int& &
vector&vector&int& & levelOrder(TreeNode *root) {
if(root == NULL) return
vector&TreeNode*& q1, q2;
q1.push_back(root);
int depth = 0;
while(!q1.empty() || !q2.empty())
ans.push_back(vector&int&(0));
for(int i = 0; i & q1.size(); i ++)
ans[depth].push_back(q1[i]-&val);
if(q1[i]-&left != NULL) q2.push_back(q1[i]-&left);
if(q1[i]-&right != NULL) q2.push_back(q1[i]-&right);
q1.clear();
if(q2.empty()) continue;
ans.push_back(vector&int&(0));
for(int i = 0; i & q2.size(); i ++)
ans[depth].push_back(q2[i]-&val);
if(q2[i]-&left != NULL) q1.push_back(q2[i]-&left);
if(q2[i]-&right != NULL) q1.push_back(q2[i]-&right);
q2.clear();
递归：左指针和右指针，对称递归，即&左的左&和&右的右&对应，&左的右&和&右的左&对应。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
bool judge(TreeNode *l, TreeNode *r)
if(l-&val != r-&val) return false;
if(l-&left != r-&right && (l-&left == NULL || r-&right == NULL)
|| l-&right != r-&left && (l-&right == NULL || r-&left == NULL))
return false;
if(l-&left != NULL && !judge(l-&left, r-&right)) return false;
if(l-&right != NULL && !judge(l-&right, r-&left)) return false;
return true;
bool isSymmetric(TreeNode *root) {
if(root == NULL) return true;
if(root-&left == NULL && root-&right == NULL) return true;
else if(root-&left != NULL && root-&right == NULL
|| root-&left == NULL && root-&right != NULL) return false;
return judge(root-&left, root-&right);
非递归：左右子树分别做一个队列，同步遍历。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
bool isSymmetric(TreeNode *root) {
if(root == NULL) return true;
if(root-&left == NULL && root-&right == NULL) return true;
else if(root-&left != NULL && root-&right == NULL
|| root-&left == NULL && root-&right != NULL) return false;
queue&TreeNode *& q1, q2;
q1.push(root-&left);
q2.push(root-&right);
while(!q1.empty())
TreeNode *now1 = q1.front(), *now2 = q2.front();
if(now1-&val != now2-&val) return false;
if(now1-&left != NULL || now2-&right != NULL)
if(now1-&left == NULL || now2-&right == NULL) return false;
q1.push(now1-&left);
q2.push(now2-&right);
if(now1-&right != NULL || now2-&left != NULL)
if(now1-&right == NULL || now2-&left == NULL) return false;
q1.push(now1-&right);
q2.push(now2-&left);
return true;
&同步遍历，比较判断。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if(p == NULL && q == NULL) return true;
if(p != q && (p == NULL || q == NULL) || p-&val != q-&val) return false;
return isSameTree(p-&left, q-&left) && isSameTree(p-&right, q-&right);
&中序遍历是二叉查找树的顺序遍历，*a, *b表示前驱节点和当前节点，因为只有一对数值翻转了，所以肯定会遇到前驱节点val比当前节点val大的情况一次或两次，遇到一次表示翻转的是相邻的两个节点。*ans1和*ans2指向两个被翻转的节点，当遇到前驱val比当前val大的情况时候，根据第一次还是第二次给ans1和ans2赋值，最终翻转回来。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
TreeNode *a, *b;
TreeNode *ans1, *ans2;
bool DFS(TreeNode *now)
if(now-&left != NULL)
DFS(now-&left);
if(a != NULL && a-&val & b-&val)
if(ans1 == NULL) ans1 =
if(now-&right != NULL)
DFS(now-&right);
void recoverTree(TreeNode *root) {
if(root == NULL) return;
a = b = ans1 = ans2 = NULL;
DFS(root);
swap(ans1-&val, ans2-&val);
&中序遍历，更新前驱节点，与当前节点比较。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
TreeNode *pre = NULL;
bool isValidBST(TreeNode *root) {
if(root == NULL) return true;
if(root-&left != NULL && !isValidBST(root-&left)) return false;
if(pre != NULL && pre-&val &= root-&val) return false;
if(root-&right != NULL && !isValidBST(root-&right)) return false;
return true;
&动态规划。如果结果是true，则任意 i, j，s1 i 之前的字符 和 s2 j 之前的字符，都能够交叉为 s3 i + j 之前的字符。
由此，当dp[i][j]时，如果s1[i]==s3[i+j]，则尝试s1[i]与s3[i+j]对应，如果dp[i-1][j]是true，则dp[i][j]也为true。如果s2[j]==s3[i+j]则同样处理。
直到最后，判断dp[s1.length()-1][s2.length()-1]是否为true。为方便初始化，坐标后移了一位。
题目不厚道的出了s1.length()+s2.length() != s3.length()的数据，特判一下。
看到网上也都是O(n^2)的解法，我也就放心了。。。
1 class Solution {
bool isInterleave(string s1, string s2, string s3) {
if(s1.length() + s2.length() != s3.length()) return false;
vector&vector&bool& & dp(s1.length() + 1, vector&bool&(s2.length() + 1, false));
for(int i = 0; i &= s1.length(); i ++)
for(int j = 0; j &= s2.length(); j ++)
if(!i && !j) dp[i][j] = true;
dp[i][j] = dp[i][j] || i & 0 && s3[i + j - 1] == s1[i - 1] && dp[i - 1][j];
dp[i][j] = dp[i][j] || j & 0 && s3[i + j - 1] == s2[j - 1] && dp[i][j - 1];
return dp[s1.length()][s2.length()];
LeetCode目前为止感觉最暴力的。递归遍历所有情况，每次返回子问题（左右子树）的vector&TreeNode *&的解，两层循环组合这些解。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&TreeNode *& generate(int start, int end)
vector&TreeNode *&
if(start & end)
TreeNode *tmp = NULL;
res.push_back(tmp);
for(int i = i &= i ++)
vector&TreeNode *& l = generate(start, i - 1), r = generate(i + 1, end);
for(int j = 0; j & l.size(); j ++)
for(int k = 0; k & r.size(); k ++)
TreeNode *tmp = new TreeNode(i);
tmp-&left = l[j];
tmp-&right = r[k];
res.push_back(tmp);
vector&TreeNode *& generateTrees(int n) {
return generate(1, n);
&经典问题，卡特兰数，可递推，可用公式（公式用组合数，也要写循环）。
1 class Solution {
int COM(int n, int m)
m = n - m & m ? n - m :
int res, i,
for(i = n, res = j = 1; i & n - i --)
for(; j &= m && res % j == 0; j ++)
int numTrees(int n) {
return COM(n && 1, n) / (n + 1);
&数据结构基础
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&int&
void inorder(TreeNode *now)
if(now == NULL) return;
inorder(now-&left);
res.push_back(now-&val);
inorder(now-&right);
vector&int& inorderTraversal(TreeNode *root) {
inorder(root);
四层递归枚举分割位置，判断数字范围和前导零，处理字符串。
1 class Solution {
vector&string&
void DFS(string s, int last, int cur, string now)
if(cur == 3)
if(last == s.length()) return;
string tmp = s.substr(last, s.length() - last);
if(atoi(tmp.c_str()) &= 255 && (tmp.length() == 1 || tmp[0] != '0'))
res.push_back(now + tmp);
for(int i = i & s.length(); i ++)
string tmp = s.substr(last, i - last + 1);
if(atoi(tmp.c_str()) &= 255 && (tmp.length() == 1 || tmp[0] != '0'))
DFS(s, i + 1, cur + 1, now + tmp + ".");
vector&string& restoreIpAddresses(string s) {
DFS(s, 0, 0, "");
&在表头添加一个&哨兵&会好写很多，额外的newhead可以帮助标记翻转之后更换了的头指针。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode *newhead = new ListNode(0);
newhead-&next =
ListNode *pre = newhead, *p = head, *start = NULL;
ListNode *
for(int i = 1; p != NULL; i ++)
if(i == m)
if(i & m && i &= n)
if(i == n)
start-&next-&next =
start-&next =
tmp = newhead-&
free(newhead);
统计地存map里，map[i]= j 表示 S 中有 j 个 i。map是有序的，用迭代器递归枚举放入集合的个数。
也可以先排序，用set标记每个数时候被放入过，第一次放入之后才可以继续放同一个数。
代码是用map的方法。
1 class Solution {
vector&vector&int& &
vector&int&
map&int, int&
void DFS(map&int, int&::iterator i)
if(i == mp.end())
res.push_back(now);
map&int, int&::iterator tmp =
for(int j = 0; j & tmp-& j ++)
now.push_back(tmp-&first);
for(int j = 0; j & tmp-& j ++)
now.pop_back();
vector&vector&int& & subsetsWithDup(vector&int& &S) {
for(int i = 0; i & S.size(); i ++)
!mp.count(S[i]) ? (mp[S[i]] = 1) : mp[S[i]] ++;
DFS(mp.begin());
递推：dp[i]表示前 i 个数字的解码种数。
dp[i]& = if(一)dp[i-1] + if(二)dp[i-2]
当 i 位置不为0，可加上 i - 1 位置的解。当当前位置和前一位置组成的两位数满足解码且高位不为0，可加上 i - 2 位置的解。
1 class Solution {
int numDecodings(string s) {
if(s.length() == 0) return 0;
vector&int& dp(s.length() + 1, 0);
dp[0] = 1;
for(int i = 0; i & s.length(); i ++)
dp[i + 1] = (s[i] != '0' ? dp[i] : 0) +
(i & 0 && s[i - 1] != '0' && atoi(s.substr(i - 1, 2).c_str()) &= 26 ? dp[i - 1] : 0);
return dp[s.length()];
格雷码有多种生成方法，可参考。
1 class Solution {
vector&int& grayCode(int n) {
vector&int&
for(int i = 0; i & (1 && n); i ++)
res.push_back((i && 1) ^ i);
&从后往前，对 A 来说一个萝卜一个坑，肯定不会破坏前面的数据。具体看代码。
1 class Solution {
void merge(int A[], int m, int B[], int n) {
int p = m + n - 1, i = m - 1, j = n - 1;
for(; i &= 0 && j &= 0;)
if(A[i] & B[j]) A[p --] = A[i --];
else A[p --] = B[j --];
while(i &= 0) A[p --] = A[i --];
while(j &= 0) A[p --] = B[j --];
&直接搜索可以过，记忆化搜索可提高效率。
&dp[i][j][k]表示从 s1[i] 和 s2[j] 开始长度为 k 的字符串是否是scrambled string。
枚举分割位置，scrambled string要求字符串对应字母的个数是一致的，可以直接排序对比。递归终点是刚好只有一个字母。
1 class Solution {
string S1, S2;
vector&vector&vector&int& & &
bool judge(string a, string b)
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for(int i = 0; i & a.length(); i ++)
if(a[i] != b[i]) return false;
return true;
int DFS(int s1start, int s2start, int len)
int &ans = dp[s1start][s2start][len - 1];
if(len == 1) return ans = S1[s1start] == S2[s2start];
if(ans != -1) return
if(!judge(S1.substr(s1start, len), S2.substr(s2start, len))) return ans = 0;
for(int i = 1; i & i ++)
|| DFS(s1start, s2start, i) && DFS(s1start + i, s2start + i, len - i)
|| DFS(s1start, s2start + len - i, i) && DFS(s1start + i, s2start, len - i);
bool isScramble(string s1, string s2) {
S1 = s1, S2 = s2;
dp = vector&vector&vector&int& & &
(s1.length(), vector&vector&int& &
(s1.length(), vector&int&
(s1.length(), -1)));
return DFS(0, 0, s1.length());
&分存大小最后合并。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
ListNode *partition(ListNode *head, int x) {
ListNode *shead, *bhead, *smaller, *bigger, *p;
for(shead = bhead = smaller = bigger = NULL, p = p != NULL; p = p-&next)
if(p-&val & x)
if(shead == NULL)
if(smaller != NULL)
smaller-&next =
if(bhead == NULL)
if(bigger != NULL)
bigger-&next =
if(smaller != NULL) smaller-&next =
if(bigger != NULL) bigger-&next = NULL;
return shead != NULL ? shead :
方法一：linecnt[i][j]统计第 i 行到第 j 位置有多少个连续的 '1'，接下来枚举列，每一列相当于一次直方图最大矩形统计，计算每个位置向前和向后最远的不少于当前位置值的位置，每次更新结果，总复杂度O(n^2)。
找&最远位置&用迭代指针，理论复杂度略高于O(n)。
1 class Solution {
int maximalRectangle(vector&vector&char& & &matrix) {
if(matrix.size() == 0) return 0;
int H = matrix.size(), W = matrix[0].size();
int ans = 0;
vector&int& left(H), right(H);
vector&vector&int& & linecnt(H, vector&int&(W, 0));
for(int i = 0; i & H; i ++)
int last = 0;
for(int j = 0; j & W; j ++)
if(matrix[i][j] == '1') last ++;
else last = 0;
linecnt[i][j] =
for(int k = 0; k & W; k ++)
for(int i = 0; i & H; i ++)
if(i == 0) left[i] = -1;
left[i] = i - 1;
while(left[i] & -1 && linecnt[left[i]][k] &= linecnt[i][k])
left[i] = left[left[i]];
for(int i = H - 1; i &= 0; i --)
if(i == H - 1) right[i] = H;
right[i] = i + 1;
while(right[i] & H && linecnt[right[i]][k] &= linecnt[i][k])
right[i] = right[right[i]];
ans = max(ans, (right[i] - left[i] - 1) * linecnt[i][k]);
用单调栈，理论复杂度O(n)。
1 class Solution {
int maximalRectangle(vector&vector&char& & &matrix) {
if(matrix.size() == 0) return 0;
vector&vector&int& & linecnt(matrix.size(), vector&int&(matrix[0].size(), 0));
for(int i = 0; i & matrix.size(); i ++)
int last = 0;
for(int j = 0; j & matrix[0].size(); j ++)
if(matrix[i][j] == '1') last ++;
else last = 0;
linecnt[i][j] =
int ans = 0;
for(int k = 0; k & matrix[0].size(); k ++)
stack&int& s,
vector&int&last(matrix.size());
for(int i = 0; i & matrix.size(); i ++)
while(!s.empty() && s.top() &= linecnt[i][k])
s.pop(), site.pop();
if(!s.empty()) last[i] = site.top() + 1;
else last[i] = 0;
s.push(linecnt[i][k]);
site.push(i);
while(!s.empty()) s.pop(), site.pop();
for(int i = matrix.size() - 1; i &= 0; i --)
while(!s.empty() && s.top() &= linecnt[i][k])
s.pop(), site.pop();
if(!s.empty()) ans = max(ans, (site.top() - last[i]) * linecnt[i][k]);
else ans = max(ans, (int)(matrix.size() - last[i]) * linecnt[i][k]);
s.push(linecnt[i][k]);
site.push(i);
方法二：每个 '1' 的点当作一个矩形的底部，left[j]、right[j]、height[j]表示当前行第 j 个位置这个点向左、右、上伸展的最大矩形的边界，作为滚动数组，下一行的数据可以由上一行结果得到，总复杂度O(n^2)。
left[j] = max(这一行最左, left[j]（上一行最左）& );
right[j] = min(这一行最右，right[j]（上一行最右）& );
height[j] = height[j - 1] + 1;
1 class Solution {
int maximalRectangle(vector&vector&char& & &matrix) {
if(matrix.size() == 0) return 0;
int H = matrix.size(), W = matrix[0].size();
vector&int& left(W, -1), right(W, W), height(W, 0);
int ans = 0;
for(int i = 0; i & H; i ++)
int last = -1;
for(int j = 0; j & W; j ++)
if(matrix[i][j] == '1')
if(last == -1) last =
left[j] = max(left[j], last);
height[j] ++;
last = -1;
left[j] = -1;
height[j] = 0;
last = -1;
for(int j = W - 1; j &= 0; j --)
if(matrix[i][j] == '1')
if(last == -1) last =
right[j] = min(right[j], last);
ans = max(ans, height[j] * (right[j] - left[j] + 1));
last = -1;
right[j] = W;
&参考上一题Maximal Rectangle方法一。
1 class Solution {
int largestRectangleArea(vector&int& &height) {
if(height.size() == 0) return 0;
vector&int& left(height.size()), right(height.size());
int ans = 0;
for(int i = 0; i & height.size(); i ++)
if(i == 0) left[i] = -1;
left[i] = i - 1;
while(left[i] & -1 && height[i] &= height[left[i]])
left[i] = left[left[i]];
for(int i = height.size() - 1; i &= 0; i --)
if(i == height.size() - 1) right[i] = height.size();
right[i] = i + 1;
while(right[i] & height.size() && height[i] &= height[right[i]])
right[i] = right[right[i]];
ans = max(ans, (right[i] - left[i] - 1) * height[i]);
&加个表头乱搞吧。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
ListNode *deleteDuplicates(ListNode *head) {
if(head == NULL || head-&next == NULL) return
ListNode *newhead = new ListNode(0);
newhead-&next =
for(ListNode *pre = newhead, *now = head, *nex = head-& nex != NULL;)
if(now-&val == nex-&val)
while(nex != NULL && now-&val == nex-&val)
free(now);
nex = nex-&
free(now);
pre-&next =
if(nex == NULL) break;
else pre =
nex = nex-&
head = newhead-&
free(newhead);
&直接操作。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
ListNode *deleteDuplicates(ListNode *head) {
if(head == NULL || head-&next == NULL) return
for(ListNode *pre = head, *p = head-& p != NULL;)
while(p != NULL && pre-&val == p-&val)
pre-&next = p-&
if(p == NULL) break;
以mid为界，左右两边至少有一边是有序的。由于不可避免地会有O(n)的可能性，所以确定的时候二分，不确定的时候单位缩减边界。
1 class Solution {
bool search(int A[], int n, int target) {
int left = 0, right = n - 1,
while(left & right)
mid = left + right && 1;
if(target & A[mid] && A[left] & target) right =
else if(target & A[right] && A[mid] & target) left = mid + 1;
if(A[left] == target || A[right] == target) return true;
else if(A[left] & target) left ++;
else if(target & A[right]) right --;
else return false;
return A[left] == target ? true : false;
&记下放了几个，多了不放。
1 class Solution {
int removeDuplicates(int A[], int n) {
for(i = j = cnt = 0; i & i ++)
if(j != 0 && A[j - 1] == A[i]) cnt ++;
else cnt = 0;
if(cnt & 2) A[j ++] = A[i];
1 class Solution {
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool DFS(int x, int y, vector&vector&char& & &board, string word, int ith)
if(board[x][y] != word[ith]) return false;
if(ith == word.length() - 1) return true;
board[x][y] = '.';
for(int i = 0; i & 4; i ++)
int nx = x + dx[i];
int ny = y + dy[i];
if(nx &= 0 && ny &= 0 && nx & board.size() && ny & board[0].size())
if(DFS(nx, ny, board, word, ith + 1))
board[x][y] = word[ith];
return true;
board[x][y] = word[ith];
return false;
bool exist(vector&vector&char& & &board, string word) {
for(int i = 0; i & board.size(); i ++)
for(int j = 0; j & board[0].size(); j ++)
if(DFS(i, j, board, word, 0)) return true;
return false;
1 class Solution {
vector&int&
vector&vector&int& &
void DFS(vector&int& &S, int ith)
if(ith == S.size())
res.push_back(now);
DFS(S, ith + 1);
now.push_back(S[ith]);
DFS(S, ith + 1);
now.pop_back();
vector&vector&int& & subsets(vector&int& &S) {
sort(S.begin(), S.end());
DFS(S, 0);
1 class Solution {
vector&int&
vector&vector&int& &
void DFS(int n, int ith, int sum, int k)
if(sum == k)
res.push_back(now);
if(sum + n - ith + 1 & k)
DFS(n, ith + 1, sum, k);
now.push_back(ith);
DFS(n, ith + 1, sum + 1, k);
now.pop_back();
vector&vector&int& & combine(int n, int k) {
DFS(n, 1, 0, k);
先统计 T 中各字符都有多少个，然后两个下标一前(i)一后(j)在 S 上跑，&当 i 跑到把 T 中字符都包含的位置时候，让 j 追到第一个包含 T 的字符的地方，更新结果，去掉 j 这个位置字符的统计，让 i 继续跑，如此反复。
i 和 j&都只遍历一遍 S，复杂度 O(n)。
1 class Solution {
string minWindow(string S, string T) {
vector&int& cnt(256, 0), need(256, 0);
int sum = 0, len = 0x3f3f3f3f;
for(int i = 0; i & T.size(); i ++)
need[T[i]] ++;
for(int i = 0, j = 0; i & S.length(); j ++)
while(i & S.length() && sum & T.length())
if(cnt[S[i]] & need[S[i]])
cnt[S[i]] ++;
while(sum == T.length() && j & S.length())
cnt[S[j]] --;
if(cnt[S[j]] & need[S[j]])
if(sum & T.length()) break;
if(i - j & len)
ans = S.substr(j, i - j), len = i -
1 class Solution {
void sortColors(int A[], int n) {
int find = 0;
for(int i = 0, j = n - 1; i & i ++)
if(A[i] == find) continue;
while(j & i && A[j] != find) j --;
if(j & i) swap(A[i], A[j]);
else i --, j = n - 1, find ++;
找到哪个放哪个：
1 class Solution {
void sortColors(int A[], int n) {
int p0, p1, p2;
for(p0 = 0, p1 = p2 = n - 1; p0 & p1; )
if(A[p0] == 0) p0 ++;
if(A[p0] == 1) swap(A[p0], A[p1 --]);
if(A[p0] == 2)
swap(A[p0], A[p2 --]);
写两个二分查找。或者把整个矩阵看作一维，直接二分，换算坐标。
1 class Solution {
bool searchMatrix(vector&vector&int& & &matrix, int target) {
int left, right,
for(left = 0, right = matrix.size(); left & right - 1; )
mid = left + right && 1;
if(matrix[mid][0] & target) right =
else left =
if(left == matrix.size() || right == 0) return false;
vector&int& &a = matrix[left];
for(left = 0, right = a.size(); left & right - 1;)
mid = left + right && 1;
if(a[mid] & target) right =
else left =
if(left == a.size() || right == 0) return false;
return a[left] ==
O(m+n)的方法是容易想到的，而空间复杂度O(1)，只要利用原矩阵的一行和一列来使用O(m+n)的方法就行了。
1 class Solution {
void setZeroes(vector&vector&int& & &matrix) {
if(matrix.size() == 0) return;
int x = -1, y = -1;
for(int i = 0; i & matrix.size(); i ++)
for(int j = 0; j & matrix[0].size(); j ++)
if(matrix[i][j] == 0)
if(x == -1)
x = i, y =
matrix[x][j] = 0;
matrix[i][y] = 0;
if(x == -1) return;
for(int i = 0; i & matrix.size(); i ++)
for(int j = 0; j & matrix[0].size(); j ++)
if((matrix[x][j] == 0 || matrix[i][y] == 0) && (i != x && j != y)) matrix[i][j] = 0;
for(int i = 0; i & matrix.size(); i ++) matrix[i][y] = 0;
for(int j = 0; j & matrix[0].size(); j ++) matrix[x][j] = 0;
&动态规划，先初始化 dp[i][0] 和 dp[0][i]，即每个字符串对应空串的编辑距离为串长度，之后对每个位置取子问题加上当前位置 改、删、增得解的最小值。
1 class Solution {
int minDistance(string word1, string word2) {
vector&vector&int& & dp(word1.length() + 1, vector&int&(word2.length() + 1, 0));
for(int i = 0; i & word1.length(); i ++) dp[i + 1][0] = i + 1;
for(int i = 0; i & word2.length(); i ++) dp[0][i + 1] = i + 1;
for(int i = 0; i & word1.length(); i ++)
for(int j = 0; j & word2.length(); j ++)
if(word1[i] != word2[j])
dp[i + 1][j + 1] = min(dp[i][j] + 1, min(dp[i][j + 1] + 1, dp[i + 1][j] + 1));
dp[i + 1][j + 1] = min(dp[i][j], min(dp[i][j + 1] + 1, dp[i + 1][j] + 1));
return dp[word1.length()][word2.length()];
&好烦人的题，没什么好说的。
1 class Solution {
string simplifyPath(string path) {
stack&string&
for(int i = 0; i & path.length(); i ++)
if(path[i] == '/')
if(str == "..")
if(!s.empty())
else if(str != "." && str != "")
s.push(str);
str.clear();
str += path[i];
if(str == "..")
if(!s.empty())
else if(str != "." && str != "")
s.push(str);
if(s.empty()) return "/";
for(str.clear(); !s.empty(); s.pop())
str = "/" + s.top() +
&递推，就是斐波那契数列。
1 class Solution {
int climbStairs(int n) {
return (int)
(pow((1+sqrt(5))/2, n + 1) / sqrt(5) -
pow((1-sqrt(5))/2, n + 1) / sqrt(5) + 0.1);
&牛顿迭代。
设输入为n，f(x)=x^2-n，解就是f(x)=0时的x。
设猜了一数x[0]，那么在f(x)在x[0]处的切线与x轴的交点x[1]更接近目标解（可画图看看）。
那么递推下去，x[i]=(x[i-1]+n/x[i-1])/2，用double，越推越精确，直到自己想要的精度。
1 class Solution {
int sqrt(int x) {
double now,
if(x == 0) return 0;
for(now = last = (double)x; ; last = now)
now = (last + (x / last)) * 0.5;
if(fabs(last - now) & 1e-5) break;
return (int)(now + 1e-6);
每行限制长度，空格均匀插入，不能完全平均的情况下优先靠前的单词间隔。
最后一行特别处理，单词间只有一个空格，剩下的放在末尾。
1 class Solution {
vector&string& fullJustify(vector&string& &words, int L) {
vector&string&
int cnt = 0, i, j, k,
for(i = 0, j = 0; j & words.size(); i ++)
if(i & words.size())
cnt += words[i].length();
if(i == j) continue;
if(i == words.size() || (L - cnt) / (i - j) & 1)
int blank = 0;
if(i & words.size()) blank = (i - j - 1) ? (L - cnt + words[i].length()) / (i - j - 1) : 0;
string tmp = "";
l = i & words.size() ? (L - cnt + words[i].length() - blank * (i - j - 1)) : 0;
for(k = k & k ++, l --)
tmp += words[k];
if(k != i - 1)
if(i != words.size())
for(int bl = 0; bl & bl ++) tmp += " ";
if(l & 0) tmp += " ";
tmp += " ";
while(tmp.length() & L) tmp += " ";
ans.push_back(tmp);
大整数加法。
1 class Solution {
vector&int& plusOne(vector&int& &digits) {
if(digits.size() == 0) return
for(i = digits.size() - 1, cur = 1; i &= 0; i --)
int tmp = digits[i] +
cur = tmp / 10;
digits[i] = tmp % 10;
if(cur) digits.insert(digits.begin(), cur);
用DFA也不麻烦，题目定义太模糊，为了理解规则错很多次也没办法。
1 class Solution {
int f[11][129];
const int fail = -1;
const int st = 0;
const int pn = 1;
const int di = 2;
//整数部分
const int del = 3;
//前面无数字小数点
const int ddi = 4;
//小数部分
const int ndel = 5;
//前面有数字小数点
const int dibl = 6;
//数后空格
const int ex = 7;
//进入指数
const int epn = 8;
//指数符号
const int edi = 9;
//指数数字
const int end = 10;
//正确结束
void buildDFA()
memset(f, -1, sizeof(f));
f[st][' '] =
f[st]['+'] = f[st]['-'] =
for(int i = '0'; i &= '9'; i ++)
f[st][i] = f[pn][i] = f[di][i] =
f[del][i] = f[ndel][i] = f[ddi][i] =
f[ex][i] = f[epn][i] = f[edi][i] =
f[di]['.'] =
f[st]['.'] = f[pn]['.'] =
f[di][' '] = f[ndel][' '] = f[ddi][' '] = f[dibl][' '] = f[edi][' '] =
f[di][0] = f[ndel][0] = f[dibl][0] = f[ddi][0] = f[edi][0] =
f[di]['e'] = f[ndel]['e'] = f[ddi]['e'] =
f[ex][' '] =
f[ex]['+'] = f[ex]['-'] =
bool DFA(const char *s)
int situ =
for(int i = 0;; i ++)
situ = f[situ][s[i]];
if(situ == end) return true;
if(situ == fail) return false;
return true;
bool isNumber(const char *s) {
buildDFA();
return DFA(s);
翻转，大整数加法，再翻转。无心情优化。
1 class Solution {
string addBinary(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int cur = 0,
for(i = 0; i & min(a.length(), b.length()); i ++)
int tmp = a[i] - '0' + b[i] - '0' +
cur = tmp && 1;
c += (tmp & 1) + '0';
string &t = a.length() & b.length() ? a :
for(; i & t.length(); i ++)
int tmp = t[i] - '0' +
cur = tmp && 1;
c += (tmp & 1) + '0';
if(cur) c += '1';
reverse(c.begin(), c.end());
归并排序的一次操作，设个哨兵头结点，结束后free。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *thead = new ListNode(0), *p =
while(l1 != NULL && l2 != NULL)
if(l1-&val & l2-&val) p-&next = l1, p = l1, l1 = l1-&
else p-&next = l2, p = l2, l2 = l2-&
while(l1 != NULL) p-&next = l1, p = l1, l1 = l1-&
while(l2 != NULL) p-&next = l2, p = l2, l2 = l2-&
p = thead-&
free(thead);
1 class Solution {
int minPathSum(vector&vector&int& & &grid) {
if(grid.size() == 0) return 0;
for(int i = 0; i & grid.size(); i ++)
for(int j = 0; j & grid[0].size(); j ++)
int tmp = 0x3f3f3f3f;
if(i & 0) tmp = min(tmp, grid[i][j] + grid[i - 1][j]);
if(j & 0) tmp = min(tmp, grid[i][j] + grid[i][j - 1]);
grid[i][j] = tmp == 0x3f3f3f3f ? grid[i][j] :
return grid[grid.size() - 1][grid[0].size() - 1];
1 class Solution {
int uniquePathsWithObstacles(vector&vector&int& & &obstacleGrid) {
if(obstacleGrid.size() == 0) return 0;
obstacleGrid[0][0] = obstacleGrid[0][0] != 1;
for(int i = 0; i & obstacleGrid.size(); i ++)
for(int j = 0; j & obstacleGrid[0].size(); j ++)
if(i == 0 && j == 0) continue;
if(obstacleGrid[i][j] == 1)
obstacleGrid[i][j] = 0;
if(i & 0) obstacleGrid[i][j] += obstacleGrid[i - 1][j];
if(j & 0) obstacleGrid[i][j] += obstacleGrid[i][j - 1];
return obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];
这是当年学组合数时候的经典题型吧。
1 class Solution {
int COM(int a, int b)
b = min(b, a - b);
int ret = 1, i,
for(i = a, j = 1; i & a - i --)
for(; j &= b && ret % j == 0; j ++)
int uniquePaths(int m, int n) {
return COM(m + n - 2, m - 1);
因为k可能比长度大，需要求长度然后k对长度取模。那么就不要矫情地追求双指针一遍扫描了。
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
9 class Solution {
10 public:
ListNode *rotateRight(ListNode *head, int k) {
if(head == NULL) return NULL;
ListNode *en, *p;
for(cnt = 1, en = en-&next != NULL; cnt ++, en = en-&next);
for(p = head, cnt --; cnt != cnt --, p = p-&next);
en-&next =
p-&next = NULL;
&一位一位算，每一位优先没使用过的较小的数字，而其后剩下的m个位置有 m! 种排列方法，用 k 减去，直到k不大于这个方法数，则这一位就是枚举到的这个数。
1 class Solution {
int permu[10];
bool vis[10];
string getPermutation(int n, int k) {
permu[0] = 1;
for(int i = 1; i & 10; i ++) permu[i] = permu[i - 1] *
memset(vis, 0, sizeof(vis));
for(int i = 1; i &= i ++)
for(int j = 1; j &= j ++)
if(!vis[j])
if(k & permu[n - i]) k -= permu[n - i];
else {ans += '0' + vis[j] = true; break;}
直接算每个位置的数是多少有木有很霸气
先看当前位置之外有几个嵌套的正方形，再看当前位置在当前正方形四条边的第几条，求出坐标(x,y)位置的数。
1 class Solution {
vector&vector&int& &
vector&int&
int calnum(int i, int j, int n)
tmp = min(min(i, j), min(n - 1 - i, n - 1 - j));
num = nsq[tmp];
if(i == tmp) return num + j - tmp + 1;
if(n - j - 1 == tmp) return num + n - 2 * tmp + i -
if(n - i - 1 == tmp) return num + 2 * (n - 2 * tmp) - 2 + n - j -
return num + 3 * (n - 2 * tmp) - 3 + n - i -
vector&vector&int& & generateMatrix(int n) {
nsq.push_back(0);
for(int i = i & 0; i -= 2) nsq.push_back(4 * i - 4);
for(int i = 1; i & nsq.size(); i ++) nsq[i] += nsq[i - 1];
for(int i = 0; i & i ++)
vector&int&
for(int j = 0; j & j ++)
tmp.push_back(calnum(i, j, n));
res.push_back(tmp);
&从后往前找。
1 class Solution {
int lengthOfLastWord(const char *s) {
for(i = strlen(s) - 1; i &= 0 && s[i] == ' '; i --);
for(j = i - 1; j &= 0 && s[j] != ' '; j --);
return i & 0 ? 0 : i -
end 比 newInterval 的 start 小的 intervals 直接插入，从 end 比 newInterval 的 start 大的 intervals 开始，到 start 比 newInterval 的 end 大的 intervals 结束，对这部分区间合并，再把之后的 intervals直接插入，特判 newInterval 最小和最大两种极端情况。
* Definition for an interval.
* struct Interval {
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
10 class Solution {
11 public:
vector&Interval&
vector&Interval& insert(vector&Interval& &intervals, Interval newInterval) {
if(intervals.size() == 0) {res.push_back(newInterval); return}
for(i = 0; i & intervals.size() && newInterval.start & intervals[i]. i ++)
res.push_back(intervals[i]);
for(j = j & intervals.size() && newInterval.end &= intervals[j]. j ++);
if(j != 0 && i != intervals.size())
res.push_back(Interval(min(intervals[i].start, newInterval.start),
max(intervals[j - 1].end, newInterval.end)));
res.push_back(newInterval);
for(; j & intervals.size(); j ++) res.push_back(intervals[j]);
先按start排个序，然后慢慢合并。。。
* Definition for an interval.
* struct Interval {
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
10 class Solution {
11 public:
vector&Interval&
static bool cxompp(const Interval &a, const Interval &b)
{return a.start & b.}
vector&Interval& merge(vector&Interval& &intervals) {
if(intervals.size() == 0) return
sort(intervals.begin(), intervals.end(), cxompp);
Interval last = intervals[0];
for(int i = 1; i & intervals.size(); i ++)
if(last.end &= intervals[i].start)
last.end = max(last.end, intervals[i].end);
res.push_back(last), last = intervals[i];
res.push_back(last);
&维护最大可跳距离，每个位置都枚举一次。
1 class Solution {
bool canJump(int A[], int n) {
if(n == 0) return false;
for(i = jumpdis = 0; i & n && jumpdis &= 0; i ++, jumpdis --)
jumpdis = max(A[i], jumpdis);
return i ==
&模拟转一遍吧。写了俩代码，差不多，处理拐弯的方式略有不同。
1 class Solution {
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector&int&
bool JudgeValid(int x, int y,
vector&vector&bool& & &vis, vector&vector&int& & &matrix)
return x &= 0 && x & matrix.size() &&
y &= 0 && y & matrix[0].size() && vis[x][y] == false;
vector&int& spiralOrder(vector&vector&int& & &matrix) {
int dir, x, y, nx,
if(matrix.size() == 0) return
vector&vector&bool& & vis(matrix.size(), vector&bool&(matrix[0].size(), false));
for(dir = x = y = 0; JudgeValid(x, y, vis, matrix); x = nx, y = ny)
res.push_back(matrix[x][y]);
vis[x][y] = true;
nx = x + dx[dir];
ny = y + dy[dir];
if(!JudgeValid(nx, ny, vis, matrix))
dir = (dir + 1) % 4;
nx = x + dx[dir];
ny = y + dy[dir];
1 class Solution {
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector&int&
vector&int& spiralOrder(vector&vector&int& & &matrix) {
int dir, x, y, nx,
int l, r, u,
if(matrix.size() == 0) return
l = u = -1;
r = matrix[0].size();
d = matrix.size();
for(dir = x = y = 0; res.size() & matrix.size() * matrix[0].size();
x = nx, y = ny)
res.push_back(matrix[x][y]);
nx = x + dx[dir];
ny = y + dy[dir];
if(nx == d || nx == u || ny == r || ny == l)
dir = (dir + 1) % 4;
if(dir == 0) l ++, r --, d --;
else if(dir == 3) u ++;
nx = x + dx[dir];
ny = y + dy[dir];
&最大子串和，子串要求至少包含一个数字。
一个变量 sum 表示当前求得的子串和，当 sum 小于0时，对后面的子串没有贡献，则把 sum 置零，中间处理一下要求至少包含一个数字的要求即可。
1 class Solution {
int maxSubArray(int A[], int n) {
int ans = A[0], sum = 0;
for(int i = 0; i & i ++)
sum += A[i];
if(sum & 0) sum = 0, ans = max(ans, A[i]);
else ans = max(ans, sum);
&题目没说 n 的取值范围，就不用 位运算 做标记了。
老老实实开三个 bool 数组，一个标记纵列，另外两个标记两个斜列，一行一行DFS。
1 class Solution {
vector&bool& col, lc,
void DFS(int cur, int n)
if(cur == n)
for(int i = 0; i & i ++)
if(!col[i] && !lc[n - cur - 1 + i] && !rc[cur + i])
col[i] = lc[n - cur - 1 + i] = rc[cur + i] = true;
DFS(cur + 1, n);
col[i] = lc[n - cur - 1 + i] = rc[cur + i] = false;
int totalNQueens(int n) {
col.resize(n, 0);
lc.resize(n && 1, 0);
rc.resize(n && 1, 0);
DFS(0, n);
1 class Solution {
vector&string&
vector&vector&string& &
vector&bool& col, lc,
void DFS(int cur, int n)
if(cur == n)
res.push_back(tmp);
string now(n, '.');
for(int i = 0; i & i ++)
if(!col[i] && !lc[n - cur - 1 + i] && !rc[cur + i])
col[i] = lc[n - cur - 1 + i] = rc[cur + i] = true;
now[i] = 'Q';
tmp.push_back(now);
DFS(cur + 1, n);
tmp.pop_back();
now[i] = '.';
col[i] = lc[n - cur - 1 + i] = rc[cur + i] = false;
vector&vector&string& & solveNQueens(int n) {
col.resize(n, 0);
lc.resize(n && 1, 0);
rc.resize(n && 1, 0);
DFS(0, n);
&很多人用特判错过了 n = - 这么优美的 trick，而不特判的话，似乎只能 long long 了。
经典}