Hobo Chen

Leetcode 突击

这篇文章是我在准备某家公司面试的时候做的Leetcode题目。

其中列出的题目代码可能在这个GitHub仓库中的leetcode子目录中找到。

动态规划

Stock I

给一个股票价格的时间序列,只允许买卖一次。

DP,记dp[i]为第i天能持有的最小成本(即0-i天内的最小值)。

DP需要$O(n)$,遍历也需要$O(n)$。

Stock II

输入和上一题一样,允许买卖任意多次。但是最多只允许一支股票在手上。

DP,记dp[i][0/1]为到了第i天持有/不持有的最大获利。最终答案一定是dp[n - 1][0]。

复杂度$O(n)$。

Stock III

输入和上一题一样,但是只允许买卖两次。

DP,记dp[i][0/1][0/1/2]为到了第i天当前持有/不持有且完成了0/1/2次买卖的最大获利。最终答案一定是max(dp[n - 1][0][i])。

复杂度$O(n)$。

Stock IV

一道DP好题,数据也造的不错(相比于leetcode其他题目);能使我不使用滚动数组的代码MLE或在k>n的情况下$O(nk)$的做法TLE。

记dp[i][0/1][0..k]为到了第i天当前持有/不持有且完成了m次买卖的最大获利。最终答案一定在max(dp[n - 1][0][i])。

时间复杂度$O(nk)$;空间复杂度$O(k)$。

这道题可以优化到$O(n + k\log n)$。

最大连乘积

和最大和的区别就是最后答案可能有两种转移。

链表

比较好的一篇博客:http://wuchong.me/blog/2014/03/25/interview-link-questions/。

单向链表删元素

假装删除一下就好。

单向链表是否有环

两个指针fast和slow,fast每次前进两格,slow每次前进一格,如果fast和slow相遇则有环。

单向链表删除倒数第m个节点

两个指针,fast先前进m格;之后fast和slow一起前进到fast到达链表尾部。

单向链表两两翻转元素

递归的方法去做。

单向链表翻转

迭代的做法:
设定三个指针,pre, cur, nxt。
递归的做法:
回溯之前拆除所有关系,回溯过程中添加指回去的指针。

二叉树

LCA问题

比较有意思的一个题。

比较常规的思路就是遍历一遍,重建一个棵带有fathor指针的树。然后DFS两次即可。

BST删节点

拍扁BST

BST删除中序后继节点

右儿子不空的话返回右子树的最左叶子节点;否则需要类似在二叉树中查找的做法。

二叉树的序列化与反序列化

字符串

单词反向

其他

外部排序

两种LCS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// substring
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A[i - 1] == B[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
}
else {
f[i][j] = 0;
}
}
}
// subsequence
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (A[i - 1] == B[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
}
}
}

O(1)空间复杂度删除二叉树