博客搬至blog.csgrandeur.com，cnblogs不再更新。
新的题解会更新在新博客：http://blog.csgrandeur.com/3/
————————————————————————————————————————
————————————————————————————————————————
LeetCode OJ 题解
LeetCode OJ is a platform for preparing technical coding interviews.
LeetCode OJ 是为与写代码有关的技术工作面试者设计的训练平台。
LeetCode OJ:http://oj.leetcode.com/
默认题目顺序为题目添加时间倒叙，本文题解顺序与OJ题目顺序一致（OJ会更新，至少目前一致。。。），目前共152题。
Made By：CSGrandeur
另外，Vimer做了Python版的题解：http://c4fun.cn/blog/2014/03/20/leetcode-solution-02/
————————————————————————————————————————
Maximum Product Subarray
维护当前位置连续乘积的最大值 tmpp 和最小值 tmpn ，最大值和最小值都可能由三种情况得到：上一个数的 tmpp*A[i]，上一个数的 tmpn*A[i]，A[i]本身。
不断更新答案，最终输出。
class Solution {
public:
int maxProduct(int A[], int n) {
int tmpp = A[], tmpn = A[], tmp, ans = A[];
for(int i = ; i < n; i ++)
{
tmp = tmpp;
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);
}
return ans;
}
};
先翻转整个字符串，然后从前往后一个单词一个单词地再翻转一次，同时去除多余空格，等于是扫描两遍，O(n)。
class Solution {
public:
void reverseWords(string &s) {
reverse(s.begin(), s.end());
int start = , end = , j = ;
while(start != s.length())
{
while(start != s.length() && s[start] == ' ') start ++;
for(end = start; end != s.length() && s[end] != ' '; end ++);
if(j != && start <= end - ) s[j ++] = ' ';
for(int i = end - ; start < i; start ++, i --)
swap(s[i], s[start]), s[j ++] = s[start];
while(start < end) s[j ++] = s[start ++];
}
s.resize(j);
}
};
Evaluate Reverse Polish Notation
逆波兰表达式计算四则运算。用栈。
class Solution {
public:
int evalRPN(vector<string> &tokens) {
int a, b;
stack<int> s;
for(int i = ; i < tokens.size(); i ++)
{
if(isdigit(tokens[i][]) || tokens[i].length() > )
{
s.push(atoi(tokens[i].c_str()));
continue;
}
a = s.top();s.pop();
b = s.top();s.pop();
switch(tokens[i][])
{
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();
}
};
Max Points on a Line
平面上一条直线最多穿过多少点。乍一看好熟悉的问题，做了这么久计算几何。。。却还真没做过这个小问题。
第一反应当然不能O(n^3)枚举了，枚举圆周好像也不行，毕竟是考察所有点，不是某个点。那么应该就是哈希斜率了吧。
肯定少不了竖直的线，哈希斜率这不像是这类OJ让写的题吧。。忘了map这回事了。
确定思路之后，还是看看别人博客吧，少走点弯路，然后就学习了还有unordered_map这么个东西，还有一个博客的思路挺好，避免double问题，把斜率转化成化简的x、y组成字符串。
再另外就是重叠的点了，想让题目坑一点，怎能少得了这种数据，单独处理一下。
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point> &points) {
int ans = ;
for(int i = ; i < points.size(); i ++)
{
unordered_map<string, int> mp;
int tmpans = , same = ;
for(int j = i + ; 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 != ) x /= g, y /= g;
else {same ++; continue;}
if(x < ) x = -x, y = -y;
string tmp = to_string(x) + " " + to_string(y);
if(!mp.count(tmp)) mp[tmp] = ;
else mp[tmp] ++;
tmpans = max(tmpans, mp[tmp]);
}
ans = max(tmpans + + same, ans);
}
return ans;
}
int gcd(int a, int b)
{
return a ? gcd(b % a, a) : b;
}
};
Sort List
又长见识了，原来链表也可以O(nlogn)排序的。没往下想就查了一下，看到人说用归并，于是才开始想能不能实现。。。
O(n)找到中点，把中点的next变成NULL，对两部分递归。递归结束后对两部分归并，先找到newhead，即两部分的头部val较小的那个，然后归并就把小的从newhead往后续。
把最后的next赋值NULL，返回newhead。
又有空数据@_@.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *sortList(ListNode *head) {
int n = ;
ListNode *p = head;
while(p != NULL)
n ++, p = p->next;
if(n <= ) return head;
n >>= ;
p = head;
while(-- n)
p = p->next;
ListNode *tmp = p->next;
p->next = NULL;
ListNode *nl = sortList(head);
ListNode *nr = sortList(tmp);
ListNode *newhead;
if(nl->val < nr->val)
{
newhead = nl;
nl = nl->next;
}
else
{
newhead = nr;
nr = nr->next;
}
p = newhead;
while(nl != NULL && nr != NULL)
{
if(nl->val < nr->val) p->next = nl, p = p->next, nl = nl->next;
else p->next = nr, p = p->next, nr = nr->next;
}
while(nl != NULL) p->next = nl, p = p->next, nl = nl->next;
while(nr != NULL) p->next = nr, p = p->next, nr = nr->next;
p->next = NULL;
return newhead;
}
};
Insertion Sort List
指针操作很烦啊。。暴力枚举插入位置，注意细节就能过了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
ListNode *newhead = head;
if(head == NULL) return NULL;
head = head->next;
newhead->next = NULL;
while(head != NULL)
{
if(head->val < newhead->val)
{
ListNode *tmp = head->next;
head->next = newhead;
newhead = head;
head = tmp;
continue;
}
ListNode *pre = newhead, *p = newhead->next;
while(p != NULL && p->val < head->val)
{
p = p->next;
pre = pre->next;
}
pre->next = head;
head = head->next;
pre = pre->next;
pre->next = p;
}
return newhead;
} };
新建数据类class Val，保存key、val和访问自增标记updatecnt。
用unordered_map更新数据，增加updatecnt，并把更新的数据放入队列，最关键是处理capacity满了的时候，队列依次出队，map中不存在的和updatecnt和最新数据不相等的项目都忽略，直到发现updatecnt和map中存的最新状态相等，则为“最近未使用”数据，出队后在map中erase。思路有点像STL队列实现版本的Dijkstra。
有一个博客的方法更好，map中存的是链表的节点指针，链表顺序表示访问情况，这样就把map内容和链表的每个节点一一对应了，没有冗余节点，且更新操作也是O(1)的。
class Val{
public:
int key;
int val;
int updatecnt;
};
class LRUCache{
public:
int cap;
unordered_map<int, Val> mp;
queue<Val> q;
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
if(mp.count(key))
{
mp[key].updatecnt ++;
q.push(mp[key]);
return mp[key].val;
}
return -;
}
void set(int key, int value) {
if(mp.count(key))
{
mp[key].val = value;
mp[key].updatecnt ++;
q.push(mp[key]);
}
else
{
if(mp.size() == cap)
{
Val tmp;
while(!q.empty())
{
tmp = q.front();
q.pop();
if(mp.count(tmp.key) && tmp.updatecnt == mp[tmp.key].updatecnt)
break;
}
mp.erase(mp.find(tmp.key));
mp[key].key = key;
mp[key].val = value;
mp[key].updatecnt = ;
q.push(mp[key]);
}
mp[key].key = key;
mp[key].val = value;
mp[key].updatecnt = ;
q.push(mp[key]);
}
}
};
Binary Tree Postorder Traversal
二叉树的非递归后序遍历，考研的时候非常熟悉了，现在写又要想好久。重点是关于右子树遍历时候需要一个标记，或者标记根节点出栈次数，或者标记右子树是否访问。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> ans;
if(root == NULL) return ans;
stack<TreeNode*> s;
TreeNode *visited;
while(root != NULL || !s.empty())
{
while(root != NULL)
s.push(root), root = root->left;
root = s.top();
if(root->right == NULL || visited == root->right)
{
ans.push_back(root->val);
s.pop();
visited = root;
root = NULL;
}
else
{
root = root->right;
}
}
return ans;
}
};
Binary Tree Preorder Traversal
前序遍历的非递归就容易多了。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
stack<TreeNode*> s;
vector<int> ans;
if(root == NULL) return ans;
s.push(root);
while(!s.empty())
{
root = s.top();
s.pop();
ans.push_back(root->val);
if(root->right != NULL) s.push(root->right);
if(root->left != NULL) s.push(root->left);
}
}
};
Reorder List
找到中间位置，把中间之后的链表反转，两个指针一个从头一个从尾开始互插，奇偶和指针绕得有点晕，理清就好了。。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode *head) {
int n = ;
ListNode *pre, *p = head;
while(p)
n ++, p = p->next;
if(n < ) return;
n >>= ;
pre = p = head;
p = p->next;
while(n --) p = p->next, pre = pre->next;
while(p != NULL)
{
ListNode *tmp = p->next;
p->next = pre;
pre = p;
p = tmp;
}
ListNode *tail = pre;
p = head;
while(true)
{
ListNode *tmp1 = p->next, *tmp2 = tail->next;
p->next = tail;
tail->next = tmp1;
p = 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 + pm; (1)
2*n = k + t + qm;(2)
这里p和q是任意整数。（不过fast速度是slow二倍，则肯定在一圈内追上，p就是0了）
2 * (1) - (2) 得k = lm - t;(l = q - 2 * p)
即 k 的长度是若干圈少了 t 的长度。
因此这时候，一个指针从head开始，另一个从相遇位置开始，都每次只走一步，当从head开始的指针走到圈开始位置时，两指针刚好相遇。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == NULL) return NULL;
ListNode *slow, *fast;
slow = fast = head;
int n = ;
do
{
n ++;
if(slow == NULL || fast == NULL) return NULL;
slow = slow->next;
fast = fast->next;
if(fast == NULL) return NULL;
fast = fast->next;
if(fast == NULL) return NULL;
}while(slow != fast);
fast = head;
while(slow != fast)
slow = slow->next, fast = fast->next;
return fast;
}
};
Linked List Cycle
呃，时间逆序做的结果。。。成买一送一了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL) return false;
ListNode *slow, *fast;
slow = fast = head;
int n = ;
do
{
n ++;
if(slow == NULL || fast == NULL) return NULL;
slow = slow->next;
fast = fast->next;
if(fast == NULL) return NULL;
fast = fast->next;
if(fast == NULL) return NULL;
}while(slow != fast);
return true;
}
};
Word Break II
先递推，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过去就得到了所有串。
class Solution {
public:
vector<string> DFS(const string &s, vector<int> *site, int ith)
{
vector<string> res;
for(int i = ; i < site[ith].size(); i ++)
{
vector<string> tmp;
string str = s.substr(site[ith][i], ith - site[ith][i]);
if(site[site[ith][i]].size() == )
res.push_back(str);
else
{
tmp = DFS(s, site, site[ith][i]);
for(int j = ; j < tmp.size(); j ++)
res.push_back(tmp[j] + " " + str);
}
}
return res;
}
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<int> *site = new vector<int>[s.length() + ];
bool *dp = new bool[s.length() + ];
memset(dp, , sizeof(bool) * s.length());
dp[] = true;
for(int i = ; i <= s.length(); i ++)
{
for(int j = ; j < i; 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
参考Word Break II，对于dp标记，当dp[i]为true时候可以停止枚举后面的 j，优化一下常数。
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
bool *dp = new bool[s.length() + ];
memset(dp, , sizeof(bool) * (s.length() + ));
dp[] = true;
for(int i = ; i <= s.length(); i ++)
for(int j = ; j < i; j ++)
{
dp[i] = dp[i] || dp[j] && dict.count(s.substr(j, i - j));
}
return dp[s.length()];
}
};
Copy List with Random Pointer
第一次遍历，把每个节点复制一份放到对应节点的下一个，即组成二倍长的链表：ori1->copy1->ori2->copy2->....
第二次遍历，利用“复制节点总是对应节点的下一个节点”特性，将每个ori->next->random指向ori->random->next，中间判断一下空指针。
第三次遍历，把两个链表拆开，恢复原链表。
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode *p = head, *newhead = NULL, *tmp;
if(p == NULL) return NULL;
while(p != NULL)
{
tmp = new RandomListNode(p->label);
tmp->next = p->next;
p->next = tmp;
p = tmp->next;
}
newhead = head->next;
p = head;
while(p != NULL)
{
tmp = p->next;
tmp->random = p->random == NULL ? NULL : p->random->next;
p = tmp->next;
}
p = head;
while(p != NULL)
{
tmp = p->next;
p->next = tmp->next;
p = tmp->next;
tmp->next = p == NULL ? NULL : p->next;
}
return newhead;
}
};
Single Number II
方法一：设置cnt[32]记录 32个比特位的1的个数，出现3次的数的对应位的1总数为3的倍数，则统计之后每个位对3取模，剩下的位为1的则对应个数为1的那个数。
class Solution {
public:
int singleNumber(int A[], int n) {
int cnt[] = {};
for(int i = ; i < n; i ++)
{
int tmp = A[i];
for(int j = ; j < ; tmp >>= , j ++)
cnt[j] += tmp & ;
}
int ans = ;
for(int i = ; i < ; i ++)
ans |= (cnt[i] % ) << i;
return ans;
}
};
方法二：设置int one, two模拟两位二进制来统计各比特位1次数，每当one和two对应二进制位都为1的时候把one和two都清零，最后剩下的one就是要求的数。
class Solution {
public:
int singleNumber(int A[], int n) {
int one = , two = ;
for(int i = ; i < n; i ++)
{
two |= one & A[i];
one ^= A[i];
int tmp = one & two;
two ^= tmp;
one ^= tmp;
}
return one;
}
};
一路异或过去就可以了。
class Solution {
public:
int singleNumber(int A[], int n) {
int tmp = ;
for(int i = ; i < n; i ++)
tmp ^= A[i];
return tmp;
}
};
Candy
时间复杂度 O(n)的方法还是容易想了，优化为空间复杂度O(1)的话也不难，只是思考代码的时候会有点绕。
上坡一步步来，下坡走个等差数列，波峰位置比较一下上坡时候记录的最大值和下坡求的的最大值，取较大的，具体看代码：
class Solution {
public:
int candy(vector<int> &ratings) {
int cnt = , i, j, start, nownum;
for(i = ; i < ratings.size(); i ++)
{
if(i == || ratings[i] == ratings[i - ])
nownum = ;
else if(ratings[i] > ratings[i - ])
nownum ++;
if(i + < ratings.size() && ratings[i + ] < ratings[i])
{
start = ;
for(j = i + ; j < ratings.size() && ratings[j] < ratings[j - ]; start++, j ++);
if(start > nownum)
cnt += (start + ) * start >> ;
else
cnt += ((start - ) * start >> ) + nownum;
nownum = ;
i = j - ;
}
else
cnt += nownum;
}
return cnt;
}
};
Gas Station
证明题。
一、如果从 i 到 j 的时候理论计算气量刚好为负数，则 i ~ j 的加气站都不可以作为起点。
反证一下，从前往后去掉站，如果去掉的站能增加气，即正数，则结果更糟。如果去掉的站是负数，那么负数如果抵消了之前的正数，则在到 j 之前已经负数了，如果不能抵消之前的正数，那么结果还是更糟。
二、判断是否能成行，一个环的和为非负就可以。
假设环为正， 0 ~ j 刚好为负， j + 1 ~ k 刚好为负数，k + 1 之后为正，则 k + 1 为答案。
也反证一下，k + 1 出发，到gas.size() - 1都为正，则转回来到 j - 1 都会为正。如果到 j 时候为负，则整个环不可能为正，所以到 j 的时候也为正，剩下的一样。这样就能够成功转一圈。
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int i, ans, sum, all;
for(i = ans = sum = all = ; i < gas.size(); i ++)
{
sum += gas[i] - cost[i];
all += gas[i] - cost[i];
if(sum < )
{
sum = ;
ans = i + ;
}
}
return all >= ? ans : -;
}
};
Clone Graph
label是唯一的，递归，用unordered_map标记。
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
unordered_map<int, UndirectedGraphNode *> mp;
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(node == NULL || mp.count(node->label)) return NULL;
UndirectedGraphNode *tmp = new UndirectedGraphNode(node->label);
mp[node->label] = tmp;
for(int i = ; i < node->neighbors.size(); i ++)
{
cloneGraph(node->neighbors[i]);
tmp->neighbors.push_back(mp[node->neighbors[i]->label]);
}
return tmp;
}
};
Palindrome Partitioning II
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的最小值。注意一下边界。
class Solution {
public:
int minCut(string s) {
bool paldp[s.length()][s.length()];
int cutdp[s.length()];
for(int i = ; i < s.length(); i ++)
{
cutdp[i] = 0x3f3f3f3f;
for(int j = i - ; j >= -; j --)
{
if(s.at(j + ) == s.at(i) && (j + >= i - || paldp[j + ][i - ]))
{
paldp[j + ][i] = true;
cutdp[i] = min(cutdp[i], (j >= ? (cutdp[j] + ) : ));
}
else
paldp[j + ][i] = false;
}
}
return cutdp[s.length() - ];
}
};
Palindrome Partitioning
O(n^2)动态规划，paldp[i][j] == true表示 i ~ j 是回文。这里DP的方法是基本的，不再多说。
得到paldp之后，DFS一下就可以了。因为单字符是回文，所以DFS的终点肯定都是解，所以不必利用其他的结构存储答案信息。
class Solution {
public:
vector<vector<string> >res;
vector<string> tmp;
bool **paldp;
void DFS(string s, int ith)
{
if(ith == s.length())
{
res.push_back(tmp);
return;
}
for(int i = ith; i < s.length(); i ++)
{
if(paldp[ith][i])
{
tmp.push_back(s.substr(ith, i - ith + ));
DFS(s, i + );
tmp.pop_back();
}
}
return;
}
vector<vector<string> > partition(string s) {
paldp = new bool*[s.length()];
for(int i = ; i < s.length(); i ++)
paldp[i] = new bool[s.length()];
for(int i = ; i < s.length(); i ++)
for(int j = i; j >= ; j --)
paldp[j][i] = s.at(i) == s.at(j) && (j + >= i - || paldp[j + ][i - ]);
DFS(s, );
return res;
}
};
Surrounded Regions
周围四条边的O做起点搜索替换为第三种符号，再遍历所有符号把O换成X，第三种符号换回O。
class Solution {
public:
typedef pair<int, int> pii;
int dx[] = {, -, , };
int dy[] = {, , , -};
queue<pii> q;
void solve(vector<vector<char> > &board) {
if(board.size() == ) return;
int width = board[].size();
int height = board.size();
for(int i = ; i < width; i ++)
{
if(board[][i] == 'O')
board[][i] = '#', q.push(pair<int, int>(, i));
if(board[height - ][i] == 'O')
board[height - ][i] = '#', q.push(pii(height - , i));
}
for(int i = ; i < height - ; i ++)
{
if(board[i][] == 'O')
board[i][] = '#', q.push(pii(i, ));
if(board[i][width - ] == 'O')
board[i][width - ] = '#', q.push(pii(i, width - ));
}
while(!q.empty())
{
pii now = q.front();
q.pop();
for(int i = ; i < ; i ++)
{
int ty = now.first + dx[i];
int tx = now.second + dy[i];
if(tx >= && tx < width && ty >= && ty < height && board[ty][tx] == 'O')
{
board[ty][tx] = '#';
q.push(pii(ty, tx));
}
}
}
for(int i = ; i < height; i ++)
for(int j = ; j < width; j ++)
{
if(board[i][j] == 'O') board[i][j] = 'X';
else if(board[i][j] == '#') board[i][j] = 'O';
}
}
};
Sum Root to Leaf Numbers
遍历一遍加起来。。。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int ans;
void DFS(TreeNode *now, int tmp)
{
if(now->left == NULL && now->right == NULL)
{
ans += tmp * + now->val;
return;
}
if(now->left != NULL)
{
DFS(now->left, tmp * + now->val);
}
if(now->right != NULL)
{
DFS(now->right, tmp * + now->val);
}
}
int sumNumbers(TreeNode *root) {
if(root == NULL) return ;
ans = ;
DFS(root, );
return ans;
}
};
Longest Consecutive Sequence
方法一：一开始竟然想了并查集，其实绕弯了，多此一举。哈希+并查集，把每个数哈希，枚举每个数看相邻的数在不在数组里，并查集合并，只是并查集的复杂度要比O(1)大一些。
class Solution {
public:
unordered_map<int, int> mp, cnt;
int ans = ;
int fa(int i)
{
i == mp[i] ? i : (mp[i] = fa(mp[i]));
}
int longestConsecutive(vector<int> &num) {
for(int i = ; i < num.size(); i ++)
mp[num[i]] = num[i], cnt[num[i]] = ;
for(int i = ; i < num.size(); i ++)
{
if(mp.count(num[i] + ) && fa(num[i]) != fa(num[i] + ))
{
cnt[fa(num[i] + )] += cnt[fa(num[i])];
ans = max(cnt[fa(num[i] + )], ans);
mp[fa(num[i])] = fa(num[i] + );
}
}
return ans;
}
};
方法二：哈希+枚举相邻数。相邻的数在数组里的话，每个数之多访问一次；相邻的数不在数组里的话，枚举会中断。所以设哈希复杂度为O(1)的话，这个方法是严格的O(n)。
其实这个题的数据挺善良，如果出了2147483647, -2147483648，那还是用long long 稳妥些。
class Solution {
public:
unordered_map<int, bool> vis;
int longestConsecutive(vector<int> &num) {
int ans = ;
for(int i = ; i < num.size(); i ++)
vis[num[i]] = false;
for(int i = ; i < num.size(); i ++)
{
if(vis[num[i]] == false)
{
int cnt = ;
for(int j = num[i]; vis.count(j); j ++, cnt ++)
{
vis[j] = true;
}
for(int j = num[i] - ; vis.count(j); j --, cnt ++)
{
vis[j] = true;
}
ans = max(ans, cnt);
}
}
return ans;
}
};
Word Ladder II
用数组类型的队列，BFS过程中记录pre路径，搜完后迭代回去保存路径。
似乎卡了常数，用queue队列，另外存路径的方法超时了。
想更快就双向广搜吧。让我想起了POJ那个八数码。
class Node
{
public:
string str;
int pace;
int pre;
Node(){}
Node(string s, int pa, int pr)
{
str = s;
pace = pa;
pre = pr;
}
};
class Solution {
public:
vector<vector<string>> ans;
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
vector<Node> q;
q.push_back(Node(end, , -));
unordered_map<string, int> dis;
dis[end] = ;
for(int i = ; i < q.size(); i ++)
{
Node now = q[i];
if(dis.count(start) && now.pace >= dis[start]) break;
for(int j = ; j < now.str.length(); j ++)
{
string tmp = now.str;
for(char c = 'a'; c <= 'z'; c ++)
{
tmp[j] = c;
if((dict.count(tmp) || tmp == start) && (!dis.count(tmp) || dis[tmp] == now.pace + ))
{
dis[tmp] = now.pace + ;
q.push_back(Node(tmp, now.pace + , i));
}
}
}
}
for(int i = q.size() - ; i >= && q[i].pace == dis[start]; i --)
{
if(q[i].str == start)
{
vector<string> tmp;
for(int j = i; j != -; j = q[j].pre)
tmp.push_back(q[j].str);
ans.push_back(tmp);
}
}
return ans;
}
};
Word Ladder
直接BFS。
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
typedef pair<string, int> pii;
unordered_set<string> flag;
queue<pii> q;
q.push(pii(start, ));
while(!q.empty())
{
pii now = q.front();
q.pop();
for(int i = ; i < now.first.length(); i ++)
{
string tmp = now.first;
for(char j = 'a'; j <= 'z'; j ++)
{
tmp[i] = j;
if(tmp == end) return now.second + ;
if(dict.count(tmp) && !flag.count(tmp))
{
q.push(pii(tmp, now.second + ));
flag.insert(tmp);
}
}
}
}
return ;
}
};
做过刘汝佳 白书的人想必都知道ctype.h和isdigit(), isalpha, tolower(), toupper()。
class Solution {
public:
bool valid(char &x)
{
x = tolower(x);
return isdigit(x) || isalpha(x);
}
bool isPalindrome(string s) {
if(s.length() == ) return true;
for(int i = , j = s.length() - ; i < j; i ++, j --)
{
while(!valid(s[i]) && i < s.length()) i ++;
while(!valid(s[j]) && j >= ) j --;
if(i < j && s[i] != s[j]) return false;
}
return true;
}
};
Binary Tree Maximum Path Sum
后续遍历，子问题为子树根节点向叶子节点出发的最大路径和。
即 l = DFS(now->left), r = DFS(now->right)。
此时，ans可能是 now->valid,可能是左边一路上来加上now->valid，可能是右边一路上来，也可能是左边上来经过now再右边一路下去，四种情况。
四种情况更新完ans后，now返回上一层只能是 now->valid或左边一路上来或右边一路上来，三种情况。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int ans;
int DFS(TreeNode *now)
{
if(now == NULL) return ;
int l = max(DFS(now->left), );
int r = max(DFS(now->right), );
ans = max(ans, l + r + now->val);
return max(l + now->val, r + now->val);
}
int maxPathSum(TreeNode *root) {
if(root == NULL) return ;
ans = -0x3f3f3f3f;
DFS(root);
return ans;
}
};
Best Time to Buy and Sell Stock III
前缀pre[i]处理 0 ~ i 买卖一次最优解，后缀suf[i]处理 i ~ prices.size() - 1 买卖一次最优解。
所有位置pre[i] + suf[i]最大值为答案O(n)。
处理最优解的时候是维护前（后）缀prices最小（大）值，与当前prices做差后和前（后）缀最优解比较取最优，O(n)。
总复杂度O(n)。
class Solution {
public:
int maxProfit(vector<int> &prices) {
int ans = ;
vector<int> pre(prices.size()), suf(prices.size());
for(int i = , mtmp = 0x3f3f3f3f; i < prices.size(); i ++)
{
mtmp = i ? min(mtmp, prices[i]) : prices[i];
pre[i] = max(prices[i] - mtmp, i ? pre[i - ] : );
}
for(int i = prices.size() - , mtmp = ; i >= ; i --)
{
mtmp = i != prices.size() - ? max(mtmp, prices[i]) : prices[i];
suf[i] = max(mtmp - prices[i], i != prices.size() - ? suf[i + ] : );
}
for(int i = ; i < prices.size(); i ++)
ans = max(ans, pre[i] + suf[i]);
return ans;
}
};
Best Time to Buy and Sell Stock II
可以买卖多次，把所有上坡差累加即可。
class Solution {
public:
int maxProfit(vector<int> &prices) {
int ans = ;
for(int i = ; i < prices.size(); i ++)
{
if(prices[i] > prices[i - ])
ans += prices[i] - prices[i - ];
}
return ans;
}
};
Best Time to Buy and Sell Stock
维护前（后）缀最小（大）值，和当前prices做差更新答案。
class Solution {
public:
int maxProfit(vector<int> &prices) {
int ans = ;
for(int i = prices.size() - , mtmp = ; i >= ; i --)
{
mtmp = max(mtmp, prices[i]);
ans = max(mtmp - prices[i], ans);
}
return ans;
}
};
Triangle
竟然遇到了ACM递推入门题，想必无数ACMer对这题太熟悉了。
从下往上递推，一维数组滚动更新即可。这里懒省事，直接把原数组改了。
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
for(int i = triangle.size() - ; i >= ; i --)
{
for(int j = ; j < triangle[i].size(); j ++)
triangle[i][j] = min(triangle[i][j] + triangle[i + ][j], triangle[i][j] + triangle[i + ][j + ]);
}
return triangle.size() == ? : triangle[][];
}
};
Pascal's Triangle II
滚动数组递推，从后往前以便不破坏上一层递推数据。
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> ans(rowIndex + , );
ans[] = ;
for(int i = ; i <= rowIndex; i ++)
{
for(int j = i; j >= ; j --)
{
ans[j] = (i == || j == || j == i ? : ans[j] + ans[j - ]);
}
}
return ans;
}
};
Pascal's Triangle
递推。。
class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<vector<int> > v;
for(int i = ; i < numRows; i ++)
{
vector<int> tmp;
for(int j = ; j <= i; j ++)
{
tmp.push_back(i == || j == || j == i ? : v[i - ][j] + v[i - ][j - ]);
}
v.push_back(tmp);
}
return v;
}
};
Populating Next Right Pointers in Each Node II
题目要求空间复杂度O(1)，所以递归、队列等传统方法不应该用。
本题可以利用生成的next指针来横向扫描，即得到一层的next指针之后，可以利用这一层的next指针来给下一层的next指针赋值。
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
TreeLinkNode *findNext(TreeLinkNode *head)
{
while(head != NULL && head->left == NULL && head->right == NULL)
head = head->next;
return head;
}
void connect(TreeLinkNode *root) {
if(root == NULL) return;
TreeLinkNode *head, *last, *nexhead;
for(head = root; head != NULL; head = nexhead)
{
head = findNext(head);
if(head == NULL) break;
if(head->left != NULL) nexhead = head->left;
else nexhead = head->right;
for(last = NULL; head != NULL; last = head, head = findNext(head->next))
{
if(head->left != NULL && head->right != NULL)
head->left->next = head->right;
if(last == NULL) continue;
if(last->right != NULL)
last->right->next = head->left != NULL ? head->left : head->right;
else
last->left->next = head->left != NULL ? head->left : head->right;
}
}
}
};
Populating Next Right Pointers in Each Node
不用考虑连续的空指针，就不用额外实现找下一个子树非空节点，比Populating Next Right Pointers in Each Node II 容易处理。
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root == NULL) return;
TreeLinkNode *head, *nexhead, *last;
for(head = root; head->left != NULL; head = nexhead)
{
nexhead = head->left;
last = NULL;
while(head != NULL)
{
head->left->next = head->right;
if(last != NULL) last->right->next = head->left;
last = head;
head = head->next;
}
}
}
};
Distinct Subsequences
典型动态规划。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]，否则不加。
class Solution {
public:
int numDistinct(string S, string T) {
if(S.length() < T.length()) return ;
vector<vector<int> > dp(S.length() + , vector<int>(T.length() + , ));
for(int i = ; i < S.length(); i ++) dp[i][] = ;
dp[][] = ;
for(int i = ; i < S.length(); i ++)
{
for(int j = ; j < T.length(); j ++)
{
dp[i + ][j + ] = dp[i][j + ];
if(S[i] == T[j]) dp[i + ][j + ] += dp[i][j];
}
}
return dp[S.length()][T.length()];
}
};
Flatten Binary Tree to Linked List
题意是优先左子树靠前，且排成一列用右子树指针，不管val的大小关系。
后序遍历一遍即可，递归返回子树中尾节点指针，注意各种条件判断。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *DFS(TreeNode *now)
{
if(now->left == NULL && now->right == NULL) return now;
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->right;
now->right = now->left;
now->left = NULL;
return rightok ? rightok : leftok;
}
else return rightok;
}
void flatten(TreeNode *root) {
if(root == NULL) return;
DFS(root);
}
};
传统递归，把路径上的数字插入vector，终点判断是否插入答案。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int goal;
vector<vector<int> >v;
vector<int> curv;
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();
return;
}
}
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) {
goal = sum;
if(root == NULL) return v;
DFS(root, );
return v;
}
};
Path Sum
遍历树。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int goal;
bool DFS(TreeNode *now, int cursum)
{
if(now->left == NULL && now->right == NULL)
return cursum + now->val == goal;
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) {
goal = sum;
if(root == NULL) return false;
return DFS(root, );
}
};
还是遍历。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode *root) {
if(root == NULL) return ;
if(root->left == NULL) return minDepth(root->right) + ;
else if(root->right == NULL) return minDepth(root->left) + ;
else return min(minDepth(root->left), minDepth(root->right)) + ;
}
};
遍历。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode *now)
{
if(now == NULL) return ;
int l = maxDepth(now->left) + ;
int r = maxDepth(now->right) + ;
return abs(l - r) > || l < || r < ? - : max(l, r);
}
bool isBalanced(TreeNode *root) {
return maxDepth(root) >= ;
}
};
Convert Sorted List to Binary Search Tree
每次找中点作为根节点，将两边递归，返回根节点指针作为左右节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
if(head == NULL) return NULL;
ListNode *p, *mid, *pre;
for(p = mid = head, pre = NULL; p->next != NULL; mid = mid->next)
{
p = p->next;
if(p->next == NULL) break;
p = p->next;
pre = mid;
};
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 = mid;
return root;
}
};
Convert Sorted Array to Binary Search Tree
递归做，比链表的容易些。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *convert(vector<int> &num, int left, int right)
{
if(right == left) return NULL;
int mid = right + left >> ;
TreeNode *root = new TreeNode(num[mid]);
root->left = convert(num, left, mid);
root->right = convert(num, mid + , right);
}
TreeNode *sortedArrayToBST(vector<int> &num) {
return convert(num, , num.size());
}
};
Binary Tree Level Order Traversal II
宽搜和深搜都可以，找对层数就行了。
本以为这题亮点是如何一遍实现从底向上顺序的vector，AC之后上网一查也全是最后把vector翻转的。。。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int> >v;
void DFS(TreeNode *now, int depth)
{
if(v.size() <= depth) v.push_back(vector<int>());
v[depth].push_back(now->val);
if(now->left != NULL) DFS(now->left, depth + );
if(now->right != NULL) DFS(now->right, depth + );
}
vector<vector<int> > levelOrderBottom(TreeNode *root) {
if(root == NULL) return v;
DFS(root, );
for(int i = , j = v.size() - ; i < j; i ++, j --)
swap(v[i], v[j]);
return v;
}
};
Construct Binary Tree from Inorder and Postorder Traversal
数据结构经典题。后序遍历的结尾是根节点 Proot，在中序遍历中找到这个节点 Iroot，则 Iroot两边即为左右子树。根据左右子树节点个数，在后序遍历中找到左右子树分界（左右子树肯定不交叉），则几个关键分界点都找到了，对左右子树递归。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *build(vector<int> &inorder, int ileft, int iright, vector<int> &postorder, int pleft, int pright)
{
if(iright == ileft)
return NULL;
int root;
for(root = ileft; inorder[root] != postorder[pright - ]; root ++);
TreeNode *node = new TreeNode(inorder[root]);
node->left = build(inorder, ileft, root, postorder, pleft, pleft + root - ileft);
node->right = build(inorder, root + , iright, postorder, pleft + root - ileft, pright - );
return node;
}
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
return build(inorder, , inorder.size(), postorder, , postorder.size());
}
};
Construct Binary Tree from Preorder and Inorder Traversal
和上一题Construct Binary Tree from Inorder and Postorder Traversal方法一样，前序和后序的信息作用相同。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *build(vector<int> &inorder, int ileft, int iright, vector<int> &preorder, int pleft, int pright)
{
if(iright == ileft)
return NULL;
int root;
for(root = ileft; inorder[root] != preorder[pleft]; root ++);
TreeNode *node = new TreeNode(inorder[root]);
node->left = build(inorder, ileft, root, preorder, pleft + , pleft + root - ileft);
node->right = build(inorder, root + , iright, preorder, pleft + root - ileft + , pright);
return node;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
return build(inorder, , inorder.size(), preorder, , preorder.size()); }
};
遍历。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode *root) {
if(root == NULL) return ;
if(root->left == NULL) return maxDepth(root->right) + ;
if(root->right == NULL) return maxDepth(root->left) + ;
return max(maxDepth(root->left), maxDepth(root->right)) + ;
}
};
Binary Tree Zigzag Level Order Traversal
BFS，奇偶层轮流走，一层左到右，一层右到左。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int> > ans;
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
if(root == NULL) return ans;
vector<TreeNode*> q1, q2;
q1.push_back(root);
int depth = ;
while(!q1.empty() || !q2.empty())
{
ans.push_back(vector<int>());
for(int i = q1.size() - ; i >= ; 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);
}
depth ++;
q1.clear();
if(q2.empty()) continue;
ans.push_back(vector<int>());
for(int i = q2.size() - ; i >= ; 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();
depth ++;
}
return ans;
}
};
Binary Tree Level Order Traversal
懒省事直接在上一题Binary Tree Zigzag Level Order Traversal的代码上改了一下。
只用一个队列的话，增加个层数信息存队列里即可。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int> > ans;
vector<vector<int> > levelOrder(TreeNode *root) {
if(root == NULL) return ans;
vector<TreeNode*> q1, q2;
q1.push_back(root);
int depth = ;
while(!q1.empty() || !q2.empty())
{
ans.push_back(vector<int>());
for(int i = ; 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);
}
depth ++;
q1.clear();
if(q2.empty()) continue;
ans.push_back(vector<int>());
for(int i = ; 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();
depth ++;
}
return ans;
}
};
Symmetric Tree
递归：左指针和右指针，对称递归，即“左的左”和“右的右”对应，“左的右”和“右的左”对应。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
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 {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
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();
q1.pop();
q2.pop();
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;
}
};
Same Tree
同步遍历，比较判断。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
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 {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *a, *b;
TreeNode *ans1, *ans2;
bool DFS(TreeNode *now)
{
if(now->left != NULL)
DFS(now->left);
a = b;
b = now;
if(a != NULL && a->val > b->val)
{
if(ans1 == NULL) ans1 = a;
ans2 = b;
}
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);
}
};
Validate Binary Search Tree
中序遍历，更新前驱节点，与当前节点比较。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
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;
pre = root;
if(root->right != NULL && !isValidBST(root->right)) return false;
return true;
}
};
Interleaving String
动态规划。如果结果是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)的解法，我也就放心了。。。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s1.length() + s2.length() != s3.length()) return false;
vector<vector<bool> > dp(s1.length() + , vector<bool>(s2.length() + , false));
for(int i = ; i <= s1.length(); i ++)
for(int j = ; j <= s2.length(); j ++)
{
if(!i && !j) dp[i][j] = true;
dp[i][j] = dp[i][j] || i > && s3[i + j - ] == s1[i - ] && dp[i - ][j];
dp[i][j] = dp[i][j] || j > && s3[i + j - ] == s2[j - ] && dp[i][j - ];
}
return dp[s1.length()][s2.length()];
}
};
Unique Binary Search Trees II
LeetCode目前为止感觉最暴力的。递归遍历所有情况，每次返回子问题（左右子树）的vector<TreeNode *>的解，两层循环组合这些解。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode *> generate(int start, int end)
{
vector<TreeNode *>res;
if(start > end)
{
TreeNode *tmp = NULL;
res.push_back(tmp);
return res;
}
for(int i = start; i <= end; i ++)
{
vector<TreeNode *> l = generate(start, i - ), r = generate(i + , end);
for(int j = ; j < l.size(); j ++)
for(int k = ; k < r.size(); k ++)
{
TreeNode *tmp = new TreeNode(i);
tmp->left = l[j];
tmp->right = r[k];
res.push_back(tmp);
}
}
return res;
}
vector<TreeNode *> generateTrees(int n) {
return generate(, n);
}
};
Unique Binary Search Trees
经典问题，卡特兰数，可递推，可用公式（公式用组合数，也要写循环）。
class Solution {
public:
int COM(int n, int m)
{
m = n - m < m ? n - m : m;
int res, i, j;
for(i = n, res = j = ; i > n - m; i --)
{
res *= i;
for(; j <= m && res % j == ; j ++)
res /= j;
}
return res;
}
int numTrees(int n) {
return COM(n << , n) / (n + );
}
};
Binary Tree Inorder Traversal
数据结构基础
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> res;
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);
return res;
}
};
Restore IP Addresses
四层递归枚举分割位置，判断数字范围和前导零，处理字符串。
class Solution {
public:
vector<string> res;
void DFS(string s, int last, int cur, string now)
{
if(cur == )
{
if(last == s.length()) return;
string tmp = s.substr(last, s.length() - last);
if(atoi(tmp.c_str()) <= && (tmp.length() == || tmp[] != ''))
res.push_back(now + tmp);
return;
}
string lin;
for(int i = last; i < s.length(); i ++)
{
string tmp = s.substr(last, i - last + );
if(atoi(tmp.c_str()) <= && (tmp.length() == || tmp[] != ''))
DFS(s, i + , cur + , now + tmp + ".");
}
}
vector<string> restoreIpAddresses(string s) {
DFS(s, , , "");
return res;
}
};
Reverse Linked List II
在表头添加一个“哨兵”会好写很多，额外的newhead可以帮助标记翻转之后更换了的头指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode *newhead = new ListNode();
newhead->next = head;
ListNode *pre = newhead, *p = head, *start = NULL;
ListNode *tmp;
for(int i = ; p != NULL; i ++)
{
tmp = p->next;
if(i == m)
start = pre;
if(i > m && i <= n)
p->next = pre;
if(i == n)
{
start->next->next = tmp;
start->next = p;
}
pre = p;
p = tmp;
}
tmp = newhead->next;
free(newhead);
return tmp;
}
};
Subsets II
统计地存map里，map[i]= j 表示 S 中有 j 个 i。map是有序的，用迭代器递归枚举放入集合的个数。
也可以先排序，用set标记每个数时候被放入过，第一次放入之后才可以继续放同一个数。
代码是用map的方法。
class Solution {
public:
vector<vector<int> > res;
vector<int> now;
map<int, int> mp;
void DFS(map<int, int>::iterator i)
{
if(i == mp.end())
{
res.push_back(now);
return;
}
map<int, int>::iterator tmp = i;
i ++;
DFS(i);
for(int j = ; j < tmp->second; j ++)
{
now.push_back(tmp->first);
DFS(i);
}
for(int j = ; j < tmp->second; j ++)
now.pop_back();
}
vector<vector<int> > subsetsWithDup(vector<int> &S) {
for(int i = ; i < S.size(); i ++)
!mp.count(S[i]) ? (mp[S[i]] = ) : mp[S[i]] ++;
DFS(mp.begin());
return res;
}
};
Decode Ways
递推：dp[i]表示前 i 个数字的解码种数。
dp[i] = if(一)dp[i-1] + if(二)dp[i-2]
当 i 位置不为0，可加上 i - 1 位置的解。当当前位置和前一位置组成的两位数满足解码且高位不为0，可加上 i - 2 位置的解。
class Solution {
public:
int numDecodings(string s) {
if(s.length() == ) return ;
vector<int> dp(s.length() + , );
dp[] = ;
for(int i = ; i < s.length(); i ++)
{
dp[i + ] = (s[i] != '' ? dp[i] : ) +
(i > && s[i - ] != '' && atoi(s.substr(i - , ).c_str()) <= ? dp[i - ] : );
}
return dp[s.length()];
}
};
Gray Code
格雷码有多种生成方法，可参考*。
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res;
for(int i = ; i < ( << n); i ++)
res.push_back((i >> ) ^ i);
return res;
}
};
Merge Sorted Array
从后往前，对 A 来说一个萝卜一个坑，肯定不会破坏前面的数据。具体看代码。
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int p = m + n - , i = m - , j = n - ;
for(; i >= && j >= ;)
{
if(A[i] > B[j]) A[p --] = A[i --];
else A[p --] = B[j --];
}
while(i >= ) A[p --] = A[i --];
while(j >= ) A[p --] = B[j --];
}
};
Scramble String
直接搜索可以过，记忆化搜索可提高效率。
dp[i][j][k]表示从 s1[i] 和 s2[j] 开始长度为 k 的字符串是否是scrambled string。
枚举分割位置，scrambled string要求字符串对应字母的个数是一致的，可以直接排序对比。递归终点是刚好只有一个字母。
class Solution {
public:
string S1, S2;
vector<vector<vector<int> > > dp;
bool judge(string a, string b)
{
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for(int i = ; 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 - ];
if(len == ) return ans = S1[s1start] == S2[s2start];
if(ans != -) return ans;
if(!judge(S1.substr(s1start, len), S2.substr(s2start, len))) return ans = ;
ans = ;
for(int i = ; i < len; i ++)
{
ans = ans
|| DFS(s1start, s2start, i) && DFS(s1start + i, s2start + i, len - i)
|| DFS(s1start, s2start + len - i, i) && DFS(s1start + i, s2start, len - i);
}
return ans;
}
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(), -)));
return DFS(, , s1.length());
}
};
Partition List
分存大小最后合并。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *shead, *bhead, *smaller, *bigger, *p;
for(shead = bhead = smaller = bigger = NULL, p = head; p != NULL; p = p->next)
{
if(p->val < x)
{
if(shead == NULL)
shead = p;
if(smaller != NULL)
smaller->next = p;
smaller = p;
}
else
{
if(bhead == NULL)
bhead = p;
if(bigger != NULL)
bigger->next = p;
bigger = p;
}
}
if(smaller != NULL) smaller->next = bhead;
if(bigger != NULL) bigger->next = NULL;
return shead != NULL ? shead : bhead;
}
};
Maximal Rectangle
方法一：linecnt[i][j]统计第 i 行到第 j 位置有多少个连续的 '1'，接下来枚举列，每一列相当于一次直方图最大矩形统计，计算每个位置向前和向后最远的不少于当前位置值的位置，每次更新结果，总复杂度O(n^2)。
找“最远位置”用迭代指针，理论复杂度略高于O(n)。
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.size() == ) return ;
int H = matrix.size(), W = matrix[].size();
int ans = ;
vector<int> left(H), right(H);
vector<vector<int> > linecnt(H, vector<int>(W, ));
for(int i = ; i < H; i ++)
{
int last = ;
for(int j = ; j < W; j ++)
{
if(matrix[i][j] == '') last ++;
else last = ;
linecnt[i][j] = last;
}
}
for(int k = ; k < W; k ++)
{
for(int i = ; i < H; i ++)
{
if(i == ) left[i] = -;
else
{
left[i] = i - ;
while(left[i] > - && linecnt[left[i]][k] >= linecnt[i][k])
left[i] = left[left[i]];
}
}
for(int i = H - ; i >= ; i --)
{
if(i == H - ) right[i] = H;
else
{
right[i] = i + ;
while(right[i] < H && linecnt[right[i]][k] >= linecnt[i][k])
right[i] = right[right[i]];
}
ans = max(ans, (right[i] - left[i] - ) * linecnt[i][k]);
}
}
return ans;
}
};
用单调栈，理论复杂度O(n)。
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.size() == ) return ;
vector<vector<int> > linecnt(matrix.size(), vector<int>(matrix[].size(), ));
for(int i = ; i < matrix.size(); i ++)
{
int last = ;
for(int j = ; j < matrix[].size(); j ++)
{
if(matrix[i][j] == '') last ++;
else last = ;
linecnt[i][j] = last;
}
}
int ans = ;
for(int k = ; k < matrix[].size(); k ++)
{
stack<int> s, site;
vector<int>last(matrix.size());
for(int i = ; i < matrix.size(); i ++)
{
while(!s.empty() && s.top() >= linecnt[i][k])
s.pop(), site.pop();
if(!s.empty()) last[i] = site.top() + ;
else last[i] = ;
s.push(linecnt[i][k]);
site.push(i);
}
while(!s.empty()) s.pop(), site.pop();
for(int i = matrix.size() - ; i >= ; 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);
}
}
return ans;
}
};
方法二：每个 '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;
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.size() == ) return ;
int H = matrix.size(), W = matrix[].size();
vector<int> left(W, -), right(W, W), height(W, );
int ans = ;
for(int i = ; i < H; i ++)
{
int last = -;
for(int j = ; j < W; j ++)
{
if(matrix[i][j] == '')
{
if(last == -) last = j;
left[j] = max(left[j], last);
height[j] ++;
}
else
{
last = -;
left[j] = -;
height[j] = ;
}
}
last = -;
for(int j = W - ; j >= ; j --)
{
if(matrix[i][j] == '')
{
if(last == -) last = j;
right[j] = min(right[j], last);
ans = max(ans, height[j] * (right[j] - left[j] + ));
}
else
{
last = -;
right[j] = W;
}
}
}
return ans;
}
};
Largest Rectangle in Histogram
参考上一题Maximal Rectangle方法一。
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
if(height.size() == ) return ;
vector<int> left(height.size()), right(height.size());
int ans = ;
for(int i = ; i < height.size(); i ++)
{
if(i == ) left[i] = -;
else
{
left[i] = i - ;
while(left[i] > - && height[i] <= height[left[i]])
left[i] = left[left[i]];
}
}
for(int i = height.size() - ; i >= ; i --)
{
if(i == height.size() - ) right[i] = height.size();
else
{
right[i] = i + ;
while(right[i] < height.size() && height[i] <= height[right[i]])
right[i] = right[right[i]];
}
ans = max(ans, (right[i] - left[i] - ) * height[i]);
}
return ans;
}
};
Remove Duplicates from Sorted List II
加个表头乱搞吧。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if(head == NULL || head->next == NULL) return head;
ListNode *newhead = new ListNode();
newhead->next = head;
for(ListNode *pre = newhead, *now = head, *nex = head->next; nex != NULL;)
{
if(now->val == nex->val)
{
while(nex != NULL && now->val == nex->val)
{
free(now);
now = nex;
nex = nex->next;
}
free(now);
pre->next = nex;
if(nex == NULL) break;
}
else pre = now;
now = nex;
nex = nex->next;
}
head = newhead->next;
free(newhead);
return head;
}
};
Remove Duplicates from Sorted List
直接操作。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if(head == NULL || head->next == NULL) return head;
for(ListNode *pre = head, *p = head->next; p != NULL;)
{
while(p != NULL && pre->val == p->val)
{
pre->next = p->next;
free(p);
p = pre->next;
}
if(p == NULL) break;
pre = p;
p = p->next;
}
return head;
}
};
Search in Rotated Sorted Array II
以mid为界，左右两边至少有一边是有序的。由于不可避免地会有O(n)的可能性，所以确定的时候二分，不确定的时候单位缩减边界。
class Solution {
public:
bool search(int A[], int n, int target) {
int left = , right = n - , mid;
while(left < right)
{
mid = left + right >> ;
if(target < A[mid] && A[left] < target) right = mid;
else if(target < A[right] && A[mid] < target) left = mid + ;
else
{
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;
}
};
Remove Duplicates from Sorted Array II
记下放了几个，多了不放。
class Solution {
public:
int removeDuplicates(int A[], int n) {
int i, j, cnt;
for(i = j = cnt = ; i < n; i ++)
{
if(j != && A[j - ] == A[i]) cnt ++;
else cnt = ;
if(cnt < ) A[j ++] = A[i];
}
return j;
}
};
基础DFS。
class Solution {
public:
int dx[] = {, -, , };
int dy[] = {, , , -};
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() - ) return true;
board[x][y] = '.';
for(int i = ; i < ; i ++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= && ny >= && nx < board.size() && ny < board[].size())
{
if(DFS(nx, ny, board, word, ith + ))
{
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 = ; i < board.size(); i ++)
{
for(int j = ; j < board[].size(); j ++)
{
if(DFS(i, j, board, word, )) return true;
}
}
return false;
}
};
Subsets
基础DFS。
class Solution {
public:
vector<int> now;
vector<vector<int> > res;
void DFS(vector<int> &S, int ith)
{
if(ith == S.size())
{
res.push_back(now);
return;
}
DFS(S, ith + );
now.push_back(S[ith]);
DFS(S, ith + );
now.pop_back();
}
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end());
DFS(S, );
return res;
}
};
Combinations
基础DFS。
class Solution {
public:
vector<int> now;
vector<vector<int> > res;
void DFS(int n, int ith, int sum, int k)
{
if(sum == k)
{
res.push_back(now);
return;
}
if(sum + n - ith + > k)
{
DFS(n, ith + , sum, k);
}
now.push_back(ith);
DFS(n, ith + , sum + , k);
now.pop_back();
}
vector<vector<int> > combine(int n, int k) {
DFS(n, , , k);
return res;
}
};
Minimum Window Substring
先统计 T 中各字符都有多少个，然后两个下标一前(i)一后(j)在 S 上跑， 当 i 跑到把 T 中字符都包含的位置时候，让 j 追到第一个包含 T 的字符的地方，更新结果，去掉 j 这个位置字符的统计，让 i 继续跑，如此反复。
i 和 j 都只遍历一遍 S，复杂度 O(n)。
class Solution {
public:
string minWindow(string S, string T) {
vector<int> cnt(, ), need(, );
int sum = , len = 0x3f3f3f3f;
string ans;
for(int i = ; i < T.size(); i ++)
need[T[i]] ++;
for(int i = , j = ; i < S.length(); j ++)
{
while(i < S.length() && sum < T.length())
{
if(cnt[S[i]] < need[S[i]])
sum ++;
cnt[S[i]] ++;
i ++;
}
while(sum == T.length() && j < S.length())
{
cnt[S[j]] --;
if(cnt[S[j]] < need[S[j]])
break;
j ++;
}
if(sum < T.length()) break;
if(i - j < len)
ans = S.substr(j, i - j), len = i - j;
sum --;
}
return ans;
}
};
轮流找：
class Solution {
public:
void sortColors(int A[], int n) {
int find = ;
for(int i = , j = n - ; i < n; 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 - , find ++;
}
}
};
找到哪个放哪个：
class Solution {
public:
void sortColors(int A[], int n) {
int p0, p1, p2;
for(p0 = , p1 = p2 = n - ; p0 < p1; )
{
if(A[p0] == ) p0 ++;
if(A[p0] == ) swap(A[p0], A[p1 --]);
if(A[p0] == )
{
swap(A[p0], A[p2 --]);
p1 = p2;
}
}
}
};
Search a 2D Matrix
写两个二分查找。或者把整个矩阵看作一维，直接二分，换算坐标。
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int left, right, mid;
for(left = , right = matrix.size(); left < right - ; )
{
mid = left + right >> ;
if(matrix[mid][] > target) right = mid;
else left = mid;
}
if(left == matrix.size() || right == ) return false;
vector<int> &a = matrix[left];
for(left = , right = a.size(); left < right - ;)
{
mid = left + right >> ;
if(a[mid] > target) right = mid;
else left = mid;
}
if(left == a.size() || right == ) return false;
return a[left] == target;
}
};
Set Matrix Zeroes
O(m+n)的方法是容易想到的，而空间复杂度O(1)，只要利用原矩阵的一行和一列来使用O(m+n)的方法就行了。
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
if(matrix.size() == ) return;
int x = -, y = -;
for(int i = ; i < matrix.size(); i ++)
{
for(int j = ; j < matrix[].size(); j ++)
{
if(matrix[i][j] == )
{
if(x == -)
{
x = i, y = j;
}
else
{
matrix[x][j] = ;
matrix[i][y] = ;
}
}
}
}
if(x == -) return;
for(int i = ; i < matrix.size(); i ++)
for(int j = ; j < matrix[].size(); j ++)
if((matrix[x][j] == || matrix[i][y] == ) && (i != x && j != y)) matrix[i][j] = ;
for(int i = ; i < matrix.size(); i ++) matrix[i][y] = ;
for(int j = ; j < matrix[].size(); j ++) matrix[x][j] = ;
}
};
Edit Distance
动态规划，先初始化 dp[i][0] 和 dp[0][i]，即每个字符串对应空串的编辑距离为串长度，之后对每个位置取子问题加上当前位置 改、删、增得解的最小值。
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int> > dp(word1.length() + , vector<int>(word2.length() + , ));
for(int i = ; i < word1.length(); i ++) dp[i + ][] = i + ;
for(int i = ; i < word2.length(); i ++) dp[][i + ] = i + ;
for(int i = ; i < word1.length(); i ++)
for(int j = ; j < word2.length(); j ++)
{
if(word1[i] != word2[j])
dp[i + ][j + ] = min(dp[i][j] + , min(dp[i][j + ] + , dp[i + ][j] + ));
else
dp[i + ][j + ] = min(dp[i][j], min(dp[i][j + ] + , dp[i + ][j] + ));
}
return dp[word1.length()][word2.length()];
}
};
Simplify Path
好烦人的题，没什么好说的。
class Solution {
public:
string simplifyPath(string path) {
stack<string> s;
string str;
for(int i = ; i < path.length(); i ++)
{
if(path[i] == '/')
{
if(str == "..")
{
if(!s.empty())
s.pop();
}
else if(str != "." && str != "")
s.push(str);
str.clear();
}
else
str += path[i];
}
if(str == "..")
{
if(!s.empty())
s.pop();
}
else if(str != "." && str != "")
s.push(str);
if(s.empty()) return "/";
for(str.clear(); !s.empty(); s.pop())
str = "/" + s.top() + str;
return str;
}
};
Climbing Stairs
递推，就是斐波那契数列。
class Solution {
public:
int climbStairs(int n) {
return (int)
(pow((+sqrt())/, n + ) / sqrt() -
pow((-sqrt())/, n + ) / sqrt() + 0.1);
}
};
Sqrt(x)
牛顿迭代。
设输入为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，越推越精确，直到自己想要的精度。
class Solution {
public:
int sqrt(int x) {
double now, last;
if(x == ) return ;
for(now = last = (double)x; ; last = now)
{
now = (last + (x / last)) * 0.5;
if(fabs(last - now) < 1e-) break;
}
return (int)(now + 1e-);
}
};
Text Justification
每行限制长度，空格均匀插入，不能完全平均的情况下优先靠前的单词间隔。
最后一行特别处理，单词间只有一个空格，剩下的放在末尾。
class Solution {
public:
vector<string> fullJustify(vector<string> &words, int L) {
vector<string> ans;
int cnt = , i, j, k, l;
for(i = , j = ; j < words.size(); i ++)
{
if(i < words.size())
{
cnt += words[i].length();
if(i == j) continue;
}
if(i == words.size() || (L - cnt) / (i - j) < )
{
int blank = ;
if(i < words.size()) blank = (i - j - ) ? (L - cnt + words[i].length()) / (i - j - ) : ;
string tmp = "";
l = i < words.size() ? (L - cnt + words[i].length() - blank * (i - j - )) : ;
for(k = j; k < i; k ++, l --)
{
tmp += words[k];
if(k != i - )
{
if(i != words.size())
{
for(int bl = ; bl < blank; bl ++) tmp += " ";
if(l > ) tmp += " ";
}
else
tmp += " ";
}
}
while(tmp.length() < L) tmp += " ";
ans.push_back(tmp);
cnt = ;
j = i;
i --;
}
}
return ans;
}
};
Plus One
大整数加法。
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
int cur, i;
if(digits.size() == ) return digits;
for(i = digits.size() - , cur = ; i >= ; i --)
{
int tmp = digits[i] + cur;
cur = tmp / ;
digits[i] = tmp % ;
}
if(cur) digits.insert(digits.begin(), cur);
return digits;
}
};
Valid Number
用DFA也不麻烦，题目定义太模糊，为了理解规则错很多次也没办法。
class Solution {
public:
int f[][];
const int fail = -; //非法
const int st = ; //起始
const int pn = ; //正负号
const int di = ; //整数部分
const int del = ; //前面无数字小数点
const int ddi = ; //小数部分
const int ndel = ; //前面有数字小数点
const int dibl = ; //数后空格
const int ex = ; //进入指数
const int epn = ; //指数符号
const int edi = ; //指数数字
const int end = ; //正确结束
void buildDFA()
{
memset(f, -, sizeof(f));
f[st][' '] = st;
f[st]['+'] = f[st]['-'] = pn;
for(int i = ''; i <= ''; i ++)
{
f[st][i] = f[pn][i] = f[di][i] = di;
f[del][i] = f[ndel][i] = f[ddi][i] = ddi;
f[ex][i] = f[epn][i] = f[edi][i] = edi;
}
f[di]['.'] = ndel;
f[st]['.'] = f[pn]['.'] = del;
f[di][' '] = f[ndel][' '] = f[ddi][' '] = f[dibl][' '] = f[edi][' '] = dibl;
f[di][] = f[ndel][] = f[dibl][] = f[ddi][] = f[edi][] = end;
f[di]['e'] = f[ndel]['e'] = f[ddi]['e'] = ex;
f[ex][' '] = ex;
f[ex]['+'] = f[ex]['-'] = epn;
}
bool DFA(const char *s)
{
int situ = st;
for(int i = ;; 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);
}
};
翻转，大整数加法，再翻转。无心情优化。
class Solution {
public:
string addBinary(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string c;
int cur = , i;
for(i = ; i < min(a.length(), b.length()); i ++)
{
int tmp = a[i] - '' + b[i] - '' + cur;
cur = tmp >> ;
c += (tmp & ) + '';
}
string &t = a.length() > b.length() ? a : b;
for(; i < t.length(); i ++)
{
int tmp = t[i] - '' + cur;
cur = tmp >> ;
c += (tmp & ) + '';
}
if(cur) c += '';
reverse(c.begin(), c.end());
return c;
}
};
归并排序的一次操作，设个哨兵头结点，结束后free。
/**
* 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 *thead = new ListNode(), *p = thead;
while(l1 != NULL && l2 != NULL)
{
if(l1->val < l2->val) p->next = l1, p = l1, l1 = l1->next;
else p->next = l2, p = l2, l2 = l2->next;
}
while(l1 != NULL) p->next = l1, p = l1, l1 = l1->next;
while(l2 != NULL) p->next = l2, p = l2, l2 = l2->next;
p = thead->next;
free(thead);
return p;
}
};
递推
class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
if(grid.size() == ) return ;
for(int i = ; i < grid.size(); i ++)
{
for(int j = ; j < grid[].size(); j ++)
{
int tmp = 0x3f3f3f3f;
if(i > ) tmp = min(tmp, grid[i][j] + grid[i - ][j]);
if(j > ) tmp = min(tmp, grid[i][j] + grid[i][j - ]);
grid[i][j] = tmp == 0x3f3f3f3f ? grid[i][j] : tmp;
}
}
return grid[grid.size() - ][grid[].size() - ];
}
};
Unique Paths II
递推
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
if(obstacleGrid.size() == ) return ;
obstacleGrid[][] = obstacleGrid[][] != ;
for(int i = ; i < obstacleGrid.size(); i ++)
for(int j = ; j < obstacleGrid[].size(); j ++)
{
if(i == && j == ) continue;
if(obstacleGrid[i][j] == )
{
obstacleGrid[i][j] = ;
continue;
}
if(i > ) obstacleGrid[i][j] += obstacleGrid[i - ][j];
if(j > ) obstacleGrid[i][j] += obstacleGrid[i][j - ];
}
return obstacleGrid[obstacleGrid.size() - ][obstacleGrid[].size() - ];
}
};
这是当年学组合数时候的经典题型吧。
class Solution {
public:
int COM(int a, int b)
{
b = min(b, a - b);
int ret = , i, j;
for(i = a, j = ; i > a - b; i --)
{
ret *= i;
for(; j <= b && ret % j == ; j ++)
ret /= j;
}
return ret;
}
int uniquePaths(int m, int n) {
return COM(m + n - , m - );
}
};
Rotate List
因为k可能比长度大，需要求长度然后k对长度取模。那么就不要矫情地追求双指针一遍扫描了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if(head == NULL) return NULL;
int cnt;
ListNode *en, *p;
for(cnt = , en = head; en->next != NULL; cnt ++, en = en->next);
k %= cnt;
for(p = head, cnt --; cnt != k; cnt --, p = p->next);
en->next = head;
en = p->next;
p->next = NULL;
return en;
}
};
Permutation Sequence
一位一位算，每一位优先没使用过的较小的数字，而其后剩下的m个位置有 m! 种排列方法，用 k 减去，直到k不大于这个方法数，则这一位就是枚举到的这个数。
class Solution {
public:
int permu[];
bool vis[];
string getPermutation(int n, int k) {
permu[] = ;
for(int i = ; i < ; i ++) permu[i] = permu[i - ] * i;
memset(vis, , sizeof(vis));
string ans;
for(int i = ; i <= n; i ++)
{
for(int j = ; j <= n; j ++)
{
if(!vis[j])
{
if(k > permu[n - i]) k -= permu[n - i];
else {ans += '' + j; vis[j] = true; break;}
}
}
}
return ans;
}
};
Spiral Matrix II
直接算每个位置的数是多少有木有很霸气
先看当前位置之外有几个嵌套的正方形，再看当前位置在当前正方形四条边的第几条，求出坐标(x,y)位置的数。
class Solution {
public:
vector<vector<int> > res;
vector<int> nsq;
int calnum(int i, int j, int n)
{
int num, tmp;
tmp = min(min(i, j), min(n - - i, n - - j));
num = nsq[tmp];
if(i == tmp) return num + j - tmp + ;
if(n - j - == tmp) return num + n - * tmp + i - tmp;
if(n - i - == tmp) return num + * (n - * tmp) - + n - j - tmp;
return num + * (n - * tmp) - + n - i - tmp;
}
vector<vector<int> > generateMatrix(int n) {
nsq.push_back();
for(int i = n; i > ; i -= ) nsq.push_back( * i - );
for(int i = ; i < nsq.size(); i ++) nsq[i] += nsq[i - ];
for(int i = ; i < n; i ++)
{
vector<int> tmp;
for(int j = ; j < n; j ++)
{
tmp.push_back(calnum(i, j, n));
}
res.push_back(tmp);
}
return res;
}
};
从后往前找。
class Solution {
public:
int lengthOfLastWord(const char *s) {
int i, j;
for(i = strlen(s) - ; i >= && s[i] == ' '; i --);
for(j = i - ; j >= && s[j] != ' '; j --);
return i < ? : i - j;
}
};
Insert Interval
end 比 newInterval 的 start 小的 intervals 直接插入，从 end 比 newInterval 的 start 大的 intervals 开始，到 start 比 newInterval 的 end 大的 intervals 结束，对这部分区间合并，再把之后的 intervals直接插入，特判 newInterval 最小和最大两种极端情况。
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> res;
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
if(intervals.size() == ) {res.push_back(newInterval); return res;}
int i, j;
for(i = ; i < intervals.size() && newInterval.start > intervals[i].end; i ++)
res.push_back(intervals[i]);
for(j = i; j < intervals.size() && newInterval.end >= intervals[j].start; j ++);
if(j != && i != intervals.size())
res.push_back(Interval(min(intervals[i].start, newInterval.start),
max(intervals[j - ].end, newInterval.end)));
else
res.push_back(newInterval);
for(; j < intervals.size(); j ++) res.push_back(intervals[j]);
return res;
}
};
先按start排个序，然后慢慢合并。。。
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> res;
static bool cxompp(const Interval &a, const Interval &b)
{return a.start < b.start;}
vector<Interval> merge(vector<Interval> &intervals) {
if(intervals.size() == ) return res;
sort(intervals.begin(), intervals.end(), cxompp);
Interval last = intervals[];
for(int i = ; i < intervals.size(); i ++)
{
if(last.end >= intervals[i].start)
last.end = max(last.end, intervals[i].end);
else
res.push_back(last), last = intervals[i];
}
res.push_back(last);
return res;
}
};
Jump Game
维护最大可跳距离，每个位置都枚举一次。
class Solution {
public:
bool canJump(int A[], int n) {
if(n == ) return false;
int i, jumpdis;
for(i = jumpdis = ; i < n && jumpdis >= ; i ++, jumpdis --)
jumpdis = max(A[i], jumpdis);
return i == n;
}
};
Spiral Matrix
模拟转一遍吧。写了俩代码，差不多，处理拐弯的方式略有不同。
代码一：
class Solution {
public:
int dx[] = {, , , -};
int dy[] = {, , -, };
vector<int> res;
bool JudgeValid(int x, int y,
vector<vector<bool> > &vis, vector<vector<int> > &matrix)
{
return x >= && x < matrix.size() &&
y >= && y < matrix[].size() && vis[x][y] == false;
}
vector<int> spiralOrder(vector<vector<int> > &matrix) {
int dir, x, y, nx, ny;
if(matrix.size() == ) return res;
vector<vector<bool> > vis(matrix.size(), vector<bool>(matrix[].size(), false));
for(dir = x = y = ; 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 + ) % ;
nx = x + dx[dir];
ny = y + dy[dir];
}
}
return res;
}
};
代码二：
class Solution {
public:
int dx[] = {, , , -};
int dy[] = {, , -, };
vector<int> res;
vector<int> spiralOrder(vector<vector<int> > &matrix) {
int dir, x, y, nx, ny;
int l, r, u, d;
if(matrix.size() == ) return res;
l = u = -;
r = matrix[].size();
d = matrix.size();
for(dir = x = y = ; res.size() < matrix.size() * matrix[].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 + ) % ;
if(dir == ) l ++, r --, d --;
else if(dir == ) u ++;
nx = x + dx[dir];
ny = y + dy[dir];
}
}
return res;
}
};
Maximum Subarray
最大子串和，子串要求至少包含一个数字。
一个变量 sum 表示当前求得的子串和，当 sum 小于0时，对后面的子串没有贡献，则把 sum 置零，中间处理一下要求至少包含一个数字的要求即可。
class Solution {
public:
int maxSubArray(int A[], int n) {
int ans = A[], sum = ;
for(int i = ; i < n; i ++)
{
sum += A[i];
if(sum < ) sum = , ans = max(ans, A[i]);
else ans = max(ans, sum);
}
return ans;
}
};
N-Queens II
题目没说 n 的取值范围，就不用 位运算 做标记了。
老老实实开三个 bool 数组，一个标记纵列，另外两个标记两个斜列，一行一行DFS。
class Solution {
public:
vector<bool> col, lc, rc;
int ans;
void DFS(int cur, int n)
{
if(cur == n)
{
ans ++;
return;
}
for(int i = ; i < n; i ++)
{
if(!col[i] && !lc[n - cur - + i] && !rc[cur + i])
{
col[i] = lc[n - cur - + i] = rc[cur + i] = true;
DFS(cur + , n);
col[i] = lc[n - cur - + i] = rc[cur + i] = false;
}
}
}
int totalNQueens(int n) {
ans = ;
col.resize(n, );
lc.resize(n << , );
rc.resize(n << , );
DFS(, n);
return ans;
}
};
同上
class Solution {
public:
vector<string> tmp;
vector<vector<string> > res;
vector<bool> col, lc, rc;
void DFS(int cur, int n)
{
if(cur == n)
{
res.push_back(tmp);
return;
}
string now(n, '.');
for(int i = ; i < n; i ++)
{
if(!col[i] && !lc[n - cur - + i] && !rc[cur + i])
{
col[i] = lc[n - cur - + i] = rc[cur + i] = true;
now[i] = 'Q';
tmp.push_back(now);
DFS(cur + , n);
tmp.pop_back();
now[i] = '.';
col[i] = lc[n - cur - + i] = rc[cur + i] = false;
}
}
}
vector<vector<string> > solveNQueens(int n) {
col.resize(n, );
lc.resize(n << , );
rc.resize(n << , );
DFS(, n);
return res;
}
};
Pow(x, n)
很多人用特判错过了 n = -2147483648 这么优美的 trick，而不特判的话，似乎只能 long long 了。
经典的快速幂，用二进制理解也好，用折半理解也好，网上很多资料。
class Solution {
public:
double pow(double x, int n) {
double res = ;
long long nn = n;
if(nn < ) x = / x, nn = -nn;
while(nn)
{
if(nn & ) res *= x;
x *= x;
nn >>= ;
}
return res;
}
};
Anagrams
这概念以前没听过诶。。题也没看到样例，不知道以后会不会更新，网上查了才明白啥意思。
调换单词字母顺序能一致的单词集合全放进答案。比如有tea, eat, aet，就都要放进答案，有cat, atc，就都要放进答案，而如果孤零零有个dog，没其他可和他一组的，那么就不放进答案。
手写hash能更快些，但是题目没给数据范围，给hash数组定多大都没合理性，干脆用unordered_map好了。
class Solution {
public:
vector<string> res;
vector<string> anagrams(vector<string> &strs) {
unordered_map<string, int> mp;
for(int i = ; i < strs.size(); i ++)
{
string tmp = strs[i];
sort(tmp.begin(), tmp.end());
if(!mp.count(tmp)) mp[tmp] = ;
else mp[tmp] ++;
}
for(int i = ; i < strs.size(); i ++)
{
string tmp = strs[i];
sort(tmp.begin(), tmp.end());
if(mp.count(tmp) && mp[tmp] > ) res.push_back(strs[i]);
}
return res;
}
};
四个一组，就地旋转。
class Solution {
public:
void rotate(vector<vector<int> > &matrix) {
if(matrix.size() == ) return;
int len = matrix.size();
int lenlimi = len + >> ;
for(int i = ; i < lenlimi; i ++)
for(int j = ; j < (len & ? lenlimi - : lenlimi); j ++)
{
int tmp = matrix[i][j];
matrix[i][j] = matrix[len - j - ][i];
matrix[len - j - ][i] = matrix[len - i - ][len - j - ];
matrix[len - i - ][len - j - ] = matrix[j][len - i - ];
matrix[j][len - i - ] = tmp;
}
}
};
Permutations II
有重复数字，把数字统计起来好了。因为题目没说数字大小，所以统计用了unordered_map。
也可以把数组排序，DFS时跳过重复的数字。
class Solution {
public:
unordered_map<int, int> mp;
vector<int> tmp;
vector<vector<int> > res;
int numsize;
void DFS(int cnt)
{
if(cnt == numsize)
{
res.push_back(tmp);
}
for(unordered_map<int, int>::iterator it = mp.begin(); it != mp.end(); it ++)
{
if(it->second != )
{
tmp.push_back(it->first);
it->second --;
DFS(cnt + );
tmp.pop_back();
it->second ++;
}
}
}
vector<vector<int> > permute(vector<int> &num) {
numsize = num.size();
for(int i = ; i < num.size(); i ++)
{
if(!mp.count(num[i])) mp[num[i]] = ;
else mp[num[i]] ++;
}
DFS();
return res;
}
};
Permutations
虽然题目没说有没有重复数字。。既然 Permutations II 说有了，那就当这个没有吧。
传统DFS。
class Solution {
public:
vector<vector<int> > res;
void DFS(int cur, vector<int> &num)
{
if(cur == num.size())
{
res.push_back(num);
return;
}
for(int i = cur; i < num.size(); i ++)
{
swap(num[cur], num[i]);
DFS(cur + , num);
swap(num[cur], num[i]);
}
}
vector<vector<int> > permute(vector<int> &num) {
DFS(, num);
return res;
}
};
Jump Game II
维护一步最远到达的位置，到达这个位置之前的位置需要的步数都是一样的，到达这个位置的时候，下一步的最远位置已经更新完毕。
class Solution {
public:
int jump(int A[], int n) {
int nex = , pace = , far = ;
for(int i = ; i <= nex && i < n - ; i ++)
{
far = max(far, A[i] + i);
if(i == nex)
{
pace ++;
nex = far;
}
}
return pace;
}
};
同步扫描两个字符串，每当 p 遇到 '*' ，记录s和p的当前扫描位置，当 s 与 p 不匹配时，跑扫描指针回到 '*' 后一个字符， s 扫描指针回到上次遇到 '*' 之后与 p 开始匹配位置的下一个位置。
class Solution {
public:
bool isMatch(const char *s, const char *p) {
int last_star = -, last_s = -, i, j;
for(i = j = ; s[i]; )
{
if(s[i] == p[j] || p[j] == '?') i ++, j ++;
else if(p[j] == '*') last_star = ++ j, last_s = i;
else if(last_star != -) i = ++ last_s, j = last_star;
else return false;
}
while(p[j] == '*') j ++;
return !s[i] && !p[j];
}
};
Multiply Strings
翻转num1和num2，大整数乘法，把结果再翻转。注意 int 和 char 的转换。
class Solution {
public:
string multiply(string num1, string num2) {
string ans(num1.length() + num2.length() + , );
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int cur = , i, j, k;
for(i = ; i < num1.length(); i ++)
{
for(j = ; j < num2.length(); j ++)
{
ans[i + j] += cur + (num1[i] - '') * (num2[j] - '');
cur = ans[i + j] / ;
ans[i + j] %= ;
}
for(k = i + j; cur; k ++)
{
ans[k] += cur;
cur = ans[k] / ;
ans[k] %= ;
}
}
for(k = ans.length() - ; k > && ans[k] == ; k --);
ans.resize(k + );
for(int i = ; i < ans.length(); i ++) ans[i] += '';
reverse(ans.begin(), ans.end());
return ans;
}
};
Trapping Rain Water
对于每个位置，取这个位置“左边最高的”和“右边最高的”的”较低者“，如果“较低者”比这个位置高，则这个位置存水高度为“较低者”减该位置高度。
class Solution {
public:
int trap(int A[], int n) {
vector<int> pre;
int i, maxheight, ans;
for(i = maxheight = ; i < n; i ++)
{
maxheight = max(A[i], maxheight);
pre.push_back(maxheight);
}
for(maxheight = ans = , i = n - ; i > ; i --)
{
maxheight = max(A[i], maxheight);
ans += max(, min(pre[i] - A[i], maxheight - A[i]));
}
return ans;
}
};
First Missing Positive
题目要求时间O(n)，空间O(1)，经分析，不得不破坏原数组 A。
方法一：
剔除非整数，把原数组 A 当作存在标记，存在的数 x 则 A[x-1]取负数。
class Solution {
public:
int firstMissingPositive(int A[], int n) {
int i, j;
for(i = j = ; i < n; i ++)
if(A[i] > ) A[j ++] = A[i];
for(i = ; i < j; i ++)
if(abs(A[i]) <= j) A[abs(A[i]) - ] = -abs(A[abs(A[i]) - ]);
for(i = ; i < j; i ++)
if(A[i] > ) return i + ;
return j + ;
}
};
方法二：
把出现的符合范围的数swap到下标和数对应的位置，再次遍历，数和下标不对应则是第一个没出现的数。注意处理有重复数字。
class Solution {
public:
int firstMissingPositive(int A[], int n) {
int i;
for(i = ; i < n; i ++)
while(A[i] <= n && A[i] > && A[i] != i + && A[A[i] - ] != A[i])
swap(A[i], A[A[i] - ]);
for(i = ; i < n; i ++)
if(A[i] != i + ) return i + ;
return i + ;
}
};
Combination Sum
基础DFS
class Solution {
public:
vector<int> tmp;
vector<vector<int> > ans;
void DFS(vector<int> &num, int ith, int now, int target)
{
if(now == target)
{
ans.push_back(tmp);
return;
}
if(ith == num.size()) return;
int cnt = ;
while(now <= target)
{
DFS(num, ith + , now, target);
now += num[ith];
cnt ++;
tmp.push_back(num[ith]);
}
while(cnt --) tmp.pop_back();
}
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
sort(candidates.begin(), candidates.end());
DFS(candidates, , , target);
return ans;
}
};
Combination Sum II
如果一个数没有被用，那么后面重复的这个数就别用，避免重复解。
class Solution {
public:
vector<int> tmp;
vector<vector<int> > ans;
void DFS(vector<int> &num, int ith, int now, int target)
{
if(now == target)
{
ans.push_back(tmp);
return;
}
if(ith == num.size()) return;
int nex;
for(nex = ith + ; nex < num.size() && num[nex] == num[ith]; nex ++);
DFS(num, nex, now, target);
if(num[ith] + now <= target)
{
now += num[ith];
tmp.push_back(num[ith]);
DFS(num, ith + , now, target);
tmp.pop_back();
}
}
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
sort(num.begin(), num.end());
DFS(num, , , target);
return ans;
}
};
Count and Say
直接模拟，递推。
class Solution {
public:
string countAndSay(int n) {
string f[];
f[] = "";
for(int i = ; i < n; i ++)
{
f[i & ].clear();
for(int j = ; j < f[i & ^ ].length();)
{
int cnt;
char x = f[i & ^ ][j];
for(cnt = ; j < f[i & ^ ].length() && f[i & ^ ][j] == x; cnt ++, j ++);
f[i & ] += '' + cnt;
f[i & ] += x;
}
}
return f[n & ^ ];
}
};
Sudoku Solver
这道题考察回溯和数独结果的判断。ACM做过，就直接拿dancing links代码了，4ms。
关于dancing links，对于面试题来说变态了些，应该不至于考察。
class Solution {
public:
int rw[], cl[], in[], RW[], CL[], IN[], goal;
char buf[];
void Mark(int i, int num)
{
rw[RW[i]] ^= << num;
cl[CL[i]] ^= << num;
in[IN[i]] ^= << num;
}
void init()
{
int i;
for(i = ; i < ; ++ i)
cl[i] = rw[i] = in[i] = ;
for(i = goal = ; buf[i]; ++ i)
goal += buf[i] == '.';
for(i = ; i < ; ++ i)
{
RW[i] = i / , CL[i] = i % , IN[i] = i / % + i / * ;
if(buf[i] != '.')
Mark(i, buf[i] - '');
}
}
inline int Judge(int i, int num)
{return ~(rw[RW[i]] | cl[CL[i]] | in[IN[i]]) & ( << num);}
int Oper(int sx, int k, int cur)
{
Mark(sx, k), buf[sx] = k + '';
if(dfs(cur + )) return ;
Mark(sx, k), buf[sx] = '.';
return ;
}
int JudgeRWCLIN(int cur)
{
int i, j, k, x, cnt, sx;
for(i = ; i < ; ++ i)
for(k = ; k < ; ++ k)
{
if(~rw[i] & ( << k))
{
for(j = cnt = ; j < ; ++ j)
{
x = i * + j;
if(buf[x] == '.' && Judge(x, k)) ++ cnt, sx = x;
}
if(cnt == ) return ;
else if(cnt == )
return Oper(sx, k, cur);
}
if(~cl[i] & ( << k))
{
for(j = cnt = ; j < ; ++ j)
{
x = j * + i;
if(buf[x] == '.' && Judge(x, k)) ++ cnt, sx = x;
}
if(cnt == ) return ;
else if(cnt == )
return Oper(sx, k, cur);
}
if(~in[i] & ( << k))
{
for(j = cnt = ; j < ; ++ j)
{
x = i / * + j / * + i % * + j % ;
if(buf[x] == '.' && Judge(x, k)) ++ cnt, sx = x;
}
if(cnt == ) return ;
else if(cnt == )
return Oper(sx, k, cur);
}
}
return ;
}
bool dfs(int cur)
{
int i, j, num, cnt;
if(cur == goal) return true;
for(i = ; i < ; ++ i)
if(buf[i] == '.')
{
for(j = cnt = ; j < ; ++ j)
if(Judge(i, j)) ++ cnt, num = j;
if(cnt == ) return false;
if(cnt == )
return Oper(i, num, cur);
}
if((num = JudgeRWCLIN(cur)) == ) return false;
else if(num == ) return true;
for(i = ; i < ; ++ i)
if(buf[i] == '.')
{
for(j = ; j < ; ++ j)
if(Judge(i, j))
{
Mark(i, j), buf[i] = j + '';
if(dfs(cur + )) return true;
Mark(i, j), buf[i] = '.';
}
}
return false;
}
void solveSudoku(vector<vector<char> > &board) {
int site = ;
for(int i = ; i < ; i ++)
for(int j = ; j < ; j ++)
buf[site ++] = board[i][j];
init();
dfs();
site = ;
for(int i = ; i < ; i ++)
for(int j = ; j < ; j ++)
board[i][j] = buf[site ++];
}
};
Valid Sudoku
行列九宫格都判断一下。
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
bool flag[][][];
memset(flag, false, sizeof(flag));
for(int i = ; i < ; i ++)
{
for(int j = ; j < ; j ++)
{
if(board[i][j] != '.')
{
int x = board[i][j] - '';
if(flag[][i][x] == true) return false;
flag[][i][x] = true;
if(flag[][j][x] == true) return false;
flag[][j][x] = true;
if(flag[][i / * + j / ][x] == true) return false;
flag[][i / * + j / ][x] = true;
}
}
}
return true;
}
};
Search Insert Position
二分
class Solution {
public:
int searchInsert(int A[], int n, int target) {
int left, right, mid;
for(left = , right = n; left < right; )
{
mid = left + right >> ;
if(A[mid] == target) return mid;
if(A[mid] > target) right = mid;
else left = mid + ;
}
return left;
}
};
Search for a Range
二分，容易错。可以用lower_bound和upper_bound。
手工代码：
class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
int left, right, mid, l, r;
for(left = , right = n; left < right; )
{
mid = left + right >> ;
if(A[mid] >= target) right = mid;
else left = mid + ;
}
l = left;
for(left = , right = n; left < right; )
{
mid = left + right >> ;
if(A[mid] > target) right = mid;
else left = mid + ;
}
r = left - ;
if(l >= n || A[l] != target) return vector<int>(, -);
vector<int> ans = {l, r};
return ans;
}
};
STL：
class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
int l = lower_bound(A, A + n, target) - A;
int r = upper_bound(A, A + n, target) - A;
if(l == n || A[l] != target) return vector<int>(, -);
vector<int> ans = {l, r - };
return ans;
}
};
Search in Rotated Sorted Array
还是二分，但是要判断一下 mid 在哪部分里。
class Solution {
public:
int search(int A[], int n, int target) {
int left = , right = n - , mid;
while(left < right)
{
mid = left + right >> ;
if(A[mid] == target) return mid;
if(A[mid] >= A[left])
{
if(target < A[mid] && A[left] <= target) right = mid;
else left = mid + ;
}
else
{
if(target <= A[right] && A[mid] < target) left = mid + ;
else right = mid;
}
}
return A[left] == target ? left : -;
}
};
这道题时间限制在O(n)，用一个 stack 实现括号配对+统计, 为了方便实现，写成数组的形式。
对不同深度的括号配对统计个数，一层配对成功把该层统计结果加给上一层，这一层清空。
class Solution {
public:
int longestValidParentheses(string s) {
vector<int> cnt(, );
int i, ans;
for(i = ans = ; i < s.length(); i ++)
{
if(s[i] == '(')
cnt.push_back();
else
{
if(cnt.size() > )
{
cnt[cnt.size() - ] += *cnt.rbegin() + ;
cnt.pop_back();
ans = max(ans, *cnt.rbegin());
}
else
cnt[] = ;
}
}
return ans;
}
};
从后往前找到第一个非降序的 num[i]，再重新从后往前找到第一个比 num[i] 大的，swap(num[i], num[j])，再把 i 之后的排序。
class Solution {
public:
void nextPermutation(vector<int> &num) {
int i, j;
for(i = num.size() - ; i >= && num[i] >= num[i + ]; i --);
for(j = num.size() - ; j > i && num[j] <= num[i]; j --);
if(i < j)
{
swap(num[i], num[j]);
sort(num.begin() + i + , num.end());
}
else
reverse(num.begin(), num.end());
}
};
Substring with Concatenation of All Words
直观的方法是枚举起点，判断这个起点下的子串是否合法，O(S.length()*L.size())。
其实可以把 S 分成 L[0].length() 个序列，每个序列都是元素间相隔 L[0].length() 的“string开头”，这些序列互不相干。
如下表，假设 L[0].length()=4，第一行数字为分组组号，第二行数字表示 S 的序号。
| (0) | (1) | (2) | (3) | (0) | (1) | (2) | (3) | (0) | (1) | (2) | (3) | (0) | (1) | (2) | (3) | (0) | (1) | (2) | (3) | (0) |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
对每个序列，用单调队列的思路来处理，一个一个子串入队，当包含了 L 中所有 string 的时候，保存答案。当新元素入队时超出统计允许时——即 L 中有 3 个 "str", 而这时候遇到第 4 个——则开始出队，一直出到队列里不足 3 个 "str"，然后继续。
这样复杂度为O(L[0].length() * S.length() / L[0].length()) = O(S.length())。目前提交结果是180ms。
class Solution {
public:
vector<int> findSubstring(string S, vector<string> &L) {
vector<int> ans;
if(L.size() == ) return ans;
unordered_map<string, int> mp, sum;
int llen = L[].length(), i, front, rear;
for(int i = ; i < L.size(); i ++)
{
if(!mp.count(L[i])) mp[L[i]] = ;
else mp[L[i]] ++;
}
for(i = ; i < llen; i ++)
{
sum = mp;
int cnt = ;
for(front = rear = i; front + llen <= S.length(); front += llen)
{
string tmp = S.substr(front, llen);
if(sum.count(tmp))
{
if(sum[tmp] > )
{
sum[tmp] --;
cnt ++;
if(cnt == L.size())
{
ans.push_back(rear);
}
}
else
{
while(sum[tmp] == )
{
string ntmp = S.substr(rear, llen);
sum[ntmp] ++;
cnt --;
rear += llen;
}
sum[tmp] --;
cnt ++;
if(cnt == L.size())
{
ans.push_back(rear);
}
}
}
else
{
while(rear < front)
{
string ntmp = S.substr(rear, llen);
sum[ntmp] ++;
cnt --;
rear += llen;
}
rear += llen;
cnt = ;
}
}
}
return ans;
}
};
Divide Two Integers
假设 dividend 与 divisor 正负一致， divisor^(2^n) 为最接近 dividend 的 divisor 的幂，那么令 newdividend = dividend - divisor^(2^n)，ans = ans + 2^n，问题就更新为 newdividend 除以 divisor，如此迭代。用 divisor^(2^n) 是因为 divisor 不停地辗转加自己就可以得到了。
有 -2147483648 这样的极限数据，因为 int 范围是 -2147483648~+2147483647，发现负数比正数范围“多1”，干脆把所有数都转成负数算，这样就避免用 long long 了。最后考察一下flag。
（如果转成正数的话，int 的 -(-2147483648)还是 -2147483648。。）
class Solution {
public:
int divide(int dividend, int divisor) {
bool flag = false;
if(divisor > ) divisor = -divisor, flag ^= true;
if(dividend > ) dividend = -dividend, flag ^= true;
int ans = , res = divisor, ex = ;
if(divisor < dividend) return ;
while(res >= dividend - res)
{
res += res;
ex += ex;
}
while(res <= divisor && dividend)
{
if(res >= dividend)
{
dividend -= res;
ans += ex;
}
res >>= ;
ex >>= ;
}
return flag ? -ans : ans;
}
};
Implement strStr()
KMP。
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int hlen = (int)strlen(haystack), nlen = (int)strlen(needle);
if(nlen == ) return haystack;
vector<int> next(nlen + );
next[] = -;
for(int i = , j = -; i < nlen;)
{
if(j == - || needle[i] == needle[j])
{
i ++, j ++;
if(needle[i] != needle[j]) next[i] = j;
else next[i] = next[j];
}
else j = next[j];
}
for(int i = , j = ; i < hlen;)
{
if(j == - || haystack[i] == needle[j])
i ++, j ++;
else j = next[j];
if(j == nlen) return haystack + i - j;
}
return NULL;
}
};
Remove Element
两个游标 i, j 异步挪动，把不等于给定值的数往前挪。
class Solution {
public:
int removeElement(int A[], int n, int elem) {
int i, j;
for(i = j = ; i < n; i ++)
if(A[i] != elem) A[j ++] = A[i];
return j;
}
};
Remove Duplicates from Sorted Array
两个游标 i, j 异步挪动，不重复值往前挪。
class Solution {
public:
int removeDuplicates(int A[], int n) {
int i, j;
for(i = j = ; i < n; i ++)
if(A[i] != A[i - ]) A[j ++] = A[i];
return n ? j : ;
}
};
用头插法来做的，顺序插入到首节点之后，就反转了。每 k 个节点处理之后，把首节指针点移动到下 k 个的开头。最后面不足 k 个的话，再反转回来。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int Reverse(ListNode *&pre, ListNode *&p, int k)
{
int i;
ListNode *nex, *tmp;
for(i = ; p != NULL; i ++, p = tmp)
{
if(i == ) nex = p;
tmp = p->next;
p->next = pre->next;
pre->next = p;
if(i == k) i = , pre = nex;
}
nex->next = NULL;
return i;
}
ListNode *reverseKGroup(ListNode *head, int k) {
if(head == NULL) return NULL;
ListNode *tmphead = new ListNode(), *pre = tmphead, *p = head;
tmphead->next = head;
if(Reverse(pre, p, k) != )
{
p = pre->next;
Reverse(pre, p, k);
}
return tmphead->next;
}
};
Reverse Nodes in k-Group的简化版。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
if(head == NULL) return NULL;
ListNode *tmphead = new ListNode(), *pre = tmphead, *p = head, *tmp, *nex;
tmphead->next = head;
for(int i = ; p != NULL; i ++, p = tmp)
{
if(i & ^ ) nex = p;
tmp = p->next;
p->next = pre->next;
pre->next = p;
if(i & ) pre = nex;
}
nex->next = NULL;
return tmphead->next;
}
};
Merge k Sorted Lists
一个堆（这里用了优先级队列），把所有 list 的首元素放堆里，O(logn)取得最小值插入新队列，异步推进。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
struct comp
{
bool operator()(ListNode *a,ListNode *b)
{return a->val > b->val;}
};
ListNode *mergeKLists(vector<ListNode *> &lists) {
ListNode *tmphead = new ListNode(), *p = tmphead;
priority_queue<ListNode*, vector<ListNode*>, comp> q;
for(int i = ; i < lists.size(); i ++)
if(lists[i] != NULL) q.push(lists[i]);
while(!q.empty())
{
p->next = q.top();
p = p->next;
q.pop();
if(p ->next != NULL) q.push(p->next);
}
return tmphead->next;
}
};
Generate Parentheses
DFS，保持当前右括号不多于左括号。
class Solution {
public:
string tmp;
vector<string> ans;
void DFS(int left, int right, int n)
{
if(left == right && left == n)
{
ans.push_back(tmp);
return;
}
if(left < n)
{
tmp[left + right] = '(';
DFS(left + , right, n);
}
if(right < left)
{
tmp[left + right] = ')';
DFS(left, right + , n);
}
}
vector<string> generateParenthesis(int n) {
tmp.resize(n << );
DFS(, , n);
return ans;
}
};
用栈配对。
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(int i = ; i < s.length(); i ++)
{
switch(s[i])
{
case '(': st.push('('); break;
case '[': st.push('['); break;
case '{': st.push('{'); break;
case ')':
if(st.empty() || st.top() != '(') return false;
st.pop(); break;
case ']':
if(st.empty() || st.top() != '[') return false;
st.pop(); break;
case '}':
if(st.empty() || st.top() != '{') return false;
st.pop(); break;
}
}
return st.empty();
}
};
Remove Nth Node From End of List
两个指针相隔 n 距离，前面的指针到了末尾，后面的指针就是删除的位置。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode *pre, *slow, *quick;
ListNode *newhead = new ListNode();
newhead->next = head;
int i = ;
for(pre = slow = quick = newhead; quick != NULL; i ++)
{
pre = slow;
if(i >= n) slow = slow->next;
quick = quick->next;
}
pre->next = slow->next;
free(slow);
return newhead->next;
}
};
Letter Combinations of a Phone Number
基础DFS。
class Solution {
public:
const vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ans;
string tmp;
void DFS(int cur, string d)
{
if(cur == d.length())
{
ans.push_back(tmp);
return;
}
for(int i = ; i < v[d[cur] - ''].length(); i ++)
{
tmp[cur] = v[d[cur] - ''][i];
DFS(cur + , d);
}
}
vector<string> letterCombinations(string digits) {
tmp.resize(digits.length());
DFS(, digits);
return ans;
}
};
4Sum
尝试了O(n^2)的，但是应该常数很大吧，超时了。就是哈希存两两的和，然后通过查哈希表找到 两两+两两，要判断数字重复情况。这题数据量挺大的，O(n^3)如果用不太好的方式实现的话也会超。
O(n^3)方法：先对num排序，然后从两头枚举两个数，O(n^2)，后两个数在前两个数之间的两端开始，和小了左边的往右，和大了右边的往左调整，O(n)，总共O(n^3)。
class Solution {
public:
vector<vector<int> > ans;
vector<vector<int> > fourSum(vector<int> &num, int target) {
if(num.size() < ) return ans;
sort(num.begin(), num.end());
for(int left = ; left < num.size() - ;)
{
for(int right = num.size() - ; right > left + ;)
{
int ml = left + , mr = right - ;
while(ml < mr)
{
int tmpsum = num[left] + num[right] + num[ml] + num[mr];
if(tmpsum > target) mr --;
else if(tmpsum < target) ml ++;
else
{
vector<int> tmp = {num[left], num[ml], num[mr], num[right]};
ans.push_back(tmp);
ml ++;
mr --;
}
for(; ml != left + && ml < mr && num[ml] == num[ml - ]; ml ++);
for(; mr != right - && ml < mr && num[mr] == num[mr + ]; mr --);
}
for(right --; right > left + && num[right] == num[right + ]; right --);
}
for(left ++; left < num.size() - && num[left] == num[left - ]; left ++);
}
return ans;
}
};
3Sum Closest
O(n^2)，先排序，枚举第一个数，后两个数一个在第一个数后边一个开始，一个从 末尾开始，和4Sum类似调整。
class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
bool findans = false;
int ans;
sort(num.begin(), num.end());
for(int i = ; i < num.size(); i ++)
{
for(int left = i + , right = num.size() - ; left < right;)
{
int tmpsum = num[i] + num[left] + num[right];
if(tmpsum > target) right --;
else if(tmpsum < target) left ++;
else return tmpsum;
if(!findans || abs(tmpsum - target) < abs(ans - target))
ans = tmpsum, findans = true;
}
}
return ans;
}
};
3Sum
同上。
class Solution {
public:
vector<vector<int> > ans;
vector<vector<int> > threeSum(vector<int> &num) {
if(num.size() < ) return ans;
sort(num.begin(), num.end());
for(int i = ; i < num.size();)
{
for(int left = i + , right = num.size() - ; left <right;)
{
int tmpsum = num[i] + num[left] + num[right];
if(tmpsum < ) left ++;
else if(tmpsum > ) right --;
else
{
vector<int> tmp = {num[i], num[left], num[right]};
ans.push_back(tmp);
left ++;
right --;
}
for(; left != i + && left < right && num[left] == num[left - ]; left ++);
for(; right != num.size() - && left < right && num[right] == num[right + ]; right --);
}
for(i ++; i < num.size() && num[i] == num[i - ]; i ++);
}
return ans;
}
};
Longest Common Prefix
一个一个扫
class Solution {
public:
string ans;
string longestCommonPrefix(vector<string> &strs) {
if(strs.size() == ) return ans;
if(strs.size() == ) return strs[];
for(int j = ; ; j ++)
{
for(int i = ; i < strs.size(); i ++)
if(strs[i].size() == j || strs[i][j] != strs[i - ][j]) return ans;
ans += strs[][j];
}
return ans;
}
};
各有各的方法，重点是记录“上一个”数比“这个”数大或小，来确定谁减谁。基本是右结合的，所以从后往前扫好处理些。
class Solution {
public:
int ro[];
int romanToInt(string s) {
ro['I'] = ;
ro['V'] = ;
ro['X'] = ;
ro['L'] = ;
ro['C'] = ;
ro['D'] = ;
ro['M'] = ;
int ans = -, last;
for(int i = s.length() - ; i >= ; i --)
{
if(ans == -) ans = ro[s[i]];
else
{
if(last > ro[s[i]]) ans -= ro[s[i]];
else ans += ro[s[i]];
}
last = ro[s[i]];
}
return ans;
}
};
Integer to Roman
每个十进制位格式是一样的，只是字母替换一下。
class Solution {
public:
vector<string> table = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
string ro = "IVXLCDM";
char convert(char x, int i)
{
if(x == 'I') return ro[i];
if(x == 'V') return ro[i + ];
if(x == 'X') return ro[i + ];
}
string intToRoman(int num) {
string ans;
for(int i = ; num; i += , num /= )
{
int x = num % ;
string tmp = table[x];
for(int j = ; j < tmp.size(); j ++)
tmp[j] = convert(tmp[j], i);
ans = tmp + ans;
}
return ans;
}
};
从两端开始枚举，较高的挡板往中间枚举的话一定无法得到更优解，故反复从较低挡板向中间枚举，O(n)。
class Solution {
public:
int maxArea(vector<int> &height) {
int left = , right = height.size() - , ans = -;
while(left < right)
{
ans = max(ans, min(height[left], height[right]) * (right - left));
if(height[left] < height[right]) left ++;
else right --;
}
return ans;
}
};
Regular Expression Matching
每遇到一个 '*' ，问题都会出现分枝，需要用到栈或者递归。
没有 '*' 的情况好处理，遇到 '*' 的时候，穷举所有匹配长度。
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if(*p == ) return *s == ;
if(*(p + ) != '*')
{
if(*s && (*s == *p || *p == '.'))
return isMatch(s + , p + );
return false;
}
else
{
for(; *s && (*s == *p || *p == '.'); s ++)
if(isMatch(s, p + )) return true;
return isMatch(s, p + );
}
}
};
Palindrome Number
首先处理负数的trick。然后主要思路就是通过 while(...) a = a * 10 + x % 10; 来将 x 翻转。
但是注意到 x 很大的时候，翻转的 x 会超出 int 范围，也许会刚好成为另一个和 a 得出的数相等的正数，所以不能完全翻转后判断，而可以在翻转恰好一半的时候判断。
class Solution {
public:
bool isPalindrome(int x) {
if(x < ) return false;
if(x == ) return true;
int a = , b = x, cnt = ;
while(x /= ) cnt ++;
for(; b && cnt >= ; b /= , cnt -= )
{
if(cnt == ) return a == b / ;
else if(cnt == ) return a == b;
a = a * + b % ;
}
return false;
}
};
String to Integer (atoi)
任何类似多符号、符号数字间有空格的小问题都直接输出 0，这就好办了。处理越界用 long long。
class Solution {
public:
int atoi(const char *str) {
long long ans = ;
bool flag = false;
for(; *str == ' '; str ++);
if(*str == '+') str ++;
else if(*str == '-') flag = true, str ++;
for(; isdigit(*str); str ++)
{
ans = ans * + *str - '';
if((flag ? -ans : ans) > INT_MAX) return INT_MAX;
else if((flag ? -ans : ans) < INT_MIN) return INT_MIN;
}
return (int)(flag ? -ans : ans);
}
};
Reverse Integer
还是关于越界的讨论，不过这道题本身没有设置处理方式，重点在于面试时的交流。
class Solution {
public:
int reverse(int x) {
int a = ;
for( int b = x >= ? x : -x; b; b /= )
a = a * + b % ;
return x >= ? a : -a;
}
};
题意的 "z" 字形指一列nRows个，然后斜着往右上一格一个回到第一行，然后再一列nRows个。比如nRows=5，如下：
| 1 | 9 | 17 | 25 | |||||||||||
| 2 | 8 | 10 | 16 | 18 | 24 | 26 | ||||||||
| 3 | 7 | 11 | 15 | 19 | 23 | 27 | … | |||||||
| 4 | 6 | 12 | 14 | 20 | 22 | 28 | 30 | |||||||
| 5 | 13 | 21 | 29 |
每行字母在原字符串中的间隔是有规律的，虽然两层for循环，但是s中每个字母只访问了一次，O(n)。
class Solution {
public:
string convert(string s, int nRows) {
if(nRows == ) return s;
string ans;
int a = (nRows << ) - , b = ;
for(int i = ; i < nRows; i ++, a -= , b += )
{
bool flag = false;
for(int j = i; j < s.length();
j += flag ? (b ? b : a) : (a ? a : b), flag ^= )
ans += s[j];
}
return ans;
}
};
网上O(n)的方法是厉害啊。。。简单解释如下：
1、预处理字符串，前后加“哨兵”字符比如 '!'，每个字母旁边加辅助字符比如'#'，这样例如字符串 s = "ababbcbb" 就变成 tmp = "!#a#b#a#b#b#c#b#b#!"。这样的好处是不用讨论回文串长度的奇偶。
2、对转化后的串，维护一个 center 和一个 reach，center 是当前已发现的 reach 最远的回文串中心位置，reach 是这个回文串最右端的位置，center和reach可初始化为 1，即第一个'#'的位置。
3、维护一个数组 vector<int> r(tmp.length())，r[i] 表示 i 位置为中心的回文串半径。
4、在考察位置 i 的时候，所有 j < i 的 r[j] 都是已知的子问题。如果 i 在 reach 的左边，则 i 包含在以 center 为中心的回文串中，那么可以想到，如果和 i 关于 center 对称位置的 mirrori 为中心的回文串覆盖范围没有到达 center 为中心的回文串边缘，则 i 为中心的回文串肯定和 mirrori 的一样。而如果 mirrori 的回文串到达了边缘甚至超过，或者 i 本来就在 reach 的右边，那么对 i 为中心的回文串进行一次扩展，则结果 或者刚好不扩展，或者一定更新了reach。无论怎样，这里都得到了 r[i]。知道了所有 r[i]，答案就出来了。
核心问题在于第4步“对 i 为中心的回文串进行扩展”的复杂度。每次发生“对 i 扩展“，必然是对 reach 的扩展(也可能刚好不扩展，这个不影响复杂度），而 reach 的扩展范围是 tmp 的长度大约 2n，所以总复杂度为 O(n)。
class Solution {
public:
string longestPalindrome(string s) {
int center = , reach = , ansstart = , anslength = ;
string tmp = "!#";
for(int i = ; i < s.length(); i ++)
tmp += s[i], tmp += '#';
tmp + '!';
vector<int> r(tmp.length());
for(int i = ; i < tmp.length(); i ++)
{
int mirrori = center * - i;
r[i] = reach > i ? min(r[mirrori], reach - i) : ;
for(; tmp[i + r[i] + ] == tmp[i - r[i] - ]; r[i] ++);
if(i + r[i] > reach) reach = i + r[i], center = i;
if(r[i] > anslength)
{
ansstart = i - r[i] >> ;
anslength = r[i];
}
}
return s.substr(ansstart, anslength);
}
};
Add Two Numbers
大整数加法的链表版。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *ans = new ListNode(), *p = ans;
int cur = ;
while(l1 != NULL || l2 != NULL || cur)
{
p->val = (l1 ? l1->val : ) + (l2 ? l2->val : ) + cur;
cur = p->val / ;
p->val %= ;
if(l1) l1 = l1->next;
if(l2) l2 = l2->next;
if(l1 || l2 || cur)
p->next = new ListNode();
p = p->next;
}
return ans;
}
};
Longest Substring Without Repeating Characters
维护一个不重复字符的区间。
代码一：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<bool> isin(, false);
int ans = ;
for(int front = , rear = ; front < s.length(); front ++)
{
if(isin[s[front]])
for(; rear < front && isin[s[front]]; isin[s[rear]] = false, rear ++);
isin[s[front]] = true;
ans = max(ans, front - rear + );
}
return ans;
}
};
代码二：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> site(, -);
int nowstart = -, ans = ;
for(int i = ; i < s.length(); i ++)
{
if(site[s[i]] >= nowstart)
nowstart = site[s[i]] + ;
site[s[i]] = i;
ans = max(i - nowstart + , ans);
}
return ans;
}
};
Median of Two Sorted Arrays
如果 A[pa] < B[pb]，那么 A[pa] 一定在 A 与 B 合并后的前 pa + pb + 2 个数中。
证明： A 中有 pa + 1 个数 <= A[pa]，B 中有小于 pb + 1 个数 <= A[pa]，合并后有少于pa + pb + 2 个数 <= A[pa]。
利用这个性质迭代找 A 与 B 合并后的第 k 大数。
class Solution {
public:
int findKth(int A[], int m, int B[], int n, int k)
{
int pm, pn;
while(true)
{
if(m == ) return B[k - ];
if(n == ) return A[k - ];
if(k == ) return min(A[k - ], B[k - ]);
if(m <= n) pm = min(k >> , m), pn = k - pm;
else pn = min(k >> , n), pm = k - pn;
if(A[pm - ] < B[pn - ]) A += pm, m -= pm, k -= pm;
else if(A[pm - ] > B[pn - ]) B += pn, n -= pn, k-= pn;
else break;
}
return A[pm - ];
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if((m + n) & ) return findKth(A, m, B, n, (m + n >> ) + );
else return (findKth(A, m, B, n, m + n >> ) +
findKth(A, m, B, n, (m + n >> ) + )) * 0.5;
}
};
Two Sum
哈希存位置，O(n)。
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
unordered_map<int, int> mp;
vector<int> ans;
for(int i = ; i < numbers.size(); i ++)
{
if(mp.count(target - numbers[i]))
{
ans.push_back(mp[target - numbers[i]] + );
ans.push_back(i + );
break;
}
if(!mp.count(numbers[i])) mp[numbers[i]] = i;
}
return ans;
}
};