LeetCode OJ 题解

博客搬至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;
}
};

Reverse Words in a String

先翻转整个字符串,然后从前往后一个单词一个单词地再翻转一次,同时去除多余空格,等于是扫描两遍,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;
} };

LRU Cache

新建数据类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;
}
};

Linked List Cycle II

设置两个指针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;
}
};

Single Number

一路异或过去就可以了。

 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 ;
}
};

Valid Palindrome

做过刘汝佳 白书的人想必都知道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);
}
};

Path Sum II

传统递归,把路径上的数字插入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, );
}
};

Minimum Depth of Binary 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:
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)) + ;
}
};

Balanced Binary 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:
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()); }
};

Maximum Depth of Binary 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:
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);
}
};

Recover Binary Search Tree

中序遍历是二叉查找树的顺序遍历,*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;
}
};

Word Search

基础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;
}
};

Sort Colors

轮流找:

 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);
}
};

Add Binary

翻转,大整数加法,再翻转。无心情优化。

 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;
}
};

Merge Two Sorted Lists

归并排序的一次操作,设个哨兵头结点,结束后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;
}
};

Minimum Path Sum

递推

 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() - ];
}
};

Unique Paths

这是当年学组合数时候的经典题型吧。

 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

直接算每个位置的数是多少有木有很霸气LeetCode OJ 题解

先看当前位置之外有几个嵌套的正方形,再看当前位置在当前正方形四条边的第几条,求出坐标(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;
}
};

Length of Last Word

从后往前找。

 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;
}
};

Merge Intervals

先按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;
}
};

N-Queens

同上

 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;
}
};

Rotate Image

四个一组,就地旋转。

 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;
}
};

Wildcard Matching

同步扫描两个字符串,每当 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 : -;
}
};

Longest Valid Parentheses

这道题时间限制在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;
}
};

Next Permutation

从后往前找到第一个非降序的 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 : ;
}
};

Reverse Nodes in k-Group

用头插法来做的,顺序插入到首节点之后,就反转了。每 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;
}
};

Swap Nodes in Pairs

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;
}
};

Valid Parentheses

用栈配对。

 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;
}
};

Roman to Integer

各有各的方法,重点是记录“上一个”数比“这个”数大或小,来确定谁减谁。基本是右结合的,所以从后往前扫好处理些。

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;
}
};

Container With Most Water

从两端开始枚举,较高的挡板往中间枚举的话一定无法得到更优解,故反复从较低挡板向中间枚举,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;
}
};

ZigZag Conversion

题意的 "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;
}
};

Longest Palindromic Substring

网上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;
}
};
 
上一篇:Cocos2d-x教程(30)-3.x版本号物理引擎的使用


下一篇:Newtonsoft.Json 高级用法