Blog By Alexander

0%

技能面试考前冲刺

编者:艾孜尔江

一、编程之美

1.2 中国象棋将帅问题

1
2
3
4
5
6
7
8
9
struct {
unsigned char a:4;
unsigned char b:4;
};

for (i.a = 1; i.a <= 9; i.a++)
for (i.b = 1; i.b <= 9; i.b++)
if (i.a % 3 != i.b % 3)
printf("%u:%u", i.a, i.b);

1.14 连连看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Grid* preClick = NULL, * curClick = NULL;
while(true) {
// listen user event
if (点击格子 xy 非空) {
preClick = curClick;
curClick.pos = x, y;
}

if (preClick && curClick && findPath(preClick, curClick)) {
显示路径
消去
preClick = curClick = NULL;
}
}

2.1 - 2.6 LeetCode

2.7 最大公约数

辗转相除法,如果一个数能够整除x,y,那么他也能够整除x,x%y。

1
2
3
4
5
int gcd(int x, int y) {
if (y == 0)
return x;
return gcd(y, x % y);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// iterative
int gcd(int x, int y) {
while (y) {
int t = x;
x = y
y = t % y;
}
return x;
}

取模运算开销较大,但如下方法在y比较小时,求解次数过多,容易溢出

```C
int gcd(int x, int y) {
if (x < y)
return gcd(y, x);
if (y == 0)
return x;
return gcd(x - y, y);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int gcd(int x, int y) {
if (x < y)
return gcd(y, x);
if (y == 0)
return x;
if (x & 0x1 == 0)
if (y & 0x1 == 0)
return gcd(x>>1, y>>1) << 1;
else
return gcd(x >>1, y);
else
if (y & 0x1 == 0)
return gcd(x, y>>1);
else
return gcd(y, x-y);
}

2.8 看下讲解

2.9 斐波那契数列

使用动态规划(Memoization)的算法不在赘述O(n)。

O(logn)的解法

通项公式

f(n), f(n-1) = (f(n-1), f(n-2)) * A

A = |1  1|
    |1  0| 

f(n), f(n-1) = (f(n-1), f(n-2)) * A = ... = (f1, f0) * A^(n-1)

下面我们计算A^n-1,太简单了,使用A^(2n) = A^n * A^n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// pesudo code
int fib(int n) {
Matrix factor = matrixPow(A, n-1);
return f1*factor + f0*factor;
}

Matrix matrixPow(Matrix m, int n) {
Matrix result = Matrix::Identity;
while (n) {
if (n & 1)
result *= m;
m *= m;
n >>= 1;
}
return result;
}

拓展问题,如果是前三项相加的数列呢,依然可以求出转移矩阵

2.11 最近点对问题

2.12-2.14 LeetCode 2.15 Cracking 2.16 2.17 LeetCode

2.18 数组分割

2.19 LeetCode

3.1 有时间可以尝试写一下

3.2 电话号码对应英文单词

递归写法

3.3 Edit Distance

3.4 删除链表节点

3.5 最短摘要的生成

问题转化为,在一个单词词组中,找出包含所有给定单词的最短区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
pair<int, int> abstract(vector<string> article, unordered_set<string> keywords) {
int start = 0, end = 0, range = INT_MAX;
unordered_map<string, int> indecies;
unordered_set<string> having;
pair<int, int> result;
while (end < article.size()) {
while (end < article.size() && !isContain(keywords, having)) {
indecies[articel[end]] = end;
end++;
}
while (isContain(keywords, having)) {
if (end - start + 1 < range) {
range = end - start + 1;
result.first = start;
result.second = end;
}
if (indecies[aritcle[start]] == start)
having.erase[article[start]];
start++;
}
}
return result;
}

3.6 判断两个链表是否相交

如果链表中有环呢?

3.7 队列中取最大值

使用连个minstack模拟队列

3.8 二叉树中两个节点之间的最远距离

显然,对一个根节点,最远距离有两种情况:

  1. 左子树或者右子树中的最远距离
  2. 左子树最长路径+有子树最长路径+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct {
int max_distance;
int max_depth;
} result_t;

// get max distance of two nodes in a tree
result_t get_max(tree_node_t* root) {
result_t result;
if (!root) {
result.max_distance = 0;
result.max_depth = -1;
return result;
}

result_t left = get_max(root->left);
result_t right = get_max(root->right);

result.max_depth = max(left.max_depth, right.max_depth) + 1;
result.max_distance = max(max(left.max_distance, right.max_distance), left.max_depth + right.max_depth + 2);
return result;
}

对于递归问题,书上的心得:

  1. 在递归的实现中,往往假设后续的调用已经完成,在此基础上,才能实现递归的逻辑。
  2. 分析清楚递归体的逻辑。
  3. 考虑清楚递归退出的边界条件,也就是return的地方。

3.9 重建二叉树

拓展问题,如何判断前序遍历和中序遍历是合理的?

测试用例:
非完全二叉树,退化的二叉树,满二叉树,普通二叉树,空树。。。

3.10 层序遍历

注意把LeetCode上的ZigZag层序都看一遍。

递归的遍历需要先计算level

3.11 注意问题

对于询问知识点,要答得正确有条理。最后写出来的程序已定要是没有严重错误完整,并尝试用一些测试用例。

4.1 金刚

询问李博士

4.2 瓷砖覆盖地板

斐波那契额数列

1x2覆盖8x8?从小到大,先找出2x2有多少种,再找出4x4有多少种,再找出8x8有多少种。还有考虑好多种,注意不要有重复
pxq覆盖mxn?

4.3 Catalan数

4.4 点是否在三角形内部

给定 ABC,逆时针顺序,判断 D 是否在 ABC 内部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 利用面积,如果 D 和 ABC 分别构成的三角形的面积小于 ABC 的面积,那么 D 在三角形内部
double area(Point A, Point B, Point, C) {
double a, b, c;
b = distance(A, C);
a = distance(B, C);
c = distance(A, B);

double p = (a + b + c) / 2;
return sqrt((p-a) * (p-b) * (p-c) * p);
}

bool isInTriangle(A, B, C, D) {
return area(A, B, D) + area(A, C, D) + area(B, C, D) <= area(A, B, C);
}
1
2
3
4
5
6
7
8
// 根据角度考虑,如果两个向量叉积为正,那么 P3 在P1P2的左边,如果一个点同时在 AB,BC,CA 的左边
double cross(Point A, Point B, Point X) {
return (B.x - A.x) * (X.y - A.y) - (X.x - A.x) * (B.y - A.y);
}

bool isInTriangle(A, B, C, D) {
return cross(A, B, D) >= 0 && cross(B, C, D) >= 0 && cross(C, A, D) >= 0;
}

4.5 磁带文件存储优化

只考虑长度,按照文件长度由短到长存放。
只考虑访问频率,按照访问频率由高到低存放。
综合考虑,按照频率/长度由高到低

4.6 桶中取黑白球

相当于使用 XOR,可以解任意问题

4.7 蚂蚁爬杆

相当于穿越

4.8 三角形测试用例

int isTriangle(int a, int b, int c);

  1. 用一个字节编码各种情况。

用不同的位表示不同的结果,注意要正交

  1. 测试用例

    1. 合法输入,各种三角形的形状,以及不是三角形的,还需要考虑交换不同边的顺序;

    2. 非法输入,负数,0,类型错误等等;

    3. 边界值,一般程序可能在< <= > >=上犯错误;

    4. 很大的数,很小的数,等等。

一般需要给出15-20个用例

4.10 数字哑谜

列出方程,使用深度优先搜索,注意剪枝

4.11 扫雷游戏的概率




二、C/C++基本算法考点

1.1 确定一个字符串中所有数字是否完全不同

首先应该询问面试官字符集的大小,是ASCII还是Unicode还是GBK,对于ASCII和GBK,
因为字符集大小有限,而且都不太大,可以使用一个数组统计,而对于Unicode,
显然只能使用Hash统计

1
2
3
4
5
6
7
8
9
10
11
bool isUniqueChars(const string& s) {
if (s.size() > 256) return false;

vector<bool> charSet(256);
for (auto c : s)
if (charSet[s])
return false;
else
charSet[c] = true;
return true;
}

注意:还可以使用位向量提高效率,但是C++的vector本身就是特质化的。

1.2 实现reverse(char* s)

1
2
3
4
5
6
7
8
9
10
11
12
void reverse(char* s) {
if (!s) return;
char* end = s;
while (*end++) ;
end--; // back one

while (s < end) {
char t = *s;
*s++ = *end;
*end-- = t;
}
}

1.3 判断两个词是否是变位词(Anagram)

1.4 编写一个方法,将字符串中的空格全部替换为%20,假设字符串结尾有足够空间

对于数组操作的好多题目,尝试从尾部做起一下子就简单多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void replaceSpaces(char* s, int len) {
int spaceCount = 0, newLength = 0;

for (int i = 0; i < len; i++)
if (isspace(s[i]))
newLength++;

newLength = len + spaceCount * 2;
s[newLength] = '\0';

for (int i = len - 1; i >= 0; i--) {
if (isspace(s[i])) {
s[--newLength] = '0';
s[--newLength] = '2';
s[--newLength] = '%';
} else {
s[--newLength] = s[i];
}
}
}

1.5 压缩字符串 aabcccccaaa -> a2b1c5a3如果压缩后变短,返回压缩后的字符串

首先要计算出新的长度,然后比较是否变短,如果变短,则执行压缩,否则返回

1.6 给定一幅由N*N矩阵表示的图像,顺时针旋转90度

1.7 若m*n矩阵中某个元素为0,就把这一行和这一列都清零

LeetCode 73 注意同样可以使用位向量提高效率

1.8 给定方法isSubstring(),判断s1是不是可以由s2旋转组成

假设s1 = xy, s2 = yx,yx一定是xyxy的字串,而且是中间部分。注意先判断长度,提高效率

1
2
3
4
5
6
7
bool isRotation(string& s1, string& s2) {
if (s1.size() != s2.size())
return false;

string s1s1 = s1 + s1;
return isSubstring(s1s1, s2);
}

2.1 移除未排序列表中的重复节点

因为是无序的,所以我们还是需要记录重复节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 显然第一个节点是不可能被移除的,所以不用返回新的头部
void removeDuplicates(ListNode* head) {
unordered_set<int> vals;
ListNode dummy, *p = dummy;
dummy.next = head;
while (p->next) {
if (vals.find(p->next->val) != vals.end())
ListNode* next = p->next;
p->next = next->next;
free(next);
} else {
vals.insert(p->next->val);
}
}
}

如果不允许使用额外空间,那么这个功能至少需要O(N^2)实现

2.2 实现一个算法,找出链表中倒数第K个元素

2.3 删除单向链表中的某个节点,假设你只有访问该节点的权限

2.4 以给定的值x分割列表,使得小于x的元素都排在x的前面

LeetCode 83

2.5 给定一个链表,每个链表节点存放一位数字,并且是反向存放的,求两个链表的和

LeetCode 2

如果是正向存放的呢?

先求出两个列表的长度,然后用零填充一个较短的链表,然后在从前往后相加。

2.6 给定一个有环链表,找到环的开头

LeetCode 141 142

2.7 判断链表是否是回文(Palindrome)

LeetCode 234

3.1 如何用一个数组实现3个栈

如果是实现两个堆栈,可以把两头作为栈底,向中间生长。

解法1: 固定分割,显然这样是不能让面试官满意的。。

解法2: 弹性分割,并把数组看成是环状的!

3.2 设计一个栈,支持min方法,返回栈中的最小值

LeetCode 155

3.3 实现SetOfStacks,由多个栈组成

这实际上是一道OOD(面向对象设计)的题目

3.4 汉诺塔

经典问题了,考虑 n=2的时候,把上面1块放到中间,然后把下面一块移动完成。那么对于n,我们把n-1块移到中间即可

1
2
3
4
5
6
7
8
void moveDisks(int n, tower_t origin, tower_t dest, tower_t buffer) {
if (n <= 0) return;

moveDisks(n-1, origin, buffer, dest); // 先把上面的n-1块放到中间
moveBottom(origin, dest) // 把最底下的盘子直接放过去
moveDisks(n-1, buffer, dest, origin) // 把中间的再放到最后

}

3.5 使用两个栈模拟一个队列

3.6 对栈进行排序,额外的数据只能使用栈

使用简单插入排序,在一个新的栈中保存排序好的数据,从unsorted中弹出以后,不断弹出sorted为新元素找到正确位置

1
2
3
4
5
6
7
8
9
10
11
12
13
stack<int> sortStack(const stack<int>& unsorted) {
stack<int> sorted;
while (!unsorted.empty()) {
int temp = unsorted.top(); // 待插入的新元素
unsorted.pop();
while (!sorted.empty() && sorted.top() > temp) { // 不断弹出,找到合适位置
int big = sorted.top(); sorted.pop();
unsorted.push(big);
}
sorted.push(temp); // 插入新元素
}
return sorted;
}

4.1 检查二叉树是否平衡: 任意两个节点之间的高度差不超过1

4.2 给定一个有向图,找出两个节点之间是否存在一条路径

碰到这类问题,有必要和面试官探讨一下DFS和BFS之间的利弊,例如,DFS实现起来比较简单,只需要简单的递归即可。BFS适合用来查找最短路径。
而DFS在访问临近借点之前可能会深度便利其中一个临近节点

🌲的遍历一定要注意visited数组或者集合,因为树中可能有几个节点指向同一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool search(Graph* graph, Node* start, Node* end) {
queue<Node*> q;
unordered_set<Node*> visited;

q.push(start);
while(!q.empty()) {
auto node = q.pop();

for (auto adj : q.adjs())
if (visited.find(adj) == visited.end())
if (adj == end)
return true;
else
q.push(adj);
}

return false;
}

4.3 给定一个有序数组,元素各不相同且按升序排列,创建一颗高度最小的二叉查找树

LeetCode 108

4.4 给定一棵二叉树,创建层序访问的链表

LeetCode 102

4.5 检查一棵二叉树是否为二叉查找树

LeetCode 98

4.6 找到二叉查找树指定节点的下一个节点(中序后继),假设每个节点都有指向父节点的指针

按照中序遍历,左子树,当前节点,右子树,显然下一个节点应该在右边。也就是右子树中最左边的节点。
考虑没有右子树的情况,如果当前节点是左子节点,下一个节点应该是父节点。如果是右节点,我们继续向上,如果到达了root,显然没有更多节点了。

对于树这种可以分情况的最好先把各种情况想好了,在写代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TreeNode* inorderSucc(TreeNode* n) {
if (!n) return NULL;
if (n->right) {
TreeNode* right = n->right;
while (right->left)
right = right->left;
return right;
} else {
TreeNode* q = n, * parent = q.parent;
while (parent && parent->left != q) { // 找到当前节点可以作为左子节点的父节点
q = parent;
parent = parent->parent;
}
return parent;
}
}

4.7 查找二叉树的公共祖先

LeetCode 236

4.8 又两棵非常大的二叉树:T1 有几百万个节点,T2,有几百个节点。判断T2是否是T1的子树

这道题并没有标准解法。值得和面试官探讨,详见树上的讲解(161页)。

4.9 打印节点数值总和为给定值的路径,路径可以从任意节点开始,任意节点结束

对于一个没有见过的问题,可以先简化,然后在推广。假设路径必须从root开始,那很简单。
如果路径可以从任意节点开始,那么我们需要向上检查是否得到了相符的总和,而不能假定root是起点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void findSum(TreeNode* root, int sum) {
int depth = depth(root);
vector<int> path(depth);
findSum(root, sum, path, 0);
}

void depth(TreeNode* root) {
if (!root) return 0;
return max(depth(root->left), depth(root->right)) + 1;
}

void findSum(TreeNode* root, int sum, vector<int> path, int level) {
if (!root)
return;

path[level] = root->val;
for (int i = level, t= 0; i >= 0; i--) {
t += path[i];
if (t == sum)
print(path, i ,level); // printing out path from i to level
}

findSum(root->left, sum, path, level + 1);
findSum(root->right, sum, path, level + 1);
}

5.1 给定一个数n,和另一个数字m,然后给定区间(i, j),区间保证可以大于m的二进制长度,把m的二进制表示插入到n的区间内

示例:n=100/000/00, m = 101, i = 2, j = 4 -> 100/101/00

  1. 把n中对应位置清零
  2. 把m移动到对应的位置
  3. 合并
1
2
3
4
5
6
7
8
9
10
int merge(int n, int m, int i, int j) {
int left_mask = ~0 << (j+1);
int right_mask = (1 << i) - 1
int mask = left_mask | right_mask;

n &= mask;
m <<= i;

return n | m;
}

5.2 给定一个0和1之间的实数,打印他的二进制表示,如果32位以内无法表示,打印error

我们知道 (0.101)2 = 1 * 2^-1 + 0 * 2^-2 + 1 * 2^-3,我们只要让这个数字不断的乘2,然后看它是否大于1,然后就可以得到第一位是不是1了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string printBinary(double num) {
if (num >= 1 || num <= 0)
return "error";

string result;
result += ".";
while (num > 0) {
if (result.size() >= 32)
return "error";
num *= 2;
if (num >= 1) {
result += "1";
num -= 1;
} else {
result += "0";
}
}

return result;
}

5.3 给定一个正整数,找出和其二进制表示中一的数字相同的数字,并且最接近,一共两个

我们需要把某个0反转为1,把某个1反转为0。
0 -> 1在1->0 左边,数字变大,在右边数字变小。
如果想变大,反转的0需要在1的左边。

把p位置1;把0到p之间请0;在添加ending1 - 1个1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int getNext(int n) {
int c = n, ending0 = 0, ending1 = 0;
while ((c & 1 == 0) && c != 0) {
ending0++;
c >>= 1;
}

while (c & 1) {
ending1++;
c >>= 1;
}

return n + (1 << ending0) + (1 << (ending1 - 1)) - 1;
}

把位p值0;把位p右边的位值1,再把0到ending0-1置0

1
2
3
4
5
6
7
8
9
10
11
12
13
int getPrev(int n) {
int c = n, ending0 = 0, ending1 = 0;
while (c & 1) {
ending1++;
c >>= 1;
}
if (c == 0) return -1;
while ((c & 1) == 0 && c != 0) {
ending0++;
c >>= 1;
}
return n - (1 << ending1) - (1 << (ending0 - 1)) + 1;
}

5.4 解释n & (n-10) == 0

LeetCode 231

5.5 A和B之间有多少位不相同/需要改变多少位,才能把A变成B

使用XOR找出不同的位,然后统计1的个位数。需要注意的是不同的题目

1
2
3
4
5
6
7
8
int bitSwapRequired(int a, int b) {
int diff = a ^ b, count = 0;
while (diff) {
diff &= diff - 1;
count++;
}
return count;
}

5.6 交换一个整数的奇数位和偶数位

这道题很有趣,选取特殊的掩码即可

1
2
3
4
5
6
// 考虑32bit int
int32_t swapBits(int32_t x) {
int32_t odd_bits = x & 0xAAAAAAAA; // 0xAA as 10101010
int32_t even_bits = x & 0x55555555; // 0x55 as 01010101
return (odd_bits >> 1) | (even_bits << 1);
}

5.8 单色屏幕存贮在一维字节数组中,每个字节存储八个像素,屏幕宽度为w px,绘制从x1到达x2的水平线

显然可以逐bit设定,然而这样是拿不到offer的。更好的做法是逐字节设定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void drawHorizentalLine(uint8_t * screen, int width, int x1, int x2, int y) {

int start_offset = x1 % 8;
int start_full_byte = x1 / 8; // x1 所在字节
if (start_offset != 0)
start_full_byte++;

int end_offset = x2 % 8;
int end_full_byte = x2 / 8; // x2 所在字节
if (end_offset != 7)
end_full_byte--;

// 逐字节设定
for (int i = start_full_byte; i <= end_full_byte; i++)
screen[width / 8 * y + i] = (uint8_t)0xff;

uint8_t start_mask = (uint8_t) (0xff >> start_offset);
uint8_t end_mast = (uint8_t) ~(0xff >> end_offset + 1);

if ((x1 / 8) == (x2 / 8)) {
uint8_t mask = (uint8_t)(start_mask & end_mask);
screen[(width / 8) * y + x1 / 8] |= mask;
} else {
if (start_offset != 0) {
int byte_number = (width / 8) * y + start_full_byte - 1;
screen[byte_number] |= start_mask;
}
if (end_offset != 7) {
int byte_number = (width / 8) * y + end_full_byte + 1;
screen[byte_number] |= end_mask;
}
}

6.1 给定直角坐标系的两条线,确定他们会不会相交

我们知道在二维平面上两条线的关系不外乎:平行,相交,重合。问题是两条线重合算不算相交呢,需要问清楚。
对于两条线如何表示,这又是面向对象设计的问题,需要讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Line {
private:
static double EPSILON;
double m_slope; // 斜率
double m_y_intercept; // y轴交点

public:
Line(double s, double y): m_slope(s), m_y_intercept(y) {};
// 重合视作相交
bool intersect(const Line& other) {
return abs(slope() - other.slope()) > EPSILON || // 斜率不同
abs(y_intercept() - other.y_intercept()) < EPSILON; // y轴交点相同
}
double slope() {return m_slope;}
double y_intercept() {return m_y_intercept;}
};

double Line::EPSILON = 0.00001;

遇到这类问题,务必:

  1. 多问,面试官可能故意模糊问题
  2. 仔细设计数据结构,权衡利弊,和面试官讨论
  3. 千万不要用==判定浮点数

6.2 只使用加号实现减法和乘除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int neg(int a) {
int result = 0;
int d = a < 0 ? 1 : -1;
while (a) {
result += d;
a += d;
}
return result;
}

int abs(int a) {
return a > 0 ? a : neg(a);
}

int minus(int a, int b) {
return a + neg(b);
}

int multiply(int a, int b) {
int sign = (a > 0) == (b > 0) ? 1 : -1;
a = abs(a);
b = abs(b);
int result = 0;
while (b--)
result += a;
return sign == 1 ? result : neg(result);
}

int devide(int a, int b) {
// see leetcode
}

6.3 找出第k个丑数

LeetCode 264

7.1 小孩上楼梯,楼梯有n阶,小孩可以一次上1,2,3步,请问一共有多少种方法

 注意如果只能1或2就是斐波那契数列。

1
2
3
4
5
6
7
8
9
// 递归
int countSteps(int n) {
static vector<int> steps(1000, 1);
if (n < 0)
return 0;
if (n > 1 && steps[n] == 1)
steps[n] = countSteps(n -1) + countSteps(n - 2) + countSteps(n - 3);
return steps[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 迭代
int countSteps(int n) {
int n3 = 1; // starts from n = 0
int n2 = 1; // starts from n = 1
int n1 = 2; // starts from n = 2

if (n < 0)
return 0;
if (n == 0 || n == 1)
return 1;
int steps = 0;
for (int i = 3; i <= n; i++) {
steps = n3 + n2 + n1;
n3 = n2;
n2 = n1;
n1 = steps;
}
return steps;
}

8.1 设计一种算法,机器人只能向右向下移动,从(0, 0)移动到(x, y)有几种走法

LeetCode 62 63

9.1 在有序数组A[0…n-1]中存在A[i] == i,找出该数字。如果存在重复值,又该如何做

1
2
3
4
5
6
7
8
9
10
11
12
13
int magic(int* A, n) {
int left = 0; right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] == mid)
return mid;
else if (A[mid] < mid)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}

9.2 返回一个集合的所有子集

LeetCode 78

9.3 全排列

LeetCode

9.4 生成n对括号的全部有效集合

LeetCode

9.5 实现填充颜色功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void paintFill(vector<vector<int>> screen, int x, int y, int color) {
if (screen[y][x] == color)
return;
paintFill(screen, int x, int y, screen[y][x], int color);
}

void paintFill(vector<vector<int>> screen, int x, int y, int start, int color) {
if (x < 0 || x >= screen[0].size() || y < 0 || y >= screen.size())
return;
if (screen[y][x] == start) {
screen[y][x] == color;
paintFill(screen, int x-1, int y, start, color);
paintFill(screen, x+1, y, start, color);
paintFill(screen, x, y+1, start, color);
paintFill(screen, x, y-1, start, color);
}
}

9.6 给定数量不限的硬币,编写代码计算有几种表示方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> makeChange(vector<int> coins, int target) {
vector<vector<int>> result;
vector<int> solution(coins.size(), 0)
make(result, coins, solution, 0, target);
return result;
}

void make(vector<vector<int>>& result, vector<int>& coins, vector<int> solution, int start, int target) {
if (target <= 0 || start >= coins.size()) {
if (target == 0)
result.push_back(solution);
return;
}
for (int i = 0; i *coins[start] < target ; i++) {
solution[start] = i;
make(result, coins, solution, start + 1, target - i * coins[start]);
}
}

9.7 N-Queen问题

LeetCode

9.8 给你一堆箱子,上面的箱子的长宽高要求小于下面的箱子,实现一个方法,搭出最高的箱子

10.1 合并两个有序数组

LeetCode 88

11.1 对一个字符串数组排序,把变位词(Anagram)放在一起

LeetCode 49

11.2 在已经被旋转过的排序数组中,查找元素

LeetCode 81

11.3 有一个20GB的文件,每行一个字符串,如何排序

20GB暗示无法放入内存中,把文件分块后,分别载入内存中,采用归并排序

12.1 使用 C++ 写个方法,打印输入文件的最后 K 行

使用循环数组,容量设为 K,同时记录当前的最早元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void printLastKLines(char* filename) {
const int K = 10;
ifstream file(filename);
string lines[K];
int size = 0;

while (file.good())
getline(file, lines[size++ % K];

int start = size > K ? (size % K) : 0;
int count = min(K, size);

for (int i = 0; i < count; i++)
cout << lines[(start + i) % K] << endl;
}

12.2 编写malloc_aligned

12.3 malloc2d函数,分配二维数组,返回int**可以通过a[i][j]访问,并且尽量少调用malloc

前面rows大小的区域用作存储指针,后面存储数据。

hhh|ddddd|ddddd|ddddd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void** malloc2d(int rows, int cols) {
int header = rows * sizeof(void*);
void** ptr = (void**)malloc(header + rows * cols);
if (!ptr)
return NULL;
void* buf = (void*)(rawptr + rows);
for (int i = 0; i < rows; i++)
ptr[i] = buf + i * cols;
return ptr;
}

void free2d(void** ptr) {
void* p = void* p;
free(p);
}

12.4 不用中间变量,直接交换两个数字

想像把 a 和 b 都放在数轴上,假设 a0,b0分别是初值,那么有 diff = a - b。我们把
diff 保存在 a 中,然后 b = b0 + diff 也就是 a0 ,而再另 a = b - diff,也就是 b0。

1
2
3
4
5
void swap(int& a, int& b) {
a = a - b;
b = b + a;
a = b - a;
}

更巧妙的是,我们还可以使用异或 XOR 在解。假设 a = a0 ^ b0,那么 b = a ^ b0 = a0 ^ b0 ^ b0 = a0,然后 a = a ^ b = a0 ^ b0 ^ a0 = b0。完美解决!
值得注意的是,因为使用异或不考虑变量的实际类型,只是粗暴地按 bit 位交换,因此适用于各种类型。不过值得注意的是千万不要用这种方法去交换变量的值,当x==y的时候会有灾难性后果。

1
2
3
4
5
6
template<typename T>
void swap(T& a, T& b) {
a ^= b;
b ^= a;
a ^= b;
}

13.1 n! 结尾有多少个零

LeetCode 172

13.2 找出两个数字中较大的一个,但不得使用判断语句

判断a>b就是判断a-b的正负号,显然我们可以使用bit运算

1
2
3
4
5
6
7
int flip(int a) { // flip last bit
return 1 ^ a;
}

int sign(int a) {
return flip((a >> 31) & 0x1);
}

13.3 把数字转换为英文单词

13.4 把数字转换为汉语句子

13.5 数组最大序列和

LeetCode 53

13.6 给定产生数字概率相同的rand5(),实现一个方法rand7(),要求产生每个数字的概率相同

扩大rand5产生随机数的范围,然后对舍去一定范围的数字,对剩下的数字取模,虽然这样会导致调用次数不固定,但实现了效果
对于randx,扩大范围的方法是 x * randx() + randx()

1
2
3
4
5
6
7
int rand7() {
while (1) {
int num = 5 * rand5() + rand5();
if (num < 21)
return num % 7;
}
}

该问题可以拓展到对于 x < y,由randx() 构造 randy()

13.7 在数组中找到两个数字,是的他们的和为指定的数字

LeetCode 1

13.8 把二叉树转化为双向链表

先把二叉树变成一个环形链表,然后再从头部解开即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

void concat(struct tree_node* x, struct tree_node* y) {
x->right = y;
y->left = x;
}

struct tree_node* convert_circular(struct tree_node* root) {
if (!root)
return NULL;
struct tree_node* left = convert_circular(root->left);
struct tree_node* right = convert_circular(root->right);

if (!left && !right) {
root->left = root;
root->right = root;
return root;
}

struct tree_node* tail_right = right ? right->left : NULL;

// 把左边添加到根部
if (!left)
concat(right->left, root);
else
concat(left->left, root);

// 把右边添加到根部
if (!right)
concat(root, left);
else
concat(root, right);

// 把右边和左边链接
if (left && right)
concat(tail_right, left);

return left ? left : root;
}

struct tree_node* convert(struct tree_node* root) {
struct tree_node* head = convert_circular(root);
head->left->right = NULL;
head->left = NULL;
return head;
}

14.2 实现加法

显然是使用位运算。

1
2
3
4
5
6
7
8
int add(int a, int b) {
while (b) {
int sum = a ^ b;
int carry = (a & b) << 1;
a = sum, b = carry;
}
return a;
}

15.2 完美洗牌,使得一副牌中任意一种排列出现的概率都相等

显然全排列是n!个,那么我们保证每一个全排列都可能出现就好了。

1
2
3
4
5
6
void shuffle(int* A, int n) {
for (int i = 0; i < n; i++) {
int k = rand(i);
swap(A[k], A[i]);
}
}

16.1 从n个数组中选出m个,要求被选中概率一样

1
2
3
4
vector<int> pink_k(vector<int> nums, int k) {
vector<int> result(k);

}

16.2 小于 n 的数字中出现2的个数

16.3 矩阵链乘法问题

16.4 判断是否是合法地出栈序列

参考

16.5 二叉树的非递归遍历

参考






三、树的遍历

树的递归遍历都非常简单,但是非递归遍历有时候不是很简单。一般做题的时候直接写递归版就行了,
但是对于三个基础的遍历方法,有时候会要求写迭代版本,基本就是花式用栈就行了。

前序遍历

递归版

1
2
3
4
5
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
return [root.val, *self.preorderTraversal(root.left), *self.preorderTraversal(root.right)]

非递归版

使用栈做了一个顺序的反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
ans = []
stack = []
stack.append(root)
while stack:
node = stack.pop()
ans.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return ans

中序遍历

递归版

1
2
3
4
5
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
return [*self.inorderTraversal(root.left), root.val, *self.inorderTraversal(root.right)]

非递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
ans = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
left = stack.pop()
ans.append(left.val)
if left.right:
node = left.right
return ans

后续遍历

LeetCode 145

递归版

1
2
3
4
5
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
return [*self.postorderTraversal(root.left), *self.postorderTraversal(root.right), root.val]

非递归版

这个方法还是有点 trick 的,类似于前序遍历,但是把左右子树反过来了,最后再翻转一遍,就变成
了后序遍历。

1
2
3
  1
/ \
2 3

比如:前序遍历是 123, 现在这种遍历方式是 132, 在翻转一次正好是 231, 也就是后续遍历了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
ans = []
stack = [root]
while stack:
node = stack.pop()
ans.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return list(reversed(ans))

参考资料

  1. https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/





四、LeetCode 突击手册

一共定义了几个标签,可以通过 Ctrl+F/Cmd+F 搜索这些标签还快速浏览相同的题目。

标签:#hash #backtracking #slidewindow #stack #queue #pointers

1 从数组中找出两个数字使得他们的和是给定的数字

tags: #hash

使用一个散列,存储数字和他对应的索引。然后遍历数组,如果另一半在散列当中,那么返回
这两个数的索引,程序结束;如果不在,把当前数字加入到散列中。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
vector<int> result(2);
for (int i = 0; i != nums.size(); ++i) {
int reminder = target - nums[i];
if (hash.find(reminder) != hash.end()) {
result[0] = hash[reminder] + 1;
result[1] = i + 1;
return result;
}
hash[nums[i]] = i;
}
return result;
}
Python 解答
1
2
3
4
5
6
7
8
9
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, num in enumerate(nums):
if target - num in seen:
return [seen[target-num], i]
else:
seen[num] = i
return [-1, -1]
rust 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
use std::collections::HashMap;

impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::with_capacity(nums.len());
for (idx, num) in nums.iter().enumerate() {
match map.get(&(target - num)) {
None => {map.insert(num, idx);},
Some(sub_idx) => {return vec![*sub_idx as i32, idx as i32]; }
}
}
vec! []
}
}
go 解答
1
2
3
4
5
6
7
8
9
10
11
12
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for index, num := range nums {
last_index, ok := m[num]
if ok {
return []int{last_index, index}
} else {
m[target - num] = index
}
}
return []int{-1, -1}
}

Follow up: 如果数组是已经排序的呢?

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
sort(nums.begin(), nums.end()) // 假设已经排序,只有一个结果
pair<int> twoSum(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int s = nums[left] + nums[right];
if (s == target)
return make_pair(left, right);
else if (s < sum)
left++;
else
right--;
}
}

2 给两个列表,数字在其中按低位到高位存储,求他们的和

直接迭代遍历数组,考察细节操作。注意 dummy head 的使用。

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy, *p = &dummy;
int carry = 0;
// 注意最后如果有 carry 的话,需要再生成一个节点
while (l1 || l2 || carry) {
int v1 = l1 ? l1->val: 0;
int v2 = l2 ? l2->val: 0;
int v = v1 + v2 + carry;
p->next = malloc(sizeof(struct ListNode));
p = p->next;
p->val = v % 10;
p->next = NULL;
carry = v / 10;

l1 = l1 ? l1->next: NULL;
l2 = l2 ? l2->next: NULL;
}
return dummy.next;
}
C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
int shift = 0;
ListNode* result = new ListNode(0);
ListNode* p = result;
while (l1 != NULL || l2 != NULL) {
ListNode* newNode = new ListNode(0);
int v1 = l1 != NULL ? l1->val : 0;
int v2 = l2 != NULL ? l2->val : 0;
newNode->val = v1 + v2 + shift;
if (newNode->val > 9) {
newNode->val -= 10;
shift = 1;
} else {
shift = 0;
}
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
p->next = newNode;
p = p->next;
}
// 注意最后多余的一个进位处理
if (shift == 1) {
p->next = new ListNode(1);
}
return result->next;
}
};
rust 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
impl Solution {
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let (mut l1, mut l2) = (l1, l2);
let mut dummy = Box<ListNode::new(0)>;
let mut carry = 0;
let mut p = dummy;
while l1.is_some() || l2.is_some() || carry != 0 {
match l1, l2{
Some(a), Some(b) => {
let mut v = a + b + carry;
l1 = l1.next();
l2 = l2.next();
},
Some(a), None => {
let mut v = a + carry;
l1 = l1.next();
},
None, Some(b) => {
let mut v = b + carry;
l2 = l2.next();
},
None, None => {
}
}
p.next = Some(Box<ListNode::new(v)>);
p = p.next;
p.val = v % 10;
carry = v / 10;
}
dummy.next
}
}
Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(-1)
p = dummy
carry = 0
while l1 or l2 or carry:
if l1:
v1 = l1.val
l1 = l1.next
else:
v1 = 0
if l2:
v2 = l2.val
l2 = l2.next
else:
v2 = 0
v = v1 + v2 + carry # 别忘了这里
if v >= 10:
carry = 1
v -= 10
else:
carry = 0
p.next = ListNode(v)
p = p.next
return dummy.next

3 最长不重复子串

tags: #slidewindow

滑动窗口解决

注意,当字符有限的时候,比如限定为 ASCII 字符,可以使用一个数组代替 Hash。

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLongestSubstring(char* s) {
int indices[256];
for (int i = 0; i < 256; i++) // init the array, memset can only be used for char
indices[i] = -1;
int left = 0;
int longest = 0;

for (int i = 0; s[i] != '\0'; i++) {
left = max(left, indices[s[i]] + 1); // 考虑新加入字符后对左边界的影响
indices[s[i]] = i; // 更新元素上次出现位置
longest = max(longest, i - left + 1); // 应用动态规划
}
return longest;
}
Python 解答
1
2
3
4
5
6
7
8
9
10
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
last_seen = {}
ans = 0
lo = 0
for i, c in enumerate(s):
lo = max(lo, last_seen.get(c, -1) + 1) # 更新下边界
last_seen[c] = i
ans = max(ans, i - lo + 1)
return ans

4 找到两个排序数组的中位数

解法参见这里

使用两个数字 i 和 j, 分别作为 AB 的分隔元素,把 AB 分成两份,比如
A[0..i], B[0..j]A[i, m], B[j, n],这样我们只需要下面两个条件就可以了:

  • i+j = m-i + n-j, 也就是 i+j = (m+n)/2
  • B[j-1] <= A[i] && A[i-1] <= B[j], B 的前一半元素小于 A 的分隔符,A 的前一半元素小于 B 的分隔符

这时候我们就得到了 A[i] 就是我们的中位数,或者之一。 i 的初始值在 0 到 m 之间,
然后我们二分搜索 i = (imin + imax) / 2, j = mid - i

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
double findMedianSortedArrays(int* A, int m, int* B, int n) {
if (m > n) return findMedianSortedArrays(B, n, A, m);
int imin = 0, imax = m, i, j, num1, mid = (m + n + 1) >> 1, num2;
while (imin <= imax) {
i = (imin + imax) // 2;
j = mid - i;
if (i < m && j > 0 && B[j-1] > A[i]) { // B 中的数字偏大
imin = i + 1;
} else if (i > 0 && j < n && B[j] < A[i-1]) { // A 中的数字偏大
imax = i - 1;
} else {
if (i == 0)
num1 = B[j-1];
else if (j == 0)
num1 = A[i - 1];
else
num1 = max(A[i-1],B[j-1]); // 普通情况
break;
}
}
if ((m + n) & 0x1) // odd
return num1;
if (i == m)
num2 = B[j];
else if (j == n)
num2 = A[i];
else
num2 = min(A[i], B[j]); // 普通情况
return (num1 + num2) / 2.0; // 注意整数除法
}

5 最长回文子串

  1. 以某个元素为中心,向两边展开,注意处理奇数和偶数两种情况
  2. Manacher 算法,参见这里
Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def longestPalindrome(self, s: str) -> str:
ans = ""
length = 0
for i in range(len(s)):
j = 0
# 奇数长度回文子串
while i - j >= 0 and i + j < len(s) and s[i-j] == s[i+j]:
if j * 2 + 1 > length:
length = j * 2 + 1
ans = s[i-j:i+j+1]
j += 1
j = 0
# 偶数长度回文子串
while i - j >= 0 and i + j + 1 < len(s) and s[i-j] == s[i+j+1]:
if j * 2 + 2 > length:
length = j * 2 + 2
ans = s[i-j:i+j+2]
j += 1
return ans
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
char* longestPalindrome(char* s) {
if (!s) return NULL;

int length = 0; // length of the longest palindromic string
int start = -1; // start of the lonest palidromic string

int len = strlen(s);
for (int i = 0; i < len; i++) {

// 奇数长度的回文子串
for (int j = 0; (i - j >= 0) && (i + j < len); j++) {
if (s[i - j] != s[i + j])
break;
if (j * 2 + 1 > length) {
length = j * 2 + 1;
start = i - j;
}
}

// 偶数长度的回文子串
for (int j = 0; (i - j >= 0) && (i + j + 1 < len); j++) {
if (s[i - j] != s[i + j + 1])
break;
if (j * 2 + 2 > length) {
length = j * 2 + 2;
start = i - j;
}
}
}

char* result = malloc(sizeof(char) * length + 1);
strncpy(result, s + start, length);
result[length] = 0;

return result;
}

6 ZigZag 字符串,把字符串掰弯,然后再按行输出

考察数学,找出规律,所以实际上并不是 Z 子形,而是由 V 组成的,然后组合按行号重构后的字符串即可。

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 这个方法不容易理解,建议看 Python 的
char* convert(char* s, int numRows) {
int len = strlen(s);
if (!s || numRows <= 1 || len < numRows) return s; // no need to convert

char* zigzag = malloc(sizeof(char) * (len + 1));
int cur = 0;

for (int i = 0; i < numRows; i++) {
for (int j = i; j < len; j += 2 * (numRows - 1)) { // 每个 v 字型长度
zigzag[cur++] = s[j];
if (i != 0 && i != numRows - 1) { // 中间行有斜线
int t = j + 2 * (numRows - 1) - 2 * i; // V 的第二笔
if (t < len)
zigzag[cur++] = s[t];
}
}
}
zigzag[cur] = '\0';
return zigzag;
}
Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows <= 1 or len(s) <= numRows: # 没有这个条件会超时
return s
interval = 2 * numRows - 2
ans = []
# 第一行
j = 0
while j < len(s):
ans.append(s[j])
j += interval
# 中间行
for i in range(1, numRows-1):
j = 0
while j < len(s):
if i + j < len(s):
ans.append(s[i+j])
if interval - i + j < len(s): # 一定要注意这里的索引
ans.append(s[interval - i + j])
j += interval
# 最后一行
j = numRows - 1
while j < len(s):
ans.append(s[j])
j += interval
return "".join(ans)

7 翻转数字,溢出返回 0

注意溢出

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
int reverse(int x) {
if (x == INT_MIN) return 0;
if (x < 0) return -reverse(-x);

long result = 0;
while (x) {
result = result * 10 + x % 10;
x /= 10;
}

return result > INT_MAX ? 0 : result;
}
Python 解答
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def reverse(self, x: int) -> int:
sign = 1 if x >= 0 else -1
x *= sign
y = 0
while x > 0:
y = y * 10 + x % 10
x //= 10
if y > 2**31:
return 0
return y * sign

8 实现 atoi

这道题考察各种细节,注意各种特殊情况:

  1. 首先过滤空格
  2. 判定符号,符号只能出现一次
  3. 是否溢出,溢出返回 INT_MAX 或者 INT_MIN
Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def myAtoi(self, s: str) -> int:
s = s.lstrip()
if not s:
return 0
sign = 1
ans = 0
i = 0
if s[i] == "-":
sign = -1
i += 1
elif s[i] == "+":
i += 1
while i < len(s) and s[i].isdigit():
ans = ans * 10 + ord(s[i]) - ord("0")
i += 1
ans *= sign
return max(min(ans, 2**31-1), - 2 ** 31)
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int myAtoi(char* str) {
if (!str) return 0;
int sign = 1;
int result = 0;

// discarding spaces
while (isspace(*str))
str++;

// determining sign
if (*str == '-' || *str == '+') {
if (*str == '-') sign = -1;
if (*str == '+') sign = 1;
str++;
}

// constructing integer
while (isdigit(*str)) {
// handling overflow
if (result > INT_MAX / 10 || result == INT_MAX / 10 && *str - '0' > INT_MAX % 10)
return sign > 0 ? INT_MAX : INT_MIN;
result = *str - '0' + result * 10;
str++;
}

return result * sign;
}

9 是否是回文数字

限定不能用额外空间,所以直接把 x 取余得到的数字作为一个反向作为一个新的数字

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
if x != 0 and x % 10 == 0:
return False
y = 0
# 回文走到一半就行了,没必要完全翻转过来
while x > y:
y = y * 10 + x % 10
x //= 10
return x == y or x == y // 10
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
bool isPalindrome(int x) {

// tricky here, for x == k * 10^j
if (x < 0 || x && (x % 10 == 0)) return false;
int y = 0;
while (x > y) {
y = y * 10 + x % 10;
x /= 10;
}

return x == y || x == y / 10; // 注意 x 可能是奇数长度也可能是偶数
}

10 正则表达式

实现正则表达式,只需要实现.代表任意字符,*代表任意重复。只需要特殊处理*
如果遇到了*,贪婪地向后匹配。和通配符的不同之处在于,正则表达式需要两个字母
组成模式,*是对前一个字母的修饰。

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isMatch(char* s, char* p) {
for (char c = *p; c != 0; s++, c = *p) {
// if next char in pattern is not *
if (*(p+1) != '*')
p++;
// if we got an *, check if we can skip `.*` or `x*`
else if (isMatch(s, p + 2))
return true;

// s ends or p and s differs
if (*s == 0 || c != '.' && c != *s)
return false;
}
return *s == 0;
}

11 盛最多水的容器

从左右向中间逼近,如果有更大的就更新。简单的一道双指针题目,别想太多。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int result = 0;
while (left < right) {
water = min(height[left], height[right]) * (right - left)
result = max(result, water);
if (height[left] < height[right])
left++;
else
right--;
}
return result;
}
Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def maxArea(self, height: List[int]) -> int:
lo = 0
hi = len(height) - 1
ans = 0
while lo < hi:
water = min(height[lo], height[hi]) * (hi - lo)
ans = max(ans, water)
if height[lo] < height[hi]:
lo += 1
else:
hi -= 1
return ans

12 十进制转换为罗马数字

直接按每位把罗马数字转换出来在拼接就好了,使用 C 的话,拼接字符串很麻烦。

Python 解答
1
2
3
4
5
6
7
class Solution:
def intToRoman(self, x: int) -> str:
thousands = ["", "M", "MM", "MMM"]
hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
return thousands[x//1000] + hundreds[x%1000//100] + tens[x%100//10] + ones[x%10]
C++ 解答
1
2
3
4
5
6
7
8
string intToRoman(int num) {
// note, the leading empty string is the trick here
string thousands[] = {"", "M", "MM", "MMM"};
string handreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
string tens[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
string ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return thousands[num / 1000] + handreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];
}
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
char *intToRoman(int num) {
int digits[4] = {0};
char* romans = (char*)malloc(sizeof(char));
char* cursor = romans;
// if num = 1234, then
// digits = {1, 2, 3, 4};
int base = 1000;
for (int i = 0; i < 4; i++) {
digits[i] = num / base;
num = num % base;
base /= 10;
}
doRoman(digits[0], '_', '_', 'M', &cursor); // '_' can be anything
doRoman(digits[1], 'M', 'D', 'C', &cursor);
doRoman(digits[2], 'C', 'L', 'X', &cursor);
doRoman(digits[3], 'X', 'V', 'I', &cursor);
*cursor = '\0';
return romans;
}

void doRoman(int number, char ten, char five, char one, char** str) {

switch (number) {
case 9:
(*str)[0] = one;
(*str)[1] = ten;
(*str) += 2;
break;
case 8:
(*str)[0] = five;
(*str)[1] = one;
(*str)[2] = one;
(*str)[3] = one;
(*str) += 4;
break;
case 7:
(*str)[0] = five;
(*str)[1] = one;
(*str)[2] = one;
(*str) += 3;
break;
case 6:
(*str)[0] = five;
(*str)[1] = one;
(*str) += 2;
break;
case 5:
(*str)[0] = five;
(*str) += 1;
break;
case 4:
(*str)[0] = one;
(*str)[1] = five;
(*str) += 2;
break;
case 3:
(*str)[0] = one;
(*str)[1] = one;
(*str)[2] = one;
(*str) += 3;
break;
case 2:
(*str)[0] = one;
(*str)[1] = one;
(*str) += 2;
break;
case 1:
(*str)[0] = one;
(*str) += 1;
break;
case 0:
default:
break;
}
}

13 罗马数字转为十进制

主要是当前一个数字小于后一个数字的时候,需要添加的是后一个数和前一个数字的差。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def romanToInt(self, s: str) -> int:
vals = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}
ans = 0
i = 0
while i < len(s):
if i+1<len(s) and vals[s[i]] < vals[s[i+1]]:
ans += vals[s[i+1]] - vals[s[i]]
i += 2
else:
ans += vals[s[i]]
i += 1
return ans
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// acts like a dict or map
int getVal(char c) {
switch (c) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
}
}

int romanToInt(char* s) {
int result = 0;
for (int i = 0; s[i] != 0; ) {
if (getVal(s[i]) < getVal(s[i+1]))
result += getVal(s[i+1]) - getVal(s[i]), i += 2;
else
result += getVal(s[i]), i++;
}
return result;
}

14 最长公共前缀

纵向扫描,从头到尾,如果不一致,返回当前子串即可。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
if len(strs) == 1:
return strs[0]
minlen = min([len(str) for str in strs])
for i in range(minlen):
for j in range(1, len(strs)):
if strs[j][i] != strs[0][i]:
return strs[0][:i]
return strs[0][:minlen]
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 纵向扫描
char* longestCommonPrefix(char** strs, int strsSize) {
if (!strs || !strs[0]) return "";
if (strsSize == 1) return strs[0];
int len = strlen(strs[0]);

for (int i = 0; i < len; i++) {
for (int j = 1; j < strsSize; j++) {
if (strs[j][i] != strs[0][i]) {
strs[0][i] = '\0';
return strs[0];
}
}
}
return strs[0];
}

15 从数组中找出三个数使得他们的和是 0

首先把数组排序,然后使用类似 two sum 的方法做就好了。做这种数组题的套路就是实在不行排个
序。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
nums.sort()
ans = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
k = len(nums) - 1
j = i + 1
while j < k:
sum = nums[i] + nums[j] + nums[k]
if sum > 0:
k -= 1
elif sum < 0:
j += 1
else:
ans.append([nums[i], nums[j], nums[k]])
while j < k and nums[j] == nums[j+1]:
j += 1
while j < k and nums[k] == nums[k-1]:
k -= 1
j += 1
k -= 1
return ans
C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i-1])
continue;
int k = nums.size() - 1;
int j = i + 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] > 0)
k--;
else if (nums[i] + nums[j] + nums[k] < 0)
j++;
else {
result.push_back({nums[i], nums[j], nums[k]});
// skipping duplicates
while (j < k && nums[k] == nums[k - 1])
k--;
while (j < k && nums[j] == nums[j + 1])
j++;
k--; // 别忘了这里,还要继续寻找下一组
j++;
}
}
}
return result;
}

16 在数组中找到三个数字使得他们得和尽可能的接近给定数字,假设结果唯一

和上一题解法类似,在 http://stackoverflow.com/q/2070359 有详尽解释

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
if len(nums) < 3:
return []
nums.sort()
ans = nums[0] + nums[1] + nums[2]
for i in range(len(nums)):
j = i + 1
k = len(nums) - 1
while j < k:
sum = nums[i] + nums[j] + nums[k]
if sum == target:
return target
elif abs(target-sum) < abs(target-ans):
ans = sum
else:
if sum > target:
k -= 1
else:
j += 1
return ans
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int cmp(int* a, int* b) {
return *a - *b;
}

int threeSumClosest(int* nums, int numsSize, int target) {
if (numsSize <= 3)
return nums[0] + nums[1] + nums[2];
qsort(nums, numsSize, sizeof(int), cmp);

int result = nums[0] + nums[1] +nums[2];
for (int i = 0; i < numsSize; i++) {
int j = i + 1;
int k = numsSize - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == target)
return target;
if (abs(target - sum) < abs(target - result))
result = sum;
if (sum > target)
k--;
else
j++;
}
}
return result;
}

17 生成电话键盘按键数字对应的所有可能的字符串,不限制返回结果的顺序

tags: #backtracking

键盘

递归:

这道题是一道典型的,最简单的深度优先遍历,生成所有可能解的问题。

迭代:

遍历数字,设当前结果为{a, b, c}, 下一个数字是3, 找出对应的字母{d, e, f}, 则新的结果是

1
{ a + {def}, b + {def}, c + {def}}

然后把新获得的数组作为下一轮的初始数组。最开始时,使用空数组开始。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
c2n = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
def dfs(combination, next_digits):
if not next_digits:
ans.append(combination)
return
for char in c2n[next_digits[0]]:
dfs(combination + char, next_digits[1:])
if not digits:
return []
ans = []
dfs("", digits)
return ans
C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// iterative
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) return vector<string> {};
string mapping[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> combinations(1, ""); // 注意使用空字符串作为种子

for (int i = 0; i < digits.size(); i++) {
int digit = digits[i] - '0';
if (mapping[digit].empty())
continue;
vector<string> temp;
for (auto& c : mapping[digit])
for (auto& combination : combinations)
temp.push_back(combination + c);
swap(combinations, temp);
}
return combinations;
}

还可以使用深度优先的搜索方法

追问:如何通过用户按的数字来查找是否有对应的单词呢

  1. 通过把所有的单词计算出来,然后查询哪个是合法的,查询可以使用 Trie
  2. 通过把已经有的单词字典转换为数字字典,然后通过数字序列查询可能的单词组合。

18 4Sum

tags: #backtracking

其实可以用 深度优先搜索的方式直接解答 nSum

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
return self.nSum(nums, target, 4)

def nSum(self, nums, target, n):
def dfs(pos: int, cur: List[int], n: int, target: int):
if n == 2:
j = pos
k = len(nums) - 1
while j < k:
sum = nums[j] + nums[k]
if sum < target:
j += 1
elif sum > target:
k -= 1
else:
solution = cur[:] + [nums[j], nums[k]]
ans.append(solution)
while j < k and nums[j] == nums[j+1]:
j += 1
while j < k and nums[k] == nums[k-1]:
k -= 1
j += 1
k -= 1
return
i = pos
while i < len(nums) - n + 1:
# 剪枝的一种情况
if nums[i] * n > target or nums[-1] * n < target:
break
# 排除重复数字
if i > pos and nums[i] == nums[i-1]:
i += 1
continue
cur.append(nums[i])
dfs(i+1, cur, n-1, target-nums[i])
cur.pop()
i += 1
ans = []
nums.sort()
dfs(0, [], n, target)
return ans

下面的 C++ 解法是一个传统解法

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
int n = nums.size();

if (n < 4) return result;

sort(nums.begin(), nums.end());
unordered_map<int, vector<pair<int, int>>> hash;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
hash[nums[i]+nums[j]].push_back(make_pair(i,j));
}
}

for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i-1])
continue;
for (int j = i+1; j < n; j++) {
if (j > i + 1 && nums[j] == nums[j-1])
continue;
int re = target - nums[i] - nums[j];
if (hash.find(re) != hash.end()) {
for (auto match : hash[re]) {
int k = match.first, l = match.second;
if (k > j) {
if (!result.empty()
&& result.back()[0] == nums[i] && result.back()[1] == nums[j]
&& result.back()[2] == nums[k] && result.back()[3] == nums[l])
continue;
result.push_back({nums[i], nums[j], nums[k], nums[l]});
}
}
}
}
}
return result;
}

19 删除链表中倒数第 k 的节点

tags: #pointers

双指针经典题目,一个快指针先走 k 步,另一个慢指针再出发,注意链表长度小于 k 时。

注意:LeetCode 给定的 n 都是有效地,但要求返回头指针,如果头指针被删除需要额外注意,因此采用 dummy head

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
p = dummy
while n >= 0:
p = p.next
n -= 1
q = dummy
while p:
q = q.next
p = p.next
q.next = q.next.next
return dummy.next
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode dummy, *fast, *slow;
dummy.next = fast = head;
slow = &dummy;

while (n--)
fast = fast->next;
while (fast) {
fast = fast->next;
slow = slow->next;
}
struct ListNode* next = slow->next;
slow->next = next->next;
free(next); // remeber to free memory
return dummy.next;
}

20 判定给定的字符串是否是合法的括号序列,可能包括大中小三类

tags: #stack

使用栈的基础题,注意逻辑简化

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def isValid(self, s: str) -> bool:
valid = True
stack = []
match = {")": "(", "]": "[", "}": "{"}
for c in s:
if c in ("(", "[", "{"):
stack.append(c)
else:
if not stack:
return False
if stack[-1] != match[c]:
return False
stack.pop()
return not stack
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char opposite(char c) {
switch (c) {
case ')' : return '(';
case ']' : return '[';
case '}' : return '{';
}
}

bool isValid(string s) {
stack<char> stk;
for (auto& c : s) {
if (c == '(' || c == '[' || c == '{')
stk.push(c);
else if (!stk.empty() && stk.top() == opposite(c))
stk.pop();
else
return false;
}

return stk.empty(); // 注意为空的条件
}
Rust 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
pub fn is_valid(s: String) -> bool {
let mut stack = vec![];
// let map =
for ch in s.chars() {
match ch {
'(' | '{' | '[' => stack.push(ch),
')' => if let Some('(') = stack.pop() {} else { return false },
'}' => if let Some('{') = stack.pop() {} else { return false },
']' => if let Some('[') = stack.pop() {} else { return false },
_ => return false
}
}
stack.len() == 0
}
}

21 合并两个已经排序的链表

tags: #pointers

考察链表的基本操作,很简单

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(-1)
p = dummy
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
if l1:
p.next = l1
if l2:
p.next = l2
return dummy.next
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
struct ListNode dummy;
dummy.next == NULL;
struct ListNode* p = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}

p = p->next;
}

if (l1)
p->next = l1;

if (l2)
p->next = l2;

return dummy.next;
}

22 给定数字 n, 生成所有合法的 n 个括号组成的序列

tags: #backtracking

一道典型的深度优先搜索题目

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def dfs(s, lefts, rights):
if lefts == 0 and rights == 0:
ans.append(s)
return
if lefts > 0:
dfs(s+"(", lefts-1, rights)
if (lefts < rights):
dfs(s+")", lefts, rights-1)
ans = []
dfs("", n, n)
return ans
C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<string> generateParenthesis(int n) {
vector<string> result;
gen(result, "", n, n);
return result;
}

// left 剩下的左括号,right 剩下的右括号
void gen(vector<string>& result, string s, int left, int right) {
if (left == 0 && right == 0) {
result.push_back(s);
return;
}
if (left != 0)
gen(result, s + '(', left - 1, right);
if (left < right)
gen(result, s + ')', left, right - 1);
}

23 合并 K 个排序的列表

使用优先级队列,复杂度最小。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
```
</details>



把列表看做一个队列,每次拿出两个列表,合并他们后放回到列表中,每次遍历列表的一半,这样每次遍历完一遍,
列表的长度都会减半,直到列表的长度为 1, 合并函数使用 21 题中的合并两个列表的函数


<details>
<summary>C 解答</summary>

```C
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
// see above
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
if (!lists || listsSize < 1)
return NULL;

while (listsSize > 1) {
// listsize is halfed
for (int i = 0; i < listsSize / 2; i++)
// merge i and last i list
lists[i] = mergeTwoLists(lists[i], lists[listsSize-1-i]);
listsSize = (listsSize + 1) / 2; // 注意这里!

}
return lists[0];
}

24 给定一个链表,交换两个相邻节点的值

最简单的做法显然是直接把前后两个节点的值交换,但是 LeetCode 规定不能改变节点的值。
主要考察链表的指针操作,注意各种细节,一定要在纸上先把链表画出来。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
p = dummy
while p.next and p.next.next:
t = p.next
p.next = t.next
t.next = p.next.next
p.next.next = t
p = p.next.next
return dummy.next
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode dummy, *temp, *pnext, *p = &dummy;
dummy.next = head;
while (p->next && p->next->next) {
temp = p->next;
p->next = temp->next;
temp->next = p->next->next;
p->next->next = temp;
p = temp;
}
return dummy.next;
}

25 给定一个链表,把相邻的 k 个节点反转

和上题一样,同样禁止改变节点的值。比较简单地解法是浪费一点空间,使用 Stack, 实现
逆转 k 个节点,注意如果 k 较大的话,这种方法是不合适的。另一种方法是直接翻转,空间是
O(1) 的,但是时间复杂度是 2N。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:

def reverseList(self, head):
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev

def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
p = dummy

while p.next:
n = k
q = p
# 找到下一组接点的头
while n > 0 and q.next:
q = q.next
n -= 1
# 如果节点不够了直接退出
if n > 0:
break
# 把这段链表先截下来
next = q.next
q.next = None
tail = p.next
p.next = self.reverseList(p.next)
p = tail
p.next = next
return dummy.next

使用 Stack 的 C++ 解法

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ListNode* reverseKGroup(ListNode* head, int k) {
stack<ListNode*> stk;
ListNode dummy(-1), *p = &dummy, *pp;
dummy.next = head;
while (1) {
pp = p;
for (int i = 0; i < k; i++) {
if (pp->next) {
stk.push(pp->next);
pp = pp->next;
} else {
break;
}
}

if (stk.size() < k) // 剩下的节点不够 k 个了
return dummy.next;

pp = stk.top()->next; // 下一组中的第一个
while (!stk.empty()) {
p->next = stk.top();
stk.pop();
p = p->next;
}

p->next = pp;
}
}

26 删除排序数组中的重复项

tags: #naive

in-place 的删除重复元素,使用两个指针,一个遍历,一个指向当前的结尾。

PS:这个基础题竟然做了半个小时才做对,⊙﹏⊙b 汗,要加强基础啊!

这类数组中去除中间元素的题写的时候还是很容易出错,重点是使用一个 length 变量,
然后还是要遍历整个数组。不要想什么双指针了。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) < 2:
return len(nums)
length = 0
for i in range(len(nums)):
# 处理 i == 0 的情况也是需要注意的
if i == 0 or nums[i] != nums[length-1]:
nums[length] = nums[i]
length += 1
return length
C 解答
1
2
3
4
5
6
7
8
int removeDuplicates(int* nums, int numsSize) {
if (numsSize <= 1) return numsSize;
int len = 0;
for (int i = 0; i < numsSize; i++)
if (i == 0 || nums[i] != nums[len - 1])
nums[len++] = nums[i];
return len;
}

27 删除元素

和上一题类似,注意细节

Python 解答
1
2
3
4
5
6
7
8
9
10
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
if not nums:
return 0
length = 0
for i in range(len(nums)):
if nums[i] != val:
nums[length] = nums[i]
length += 1
return length
C 解答
1
2
3
4
5
6
7
8
9
int removeElement(int* nums, int numsSize, int val) {
if (!nums || numsSize == 0) return 0;
int len = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] != val)
nums[len++] = nums[i];
}
return len;
}

28 实现 strstr 函数,即查找子串

使用暴力算法,时间复杂度 O(n)。也可以用 kmp 算法。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# kmp 算法
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
next = [0]
j = 0
# 特别注意这里的 1
for i in range(1, len(needle)):
while j > 0 and needle[i] != needle[j]:
j = next[j-1]
if needle[i] == needle[j]:
j += 1
next.append(j)
j = 0
for i in range(len(haystack)):
while j > 0 and haystack[i] != needle[j]:
j = next[j-1]
if haystack[i] == needle[j]:
j += 1
if j == len(needle):
return i - j + 1
return -1
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* Brute Force
*/
int strStr(char* haystack, char* needle) {
int h = strlen(haystack);
int n = strlen(needle);
if (n == 0) return 0;
// note h - n + 1
for (int i = 0; i < h - n + 1; i++) {
for (int j = 0; j < n; j++) {
if (needle[j] != haystack[i+j])
break;
if (j == n - 1)
return i;
}
}
return -1;
}

29 给定连个整数,不使用乘法和除法计算除法。

这里 有一个非常好的算法

计算可以从被除数中减去除数的次数

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int divide(int dividend, int divisor) {
// abs(INT_MIN) == INT_MAX + 1
if (divisor == 0 || (dividend == INT_MIN && divisor == -1))
return INT_MAX;
int sign = (dividend > 0) == (divisor > 0) ? 1 : -1;
long long n = labs(dividend);
long long d = labs(divisor);

int result = 0;
while (n >= d) {
long long temp = d;
long long multi = 1;
while (n >= (temp << 1)) {
temp <<= 1;
multi <<= 1;
}
n -= temp;
result += multi;
}

return sign * result;
}

30 包串联所有单词的子串

tags: #slidewindow

一道诡异的滑动窗口的题目,对这类问题还是不很熟啊。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
```
</details>



<details>
<summary>C++ 解答</summary>

```C++
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> counts;
for (string word : words)
counts[word]++;
int n = s.length(), num = words.size(), len = words[0].size();
vector<int> indexes;
for (int i = 0; i < n - num * len + 1; i++) {
unordered_map<string, int> seen;
int j = 0;
for (; j < num; j++) {
string word = s.substr(i + j * len, len);
if (counts.find(word) != counts.end()) {
seen[word]++;
if (seen[word] > counts[word])
break;
} else {
break;
}
}
if (j == num)
indexes.push_back(i);
}
return indexes;
}

31 全排列,下一个

首先,对于所有的组合,最小的一个一定是按照升序排序的,最大的一定是倒过来,因此

  1. 如果我们发现是完全倒序的,直接翻转就好了;
  2. 如果是一般情况,从后向前遍历,找到逆序的数字的边界,假设是 k。那么后边这段已经是完全
    逆序的,无法变小了,为了保证生成的数字变大,我们再从后向前找到第一个比 k 大的数字,交
    换这两个数字,再把后续的逆序数组翻转。
Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 前后都是闭区间
def reverse(nums, lo, hi):
while lo < hi:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1

k = -1
for i in range(len(nums)-2, -1, -1):
if nums[i] < nums[i + 1]:
k = i
break

if k == -1:
reverse(nums, 0, len(nums)-1)
return

l = -1
for i in range(len(nums)-1, k, -1):
if nums[i] > nums[k]:
l = i
break
nums[l], nums[k] = nums[k], nums[l]
reverse(nums, k+1, len(nums)-1)
C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void nextPermutation(vector<int>& nums) {
int k = -1; // 升序排列的最后一个数字
for (int i = nums.size() - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
k = i;
break;
}
}
// 完全是逆序的,直接返回第一个,也就是升序排列
if (k == -1) {
reverse(nums.begin(), nums.end());
return;
}
int l = -1; // 逆序数字中比 k 大的最小的数字
for (int i = nums.size() - 1; i > k; i--) {
if (nums[i] > nums[k]) {
l = i;
break;
}
}
swap(nums[k], nums[l]); // 保证变大
reverse(nums.begin() + k + 1, nums.end()); // 保证是下一个
}

32 从一个括号构成的字符串中找出最长的合法括号序列

动态规划的基础题目。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def longestValidParentheses(self, s: str) -> int:
dp = [0] * len(s)
ans = 0
for i in range(1, len(s)):
if s[i] == ")":
if s[i-1] == "(":
if i >= 2:
dp[i] = dp[i-2] + 2
else:
dp[i] = 2
elif i - dp[i-1] > 0 and s[i-dp[i-1]-1] == "(":
if i - dp[i-1] >= 2:
dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
else:
dp[i] = dp[i-1] + 2
ans = max(ans, dp[i])
return ans

也可以使用栈来解。但是这种方法非常 tricky, 因为要考虑到 ()() 的情况。

33 在排序后又被反转的数组中搜索

既然是部分有序的,自然还是使用二分搜索了,注意终止条件。
不同于普通二分搜索的两种情况,我们有了四种情况:

  1. 前半部分有序,并且在前半部分当中,
  2. 前半部分有序,但是不在前半部分
  3. 后半部分有序,并且在后半部分
  4. 后半部分有序,但是不在后半部分
Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
lo = 0
hi = len(nums) - 1
while lo <= hi:
mi = lo + (hi - lo) // 2
if nums[mi] == target:
return mi
# 这里为什么要包含等于号呢
if nums[lo] <= nums[mi]:
if nums[lo] <= target < nums[mi]:
hi = mi - 1
else:
lo = mi + 1
else:
if nums[mi] < target <= nums[hi]:
lo = mi + 1
else:
hi = mi - 1
return -1
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int search(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 1;

while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;

// left half is sorted
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
// right half is sorted
} else {
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}

return -1;
}

34 在排序数组中查找元素的第一个和最后一个位置

在 C++ 的标准库中包含了这两个函数,分别是std::lower_boundstd::upper_bound.

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1, -1]

lo = 0
hi = len(nums)
lower = -1
while lo < hi:
mi = lo + (hi - lo) // 2
if nums[mi] < target:
lo = mi + 1
else:
hi = mi
if lo < len(nums) and nums[lo] == target:
lower = lo

lo = 0
hi = len(nums)
upper = -1
while lo < hi:
mi = lo + (hi - lo) // 2
if nums[mi] <= target:
lo = mi + 1
else:
hi = mi
if nums[lo-1] == target:
upper = lo - 1

return [lower, upper]

35 二分查找数字,如果没有找到,返回应该插入的位置

就是最基础的二分查找

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
lo = 0
hi = len(nums)
while lo < hi:
mi = lo + (hi - lo) // 2
if nums[mi] == target:
return mi
elif nums[mi] < target:
lo = mi + 1
else:
hi = mi
return lo
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
int searchInsert(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return left;
}

36 合法数独,给定一个数独表,判定当前是否合法

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
"""
这道题的关键就在于小格子也是可以用 i 和 j 来计算的:
box_index = (row / 3) * 3 + columns / 3
"""
# 特别注意浅拷贝的问题
used_i = [[0] * 9 for _ in range(9)]
used_j = [[0] * 9 for _ in range(9)]
used_k = [[0] * 9 for _ in range(9)]
for i in range(9):
for j in range(9):
piece = board[i][j]
if piece == ".":
continue
n = int(piece) - 1
k = i // 3 * 3 + j // 3
if used_i[i][n] or used_j[j][n] or used_k[k][n]:
return False
used_i[i][n] = used_j[j][n] = used_k[k][n] = 1
return True
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 有点浪费空间
bool isValidSudoku(char** board, int row, int col) {
bool used_row[9][9] = {false}, used_col[9][9] = {false}, used_box[9][9] = {false};
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
if (board[i][j] != '.') {
int num = board[i][j] - '0' - 1;
int k = i / 3 * 3 + j / 3;
if (used_row[i][num] || used_col[j][num] || used_box[k][num])
return false;
used_row[i][num] = used_col[j][num] = used_box[k][num] = true;
}
return true;
}

37 求解数独

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void solveSudoku(vector<vector<char>>& board) {
solve(board, 0);
}
bool solve(vector<vector<char>>& board, int ind){
if(ind==81) return true;
int i=ind/9, j=ind%9;
if(board[i][j]!='.')
return solve(board, ind+1);
else{
for(char f = '1'; f <= '9'; f++) {
if(isValidFill(board, i, j, f)) {
board[i][j]= f;
if(solve(board, ind+1)) return true;
board[i][j]='.';
}
}
return false;
}
}
bool isValidFill(vector<vector<char>>& board, int i, int j, char fill) {
for(int k=0; k<9; k++) {
if(board[i][k]==fill) return false; //check the row
if(board[k][j]==fill) return false; //check the column
int r= i/3*3+j/3; //select the block
if(board[r/3*3+k/3][r%3*3+k%3]==fill) return false; //check the block
}
return true;
}

38 数数并说出来

不太理解这道题有什么意义,直接暴力做出来了

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string countAndSay(int n) {
string result = "1";
for (int i = 0; i < n -1; i++) {
string temp;
for (int j = 0; j < result.size(); j++) {
int count = 1;
while (j + 1 < result.size() && result[j+1] == result[j]) {
j++; count++;
}
temp += count + '0';
temp += result[j];
}
result = temp;
}
return result;
}

39 给定一个集合,在集合中找出和为 target 的数字,数字可以使用多次,集合中没有重复数字

典型的深度优先搜索

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
dfs(result, candidates, {}, target);
return result;
}

void dfs(vector<vector<int>>& result, vector<int>& candidates, vector<int> comb, int target) {
if (target == 0) {
result.push_back(comb);
return;
}

for (auto c : candidates) {
if (c > target) continue; // 数字太大了
if (!comb.empty() && c < comb.back()) continue; // 保证不重复且升序
comb.push_back(c);
dfs(result, candidates, comb, target - c);
comb.pop_back(); // 注意此处还需要弹出,因为需要循环
}
}

40 同上题一样,但是集合中的数字只能使用一次,并且集合中有重复数字

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> result;
sort(candidates.begin(), candidates.end());
dfs(result, candidates, {}, target, 0);
return result;
}

void dfs(vector<vector<int>>& result, vector<int>& candidates, vector<int> comb, int target, int start) {
if (target == 0) {
result.push_back(comb);
return;
}

for (int i = start; i < candidates.size(); i++) {
if (candidates[i] > target)
break;
if (i != start && candidates[i] == candidates[i-1])
continue;
comb.push_back(candidates[i]);
dfs(result, candidates, comb, target - candidates[i], i + 1);
comb.pop_back();
}
}

41 给定一个数组,找到第一个缺失的正数

显然,结果的范围是 [1..n+1]. 而数组的长度为 n 我们把每个位置都放上 i+1,
这样如果有位置不是 i+1, 则找到了结果,如果都相等则是 n+1.

c 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void swap(int* a, int* b) {
int t = *a; *a = *b; *b = t;
}

int firstMissingPositive(int* nums, int numsSize) {
for (int i = 0; i < numsSize; i++)
// 注意此处的 while
while (nums[i] > 0 && nums[i] <= numsSize && nums[i] != nums[nums[i] - 1])
swap(&nums[i], &nums[nums[i] - 1]);

for (int i = 0; i < numsSize; i++)
if (nums[i] != i + 1)
return i + 1;

return numsSize + 1;
}

42 给定一个数组表示柱子的高度,求能存贮的雨水的总量

从两边向中间收拢

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int trap(int* height, int heightSize) {
int left = 0, right = heightSize - 1;
int water = 0;
int max_left = 0, max_right = 0;

// 从两侧向中间缩小,可以算作是两个指针吧
while (left <= right) {
if (height[left] <= height[right]) {
if (height[left] >= max_left)
max_left = height[left];
else
water += max_left - height[left];
left++;
} else {
if (height[right] >= max_right)
max_right = height[right];
else
water += max_right - height[right];
right--;
}
}
return water;
}
Rust 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
impl Solution {
pub fn trap(height: Vec<i32>) -> i32 {

if height.is_empty() {
return 0;
}

let mut left = 0;
let mut right = height.len() - 1;
let mut water = 0;
let mut max_left = 0;
let mut max_right = 0;

while left <= right {
if height[left] <= height[right] {
if height[left] >= max_left {
max_left = height[left];
} else {
water += max_left - height[left];
}
left += 1;
} else {
if height[right] >= max_right {
max_right = height[right];
} else {
water += max_right - height[right];
}
right -= 1;
}
}
water
}
}
t

43 给定两个任意长的字符串,返回一个字符串,代表他们相乘的结果

按整数除法运算即可,重点是下标的表示

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define tonum(c) (c - '0')
#define tochar(i) (i + '0')

char* multiply(char* num1, char* num2) {
// 结果的长度不会超过 m+n,
// 假设某个数是 n 位的 9, 则结果比另一个数结尾加上 n 个 0 还小
int n = strlen(num1), m = strlen(num2);
int len = m+n;
char* result = malloc(sizeof(char) * (len + 1));
for (int i = 0; i < len; i++)
result[i] = '0';
result[len] = '\0';

for (int i = n - 1; i >= 0; i--) {
int carry = 0;
for (int j = m - 1; j >= 0; j--) {
int v = tonum(result[i+j+1]) + tonum(num1[i]) * tonum(num2[j]) + carry;
result[i+j+1] = tochar(v % 10);
carry = v / 10;
}
result[i] += carry;
}

for (int i = 0; i < len; i++)
if (result[i] != '0')
return result+i;

return "0";
}

44 通配符匹配,? 代表任意一个字符,*代表任意一个或多个字符

注意和正则表达式的区别,要求完全匹配。这道题的关键在于对星号的处理,如果出现星号的时候,我们记录当时的 p 和 s 的值,如果发生了不匹配的话,我们尝试回到该位置的下一个位置开始匹配

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

bool isMatch(char* s, char* p) {
char* star = NULL;
char* revert = s;
while (*s) {
if (*s == *p || *p == '?')
s++, p++;
else if (*p == '*')
star = p++, revert = s;
else if (star)
p = star + 1, s = ++revert;
else
return false;
}

// 如果剩下了 p, 那应该全都是*才对
while (*p) {
if (*p++ != '*')
return false;
}

return true;
}

45 跳跃游戏,给定一个数组,每个数字是在该位置可以向前移动的距离,返回最少需要多少次才能到达终点

比较简单,看注释吧

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int jump(int* nums, int numsSize) {
int steps = 0;
int last = 0; // last range
int cur = 0; // current range

for (int i = 0; i < numsSize; i++) {
// beyond range, make another jump
if (i > last)
last = cur, steps++;
// if we could reach longer?
if (nums[i] + i > cur)
cur = nums[i] + i;
}
return steps;
}

46 生成全排列

Cracking 上给出了一种解法,通过不断的添加下一个元素到上一组元素的不同位置来生成全排列,这样固然可以,但是大规模的拼接数组或者字符串是很耗费资源的。

在已经有了字符串(或者数组)的初始排列以后,可以通过不断交换的方法生成每一组全排列。
比如对于 xyz,我们有全排列为

x + per(yx)
y + per(xz)
z + per(xy)

那么我们通过把每个元素交换到第一个位置,就把问题规模缩小了,知道把问题规模缩小为 1.

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
per(result, nums, 0);
return result;
}

void per(vector<vector<int>>& result, vector<int>& nums, int begin) {
if (begin >= nums.size()) {
result.push_back(nums);
return;
}

for (int i = begin; i < nums.size(); i++) { // 注意是从 begin 开始,这样未改变的才能加入进来
swap(nums[begin], nums[i]);
per(result, nums, begin + 1);
swap(nums[begin], nums[i]); // 注意因为参数中是传引用,这里需要复原
}
}
Rust 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut result: Vec<Vec<i32>> = vec![];
Self::per(&mut result, nums, 0);
result
}

pub fn per(result: &mut Vec<Vec<i32>>, nums: Vec<i32>, begin: usize) {
if begin >= nums.len() {
result.push(nums);
return
}
for i in begin..nums.len() {
let mut nums = nums.clone();
nums.swap(begin, i);
Self::per(result, nums, begin + 1);
}
}
}

47 全排列,数组中有重复元素

和上一题基本是一样的,注意跳过重复元素就好了

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
per(result, nums, 0);
return result;
}

void per(vector<vector<int>>& result, vector<int> nums, int start) {
if (start >= nums.size()) {
result.push_back(nums);
return;
}

for (int i = start; i < nums.size(); i++) {
if (start != i && nums[start] == nums[i])
continue;
swap(nums[start], nums[i]);
per(result, nums, start + 1); // 事实证明,传引用反倒会超时
}
}

48 给定一个n*n的图像旋转图像,顺时针旋转 90 度

做法显然是从里到外,一层一层的旋转,这道题主要考察下标的操作

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void rotate(int** matrix, int m, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - layer;
for (int i = first; i < last; i++) {
int offset = i - first;
int top = matrix[first][i];
// up <- left
matrix[first][i] = matrix[last-offset][first];
// left <- down
matrix[last-offset][first] = matrix[last][last-offset];
// down <- right
matrix[last][last-offset] = matrix[i][last];
// right <- up
matrix[i][last] = top;
}
}
}

49 给定字符数组,把他们按照 Anagram 分组

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Anagram 分组
// 这道题没什么可做的,只需要统计
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> result;
string temp;
unordered_map<string, vector<string>> records;
for (int i = 0; i < strs.size(); ++i) {
temp = strs[i];
sort(temp.begin(), temp.end());
records[temp].push_back(strs[i]);
}
for (auto& record : records) {
sort(record.second.begin(), record.second.end());
result.push_back(record.second);
}
return result;
}

50 实现 pow(x, n)

显然不能直接阶乘过去,分治法

递归做法

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
// recursive
double myPow(double x, int n) {
if (n == INT_MIN) return myPow(x, n - 1) * x;
if (n < 0) return 1 / myPow(x, -n);
if (n == 0) return 1;
if (n == 1) return x;
double y = myPow(x, n / 2);
if (n & 0x1)
return y * y * x;
else
return y * y;
}

迭代做法

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
// iteratively
double myPow(double x, long p) {
double result = 1;
if (p < 0)
return 1 / myPow(x, -p);
while (p) {
if (p & 1)
result *= x;
x *= x;
p /= 2;
}
return result;
}

51 N 皇后问题

需要大幅度修改

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// N 皇后问题,皇后不能再一条直线,一条竖线,一条斜线上

// 使用深度优先求解,对于 dfs 问题,我们首先把算法的框架写下来,然后确定这个问题的限制条件
// 对于这个问题,限制条件当前行的元素不能在以前的列中出现过,也不能在对角线中出现过
vector<vector<string>> result;

vector<vector<string>> solveNQueens(int n) {
if (n < 1) return result;
vector<int> x(n);
dfs(0, x, n);
return result;

}

void dfs(int t, vector<int>& x, int n) {
// 当新添加一个 Q 到当前解的时候
if (t >= n) {
// result.push_back(make_solution(x));
// return;
vector<string> solution;
for (int i = 0; i < n; i++) {
string line(n, '.');
line[x[i]] = 'Q';
solution.push_back(line);
}
result.push_back(solution);
} else {
for (int i = 0; i < n; i++) {
bool skip = false;
for (int j = 0; j < t; j++) {
if (x[j] == i || abs(i - x[j]) == abs(t - j)) {
skip = true;
break;
}
}
if (skip) continue;
x[t] = i;
dfs(t+1, x, n);
}
}
}

52 N 皇后一共有多少个解

不要直接把皇后放好,而是把占用的都记录下来,然后继续深度优先搜索

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
unordered_set<int> cols, digs1, digs2;
int totalNQueens(int n) {
return total(0, 0, n);
}

int total(int row, int count, int n) {
for (int col = 0; col < n; col++) {
if (cols.find(col) != cols.end()
|| digs1.find(row - col) != digs1.end()
|| digs2.find(row + col) != digs2.end())
continue;

if (row == n-1)
count++;
else {
cols.insert(col);
digs1.insert(row-col);
digs2.insert(row+col);
count = total(row+1, count, n);
cols.erase(col);
digs1.erase(row-col);
digs2.erase(row+col);
}
}
return count;
}
};

53 最大子序列和

动态规划经典题目,遍历数组,如果已经当前子序列已经小于 0 了,抛弃并置 sum = 0
如果比当前和更大,更新。对于一个子序列,要么使得序列和增大,要么减小。

dp[n+1] = max(dp[n], dp[n] + A[n+1])

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
int maxSubArray(int* nums, int numsSize) {
int sum = 0;
int m = INT_MIN;

for (int i =0; i< numsSize; i++) {
sum += nums[i];
if (sum > m)
m = sum;
if (sum < 0)
sum = 0;
}
return m;
}
Python 解答
1
2
3
4
5
6
7
8
9
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
current_sum = 0
max_value = float('-inf')
for i in nums:
current_sum += i
max_value = max(max_value, current_sum)
current_sum = max(0, current_sum)
return max_value

54 顺时针螺旋打印矩阵

一圈一圈地打印就好了

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int* spiralOrder(int** matrix, int row, int col) {
if (row == 0 || col == 0) return NULL;
int top = 0, right = col - 1, down = row - 1, left = 0;
int index = 0;
int* result = malloc(sizeof(int) * row * col);
while (top <= down && left <= right) {
for (int i = left; i <= right; i++)
result[index++] = matrix[top][i];
top++; //
for (int i = top; i <= down; i++)
result[index++] = matrix[i][right];
right--; //
// 注意这个 if 语句
if (top <= down)
for (int i = right; i >= left; i--)
result[index++] = matrix[down][i];
down--; //
// 注意这个 if 语句
if (left <= right)
for (int i = down; i >= top; i--)
result[index++] = matrix[i][left];
left++; //
}
return result;
}

55 给定一个数组,每个数字表示在当前步可以移动的距离,返回是不是能够到达终点

使用动态规划求解,如果当前距离大于最远距离,更新最远距离,如果已经超过了最远距离,跳出

C 解答
1
2
3
4
5
6
7
bool canJump(int* nums, int numsSize) {
int i;
int reach = 0;
for (i = 0; i < numsSize && i <= reach; i++)
reach = max(reach, nums[i] + i);
return i == numsSize;
}

56 合并序列,给定一组序列,把其中重叠的序列合并

这道题用 Python 做竟然比用 C++ 还要快

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"""
class Interval(object):
def __init__(self, start=0, end=0):
self.start = start
self.end= end
"""

def merge(intervals):
intervals.sort(key=lambda x: x.start)
combined = []
for interval in intervals:
if combined and interval.start <= combined[-1].end:
combined[-1].end = max(combined[-1].end, interval.end)
else:
combined.append(interval)
return combined

57 添加序列,给定一组已经排序的序列,向其中插入一个序列,需要合并的合并

把剩余的部分都拷贝过来也不失为一种机智的做法。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def insert(self, intervals, newInterval):
ans = []
start, end = newInterval
remainder = 0
for x, y in intervals:
# 未重叠
if start > y:
ans.append([x, y])
# 进入重叠状态
else:
if end < x: # 当前区间已经不重叠了
break # 找到了结尾了
start = min(start, x)
end = max(end, y)
remainder += 1
ans.append([start, end])
ans += intervals[remainder:]
return ans

58 给定一个字符串,求其中最后一个单词的长度

显然这道题可以用 strlen 求出长度然后从后往前数,但是,这样相当于多遍历了一次
直接从后往前可以保证只遍历一次

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int lengthOfLastWord(char* s) {
int len = 0;
bool inWord = false;
while (*s) {
if (isspace(*s)) {
inWord = false;
} else {
if (!inWord) {
len = 1;
inWord = true;
} else {
len++;
}
}
s++;
}
return len;
}

59 给定 n,把 1, 2, 3 … 螺旋打印到矩阵中

和上一个完全一样的思路,只是这次是打印罢了

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Return an array of arrays.
* Note: The returned array must be malloced, assume caller calls free().
*/
int** generateMatrix(int n) {
int** matrix = malloc(sizeof(int*) * n);
for (int i = 0; i < n; i++)
matrix[i] = malloc(sizeof(int) * n);

int top = 0, left = 0, down = n - 1, right = n - 1;
int a = 1;
while (top <= down && left <= right) {
for (int i = left; i <=right; i++)
matrix[top][i] = a++;
top++;
for (int i = top; i <= down; i++) {
matrix[i][right] = a++;
}
right--;
if (top <= down)
for (int i = right; i >= left; i--)
matrix[down][i] = a++;
down--;
if (left <= right)
for (int i = down; i >= top; i--)
matrix[i][left] = a++;
left++;
}
return matrix;
}

60 给定 n 个数字,找出第 k 个 Permutation

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
/*The logic is as follows:
for n numbers the permutations can be divided to (n-1)! groups,
thus k/(n-1)! indicates the index of current number,
and k%(n-1)! denotes remaining sequence (to the right).
We keep doing this until n reaches 0, then we get n numbers permutations that is kth.
*/
string getPermutation(int n, int k) {
int f = 1;
string s(n, '0');
for (int i = 1; i <= n; i++) {
f *= i;
s[i-1] = i + '0';
}
// 给定 n, 一共有 n! 个序列,f == n!

k--;
for (int i = 0; i < n; i++) {
f /= n - i; // f /= n, f /= n - 1 ...
int j = i + k / f;
char c= s[j];
for (;j > i; j--) // shift space to put `c`, actually we could use swap
s[j] = s[j-1];
s[i] = c;
k %= f;
}

return s;
}
};

61 把列表旋转到倒数第 k 位

需要注意的是 k 大于列表长度的情况,这时候需要取余

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct ListNode* rotateRight(struct ListNode* head, int k) {
if (!head || k <= 0) return head;

int l = 1;
struct ListNode* n = head;
while (n->next) {
n = n->next;
l++;
}
// n is now the tail!

if (k >= l) k %= l;
if (k == 0) return head;

struct ListNode dummy, *p = &dummy;
dummy.next = head;
int i = l - k;
while (i--)
p = p->next;

dummy.next = p->next;
p->next = NULL;
n->next = head;

return dummy.next;
}

62 给定一个m*n的矩阵,有多少种方法从左上角移动到右下角

显然可以使用组合数学直接求出来解,但是容易溢出。而且这是一道经典的动态规划题目,对于
每个格子,可以从他的上部或者左面移动过来。

C++ 解答
1
2
3
4
5
6
7
int uniquePaths(int m, int n) {
vector<vector<int>> grid(m, vector<int> (n, 1));
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
return grid[m - 1][n - 1];
}

63 同上题,区别是在一些位置是有障碍物的

经过分析可知,递推关系是一样的,只需要把有障碍格子的到达方法设定为 0。这个主要是实现上的一些技巧,
见注释。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
// 注意设定长宽均 +1,但是初始化为 0,边界就成了障碍
vector<vector<int>> pathes(m + 1, vector<int> (n + 1, 0));
pathes[0][1] = 1; // 给定一个入口
for (int i = 1; i < m + 1; i++)
for (int j = 1; j < n + 1; j++)
// 注意此处的偏移
if (obstacleGrid[i-1][j-1] == 1)
pathes[i][j] = 0;
else
pathes[i][j] = pathes[i-1][j] + pathes[i][j-1];
return pathes[m][n];
}

64 给定一个m*n矩阵,每个数字代表经过该处的耗费,找出一条耗费最小的路径

依然是动态规划

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int minPathSum(vector<vector<int>>& grid) {
// if modifying the grid is disallowed, copy it
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (i == 0 && j == 0)
continue;
else if (i == 0 && j != 0)
grid[i][j] += grid[i][j-1];
else if (i != 0 && j == 0)
grid[i][j] += grid[i-1][j];
else
grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
return grid[m-1][n-1];
}

65 判定一个字符串是否是合法的数字,包括了正负号,小数点,e

一些例子:

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

这道题就是细节题,用 C 处理字符串太蛋疼了,直接上 Python 了

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def isNumber(self, s):
BEFORE = 0 # before dot
AFTER = 1 # after dot
EXP = 2 # after e
phase = BEFORE
allow_sign = True

s = s.strip()

if not any([c.isdigit() for c in s]):
return False

if s == '' or s[0] == 'e' or s[-1] == 'e' or s == '.':
return False
if s[0] == '.' and s[1] == 'e':
return False
if s[0] == '-' and s[1] == 'e':
return False

for c in s:
if '0' <= c <= '9':
allow_sign = False
elif c == '.':
allow_sign = False
if phase == EXP or phase == AFTER:
return False
else:
phase = AFTER
elif c == 'e':
if phase == EXP:
return False
allow_sign = True
phase = EXP

elif c == '-' or c == '+':
if not allow_sign:
return False
allow_sign = False
else:
return False

if phase == EXP:
return s[-1].isdigit()

return True

66 给定一个字符串代表的数字,返回加 1 后的数字

乍一看如果需要进位的话,可能需要拷贝整个数组。实际上并不需要,我们知道只有当数字是 999…999 的时候,才会使得数字的长度 +1 变为 1000…000。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> plusOne(vector<int>& digits) {
int n = digits.size();
for (int i = n - 1; i >= 0; i--) {
if (digits[i] == 9) {
digits[i] = 0;
} else {
digits[i]++;
return digits;
}
// trick here, we know that the number is 999...999
digits[0] = 1;
digits.push_back(0);
return digits;
}
Rust 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
impl Solution {
pub fn plus_one(mut digits: Vec<i32>) -> Vec<i32> {
for i in (0..digits.len()).rev() {
match digits[i] {
9 => digits[i] = 0,
_ => {digits[i] += 1; return digits}
}
}
digits[0] = 1;
digits.push(0);
digits
}
}

67 给定两个字符串代表的二进制数字,返回他们相加的和

和上一题一样,按照加法定义做就好了

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define tonum(c) (c - '0')
#define tochar(i) (i + '0')

char* addBinary(char* a, char* b) {
int m = strlen(a), n = strlen(b);
int len = (m > n ? m : n) + 1; // strlen(c)
char* c = malloc(sizeof(char) * len + 1); // with ending null
memset(c, '0', len+1);
c[len] = 0;
int carry = 0;
for (int i = 1; i <= len; i++) {
c[len-i] = tochar((i <= m ? tonum(a[m-i]) : 0) ^ (i <= n ? tonum(b[n-i]) : 0) ^ carry);
carry = ((i <= m ? tonum(a[m-i]) : 0) + (i <= n ? tonum(b[n-i]) : 0) + carry) >> 1;
}
return c[0] == '0' ? c+1 : c;
}

68 文字对齐

待研究

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<string> fullJustify(vector<string>& words, int L) {
vector<string> res;
for(int i = 0, k, l; i < words.size(); i += k) {
for(k = l = 0; i + k < words.size() and l + words[i+k].size() <= L - k; k++) {
l += words[i+k].size();
}
string tmp = words[i];
for(int j = 0; j < k - 1; j++) {
if(i + k >= words.size()) tmp += " ";
else tmp += string((L - l) / (k - 1) + (j < (L - l) % (k - 1)), ' ');
tmp += words[i+j+1];
}
tmp += string(L - tmp.size(), ' ');
res.push_back(tmp);
}
return res;
}

69 给定整数 x,求 sqrt(x)

比较坑的是 LeetCode 要求的是 y*y < x 的最大整数

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
int mySqrt(int x) {
if (x <= 1) return x;
const double EPS = x * 0.0001;
double y = x / 2; // initial guess
while (fabs(y * y - x) > EPS) {
y = (y + x / y) / 2;
}

long z = (long) y;
while (z * z > x) z--;
return z;
}

70 爬梯子,一次可以爬一步或者两步,有几种方法爬完梯子

斐波那契数列,也可以理解为动态规划

C 解答
1
2
3
4
5
6
int climbStairs(int n) {
int a = 1, b = 1, t;
for (int i = 1; i < n; i++)
t = b, b += a, a = t;
return b;
}

71 简化 Unix 路径,需要处理., .. 和多个斜杠等情况

没有什么需要注意的,主要是使用 stringstream 用作 string.split

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string simplifyPath(string& path) {
vector<string> dirs;
stringstream ss(path);
string dir;
while (getline(ss, dir, '/')) {
if (dir == "." || dir == "")
continue;
else if (dir == "..") {
if (!dirs.empty())
dirs.pop_back();
} else
dirs.push_back(dir);
}
string result;
for (auto& dir : dirs)
if (!dir.empty())
result += "/" + dir;
return result.size() ? result : "/";
}

72 编辑距离,允许替换,删除,插入三种操作

对于两个字符串比较,往往要使用二维的动态规划。
使用 f[i][j] 表示 word1[1..i] 和 word2[1..j] 之间的距离。
see here

那么:

  1. 相等 f[i][j] = f[i-1][j-1];

  2. 不相等

    1. 替换:f[i][j] = f[i-1][j-1] + 1; 都向前一步
    2. 添加:f[i][j] = f[i][j-1] + 1; word2 向前一步
    3. 删除:f[i][j] = f[i-1][j] + 1; word1 向前一步

另外使用一维数组表示二维数组还需要了解

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// unoptimized code
int minDistance(string word1, string word2) {
int m = word1.length(), n = word2.length();
vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));
for (int i = 1; i <= m; i++)
dp[i][0] = i;
for (int j = 1; j <= n; j++)
dp[0][j] = j;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
}
}
return dp[m][n];
}
C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// optimized
int minDistance(string word1, string word2) {
int m = word1.length(), n = word2.length();
vector<int> cur(m + 1, 0);
// 把剩余的字符删掉的距离
for (int i = 1; i <= m; i++)
cur[i] = i;
for (int j = 1; j <= n; j++) {
int pre = cur[0];
cur[0] = j;
for (int i = 1; i <= m; i++) {
int temp = cur[i];
if (word1[i - 1] == word2[j - 1])
cur[i] = pre;
else cur[i] = min(pre + 1, min(cur[i] + 1, cur[i - 1] + 1));
pre = temp;
}
}
return cur[m];
}
C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// recursive code from beauty of programming
// TLE on LeetCode
int minDistance(string word1, string word2) {
return minDistance(&word1.front(), &word1.back(), &word2.front(), &word2.back())
}

int minDistance(char* start1, char* end1, char* start2, char* end2) {
if (start1 > end1)
return start2 > end2 ? 0 : end2 - start2 + 1;

if (start2 > end2)
return start1 > end1 ? 0 : end1 - start1 + 1;

if (*start1 == *start2)
return minDistance(start1 + 1, end1, start2 + 1, end2);
else {
int t1 = minDistance(start1 + 1, end1, start2 + 1, end2);
int t2 = minDistance(start1 + 1, end1, start2, end2);
int t3 = minDistance(start1, end1, start2 + 1, end2);
return min(t1, min(t2, t3)) + 1;
}
}

73 给定一个矩阵,如果某个元素为零,把所在的行和所在的列都设为零

一种可以接受的方法是使用 O(m+n) 的空间,记录哪行哪列需要设为零

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m == 0) return;
int n = matrix[0].size();
if (n == 0) return;

vector<bool> row(m), column(n);

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (matrix[i][j] == 0)
row[i] = true, column[j] = true;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (row[i] || column[j])
matrix[i][j] = 0;
}

74 搜索矩阵,矩阵每行从左到右依次增大,每行都比上一行大

当做数组直接二分搜索就可以了

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
bool searchMatrix(int** matrix, int row, int col, int target) {
int left = 0, right = row * col - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[mid/col][mid%col] < target)
left = mid + 1;
else if (matrix[mid/col][mid%col] == target)
return true;
else
right = mid - 1;
}
return false;
}

75 颜色排序,每个物体有颜色属性,把他们按照 RGB 的顺序排序 (🇳🇱国旗问题)

一种方法是简单地 2 pass 解法,遍历一遍计数再输出。另一种方法是把红色往前交换,蓝色往后交换

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
void swap(int* a, int* b) {
int t = *a; *a = *b; *b = t;
}

void sortColors(int* nums, int numsSize) {
const int RED = 0, GREEN = 1, BLUE = 2;
int reds = 0, blues = numsSize - 1;
for (int i = 0; i <= blues; i++) {
while (nums[i] == BLUE && i < blues) swap(&nums[i], &nums[blues--]);
while (nums[i] == RED && i > reds) swap(&nums[i], &nums[reds++]);
}
}

76 跳过

77 给定数字 n 和 k,生成从 n 中取出 k 个数字的所有情况

数学上的组合,使用回溯来做,对状态空间进行深度搜索。

回溯方法通常适合对状态空间树的深度优先搜索相结合的,当一个解已经不满足条件时,剪枝;
如果满足条件,直到找到完全解未知。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 组合是不要求顺序的
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
if (n < k)
return result;
vector<int> temp(0, k);
combine(result, temp, 0, 0, n, k);
return result;
}

void combine(vector<vector<int>>& result, vector<int>& temp, int start, int count, int n, int k) {
// 1. 回溯条件,找到了一个解
if (count == k) {
result.push_back(temp);
return;
}
// 2. 深度优先搜索
for (int i = start; i < n; i++) {
temp.push_back(i + 1);
// 只搜索比 i 大的即可
combine(result, temp, i+ 1, count+1, n, k);
temp.pop_back();
}
}

78 给定一个集合,找到它的所有子集

这道题至少有 3 种解法:

  1. DFS,我们知道对于 n 个元素的集合,有 2^n 个子集,通过每个元素在不在子集中构造一个状态空间树
  2. 类似于电话键盘生成字母,迭代
  3. 巧妙的利用 1..2^n 对应
C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// use backtracking and do a dfs search

vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
if (nums.empty()) return result;
sort(nums.begin(), nums.end());
vector<int> temp;
subsets(nums, result, temp, 0);
return result;
}

// for each solution, the can be divided into two sub solutions: in or out
void subsets(vector<int>& nums, vector<vector<int>>& result, vector<int> temp, int i) {
if (i == nums.size()) {
result.push_back(temp);
return;
}

vector<int> t = temp;
subsets(nums, result, temp, i + 1);
temp.push_back(nums[i]);
subsets(nums, result, temp, i + 1);
}
C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// iterative
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
result.push_back({});
if (nums.empty())
return result;
result.push_back(vector<int>(1, nums[0]));
for (int i = 1; i < nums.size(); i++) {
int size = result.size(); // notice the cached size
for (int j = 0; j < size; j++) {
auto new_subset = result[j];
new_subset.push_back(nums[i]);
sort(new_subset.begin(), new_subset.end());
result.push_back(new_subset);
}
}
return result;
}
C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// tricky
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
int size = (1 << nums.size());
for (int i = 0; i < size; i++) {
vector<int> subset;
int k = i;
for (int j = 0; j < nums.size(); j++) {
if (k & 0x1)
subset.push_back(nums[j]);
k >>= 1;
}
sort(subset.begin(), subset.end());
result.push_back(subset);
}
return result;
}

79 给定一个二维字符数组,查找一个单词是否能够有连续的字母构成,不能交叉

也是深度优先的做法,首先找到开始的字母,然后依次向上下左右查找,注意还需要统计有没有访问过

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool exist(vector<vector<char>>& board, string word) {
int row = board.size();
int col = board[0].size();
vector<vector<bool>> visited(row, vector<bool> (col, false));

bool found = false;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == word[0]) {
if (findNext(board, word, visited, i, j, 0))
found = true;
}
}
}
return found;
}

bool findNext(vector<vector<char>>& board, string& word, vector<vector<bool>>& visited, int m, int n, int i) {

if (i == word.size())
return true;
if (m >= board.size() || n >= board[0].size() || m < 0 || n < 0|| visited[m][n] || board[m][n] != word[i])
return false;
char temp = board[m][n];
board[m][n] = -1;

bool exist = findNext(board, word, visited, m + 1, n, i+1) ||
findNext(board, word, visited, m - 1, n, i+1) ||
findNext(board, word, visited, m, n+1, i+1) ||
findNext(board, word, visited, m, n-1, i+1);
board[m][n] = temp;
return exist;
}

80 从排序数组中删除重复元素,但是允许一个元素重复出现两次

巧妙地解法,和i-2的元素对比

C 解答
1
2
3
4
5
6
7
8
9
int removeDuplicates(int* nums, int numsSize) {
if (!nums || numsSize < 1) return 0;
int len = 0, counter = 0;
for (int i = 0; i < numsSize; i++) {
if (len < 2 || nums[i] != nums[len-2])
nums[len++] = nums[i];
}
return len;
}

81 在被翻转的数组中查找元素,可能包含重复元素

经典题目,还是一个二分查找问题,只是要分很多种情况

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool search(int A[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left)/2;
if (A[mid] == key)
return true; //return m in Search in Rotated Array I
if (A[left] < A[mid]) { //left half is sorted
if (A[left] <= key && key < A[mid])
right = mid - 1;
else
left = mid + 1;
} else if (A[left] > A[mid]) { //right half is sorted
if (A[mid] < key && key <= A[right])
left = mid + 1;
else
right = mid - 1;
} else { // A[left] == A[mid]
left++;
}
}
return false;
}

82 从已经排序的链表中删除所有重复过的元素,只留下只出现一次的元素

考察链表操作

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct ListNode* deleteDuplicates(struct ListNode* head) {
struct ListNode dummy, *p = &dummy;
dummy.next = head;
while (p && p->next && p->next->next) {
if (p->next->val == p->next->next->val) {
struct ListNode* distinct = p->next;
int dup = p->next->val;
while (distinct && distinct->val == dup) {
distinct = distinct->next; // TODO: fix mem leak
}
p->next = distinct;
} else {
p=p->next;
}
}
return dummy.next;
}

83 从已经排序的链表中删除所有重复过的元素,但是重复过的也留下一个,即,使新链表不重复

同样是考察链表基本操作

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
struct ListNode* deleteDuplicates(struct ListNode* head) {
struct ListNode dummy, *p = &dummy; dummy.next = head; dummy.val = head->val + 1;
while (p && p->next) {
if (p->val == p->next->val) {
int dup = p->val;
while (p->next && p->next->val == dup)
p->next = p->next->next; // TODO: fix mem leak
} else
p = p->next;
}
return dummy.next;
}

84 在柱状图中查找最大的矩形

见注释

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int largestRectangleArea(vector<int>& height) {
stack<int> stk;
height.push_back(0); // dummy end
int result =0;
// 总结,对于需要查找上一次最大元素的问题,可以考虑使用栈存储
for (int i = 0; i < height.size(); ) {
// 当遇到更高的柱子时候,先存入堆栈
if (stk.empty() || height[i] > height[stk.top()]) // meet higher
stk.push(i++);
// 当遇到低一些的柱子时候,计算这些柱子到上一个更矮的柱子之间的最大举行,如果已经清空,说明之前所有柱子都更低
else { // lower
int h = stk.top();
stk.pop();
result = max(result, height[h] * (stk.empty() ? i : i - stk.top() -1));
}
}
return result;
}

85 最大的长方形

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int max(int a, int b) {
return a > b ? a : b;
}

int min(int a, int b) {
return a < b ? a : b;
}

int maximalRectangle(char** matrix, int row, int col) {
if (!matrix) return 0;
int left[col], right[col], height[col];
for (int i = 0; i < col; i++)
left[i] = 0, right[i] = col, height[i] = 0;
int area = 0;
for (int i = 0; i < row; i++) {
int cur_left = 0, cur_right = col;
for (int j = 0; j < col; j++)
if (matrix[i][j] == '1') // 在第 j 列的高度
height[j]++;
else
height[j] = 0;
for (int j = 0; j < col; j++)
if (matrix[i][j] == '1')
left[j] = max(left[j], cur_left);
else
left[j] = 0, cur_left = j + 1;
for (int j = col - 1; j >= 0; j--)
if (matrix[i][j] == '1')
right[j] = min(right[j], cur_right);
else
right[j] = col, cur_right = j;
for (int j = 0; j < col; j++)
area = max(area, (right[j] - left[j]) * height[j]);
}

return area;
}

86 链表分区,要求把小于某个值得元素全都放到前面

对于链表这道题很简单,分两个列表在合并就好了,问题是当我们处理类似的数组问题时,也有一种巧妙地 O(n) 的解法

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct ListNode* partition(struct ListNode* head, int x) {
struct ListNode small, *psmall = &small; // double dummy head
struct ListNode big, *pbig = &big;
psmall->next = pbig->next = NULL;

while (head != NULL) {
if (head->val < x) {
psmall->next = head;
psmall = psmall->next;
} else {
pbig->next = head;
pbig = pbig->next;
}
head = head->next;
}
psmall->next = big.next;
pbig->next = NULL;
return small.next;
}

87 把字符串分区后,交换得到的字符串

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isScramble(string s1, string s2) {
if(s1==s2)
return true;

// 先判断字符是否一致
int len = s1.size();
int count[26] = {0};
for(int i=0; i<len; i++) {
count[s1[i]-'a']++;
count[s2[i]-'a']--;
}

for(int i = 0; i < 26; i++)
if(count[i]!=0)
return false;

for(int i = 1; i < len; i++) {
if( isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i)))
return true;
if( isScramble(s1.substr(0,i), s2.substr(len-i)) && isScramble(s1.substr(i), s2.substr(0,len-i)))
return true;
}
return false;
}

88 合并已排序数组,要求合并到其中一个空间较大的数组中

对于这种要求 in-place 的算法,从后往前往往可以解决

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge(int* nums1, int m, int* nums2, int n) {
int len = m + n - 1;
m--, n--;
while (m >= 0 && n >= 0) {
if (nums1[m] > nums2[n]) {
nums1[len--] = nums1[m--];
} else {
nums1[len--] = nums2[n--];
}
}
while (n >= 0) {
nums1[n] = nums2[n];
n--;
}

}

89 生成格雷码 (Gray Code)

记住格雷码的生成规则

C++ 解答
1
2
3
4
5
6
7
vector<int> grayCode(int n) {
vector<int> v;
for (int i = 0; i < (1 << n); i++) {
v.push_back((i >> 1) ^ i);
}
return v;
}

90 由给定元素生成子集,可能包含重复元素

使用了和手机键盘生成字符串号码类似的迭代算法,注意其中对重复元素的处理,当然也可以用 DFS 来做

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> sets;
sets.push_back({});
sort(nums.begin(), nums.end()); // 处理包含重复元素的一半需要预排序
for (int i = 0; i < nums.size(); ) {
int count = 0; // dup count
while (count + i < nums.size() && nums[count+i] == nums[i])
count++;
int prev_n = sets.size();
for (int j = 0; j < prev_n; j++) {
vector<int> instance = sets[j];
// put dup element `count` times
for (int k = 0; k < count; k++) {
instance.push_back(nums[i]);
sets.push_back(instance);
}
}
i += count;

}
return sets;
}

91 给定一个数组只包含 1-9,可以用 1-26 代表字母,求出从其中能都得到多少字符串

使用动态规划,但是注意其中 0 的处理,很玄妙

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int numDecodings(char* s) {
if (!s || strlen(s) == 0 || s[0] == '0') return 0;
int r1 = 1, r2 = 1; // r1: 前一个字符, r2:前两个字符
char* p = s++; // 上一个字符

while (*s) {
if (*s == '0')
r1 = 0; // 0 不能单独构成字母
if (*p == '1' || *p == '2' && *s < '7') { // 形成两种可能
int t = r1;
r1 = r2 + r1;
r2 = t;
} else {
r2 = r1; // 新加入的数字只能单独构成字母
}

p = s++;
}
return r1;
}

92 在给定区间上翻转数组

同样是数组操作细节题

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
if (m == n) return head;
struct ListNode dummy, *p = &dummy, * small_node, * big_node; // actually the prev ones
dummy.next = head;
n -= m;

while (--m) // m starts from 1, so not m--
p = p->next;
struct ListNode* start = p->next;
while (n--) {
struct ListNode* next = start->next;
start->next = next->next;
next->next = p->next;
p->next = next;
}

return dummy.next;
}

93 恢复 IP 地址,给定一个字符串,适当插入点,一共有多少种方式构成 IP 地址

又是一道 DFS 的题,注意对于字符串问题如何处理

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<string> restoreIpAddresses(string s) {
vector<string> result;
restore(result, s, "", 0, 0);
return result;
}

void restore(vector<string>& result, string& s, string restored, int start, int dots) {
if (dots > 4) return;
if (dots == 4 && start == s.size())
result.push_back(restored);

for (int i = 1; i < 4; i++) {
if (start + i > s.size())
break;
string part = s.substr(start, i);
if (part[0] == '0' && part.size() > 1 || i == 3 && stoi(part) > 255)
continue;
restore(result, s, restored + part + (dots==3 ? "" : "."), start + i, dots + 1);

}
}

94 中序遍历二叉树

当然是使用栈了

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stk;
TreeNode* current = root;

while (!stk.empty() || current) {
if (current) {
stk.push(current);
current = current->left;
} else {
current = stk.top();
stk.pop();
result.push_back(current->val);
current = current->right;
}
}
return result;
}

递归解法

go 解答
1
2
3
4
5
6
7
8
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
left := inorderTraversal(root.Left)
right := inorderTraversal(root.Right)
return append(append(left, root.Val), right...)
}

95 生成二叉树,同下题一样

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<TreeNode*> generateTrees(int n) {
return gen(1, n);
}

vector<TreeNode*> gen(int start, int end) {
vector<TreeNode*> result;
if (start > end) {
result.push_back(NULL);
return result;
}

for (int i = start; i <= end; i++) {
auto leftTrees = gen(start, i - 1);
auto rightTrees = gen(i + 1, end);
for (auto& l : leftTrees) {
for (auto& r : rightTrees) {
auto root = new TreeNode(i);
root->left = l;
root->right = r;
result.push_back(root);
}
}
}
return result;
}

96 给定数字 n,从 1 到 n 作为节点有多少种方式生成二叉树

这道题看似是树,实际上是一个动态规划问题。

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numTrees(int n) {
if (n == 0) return 0;

int* dp = malloc(sizeof(int) * (n+1));
dp[0] = 1;

for (int i = 1; i <= n; i++) {
int num = 0;
for (int j = 0; j <= i; j++) // 依次选取第 k 个点作为根
num += dp[j - 1] * dp[i - j];
dp[i] = num;
}
return dp[n];
}

97 给定两个字符串交叉是否能够构成第三个字符串

这道题是一道二维的 DP 问题,因为需要对于每个字符串的每个位置用另一个字符串尝试匹配

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isInterleave(char* s1, char* s2, char* s3) {
int l1 = strlen(s1), l2 = strlen(s2), l3 = strlen(s3);
if (l1 + l2 != l3) return false;
// 在 i+j 位置 s1[i] s2[j] 是否能够构成 s[i+j]
bool** dp = malloc(sizeof(bool*) * (l1 + 1));
for (int i = 0; i <= l1; i++)
dp[i] = malloc(sizeof(bool) * (l2 + 1));

for (int i = 0; i <= l1; i++)
for (int j = 0; j <= l2; j++)
if (i == 0 && j == 0)
dp[i][j] = true;
else if (i == 0)
dp[i][j] = (dp[i][j-1] && s2[j-1] == s3[i+j-1]); // 注意:赋值的优先级更高
else if (j == 0)
dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1]);
else
dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1] || dp[i][j-1] && s2[j-1] == s3[i+j-1]);
return dp[l1][l2];
}

98 验证二叉搜索树是否合法

先序遍历即可

C 解答
1
2
3
4
5
6
7
8
9
bool valid(struct TreeNode* root, long left, long right) {
return root == NULL || root->val > left && root->val < right &&
valid(root->left, left, root->val) &&
valid(root->right, root->val, right);
}

bool isValidBST(struct TreeNode* root) {
return valid(root, INT_MIN - 1l, INT_MAX + 1l);
}

99 在二叉搜索树中有两个节点被调换了,找出这两个节点,并恢复该二叉树

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct TreeNode* prev = NULL;
struct TreeNode* first = NULL;
struct TreeNode* second = NULL;

void traverse(struct TreeNode* root) {
if (!root) return;
traverse(root->left);
if (prev && prev->val > root->val) {
if (!first) first = prev;
second = root;
}
prev = root;
traverse(root->right);
}

void recoverTree(struct TreeNode* root) {
prev = first = second = NULL;
traverse(root);
if (!first) return;
int temp = first->val;
first->val = second->val;
second->val = temp;
}

100 判断是否是相同的树

C 解答
1
2
3
4
5
6
7
8
9
bool isSameTree(struct TreeNode *p, struct TreeNode *q) {
if (p == NULL || q == NULL) {
return p == q;
} else {
return p->val == q->val
&& isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
}

101 判断是不是左右对称的树

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
bool sym(struct TreeNode* left, struct TreeNode* right) {
if (left && !right || !left && right)
return false;
return !left && !right ||
left->val == right->val &&
sym(left->left, right->right) &&
sym(right->left, left->right);
}

bool isSymmetric(struct TreeNode* root) {
if (!root) return true;
return sym(root->left, root->right);
}

102 二叉树层序遍历

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
vector<TreeNode*> current, next;
current.push_back(root);
while (!current.empty()) {
next.resize(0);
vector<int> vals;
for (int i = 0; i < current.size(); i++) {
if (current[i]->left)
next.push_back(current[i]->left);
if (current[i]->right)
next.push_back(current[i]->right);
vals.push_back(current[i]->val);
}
result.push_back(vals);
current = next;
}
return result;
}

103 二叉树 ZigZag 层序遍历

这道题更好的做法是使用一个栈,从而使得每行的顺序都是上一行的翻转

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
vector<TreeNode*> current, next;
current.push_back(root);
bool odd = true;
while (!current.empty()) {
next.resize(0);
vector<int> vals;
for (int i = 0; i < current.size(); i++) {
if (current[i]->left)
next.push_back(current[i]->left);
if (current[i]->right)
next.push_back(current[i]->right);
vals.push_back(current[i]->val);
}
if (!odd) reverse(vals.begin(), vals.end());
odd = !odd;
result.push_back(vals);
current = next;
}
return result;
}

104 树的最大深度

C 解答
1
2
3
4
5
int maxDepth(struct TreeNode* root) {
if (!root) return 0;
int left = maxDepth(root->left), right = maxDepth(root->right);
return (left > right ?left : right) + 1;
}

105 从前序遍历和中序遍历生成生二叉树

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct TreeNode* build(int* prestart, int* preend, int* instart, int* inend) {
struct TreeNode* root = malloc(sizeof(struct TreeNode));
root->val = *prestart;
root->left = root->right = NULL;

if (prestart == preend)
return root;

int* root_inorder = instart;
while (root_inorder <= inend && *root_inorder != *prestart)
root_inorder++;
int left_len = root_inorder - instart;
int right_len = inend - root_inorder;
if (left_len > 0)
root->left = build(prestart + 1, prestart + left_len, instart, root_inorder - 1);
if (right_len > 0)
root->right = build(prestart + left_len + 1, preend, root_inorder + 1, inend);
return root;
}
// m always equals n, otherwise it's bad input
struct TreeNode* buildTree(int* preorder, int m, int* inorder, int n) {
if (n==0) return NULL;
return build(preorder, preorder + n - 1, inorder, inorder + n - 1);
}

106 从中序遍历和后序遍历生成二叉树

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct TreeNode* build(int* instart, int* inend, int* poststart, int* postend) {
struct TreeNode* root = malloc(sizeof(struct TreeNode));
root->val = *postend;
root->left = root->right = NULL;

if (poststart == postend)
return root;

int* root_inorder = instart;
while (root_inorder <= inend && *root_inorder != *postend)
root_inorder++;
int left_len = root_inorder - instart;
int right_len = inend - root_inorder;
if (left_len > 0)
root->left = build(instart, root_inorder - 1, poststart, poststart + left_len - 1);
if (right_len > 0)
root->right = build(root_inorder + 1, inend, poststart + left_len, postend - 1);
return root;
}
struct TreeNode* buildTree(int* inorder, int m, int* postorder, int n) {
if (n == 0) return NULL;
return build(inorder, inorder + n - 1, postorder, postorder +n - 1);
}

107 二叉树层序遍历,但要生成翻转的遍历序列

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
vector<TreeNode*> current, next;
current.push_back(root);
while (!current.empty()) {
next.resize(0);
vector<int> vals;
for (int i = 0; i < current.size(); i++) {
if (current[i]->left)
next.push_back(current[i]->left);
if (current[i]->right)
next.push_back(current[i]->right);
vals.push_back(current[i]->val);
}
result.push_back(vals);
current = next;
}
reverse(result.begin(), result.end());
return result;
}

108 把排序数组转化为二叉树

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 struct TreeNode* bst(int* left, int* right) {
int* mid = left + (right - left) / 2;
struct TreeNode* root = malloc(sizeof(struct TreeNode));
root->val = *mid;
root->left = root->right = NULL;
if (left < mid)
root->left = bst(left, mid-1);
if (mid < right)
root->right = bst(mid+1, right);
return root;
}
struct TreeNode* sortedArrayToBST(int* nums, int n) {
if (n == 0) return NULL;
return bst(nums, nums + n -1);
}

109 把排序列表转化为二叉树

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct ListNode* list;
int len(struct ListNode* head) {
int l = 0;
while (head)
head = head->next, l++;
return l;
}

struct TreeNode* bst(int n) {
if (n == 0) return NULL;
struct TreeNode* root = malloc(sizeof(struct TreeNode));
root->left = bst(n/2);
root->val = list->val;
list = list->next;
root->right = bst(n - n / 2 - 1);
return root;
}
struct TreeNode* sortedListToBST(struct ListNode* head) {
if (!head) return 0;
list = head;
return bst(len(head));
}

110 平衡二叉树

C 解答
1
2
3
4
5
6
7
8
9
10
11
int height(struct TreeNode* root) {
if (!root) return 0;
int left = height(root->left);
int right = height(root->right);
if (left > right + 1 || right > left + 1 || left == -1 || right == -1)
return -1;
return (left > right ? left : right) + 1;
}
bool isBalanced(struct TreeNode* root) {
return height(root) != -1;
}

111 二叉树最小高度

C 解答
1
2
3
4
5
6
7
8
9
int minDepth(struct TreeNode* root) {
if (!root) return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
if (!right) return left + 1;
if (!left) return right + 1; // tricky here, 当有空节点时,不能返回 0,而是返回另一个值

return (left < right ? left : right) + 1;
}

112 二叉树中是否存在和为某个数的路径

C 解答
1
2
3
4
5
6
bool hasPathSum(struct TreeNode* root, int sum) {
if (!root) return false;
if (!root->left && !root->right) return sum == root->val;
return hasPathSum(root->left, sum - root->val) ||
hasPathSum(root->right, sum - root->val);
}

113 接上题,把这个路径找出来

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> result;
vector<int> path;
getPaths(result, path, root, sum);
return result;
}

void getPaths(vector<vector<int>>& result, vector<int> path, TreeNode* root, int sum) {
if (!root)
return;
path.push_back(root->val);
if (!root->left && !root->right && sum == root->val) {
result.push_back(path);
return;
}

getPaths(result, path, root->left, sum - root->val);
getPaths(result, path, root->right, sum - root->val);
}

114 把二叉树扁平成列表

C++ 解答
1
2
3
4
5
6
7
8
9
TreeNode* prev;
void flatten(TreeNode* root) {
if (!root) return;
flatten(root->right);
flatten(root->left);
root->right = prev;
root->left = NULL;
prev = root; // last flattened element
}

115 通过删掉一些字母得到子序列,问有多少种方法能够得到子序列呢

使用 DP,

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Solution (DP):
* 我们扫描字符串 s
* Path[i][j] 代表 T.substr(1...i) 在 S(1...j) 不同的子序列的数量
*
* Path[i][j] = Path[i][j-1] (discard S[j])
* + Path[i-1][j-1] (S[j] == T[i] and we are going to use S[j])
* or 0 (S[j] != T[i] so we could not use S[j])
* while Path[0][j] = 1 and Path[i][0] = 0.
*/


class Solution {
public:
int numDistinct(string s, string t) {
int m = t.size();
int n = s.size();

if (m > n)
return 0;
vector<vector<int>> path(m+1, vector<int>(n+1, 0));

for (int i = 0; i <= n; i++)
path[0][i] = 1;

for (int j = 1; j <= n; j++) // S
for (int i = 1; i <= m; i++) // T
path[i][j] = path[i][j-1] + (t[i-1] == s[j-1] ? path[i-1][j-1] : 0);

return path[m][n];
}
};

116 完全二叉树中把每个节点指向他这一层的右面的节点

显然左节点的下一个节点是父节点的右节点,右节点的下一个节点是父节点下一个节点的左节点。

C 解答
1
2
3
4
5
6
7
8
9
10
void connect(struct TreeLinkNode *root) {
if (!root)
return;
if (root->left)
root->left->next = root->right;
if (root->right)
root->right->next = root->next ? root->next->left : NULL;
connect(root->left);
connect(root->right);
}

117 同上题,但是是任意的🌲

通过上一层已经被连接的 next 指针,顺序层序访问,从而连接下一层。

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void connect(struct TreeLinkNode *root) {
struct TreeLinkNode* head = root, * prev = NULL, *p = NULL;
while (head) { // head 是每层的开始
p = head;
prev = head = NULL;

while (p) {
if (p->left) {
if (prev)
prev->next = p->left;
else
head = p->left;
prev = p->left;
}

if (p->right) {
if (prev)
prev->next = p->right;
else
head = p->right;
prev = p->right;
}
p = p->next;
}
}
}

118 杨辉三角

注意坐标关系,不要被骗了

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
vector<vector<int>> generate(int n) {
vector<vector<int>> result(n);


for (int i = 0; i < n; i++) {
result[i].resize(i+1);
result[i][0] = result[i][i] = 1;
for (int j = 1; j < i; j++)
result[i][j] = result[i-1][j-1] + result[i-1][j];
}
return result;
}

119 返回杨辉三角的第 k 行

要求只能使用 O(k) 的额外空间,比较蛋疼的是这里的 k 是从 0 计数的。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> getRow(int rowIndex) {
rowIndex++;
vector<int> row;
for (int i = 0; i < rowIndex; i++) {
vector<int> newRow(i+1);
newRow[0] = newRow[i] = 1;
for (int j = 1; j < i; j++)
newRow[j] = row[j-1] + row[j];
swap(row, newRow);
}
return row;
}

120 给定一个类似杨辉三角形状的数组,求从顶部到底部的最短路径

显然是使用 DP,但是有一个问题,如果是 top down 的话,最后还需要遍历一下,而如果是 bottom up 就只需要返回 dp[0] 就好了。

C++ 解答
1
2
3
4
5
6
7
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> dp(triangle.back()); // 复制最后一行
for (int layer = triangle.size() - 2; layer >= 0; layer--)
for (int i = 0; i <= layer; i++)
dp[i] = triangle[layer][i] + min(dp[i], dp[i+1]);
return dp[0];
}

121 买卖股票最佳时机,只能交易一次

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProfit(int* prices, int pricesSize) {
if (pricesSize < 2) return 0;
int profit = 0;
int min = prices[0];
// 从前到后依次遍历,如果有更好的收益更新,或者更新 min,限制条件是先出现最小值
for (int i = 0; i < pricesSize; i++) {
if (prices[i] > min) {
profit = max(profit, prices[i] - min);
} else {
min = prices[i];
}
}
return profit;
}

122 买卖股票的最佳时机,可以做任意多比交易

有两种解法,一种是不断做交易,完全不考虑交易次数,这种做法不符合实际情况。
另一种做法是模拟交易,这样会生成最少的交易次数,结果也是对的。

C 解答
1
2
3
4
5
6
7
8
9
// 1
int maxProfit(int* prices, int pricesSize)
int total = 0;
for (int i=0; i< pricesSize-1; i++)
if (prices[i+1]>prices[i])
total += prices[i+1]-prices[i];

return total;
}
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 2
int maxProfit(int* prices, int pricesSize) {
if (!prices) return 0;
int profit = 0;bool buy = true;
int min = prices[0], max = prices[0];
for (int i = 0; i < pricesSize; i++) {
if (prices[i] < min && buy) {
min = prices[i];
max = prices[i];
}
if (prices[i] > min && buy)
buy = false;
if (prices[i] > max && !buy)
max = prices[i];
if ((prices[i] < max || i == pricesSize - 1) && !buy){
profit += max - min;
min = prices[i];
max = prices[i];
buy = true;
}

}
return profit;

}

123 股票交易,限制只能交易两股

每次求解的是:卖出两股以后的最大值,刚刚买入第二股的最大值,卖出第一股时候的最大值,买入第一股时候的最大值。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProfit(vector<int>& prices) {
int hold1 = INT_MIN, hold2 = INT_MIN;
int release1 = 0, release2 = 0;

for (auto i : prices) {
release2 = max(release2, hold2 + i);
hold2 = max(hold2, release1 - i);
release1 = max(release1, hold1 + i);
hold1 = max(hold1, -i);
}

return release2;
}

124 二叉树路径最大和,路径可以从任意一个节点开始到任意一个节点结束

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int max(int a, int b) {
return a > b ? a : b;
}

int doSum(struct TreeNode* root, int* sum) {
if (!root)
return 0;
int left = max(0, doSum(root->left, sum));
int right = max(0, doSum(root->right, sum));
*sum = max(*sum, left+right+root->val);
return max(left, right) + root->val;
}


int maxPathSum(struct TreeNode* root) {
int sum = INT_MIN;
doSum(root, &sum);
return sum;
}

这道题是把最终答案放在了全局变量中,并采用了辅助函数的方法。全局变量中存储两条路径的和,
而返回值中存储当前子树中最长的单边。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def __init__(self):
self.ans = float('-inf')

def _maxPathSum(self, root: TreeNode) -> int:
if root is None:
return 0
# 注意这里要取 max,以防添加了负路径
left = max(0, self._maxPathSum(root.left))
right = max(0, self._maxPathSum(root.right))
self.ans = max(self.ans, left + right + root.val)
return max(left, right) + root.val

def maxPathSum(self, root: TreeNode) -> int:
self._maxPathSum(root)
return self.ans

125 给定一个字符串,只考虑字母和数字,忽略大小写,判断是否是回文字符串

太简单了,没啥可说的

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isPalindrome(char* s) {
int len = strlen(s);
if (len == 0) return true;
int left = 0, right = len - 1;
while (left < right) {
char l = s[left], r = s[right];
if (isalnum(l) && isalnum(r)) {
if (tolower(l) != tolower(r))
return false;
left++, right--;
} else {
if (!isalnum(l))
left++;
if (!isalnum(r))
right--;
}
}
return true;
}

127 单词梯子

给定梯子,和开始单词和结束单词,最少需要多少个中间单词,才能变化过去,每次只能变化一个字母

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
unordered_set<string> beginSet, endSet, *set1, * set2;
beginSet.insert(beginWord);
endSet.insert(endWord);

int dist = 2;
while (!beginSet.empty() && !endSet.empty()) {
if (beginSet.size() < endSet.size()) {
set1 = &beginSet;
set2 = &endSet;
} else {
set1 = &endSet;
set2 = &beginSet;
}

unordered_set<string> temp;
for (auto word : *set1) { // notice word in not ref
wordList.erase(word);
for (auto& letter : word) {
for (int i = 0; i < 26; i++) {
char oldLetter = letter;
letter = 'a' + i;
if (set2->find(word) != set2->end())
return dist;
if (wordList.find(word) != wordList.end()) {
temp.insert(word);
wordList.erase(word);
}
letter = oldLetter;
}
}
}
dist++;
swap(*set1, temp);

}
return 0;
}

128 最长递增子序列

使用动态规划

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int longestConsecutive(vector<int>& nums) {
int result = 0;
unordered_map<int, int> hash; // 每个元素和它们所在序列的长度

for (auto n : nums) {
if (hash.find(n) == hash.end()) {
// 查找两边的元素,如果找到,把新元素合并进去
int left = hash.find(n-1) != hash.end() ? hash[n-1] : 0;
int right = hash.find(n+1) != hash.end() ? hash[n+1] : 0;
int sum = left + right + 1;
hash[n] = hash[n-left] = hash[n+right] = sum; // 注意此处的更新,并不需要更新区间内的每个值,只需要更新边界即可
result = max(result, sum);
}
}

return result;
}

129 二叉树中只有 0-9 找出所有根节点到子节点的和

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int sum(struct TreeNode* root, int x) {
if (!root->left && !root->right)
return x * 10 + root->val;
int val = 0;
if (root->left)
val += sum(root->left, x * 10 + root->val);
if (root->right)
val += sum(root->right, x * 10 + root->val);
return val;
}

int sumNumbers(struct TreeNode* root) {
if (!root) return 0;
return sum(root, 0);
}

130 把所有被包围的 O 置为 X

使用并查集

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class UnionFind {
private:
vector<int> m_father, m_rank;
public:
UnionFind(int n): m_father(n), m_rank(n, 0) {
for (int i = 0; i < m_father.size(); i++)
m_father[i] = i;
}

int find(int x) {
if (x != m_father[x])
m_father[x] = find(m_father[x]);
return m_father[x];
}

void unionify(int x, int y) {
x = find(x);
y = find(y);

if (x == y) return;

if (m_rank[x] > m_rank[y]) {
m_father[y] = x;
} else {
if (m_rank[x] == m_rank[y])
m_rank[y]++;
m_father[x] = y;
}
}
};

class Solution {
public:
void solve(vector<vector<char>>& board) {
int n = board.size();
if (n == 0) return;
int m = board[0].size();
UnionFind uf(n*m+1);

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if ((i == 0 || j == 0 || i == n-1 || j == m-1) && board[i][j] == 'O')
uf.unionify(i * m + j, n * m);
else if (board[i][j] == 'O') {
if (board[i-1][j] == 'O')
uf.unionify(i * m + j, (i - 1) * m + j);
if (board[i+1][j] == 'O')
uf.unionify(i*m+j, (i+1)*m+j);
if (board[i][j-1] == 'O')
uf.unionify(i*m+j, i*m+j-1);
if (board[i][j+1] == 'O')
uf.unionify(i*m+j, i*m+j+1);
}
}
}

for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (uf.find(i*m+j) != uf.find(n*m))
board[i][j] = 'X';
}
};

131 对字符串分组,是的每个字串都是回文,返回所有可能的分组

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> group;
dfs(result, s, group, 0);
return result;
}

void dfs(vector<vector<string>>& result, const string& s, vector<string>& group, int start) {
if (start == s.size()) {
result.push_back(group);
return;
}

for (int i = start; i < s.size(); i++) {
if (isPalindrome(s, start, i)) {
group.push_back(s.substr(start, i - start + 1));
dfs(result, s, group, i + 1);
group.pop_back();
}
}
}

bool isPalindrome(const string& s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--])
return false;
}
return true;
}

132 如上题,找出最少需要分组几次

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int minCut(string s) {
vector<int> cut(s.size() + 1, 0);
for (int i = 0; i < s.size() + 1; i++)
cut[i] = i - 1;

for (int i = 0; i < s.size(); i++) {
for (int j = 0; i - j >= 0 && i + j < s.size() && s[i+j] == s[i-j]; j++)
cut[i+j+1] = min(cut[i+j+1], cut[i-j] + 1); // i-j -> i+j 是 palindrome,所以只需要 cut[i-j] 在加上这一段就好了
for (int j = 1; i - j + 1 >= 0 && i + j < s.size() && s[i+j] == s[i-j+1]; j++)
cut[i+j+1] = min(cut[i+j+1], cut[i - j + 1] + 1);
}

return cut[s.size()];
}

133 复制有向图

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> hash; // old -> new pair
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (!node)
return NULL;
if (hash.find(node) == hash.end()) {
hash[node] = new UndirectedGraphNode(node->label);
for (auto n : node->neighbors)
hash[node]->neighbors.push_back(cloneGraph(n));
}

return hash[node];
}

134 加油站

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
int total = 0;
int j = -1;

for (int i = 0, sum = 0; i < gasSize; ++i) {
sum += gas[i] - cost[i]; // 从此处经过能够净增多少汽油
total += gas[i] - cost[i]; // 记录总的汽油量是否是正的
if (sum < 0) { // 如果当前汽油量已经小于 0,说明之前的节点都是不行的,到下一个节点
j = i;
sum = 0; // 同时重新开始计数
}
}

return total >= 0 ? j + 1 : -1;
}

135 糖块,成绩高的需要比他身边成绩低的获得更多的糖

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int candy(vector<int>& ratings) {
int n = ratings.size();
if (n <= 1)
return n;
vector<int> candies(n, 1);

for (int i =1; i < n; i++)
if (ratings[i] > ratings[i-1])
candies[i] = candies[i-1] + 1;

for (int i = n - 1; i > 0; i--)
if (ratings[i-1] > ratings[i])
candies[i-1] = max(candies[i] + 1, candies[i-1]);

int result = 0;
for (auto i : candies)
result += i;

return result;
}

136 找出数组中只出现一次的数字

C 解答
1
2
3
4
5
6
int singleNumber(int* nums, int numsSize) {
int result = nums[0];
for (int i = 1; i < numsSize; i++)
result ^= nums[i];
return result;
}

137 一个数组中,所有数字都出现三次,除了一个数字以外,找出这个数字

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
// 使用二进制计算
// 00->10->01->00(0->1->2->3/0)
// ones = ones ^ A[i]; if (twos == 1) then ones = 0
// twos = twos ^ A[i]; if (ones* == 1) then twos = 0

int singleNumber(int* nums, int numsSize) {
int ones = 0, twos = 0;
for (int i = 0; i < numsSize; i++) {
ones = (ones ^ nums[i]) & ~twos;
twos = (twos ^ nums[i]) & ~ones;
}
return ones;
}

138 复制复杂结构链表

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* struct RandomListNode *next;
* struct RandomListNode *random;
* };
*/
struct RandomListNode *copyRandomList(struct RandomListNode *head) {
struct RandomListNode* p;
p = head;
while (p) {
struct RandomListNode* node = malloc(sizeof(struct RandomListNode));
node->next = node->random = NULL; // spicial notice to struct initialization in c
node->label = p->label;
node->next = p->next;
p->next = node;
p = node->next;
}

p = head;
while (p) {
if (p->random)
p->next->random = p->random->next;
p = p->next->next;
}

struct RandomListNode dummy, *q = &dummy;
dummy.next = dummy.random = NULL;
p = head;
while (p) {
q->next = p->next;
q = q->next;
p->next = p->next->next;
p = p->next;
}
return dummy.next;
}

139 查找单词是否能组成句子

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool wordBreak(string s, unordered_set<string>& wordDict) {
if (wordDict.empty()) return false;
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
// 动态规划,假设前 i 个字符已经匹配到了,尝试匹配 i 到 i+j,如果找到了,就匹配到了 i+j
for (int i = 1; i <= s.size(); i++) {
for (int j = i-1; j >= 0; j--) {
if (dp[j]) {
string word = s.substr(j, i-j);
if (wordDict.find(word) != wordDict.end()) {
dp[i] = true;
break;
}
}
}
}
return dp[s.size()];
}

141 列表是否有环

slow 每次走一步,而 fast 每次走两步,因此在进入环之后,两者一定会相遇

C 解答
1
2
3
4
5
6
7
8
9
10
bool hasCycle(struct ListNode *head) {
struct ListNode* slow = head, * fast = head;
while (fast && fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast)
return true;
}
return false;
}

142 列表是否有环?如果有找到环的开始

从两者出发,到两者相遇,slow 指针走了 p 步,而 fast 指针走了 2p 步,显然 fast 多走了一圈(或者多圈)。
设 p = k + x, 2p = k + x + loop -> 2k + 2x = k + x + loop -> k + x = loop -> k = loop - x,剩下的长度正好也是 k。
假设入口处距离起点的距离是 k,那么发生碰撞的点距离环的入口处距离也是 k,所以两个指针分别从开始和碰撞点出发匀速一定会在环的入口相遇。

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head, * fast = head, *entry = NULL;
bool found = false;
while (!found && fast && fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast)
found = true;
}

if (!found) return NULL;

slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}

return slow;
}

144 前序遍历

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
if (!root) return result;

stack<TreeNode*> stk;
stk.push(root);

while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
result.push_back(node->val);
if (node->right)
stk.push(node->right);
if (node->left)
stk.push(node->left);

}

return result;

}

145 二叉树的后序遍历

参见树的遍历

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (!root) return result;
stack<TreeNode*> stk, output;
stk.push(root);
while (!stk.empty()) {
auto node = stk.top();
stk.pop();
output.push(node);

if (node->left)
stk.push(node->left);
if (node->right)
stk.push(node->right);
}
while (!output.empty()) {
result.push_back(output.top()->val);
output.pop();
}
return result;
}

146 LRU 缓存

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class LRUCache{
public:
typedef unordered_map<int, pair<int, list<int>::iterator>> cache_t; // k: v, iter

LRUCache(int capacity) : m_capacity(capacity) {

}

int get(int key) {
auto it = m_cache.find(key);
if (it == m_cache.end())
return -1;
touch(it);
return it->second.first;
}

void set(int key, int value) {
auto it = m_cache.find(key);
if (it != m_cache.end()) {
touch(it);
} else {
if (m_cache.size() == m_capacity) {
m_cache.erase(m_used.back());
m_used.pop_back();
}
m_used.push_front(key);
}
m_cache[key] = {value, m_used.begin()};
}
private:
void touch(cache_t::iterator it) {
int key = it->first;
m_used.erase(it->second.second);
m_used.push_front(key);
it->second.second = m_used.begin();
}

cache_t m_cache;
list<int> m_used;
int m_capacity;
};

147 链表插入排序

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct ListNode* insertionSortList(struct ListNode* head) {
if (!head) return NULL;
struct ListNode dummy, *p = head;
dummy.val = INT_MIN;
dummy.next = NULL;
while (p) {
struct ListNode* iter = &dummy;
while (iter->next && iter->next->val < p->val)
iter = iter->next;
struct ListNode* pnext = p->next;
p->next = iter->next;
iter->next = p;
p = pnext;
}
return dummy.next;
}

148 排序链表,要求达到 O(nlogn) 时间复杂度

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
void split(struct ListNode* source, struct ListNode** frontptr, struct ListNode** backptr) {
struct ListNode* fast, * slow;
if (!source || !source->next)
*backptr = source;
else {
slow = source;
fast = source->next;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;

}

*backptr = slow->next;
slow->next = NULL;
}
*frontptr = source;
}

struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
struct ListNode dummy;
dummy.next == NULL;
struct ListNode* p = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}

p = p->next;
}

if (l1)
p->next = l1;

if (l2)
p->next = l2;

return dummy.next;
}

// merge sort
struct ListNode* sortList(struct ListNode* head) {
struct ListNode* front, * back;
if (!head || !head->next) return head;
split(head, &front, &back);
front = sortList(front);
back = sortList(back);
head = merge(front, back);
return head;
}

149 在同一条线上的点最多的线

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int maxPoints(vector<Point>& points) {
if (points.size() < 2) return points.size();
int result = 0;

// 对于每一个点
for (int i = 0; i < points.size(); i++) {
// 经过该点的直线,使用分数作为斜率,避免使用浮点数
map<pair<int, int>, int> lines;
int localMax = 0, overlap = 0;
for (int j = i + 1; j < points.size(); j++) { // 避免重复计算
if (points[j].x == points[i].x && points[j].y == points[i].y) {
overlap++; // 同一个点
continue;
} else {
int x = points[j].x - points[i].x;
int y = points[j].y - points[i].y;
int g = gcd(x, y);
x /= g, y /= g; // verticle case: x == 0 -> (0, 1)
lines[make_pair(x, y)]++;
localMax = max(localMax, lines[make_pair(x, y)]);
}
}
// overlap 算在任意条线上
result = max(result, localMax + overlap + 1);
}
return result;
}

int gcd(int x, int y) {
if (y == 0) return x;
else return gcd(y, x % y);
}

150 后缀表达式求值

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool is_operator(char t) {
return t == '+' || t == '-' || t == '*' || t == '/';
}
int calc(int left, char op, int right) {
switch(op) {
case '+': return left + right;
case '-': return left - right;
case '*': return left * right;
case '/': return left / right;
}
}
int evalRPN(vector<string>& tokens) {
stack<int> nums;
for (auto& token : tokens) {
if (is_operator(token[0]) && token.size() == 1) {
char op = token[0];
int right_num = nums.top();
nums.pop();
int left_num = nums.top();
nums.pop();
nums.push(calc(left_num, op, right_num));
} else {
nums.push(stoi(token));
}
}
return nums.top();
}

151 反转句子中的单词顺序

一般面试的时候会假定没有多余字符的,解法是

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
```
</details>


LeetCode 需要处理多余空格:


<details>
<summary>C 解答</summary>

```C
void swap(char *a, char *b) {
char tmp = *a; *a = *b; *b = tmp;
}

void reverse(char* start, char* end) {
while(start < end)
swap(start++, end--);
}

void trim(char* s) {

char* fast, *slow;
for (fast = s; *fast !='\0'; fast++) {
if (isspace(*fast)) {
while(isspace(*(fast + 1)) && *(fast + 1) != 0)
fast++;
if(*(fast+1) == 0)
break;
if(slow == s)
continue;
}
swap(fast, slow++);
}
*slow = 0;
}

void reverseWords(char *s) {
int len = strlen(s);
if (len == 0)
return;
trim(s);
len = strlen(s);
if (len == 0)
return;
reverse(s, s + len - 1);
char* head = s, * tail =s ;
while (*(tail + 1) != '\0') {
tail = head;
while (!isspace(*(tail + 1)) && *(tail + 1) != '\0')
tail++;
reverse(head, tail);
}
}

152 最大子序列乘积

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProduct(vector<int>& A) {
int n = A.size();
int r = A[0];
for (int i = 1, imax = r, imin = r; i < n; i++) {
if (A[i] < 0)
swap(imax, imin);

imax = max(A[i], imax * A[i]);
imin = min(A[i], imin * A[i]);

r = max(r, imax);
}
return r;
}

153 在旋转数组中查找最小值

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
int findMin(int* A, int n) {
int left = 0; int right = n - 1;
while (left < right - 1) {
int mid = left + (right - left) / 2;
if (A[left] > A[mid])
right = mid;
else if (A[right] < A[mid])
left = mid;
else
right = mid;
}
return A[left] < A[right] ? A[left] : A[right];
}

154 在旋转数组中查找最小值,可能有重复

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findMin(int* A, int n) {
int left = 0, right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (A[mid] > A[right]) { // 当需要找的是 left,也就是较小的数字,使用 right 比较不需要等于号
left = mid + 1;
} else if (A[right] < A[mid]) {
right = mid;
} else {
right--;
}
}
return A[left];
}

155 设计一个栈,在普通栈的基础上支持 getmin 操作

解法 1: 使用额外的栈,每个值都记录一个当前最小值,浪费空间

解法 2: 也是使用额外的栈,但是惰性记录,只有当需要更新的时候才去记录

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class MinStack {
private:
stack<int> m_stk;
stack<int> m_min;
public:
void push(int x) {
if (x <= getMin())
m_min.push(x);
m_stk.push(x);
}

void pop() {
if (m_stk.top() == getMin())
m_min.pop();
m_stk.pop();
}

int top() {
return m_stk.top();
}

int getMin() {
return m_min.empty() ? INT_MAX : m_min.top();
}
};

156-159 Locked

160 求两个链表的交叉点

分析题目可知,如果有一个交叉点,那么在这之后的所有点都是交叉的。这里有一个非常巧妙
的做法。使用两个指针,如果到达结尾就指向另一个链表,会产生一下三种情况:

  1. 如果交叉点前面的节点数目相同,显然会返回正确节点。
  2. 如果不同假设 A 的节点为 a + c,B 的节点为 b + c,则在下一次遍历时:
    a + c + b == b + c + a,恰好到达相同部分的第一个顶点 C1
  3. 如果两个列表不相交,那么经过 a + b, b + a 距离后,恰好都等于 NULL
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if (!headA || !headB) return NULL;
struct ListNode *p1 = headA, *p2=headB;
while (p1 != p2) {
// 两个列表手尾相接,如果有一个点相同,一定会返回
// a + c + b == b + c + a --> C1
// a + b == b + a --> NULL
p1 = p1 ? p1->next : headB;
p2 = p2 ? p2->next : headA;
}

return p1;
}

161 Locked

162 找到极大值,给定一个数组,可能有多个极大值,找到任意一个即可,给定数组中 A[i] != A[i+1]

题目要求在对数时间内做出来,二分搜索,如果中间的数在左半部分,就向右找。

C 解答
1
2
3
4
5
6
7
8
9
10
11
int findPeakElement(int* nums, int numsSize) {
int left = 0, right = numsSize - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) // mid in left part of summit
left = mid + 1;
else // mid in right part of summit
right= mid;
}
return left;
}

163 Locked

164 未排序数组中相差最大的两个数之间的差

根据抽屉原理,最大差不可能小于 (max - min) / (n - 1)。证明:如果小于,那么整个数组的大小就会小于 max - min。
因此我们把

165 比较版本号大小

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<int> ver(const string& version) {
vector<int> result;
int num = 0;
for (auto c : version) {
if (c != '.') {
num = num * 10 + c - '0';
} else {
result.push_back(num);
num = 0;
}
}
// 对于所有这种分割符中读取数字的都需要注意最后一个
result.push_back(num); // notice here
return result;
}

int compareVersion(string version1, string version2) {
auto v1 = ver(version1);
auto v2 = ver(version2);

for (int i = 0; i < v1.size() || i < v2.size(); i++) {
int a = i < v1.size() ? v1[i] : 0;
int b = i < v2.size() ? v2[i] : 0;
if (a != b)
return a > b ? 1 : -1;
}

return 0;
}

166 分数生成小数

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
string fractionToDecimal(long numerator, long denominator) {
if (numerator == 0) return "0";
string result;

// 符号
if (numerator < 0 ^ denominator < 0)
result += "-";
long n = abs(numerator), d = abs(denominator);

// 整数部分
result += to_string(n / d);
if (n % d == 0) return result;

// 小数部分
result+= ".";
unordered_map<int, int> map;
for (long r = n % d; r != 0; r %= d) { // 模拟手工除法
if (map.count(r) > 0) {
result.insert(map[r], 1, '(');
result += ")";
break;
}

map[r] = result.size(); // 记录对应的位置,以便插入括号
r *= 10; // 从上借位
result += to_string(r / d);
}
return result;
}

167 Locked

168 生成 Excel 表格标题

注意 A 对应的是 1 而不是 0,而且数字也是从 1 开始的

C++ 解答
1
2
3
4
5
6
7
8
9
string convertToTitle(int n) {
string title;
while (n) {
char c = (n-1) % 26 + 'A';
n = (n-1) / 26;
title = c + title;
}
return title;
}

169 给定一个数组,有一个数字的出现频率超过了一半,找出这个数字

非常经典的一道题,首先我们假设拿到的数字就是目标,并记录他出现的次数,如果下一个
数字和他不一样,那么我们减一,当次数为 0 的时候,我们知道这个数字在已经遍历过的数字
中出现小于一半了,这时候我们换下一个数字,最后剩下的一定是超过一半的数字。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
int majorityElement(vector<int>& nums) {
int candidate, count = 0;
for (auto i : nums) {
if (count == 0 || candidate == i) {
count++;
candidate = i;
} else {
count--;
}
}
return candidate;
}

170 Locked

171 Excel 标题转换为数字

同样,我们需要注意 A 对应的是 1,而不是 0

C 解答
1
2
3
4
5
6
int titleToNumber(char* s) {
int result = 0;
while (*s)
result = result * 26 + *s++ - 'A' + 1;
return result;
}

172 阶乘中能有几个 0

显然先算出阶乘数字是会溢出的,而有 0 的话,就是需要 10,也就是就需要 2 和 5,
显然 2 是比 5 多的。那么我们只要考虑 5 的个数就行了, 这时候需要注意,5/15 等是算一个 5,
而 25/75 包含了两个 5,所以我们计算的时候,数一遍包含 5 的(这时 25 等也被计算了),
然后再数一遍包含 25 的就像当于数了两次了。

C 解答
1
2
3
4
5
6
7
8
int trailingZeroes(int n) {
if (n < 0)
return -1;
int fives = 0;
for (int i = 5; n / i > 0; i *= 5)
fives += n / i;
return fives;
}

173 二叉树中序遍历迭代器

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
pushAll(root);
}

/** @return whether we have a next smallest number */
bool hasNext() {
return !m_stack.empty();

}

/** @return the next smallest number */
int next() {
TreeNode* temp = m_stack.top();
m_stack.pop();
pushAll(temp->right);
return temp->val;
}

private:
stack<TreeNode*> m_stack;
void pushAll(TreeNode* root) {
while (root) {
m_stack.push(root);
root = root->left;
}
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

174 地下城游戏

王子在格子的左上角,需要到右下角去救公主,在过程中王子不能死掉,和机器人走路一样,使用动态规划

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int row = dungeon.size();
int col = dungeon[0].size();
vector<vector<int>> bloods(row + 1, vector<int> (col + 1, INT_MAX));
bloods[row][col-1] = bloods[row-1][col] = 1; // 公主的两边
// 从公主那里逆向推
for (int i = row-1; i >= 0; i--) {
for (int j = col-1; j >= 0; j--) {
int need = min(bloods[i+1][j], bloods[i][j+1]) - dungeon[i][j]; // 缺乏的血量 = 到达下一步最少的血量 - 这一步消耗的血量
bloods[i][j] = need > 0 ? need : 1; // 王子的血量至少为 1
}
}
return bloods[0][0];
}

175-178 Missing

179 最大的数字

神奇的排序方法

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string largestNumber(vector<int>& nums) {
vector<string> num_strings(nums.size());
for (int i = 0; i < nums.size(); i++)
num_strings[i] = to_string(nums[i]);
auto comparator = [] (string& s1, string& s2) {
return s1 + s2 > s2 + s1;
};
sort(num_strings.begin(), num_strings.end(), comparator);
string result;
for (auto& num_string: num_strings)
result += num_string;
int start = result.find_first_not_of("0");
if (start == string::npos) return "0";
return result.substr(start);
}

180-185 Missing

186 Locked

187 找到所有 10 个字母唱的重复 DNA 序列

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
// naive 的做法从前往后,记录字符串
// 观察 ATCG 四个字符的特征,并把他们编码为一个 int
// 十个字符正好编码在 32bit 的 int 中
vector<string> findRepeatedDnaSequences(string s) {
unordered_map<int, int> hash;
vector<string> result;
for (int t = 0, i = 0; i < s.size(); i++)
// 左移弹出老元素,求交为了只使用 30bit,求或添加新元素。
if (hash[t = t << 3 & 0x3FFFFFFF | s[i] & 0b111]++ == 1) // 等于 1 为了避免重复
result.push_back(s.substr(i - 9, 10));
return result;
}

189 翻转树组

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void reverse(int* nums, int left, int right) {
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}

}

void rotate(int* nums, int numsSize, int k) {
if (k >= numsSize) k %= numsSize;
if (k <= 0) return;
reverse(nums, 0, numsSize - k - 1);
reverse(nums, numsSize - k, numsSize - 1);
reverse(nums, 0, numsSize - 1);
}

190 翻转二进制表示

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
uint32_t reverseBits(uint32_t n) {
uint32_t r = 0;
int len = sizeof(n) * 8 - 1;
while (len--) { // 31 times shift
r |= n & 0x1;
n >>= 1;
r <<= 1; // only shift 31 times
}

r |= n & 0x1;
return r;
}

191 数字二进制表示中 1 的个数

我们知道 n&(n-1) 会把 n 中的最后一个 1 去掉,所以循环直到 n 为 0 即可

C 解答
1
2
3
4
5
6
7
8
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
n &= n - 1;
count++;
}
return count;
}

还可以采用查表法,对于表我们可以预先构造,或者利用上一个方法生成,对于长度过大的,我们可以分块查表。

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <stdlib.h>

int counts[16];

int _get_count(n) {
int count = 0;
while (n) {
n &= n-1;
count++;
}
return count;
}

int init_counts() {
for (int i = 0; i < 16; i++)
counts[i] = _get_count(i);
};

int get_count(n) {
int count = 0;
while (n) {
int index = n & 0xF;
count += counts[index];
n >>= 4;
}
return count;
}

int main() {
init_counts();
for (int i = 0; i < 100; i++)
printf("%d: %d\n", _get_count(i), get_count(i));
return 0;
}

192-197 Missing

198 有一排房子,每个房子中都有一定财产,但是不能偷相邻的两个房子,求能偷到的最大值

使用 DP,对于每个房子,可以选择不偷或者前 i-1 个房子加上偷当前房子,即dp[i+1] = max(dp[i], dp[i-1] + A[i])

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
int rob(int* nums, int numsSize) {
if (!nums) return 0;
// 因为不能相邻,所以可以从相隔一个的取值
// dp[n] = max(dp[n-1], dp[n-2] + A[n])
int temp, m = 0, n = nums[0];
for (int i = 1; i < numsSize; i++) {
temp = n;
if (m + nums[i] > n)
n = m + nums[i];
m = temp;
}
return n;
}

199 从右边看二叉树的效果

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// level order 遍历
vector<int> rightSideView(TreeNode* root) {
vector<int> result;
if (!root)
return result;
queue<TreeNode*> q;
q.push(root);

while (!q.empty()) {
TreeNode* node;
int len = q.size(); // 保存为了获得最后一个元素
for (int i = 0; i < len; i++) { // 当前数组的最后一个元素就是最右边的元素
node = q.front();
q.pop();
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
result.push_back(node->val);
}
return result;
}

200 找出小岛的数量

采用并查集,找到最后集合的数量

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class UnionFind {
private:
vector<int> m_father, m_rank;
int m_count; // sets count
public:
UnionFind(int n): m_father(n), m_rank(n, 0), m_count(n) {
for (int i = 0; i < m_father.size(); i++)
m_father[i] = i;
}

int find(int x) {
if (x != m_father[x])
m_father[x] = find(m_father[x]);
return m_father[x];
}

void unionify(int x, int y) {
x = find(x);
y = find(y);

if (x == y) return;

if (m_rank[x] > m_rank[y]) {
m_father[y] = x;
} else {
if (m_rank[x] == m_rank[y])
m_rank[y]++;
m_father[x] = y;
}
m_count--;
}

int getCount() {
return m_count;
}
};

class Solution {
const static char LAND = '1';
const static char WATER = '0';

public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty())
return 0;
int r = grid.size(), c = grid[0].size();
UnionFind uf(r * c + 1); // extra element is for water
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] == LAND) {
if (i != r - 1 && grid[i+1][j] == LAND)
uf.unionify(i*c+j, (i+1)*c+j);
if (j != c - 1 && grid[i][j+1] == LAND)
uf .unionify(i*c+j, i*c+j+1);
} else {
uf.unionify(i*c+j, c*r);
}
}
}
return uf.getCount() - 1; // islands + water - 1;
}
};
python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class UnionFind:
def __init__(self, count):
self.count = count
self.parents = list(range(count)) # 初始化时 parent 指针指向自己
self.ranks = [1] * count # 记录每棵树的大小

def union(self, p, q):
"""把 p, q 两个节点连通起来"""
p_root = self.find(p)
q_root = self.find(q)
if p_root == q_root:
return
if self.ranks[p_root] > self.ranks[q_root]:
self.parents[q_root] = p_root
else:
if self.ranks[p_root] == self.ranks[q_root]:
self.ranks[q_root] += 1
self.parents[p_root] = q_root
self.count -= 1

def find(self, p):
"""找到 p 节点的根节点"""
while self.parents[p] != p:
# 神奇的路径压缩
self.parents[p] = self.parents[self.parents[p]]
p = self.parents[p]
return p

def is_connected(self, p, q):
p_root = self.find(p)
q_root = self.find(q)
return p_root == q_root


class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0

m = len(grid)
n = len(grid[0])

uf = UnionFind(m * n + 1)
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
up = max(i - 1, 0)
if grid[up][j] == "1":
uf.union(i * n + j, up * n + j)
left = max(j - 1, 0)
if grid[i][j - 1] == "1":
uf.union(i * n + j, i * n + left)
else:
uf.union(i * n + j, m * n)
return uf.count - 1

201 给定区间内,所有数字 AND 的结果

显然直接过一遍是会超时的,那么分析可知

C 解答
1
2
3
4
5
6
7
8
9
10
// 如果两个数不相等,一定是有不同的位,那么这一位一定为 0
int rangeBitwiseAnd(int m, int n) {
int t = 0;
while (m != n) {
t++;
m >>= 1;
n >>= 1;
}
return m << t;
}

202 快乐数字,各位数字平方相加得到下一个数字,如果最后等于 1

没啥,一直算就可以了。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
bool isHappy(int n) {
while (n > 6) {
int next = 0;
while (n) {
next += (n%10) * (n%10);
n /= 10;
}
n = next;
}
return n == 1;
}

203 删除链表中给定的值

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode dummy, *p = &dummy;
dummy.next = head;
while (p) {
if (p->next && p->next->val == val) { // not forward here
struct ListNode* next = p->next;
p->next = next->next;
free(next);
} else {
p = p->next;
}

}
return dummy.next;
}

204 找出素数

什么筛子,忘了

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int countPrimes(int n) {
vector<bool> primes(n, true);
primes[0] = primes[1] = false;

for (int i = 2; i * i < n; i++) // 注意,只到 sqrt(n)
if (primes[i])
for (int j = i * i; j < n; j += i) // 从 i * i 开始,因为 i* i-- 已经被杀过了
primes[j] = false;

int count = 0;
for (int i = 2; i < n; i++)
if (primes[i])
count++;
return count;
}

205 同构字符串,可以看作 word pattern 的简化

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isIsomorphic(char* s, char* t) {
int ss[256] = { 0 };
int ts[256] = { 0 };
if (strlen(s) != strlen(t))
return false;
int i = 0;
while (s[i]) {
if (ss[s[i]] != ts[t[i]])
return false;
ss[s[i]] = ts[t[i]] = i + 1;
i++;
}
return true;
}

206 反转链表

tags: #pointers

最最基础的指针操作题目了

Python 解答
1
2
3
4
5
6
7
8
9
10
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev # 关键在这里
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
struct ListNode* reverseList(struct ListNode* head) {
if (!head || !head->next)
return head;
struct ListNode *p = NULL, *cur = head, *next;

while (cur) {
next = cur->next; // cache
cur->next = p; // reverse pointing
p = cur; // moves forwards
cur = next;
}
return p;
}
C 解答
1
// recursive

207 标准的拓扑排序

给定边这种方法表示图也是醉了

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { // next -> before
vector<unordered_set<int>> graph(numCourses); // 每条边和他的下一步,临接表
for (auto& p : prerequisites)
graph[p.second].insert(p.first);

vector<int> d(numCourses, 0); // in degree

for (auto& nexts : graph)
for (auto next : nexts)
d[next]++;

for (int i = 0; i < numCourses; i++) {
int nondep; // in degree == 0
for (nondep = 0; nondep < numCourses && d[nondep] != 0; nondep++)
;
if (nondep == numCourses)
return false;
d[nondep] = -1; // remove
for (auto next : graph[nondep]) // 所有下一步都 -1
d[next]--;
}

return true;
}

208 实现前缀树

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class TrieNode {
public:
static const int branchCount = 26;
bool isWord;
TrieNode* next[branchCount];
// Initialize your data structure here.
TrieNode() : isWord(false) {
for (int i = 0; i < branchCount; i++)
next[i] = NULL;
}
};

class Trie {
public:
Trie() {
root = new TrieNode();
}

// Inserts a word into the trie.
void insert(string word) {
TrieNode* location = root;
for (auto& c : word) {
if (!location->next[c - 'a'])
location->next[c - 'a'] = new TrieNode;
location = location->next[c - 'a'];
}
location->isWord = true;
}

// Returns if the word is in the trie.
bool search(string word) {
TrieNode* location = root;
for (auto& c : word) {
location = location->next[c - 'a'];
if (!location)
return false;
}
return location->isWord;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode* location = root;
for (auto& c : prefix) {
location = location->next[c - 'a'];
if (!location)
return false;
}
return true;
}

private:
TrieNode* root;
};

// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");

209 最短子数组使得和大于某个数

双指针,超过和之后再尝试从开始处减去元素

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
int minSubArrayLen(int s, vector<int>& nums) {
int start = 0, sum = 0, len = INT_MAX;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
while (sum >= s) {
len = min(len, i - start + 1);
sum -= nums[start++];
}
}

return len == INT_MAX? 0 : len;
}

210 Course Schedule II

BFS

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
vector<int> degrees = compute_indegree(graph);
queue<int> zeros;
for (int i = 0; i < numCourses; i++)
if (!degrees[i]) zeros.push(i);
vector<int> toposort;
for (int i = 0; i < numCourses; i++) {
if (zeros.empty()) return {};
int zero = zeros.front();
zeros.pop();
toposort.push_back(zero);
for (int neigh : graph[zero]) {
if (!--degrees[neigh])
zeros.push(neigh);
}
}
return toposort;
}
private:
vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph(numCourses);
for (auto pre : prerequisites)
graph[pre.second].insert(pre.first);
return graph;
}
vector<int> compute_indegree(vector<unordered_set<int>>& graph) {
vector<int> degrees(graph.size(), 0);
for (auto neighbors : graph)
for (int neigh : neighbors)
degrees[neigh]++;
return degrees;
}
};

211 添加和搜索字符串

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class TrieNode {
public:
static const int branchCount = 26;
bool isWord;
TrieNode* next[branchCount];
// Initialize your data structure here.
TrieNode() : isWord(false) {
for (int i = 0; i < branchCount; i++)
next[i] = NULL;
}
};

class Trie {
public:
Trie() {
root = new TrieNode();
}

// Inserts a word into the trie.
void insert(string word) {
TrieNode* location = root;
for (auto& c : word) {
if (!location->next[c - 'a'])
location->next[c - 'a'] = new TrieNode;
location = location->next[c - 'a'];
}
location->isWord = true;
}

// Returns if the word is in the trie.
virtual bool search(string word) {
TrieNode* location = root;
for (auto& c : word) {
location = location->next[c - 'a'];
if (!location)
return false;
}
return location->isWord;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode* location = root;
for (auto& c : prefix) {
location = location->next[c - 'a'];
if (!location)
return false;
}
return true;
}

TrieNode* getRoot() {
return root;
}

private:
TrieNode* root;
};


class WordDictionary : public Trie{

public:
WordDictionary() : Trie(){}

// Adds a word into the data structure.
void addWord(string word) {
insert(word);
}

// Returns if the word is in the data structure. A word could
// contain the dot character '.' to represent any one letter.
bool search(string word) override {
return search(word.c_str(), getRoot());
}

bool search(const char* word, TrieNode* root) {
TrieNode* run = root;
for (int i = 0; word[i]; i++) {
if (run && word[i] != '.')
run = run->next[word[i] - 'a'];
else if (run && word[i] == '.') {

// skip checking this char
TrieNode* tmp = run;
for (int j = 0; j < 26; j++) {
run = tmp->next[j];
if (search(word + i + 1, run))
return true;
}
}
else break;
}
return run && run->isWord;
}
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

212 单词搜索

Trie 结构见前面,注意要记录 visited,还有边界的问题,另外集合的使用

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
private:
Trie m_trie;
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
for (auto& word : words)
m_trie.insert(word);
int row = board.size();
int col = board[0].size();

unordered_set<string> result_set;
vector<vector<bool>> visited(row, vector<bool>(col, false));
for (int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
find(result_set, board, visited, "", i, j);
vector<string> result;
for (auto& r : result_set)
result.push_back(r);
return result;
}

void find(unordered_set<string>& r, vector<vector<char>>& board, vector<vector<bool>>& visited, string word, int i, int j) {
if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j])
return;
word += board[i][j];
if (!m_trie.startsWith(word))
return;
if (m_trie.search(word))
r.insert(word);

visited[i][j] = true;
find(r, board, visited, word, i-1, j);
find(r, board, visited, word, i+1, j);
find(r, board, visited, word, i, j-1);
find(r, board, visited, word, i, j+1);
visited[i][j] = false;

}

};

213 小偷偷环状数组

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int max(int a, int b) {
return a > b ? a : b;
}

int robNonCyclic(int* nums, int numsSize) {
if (!nums) return 0;
// 因为不能相邻,所以可以从相隔一个的取值
// dp[n] = max(dp[n-1], dp[n-2] + A[n])
int temp, m = 0, n = nums[0];
for (int i = 1; i < numsSize; i++) {
temp = n;
if (m + nums[i] > n)
n = m + nums[i];
m = temp;
}
return n;
}

int rob(int* nums, int numsSize) {
return max(robNonCyclic(nums, numsSize - 1), robNonCyclic(nums + 1, numsSize - 1));
}

214 最短回文字符串,给指定的字符串添加字母获得回文

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// based on kmp next array
string shortestPalindrome(string s) {
string rev_s = s;
reverse(rev_s.begin(), rev_s.end());
string l = s + "#" + rev_s;

vector<int> p(l.size(), 0);
for (int i = 1; i < l.size(); i++) {
int j = p[i - 1];
while (j > 0 && l[i] != l[j])
j = p[j - 1];
p[i] = (j += l[i] == l[j]);
}

return rev_s.substr(0, s.size() - p[l.size() - 1]) + s;
}

215 数组中第 k 大的数字

实际上这道题更可能的题目是找到前 k 大的所有数字。
首先,设计到数组排序的问题一定向面试官要问清楚数据量的大小,这影响到接下来的实现,
同时和面试官探讨数据量大小对实现的影响,有助于更好的把握局面。

我们先假设数据量是比较小的,也就是能够放到内存中。

  1. 使用排序就实在是 naive 了,不过面试官非要问的话,当然是使用选择排序更好了。
  2. 使用快排中的 partition 算法,时间复杂度 O(n*logk)。
  3. 使用 size 为 k 的堆,时间复杂度也是 O(n*logk),不管数字多大,都只需要遍历一遍。
  4. 使用类似插入排序的方法,保持数组大小不变,这样的时间复杂度是 O(n*k)。
  5. 数据的范围有限时候,使用计数排序。

当数据过大的时候,我们可以想通过哈希取模之后把文件分组,找出每个文件中最大的 k 个数字

如果数字中有重复呢?使用计数排序,计数强制按一算
如果既有重复又是浮点数呢?

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}

int partition(int* nums, int start, int end) {
int small = start - 1;
int pivot = nums[end];
for (int i = start; i < end; i++)
if (nums[i] < pivot)
swap(&nums[++small], &nums[i]);
swap(&nums[++small], &nums[end]);
return small;
}

int findKthLargest(int* nums, int numsSize, int k) {
int left = 0, right = numsSize - 1;
while (1) {
int index = partition(nums, left, right);
if (index == numsSize - k)
return nums[index];
if (index > numsSize - k)
right = index - 1;
else
left = index + 1;
}
}

216 找到 k 个数字 [1…9],使得他们的和是 n

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
dfs(result, {}, n, k);
return result;
}

void dfs(vector<vector<int>>& result, vector<int> combination, int n, int k) {
if (combination.size() == k) {
if (n == 0)
result.push_back(combination);
return;
}
int i = combination.empty() ? 1 : combination.back() + 1; // 保证不重复切实递增序列
while (i <= n && i < 10) {
combination.push_back(i);
dfs(result, combination, n-i, k);
combination.pop_back();
i++;
}
}

217 包含重复数字

这道题太简单了,也没有什么精妙的解法,可以使用排序,Hash 等多种解法

C++ 解答
1
2
3
4
5
6
7
8
9
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> s;
for (auto& n : nums)
if (s.find(n) != s.end())
return true;
else
s.insert(n);
return false;
}

218 获得矩形重合部分的拐点

抄过来的,还没仔细研究

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> res;
int cur=0, cur_X, cur_H =-1, len = buildings.size();
priority_queue< pair<int, int>> liveBlg; // first: height, second, end time
while(cur<len || !liveBlg.empty()) { // if either some new building is not processed or live building queue is not empty
cur_X = liveBlg.empty()? buildings[cur][0]:liveBlg.top().second; // next timing point to process

if(cur>=len || buildings[cur][0] > cur_X) { //first check if the current tallest building will end before the next timing point
// pop up the processed buildings, i.e. those have height no larger than cur_H and end before the top one
while(!liveBlg.empty() && ( liveBlg.top().second <= cur_X) ) liveBlg.pop();
} else { // if the next new building starts before the top one ends, process the new building in the vector
cur_X = buildings[cur][0];
while(cur<len && buildings[cur][0]== cur_X) // go through all the new buildings that starts at the same point
{ // just push them in the queue
liveBlg.push(make_pair(buildings[cur][2], buildings[cur][1]));
cur++;
}
}
cur_H = liveBlg.empty()?0:liveBlg.top().first; // outut the top one
if(res.empty() || (res.back().second != cur_H) ) res.push_back(make_pair(cur_X, cur_H));
}
return res;
}

219 包含重复数字,并且两个的坐标不超过 k

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 滑动窗口保存前 k 个值,如果有重复的就返回
// num[i-k] num[i-1],如果滑过了,就删除该元素
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> s;
if (k <= 0)
return false;
if (k >= nums.size()) // notice here
k = nums.size() - 1;

for (int i = 0; i < nums.size(); i++) {
if (i > k)
s.erase(nums[i - k - 1]); // delete first note
if (s.find(nums[i]) != s.end())
return true;
s.insert(nums[i]); // insert
}

return false;
}

220 同上一题,同时保证两个数字之间小于 t

保证两个数字之差小于 t

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<int> window; // 注意不能使用 unordered
if (k <= 0)
return false;
if (k >= nums.size()) // notice here
k = nums.size() - 1;
for (int i = 0; i < nums.size(); i++) {
if (i > k)
window.erase(nums[i - k - 1]);
auto pos = window.lower_bound(nums[i] - t); // notice set.lower_bound
if (pos != window.end() && *pos - nums[i] <= t)
return true;
window.insert(nums[i]);
}
return false;
}

221 找到最大的正方形

使用动态规划 https://leetcode.com/discuss/38489/easy-solution-with-detailed-explanations-8ms-time-and-space

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> dp(m + 1, 0);
int maxsize = 0, pre = 0;
for (int j = 0; j < n; j++) { // 每一列
for (int i = 1; i <= m; i++) { // notice i range
int temp = dp[i];
if (matrix[i - 1][j] == '1') {
dp[i] = min(dp[i], min(dp[i - 1], pre)) + 1;
maxsize = max(maxsize, dp[i]);
}
else dp[i] = 0;
pre = temp;
}
}
return maxsize * maxsize;
}

222 给定一个完全树,计算节点的数量。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int countNodes(struct TreeNode* root) {
if (!root)
return 0;
int left_height = 0, right_height = 0;
struct TreeNode* left = root, *right = root;
while (left) {
left = left->left;
left_height++;
}

while (right) {
right = right->right;
right_height++;
}

if (left_height == right_height) // 满树 2^h - 1
return (1 << left_height) - 1;

return countNodes(root->left) + countNodes(root->right) + 1;
}

223 找出两个长方形覆盖的面积

C 解答
1
2
3
4
5
6
7
8
9
10
int computeArea(int left1, int down1, int right1, int up1, int left2, int down2, int right2, int up2) {
int left = max(left1, left2); // 靠右的
int right = max(min(right1, right2), left);// 靠左的,但是比左边大

int down = max(down1, down2);
int up = max(min(up1, up2), down);

// 不小心写反了。
return -((left1 - right1) * (up1 - down1) + (left2 - right2) * (up2 - down2) - (left - right) * (up - down));
}

224 给定一个字符串,包含加减和括号,计算值

难点是对括号的处理,注意每次都要和 signs.top() 相乘

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int calculate(string s) {
stack<int> signs; // signs before braces
int sign = 1;
int num = 0;
int result = 0;

signs.push(1);
for (auto c : s) {
if (isdigit(c)) {
num = 10 * num + (c - '0');
} else if (c == '+' || c == '-') {
result += signs.top() * sign * num;
num = 0;
sign = c == '+' ? 1 : -1;
} else if (c == '(') {
signs.push(sign * signs.top()); // tricky
sign = 1;
} else if (c == ')') {
result += signs.top() * sign * num;
num = 0;
signs.pop();
sign = 1;
}
}

result += signs.top() * sign * num; // tricky

return result;
}

225 使用队列模拟栈

其实有两种做法,一种是在 push 的时候,把队列清空,把 x 放到最底下。
另一种是在 pop 的时候,把队列清空到 1,然后弹出。应当询问面试官究竟是 push 居多还是 pop 居多

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Stack {
public:
// Push element x onto stack.
void push(int x) {
while (!nums.empty()) {
temp.push(nums.front());
nums.pop();
}
nums.push(x);
while (!temp.empty()) {
nums.push(temp.front());
temp.pop();
}
}

// Removes the element on top of the stack.
void pop() {
nums.pop();
}

// Get the top element.
int top() {
return nums.front();
}

// Return whether the stack is empty.
bool empty() {
return nums.empty();
}
private:
queue<int> nums;
queue<int> temp;
};

226 反转二叉树

C 解答
1
2
3
4
5
6
7
struct TreeNode* invertTree(struct TreeNode* root) {
if (!root) return NULL;
struct TreeNode* temp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(temp);
return root;
}

227 给定一个字符串包含 +-*/ 计算他的值

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int calculate(string s) {
vector<int> stk; // 使用 vector 便于统计最后的值
char token = '+';
int num = 0;
for (int i = 0; i < s.size(); i++) {
if (isdigit(s[i]))
num = num * 10 + s[i] - '0';
// 这里不是 else if
if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == s.size() - 1) { // 注意最后一步还需要把最后的值计算
int a;
switch (token) {
case '+':
stk.push_back(num);
break;
case '-':
stk.push_back(-num);
break;
case '*':
a = stk.back();
stk.pop_back();
stk.push_back(a * num);
break;
case '/':
a = stk.back();
stk.pop_back();
stk.push_back(a / num);
break;
};
token = s[i];
num = 0;
}
}

int result = 0;
for (auto i : stk)
result += i;
return result;
}

228 聚合区间,给定一排序数组,把相邻的数字用区间表示

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<string> summaryRanges(vector<int>& nums) {
int n = nums.size();
vector<string> result;
if (n == 0) return result;

for (int i = 0; i < n; ) {
int start = i, end = i;
while (end + 1 < n && nums[end + 1] == nums[end] + 1)
end++;
if (end > start)
result.push_back(to_string(nums[start]) + "->" + to_string(nums[end]));
else
result.push_back(to_string(nums[start]));
i = end + 1;
}

return result;
}

229 找出超过三分之一的元素

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
vector<int> majorityElement(vector<int>& nums) {

int count1 = 0, count2 = 0;
int a, b;

for (auto n : nums) {
if (count1 == 0 || n == a) {
count1++;
a = n;
} else if (count2 == 0 || n == b) {
count2++;
b = n;
} else {
count1--;
count2--;
}
}

count1 = count2 = 0;
for (int n : nums) {
if (n == a) count1++;
if (n == b) count2++;
}

vector<int> result;

if (count1 > nums.size() / 3) // verify a
result.push_back(a);
if (count2 > nums.size() / 3 && a != b) // verify b
result.push_back(b);
return result;
}

230 二叉树中第 k 小的数字

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 传递指针
void inorder(struct TreeNode* root, int* k, int* number) {
if (!root)
return;
inorder(root->left, k, number);
(*k)--;
if (*k == 0) {
*number = root->val;
return;
}
inorder(root->right, k, number);
}
int kthSmallest(struct TreeNode* root, int k) {
int number;
inorder(root, &k, &number);
return number;
}

231 2 的次方

C 解答
1
2
3
4
bool isPowerOfTwo(int n) {
if (n <= 0) return false;
return (n & (n - 1)) == 0;
}
Rust 解答
1
2
3
4
5
6
7
8
impl Solution {
pub fn is_power_of_two(n: i32) -> bool {
if n <= 0 {
return false;
}
(n & (n-1)) == 0
}
}

232 使用栈模拟队列

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Queue {
public:
// Push element x to the back of queue.
void push(int x) {
in.push(x);
}

// Removes the element from in front of queue.
void pop(void) {
if (empty())
return;
if (out.empty())
transfer();
out.pop();
}

// Get the front element.
int peek(void) {
if (empty())
return INT_MIN;
if (out.empty())
transfer();
return out.top();
}

// Return whether the queue is empty.
bool empty(void) {
return in.empty() && out.empty();
}
private:
void transfer() {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
};
stack<int> in;
stack<int> out;
};

233 小于 n 的数字中 1 的个数

对于每一位,有三种情况:

  1. 当是数字 0 的时候,可能出先 1 的情况完全由高位出现决定,因为这一位不能贡献 1
  2. 当是数字 1 的时候,同上,但是这一位和低位一起可以贡献一个 1
  3. 当时数字 2-9 的时候,相当于这一位的 1 可以任意出现,因此高位+1
C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
int countDigitOne(int n) {
int ones = 0;
for (int m = 1; m <= n; m *= 10) { // m is the factor
int a = n/m, b = n%m; // a is left half, b is right half
if (a % 10 >= 2)
ones += (a / 10 + 1) * m;
if (a % 10 == 1)
ones += (a / 10) * m + b + 1;
if (a % 10 == 0)
ones += (a / 10) * m;
}
return ones;
}

二进制呢

C 解答
1
2
3
4
5
6
7
8
9
10
int countDigitOneBinary(int n) {
int ones = 0;
for (int m = 1; m <= n; m <<= 1) {
int a = n / m, b = n % m;
if (a & 0x01)
ones += (a >> 1) * m + b + 1;
else
ones += (a >> 1) * m;
}
}

求最大的 countDigitOne(n) == n

9    1
99   20
999  300
...
99999999  10000000

234 判断一个链表是否是回文

解法 1: 如果链表是可以改变的,不妨反转它的前半部分,然后再与后半部分比较

解法 2: 如果是只读的,复制一份也可以,但是不如使用堆栈

注意对奇数偶数的处理

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool isPalindrome(ListNode* head) {
if (!head || !head->next)
return true;
int len = 0;
ListNode* temp = head;
while (temp) {
len++;
temp = temp->next;
}

stack<int> stk;
temp = head;
int mid = len / 2;
while (mid--) {
stk.push(temp->val);
temp = temp->next;
}

if (len & 0x01)
temp = temp->next;

while (temp != NULL && !stk.empty()) {
int a = stk.top();
stk.pop();
int b = temp->val;
temp = temp->next;
if (a != b) {
return false;
}
}

return true;
}

235 二叉搜索树公共祖先

C 解答
1
2
3
4
5
6
7
8
9
10
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
while (root) {
if (root->val > p->val && root->val > q->val)
root = root->left;
else if (root->val < p->val && root->val < q->val)
root = root->right;
else
return root;
}
}

236 二叉树公共祖先

如果二叉树的根就是其中一个节点,那显然是这个。
在两颗子树中分别查找,如果找到了,返回一个非 NULL 值,如果都找到了,则这个节点就是 LCA

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if (!root || root == p || root == q)
return root;
struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

if (!left) // not in left subtree
return right;
if (!right)
return left;
return root; // both left and right are found!
}

237 删除链表中的元素

直接将后继节点的值复制到当前节点

C 解答
1
2
3
4
5
6
7
8
void deleteNode(struct ListNode* node) {
if (!node || !node->next)
return;
struct ListNode* next = node->next;
node->val = next->val;
node->next = next->next;
free(next);
}

238 数组除了自己以外的乘积,规定不能用除法

首先从前往后乘,错开一位元素,这样每个元素都乘到了他之前的所有元素,最后一个元素已经是结果了。
然后从后往前乘,同样错开一位,这样每个元素又把他之后的元素都得到了。

239 滑动窗口最大值,给定一个滑动窗口,返回它移动过程中的最大值

单调队列的应用,复杂度是 O(n) 的。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from collections import deque

class MonoQueue:
def __init__(self):
self.q = deque() # 实际储存数据
self.m = deque() # 维护单调关系,队首元素总是最大值

def push(self, x):
self.q.append(x)
while len(self.m) > 0 and self.m[-1] < x:
self.m.pop()
self.m.append(x)

def pop(self):
x = self.q.popleft()
if self.m[0] == x:
self.m.popleft()
return x

def __len__(self):
return len(self.q)

def top(self):
return self.m[0]

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = MonoQueue()
for i in range(k):
q.push(nums[i])
ans = []
for i in range(k, len(nums)):
ans.append(q.top())
q.pop()
q.push(nums[i])
ans.append(q.top())
return ans

另一种现在我已经看不懂的做法

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 题目给定 k 一定是有效地
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
if (nums.empty() || k <= 0)
return result;
deque<int> dq; // 存储的是索引,front 存储最大值,保证递减
for (int i = 0; i < nums.size(); i++) {
while (!dq.empty() && dq.front() < i - k + 1) // 弹出滑过的窗口
dq.pop_front();
while (!dq.empty() && nums[dq.back()] < nums[i]) // 弹出小的
dq.pop_back();
dq.push_back(i);
if (i >= k - 1)
result.push_back(nums[dq.front()]);
}
return result;
}

240 给定一个矩阵,每行从左到右都是增大的,每一列从上到下都是增大的,找出给定数字是否存在

我们考虑右上角的元素

  1. 如果这个元素比 taget 大,那么整列都比 target 大,我们可以 c–
  2. 如果这个元素比 target 小,那么正行都比 target 小,我们可以 r++
C 解答
1
2
3
4
5
6
7
8
9
10
11
bool searchMatrix(int** matrix, int row, int col, int target) {
int r = 0, c = col - 1; // 右上角
while (r < row && c > -1) // 向左下角
if (matrix[r][c] == target)
return true;
else if (matrix[r][c] > target)
c--;
else
r++;
return false;
}

241 添加括号得到不同的结果

对每一个符号,在他的两边添加括号的好的不同结果再计算。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> diffWaysToCompute(string input) {
vector<int> output;
for (int i = 0; i < input.size(); i++) {
char token = input[i];
if (!isdigit(token)) // not digit
for (int a : diffWaysToCompute(input.substr(0, i))) // 左半部分
for (int b : diffWaysToCompute(input.substr(i+1))) // 右半部分
output.push_back(token == '+' ? a + b : token == '-'? a - b: a *b); // 两半部分之和
}

if (output.empty())
output.push_back(stoi(input));
return output;
}

242 一个单词是否能由另一个变幻而来

还是,对于 ASCII 字符,直接用数组代替字典

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
bool isAnagram(char* s, char* t) {
char ss[26] = {0};
char ts[26] = {0};
while (*s) {
ss[*s - 'a']++;
s++;
ts[*t - 'a']++;
t++;
}
if (*t) return false;
return memcmp(ss, ts, sizeof(ss)) == 0;
}

243-256 Locked

257 二叉树左右路径

典型的 DFS,发挥所有从根节点到叶节点的路径

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
if (!root) return result;
paths(result, "", root);
return result;
}

void paths(vector<string>& result, string path, TreeNode* root) {
if (path.empty())
path += to_string(root->val);
else
path += "->" + to_string(root->val);
if (root->left)
paths(result, path, root->left);
if (root->right)
paths(result, path, root->right);
if (!root->left && !root->right)
result.push_back(path);
}

258 把数字的每一位加起来,直到变成一个一位的数字

这完全是一道数学题,对于每个进制的数字都有规律 (n - 1) % (x - 1) + 1。实际上是把 10 进制的转化为 9 进制数字

C 解答
1
2
3
int addDigits(int num) {
return (num - 1) % 9 + 1;
}

259 Locked

260 给定一个数组,每个数字都是重复的,只有两个数字不是,找出这两个数字

这道题很奇妙,依然可以使用 XOR 来解,首先遍历一遍,这时候由于有两个数字是不同的,那么一定结果不为 0,那么其中一个 bit 位一定是一个数字有,另一个数字没有。
在遍历一遍,同时把数字分两组,一组是有这个 bit 位,一组没有。就得出了结果。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> singleNumber(vector<int>& nums) {
int r = 0;
for (auto& n : nums)
r ^= n;
int bit = r & -r; // last sig bit

vector<int> result = {0, 0};
for (auto& n : nums)
if (n & bit)
result[0] ^= n;
else
result[1] ^= n;
return result;
}

261 262 Locked

263 丑陋的数字,质数因子只含有 2,3,5 的数字

按定义做就好了

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isUgly(int n) {
if (n <= 0)
return false;
if (n == 1)
return true;
while (n > 1)
if (n % 2 == 0)
n /= 2;
else if (n % 3 == 0)
n /= 3;
else if (n % 5 == 0)
n /= 5;
else
return false;
return true;
}

264 找出第 n 个丑陋数字

使用数列记录 n 个丑陋数字,每一个丑陋数字肯定是之前数字乘以 235 得到的,然后用三个指针分别指向上一个做乘法的数字,每次找出最小的一个

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MIN(a,b) ((a)<(b)?(a):(b))

int nthUglyNumber(int n) {
if (n <= 0)
return -1;
if (n < 6) // 1..6 恰好都是
return n;
int s2 = 0, s3 = 0, s5 = 0;
int* uglies[n];
uglies[0] = 1;
for (int i = 1; i < n; i++) {
int c2 = uglies[s2] * 2, c3 = uglies[s3] * 3, c5 = uglies[s5] * 5;
uglies[i] = MIN(c2, MIN(c3, c5));
if (uglies[i] == c2) s2++;
if (uglies[i] == c3) s3++;
if (uglies[i] == c5) s5++;
}
return uglies[n-1];
}

268 丢失的数字,给定 0…n,丢失了一个,然后放在长度为 n 的数组之中,找出这个数字

显然还是使用异或,注意 0 ^ x == x,所以直接把 0 忽略就行了。把每个数字都和 i 异或,丢失的数字就出来了

C 解答
1
2
3
4
5
6
int missingNumber(int* nums, int n) {
int result = 0;
for (int i = 0; i < n; i++)
result = result ^ (i + 1) ^ nums[i];
return result;
}

269-272 Locked

273 数字转换为英语单词

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
vector<string> digits = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
vector<string> tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
vector<string> seps = {"", " Thousand ", " Million ", " Billion "}; // notice the trailing spaces

string numberToWords(int num) {
if (num == 0)
return "Zero";
if (num < 0)
return "Negative " + numberToWords(-num);
int count = 0;
string result;

while (num) {
if (num % 1000 != 0)
result = s2word(num % 1000) + seps[count] + result;
num /= 1000;
count++;
}

// removw unnecessary tailing space
if (isspace(result.back()))
result.resize(result.size() - 1);

return result;

}

string s2word(int num) {
string result;
if (num >= 100) {
result += digits[num/100] + " Hundred ";
num %= 100;
}

if (num >= 20) {
result += tens[num / 10] + " ";
num %= 10;
}

if (num >= 1 && num <= 19)
result += digits[num];

// remove tailing spaces
if (isspace(result.back()))
result.resize(result.size() - 1);

return result;

}
};

274 H-Index

H-Index 的定义:一个科学家的 N 篇论文 h 个至少有 h 个引用,而且剩下的 N-h 篇论文都没有超过 h 个引用。

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int hIndex(int* cites, int n) {
int hs[n+1]; // Hindex 不可能大于 N

for (int i = 0; i <= n; i++)
hs[i] = 0;

for (int i = 0; i < n; i++) {
if (cites[i] > n)
hs[n]++;
else
hs[cites[i]]++;
}

for (int i = n, papers = 0; i >= 0; i--) { // 从后往前,如果有符合条件的,那么就是 Hindex
papers += hs[i];
if (papers >= i)
return i;
}

return 0;
}

275 H-index II,论文已经按照引用数量排序

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
int hIndex(int* citations, int n) {
int left = 0, right = n - 1;
while (left <= right) { // 二分查找是小于等于
int mid = left + (right - left) / 2;
if (citations[mid] == n - mid)
return citations[mid];
else if (citations[mid] < n - mid)
left = mid + 1;
else
right = mid - 1;
}
return n - right - 1;
}

276-277 Locked

278 第一个坏版本

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
// 实际上是 lower_bound 函数
int firstBadVersion(int n) {
int left = 0, right = n; // 记住 lower_bound 的 right 是 n
while (left < right) { // 使用小于号
int mid = left + (right - left) / 2;
if (!isBadVersion(mid))
left = mid + 1;
else
right = mid;
}
return left;
}

279 分解为平方数的和

最多 4 个即可,尝试在三个以内是否可以。

C 解答
1
2
3
4
5
6
7
8
9
10
11
int numSquares(int n) {
int ub = sqrt(n);
for (int a=0; a<=ub; ++a) {
for (int b=a; b<=ub; ++b) {
int c = sqrt(n - a*a - b*b);
if (a*a + b*b + c*c == n)
return !!a + !!b + !!c;
}
}
return 4;
}

282 添加运算符使得算式成立

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<string> addOperators(string num, int target) {
vector<string> result;
if (num.size() == 0)
return result;
dfs(num, target, result, num[0] - '0', num.substr(0, 1), 1, 1);
return result;
}

void dfs(string num, int target, vector<string> & v, long long last, string s, int idx, int left) {
if (idx == num.length()){
if (target == last*left)
v.push_back(s);
return;
} else {
if(last!=0)
dfs(num, target, v, last * 10 + num[idx] - '0', s + num.substr(idx, 1), idx + 1, left); // 尝试拼成 10
dfs(num, target, v, num[idx] - '0', s + '*' + num.substr(idx, 1), idx + 1, last*left);
dfs(num, target - left*last, v, num[idx] - '0', s + '+' + num.substr(idx, 1), idx + 1, 1);
dfs(num, target - left*last, v, num[idx] - '0', s + '-' + num.substr(idx, 1), idx + 1, -1);
}
}

283 移动 0

注意 swap 的使用

C++ 解答
1
2
3
4
5
6
7
void moveZeroes(vector<int>& nums) {
int n = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0)
swap(nums[n++], nums[i]);
}
}

284 Peek Iterator

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.
class Iterator {
struct Data;
Data* data;
public:
Iterator(const vector<int>& nums);
Iterator(const Iterator& iter);
virtual ~Iterator();
// Returns the next element in the iteration.
int next();
// Returns true if the iteration has more elements.
bool hasNext() const;
};


class PeekingIterator : public Iterator {
public:
PeekingIterator(const vector<int>& nums) : Iterator(nums) {
// Initialize any member here.
// **DO NOT** save a copy of nums and manipulate it directly.
// You should only use the Iterator interface methods.

}

// Returns the next element in the iteration without advancing the iterator.
int peek() {
return Iterator(*this).next();
}

// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
int next() {
return Iterator::next();
}

bool hasNext() const {
return Iterator::hasNext();
}
};

285 ~ 286 Locked

287 一个 n 的数组包含了 1…n-1 中的这些数字,证明一定存在重复,并找出这个重复

使用抽屉原理可以证明一定存在重复。据说高纳德解这个问题花了四个小时。

我们把这个数组看做一个变幻方程 f(i) = A[i],把一些数字变幻到另一些,那么存在一个 i != j s.t. f(i) == f(j).
那么这个问题变成了链表求环的问题。对于链表,我们有 n = n->next 遍历列表,对于这个序列,则是 n = f(n)

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findDuplicate(int* nums, int n) {
// 从 n-1 开始
int fast = n - 1, slow = n - 1;
do {
slow = nums[slow] - 1; // 减一是为了转化为坐标
fast = nums[nums[fast] - 1] - 1;
} while (slow != fast);

fast = n - 1;
do {
slow = nums[slow] - 1;
fast = nums[fast] - 1;
} while (slow != fast);

return slow + 1; // 从坐标到数字
}

288 Locked

289 Conway’s Game of Life

哈哈,机智,使用没有使用的第二个位存储下一代

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int max(int a, int b) {return a > b ? a :b;}
int min(int a, int b) {return a < b ? a :b;}
void gameOfLife(int** board, int row, int col) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
int count = 0;
for (int m=max(i-1, 0); m<min(i+2, row); m++) // 这里的 min,max 使用的太屌了
for (int n=max(j-1, 0); n<min(j+2, col); n++)
count += (board[m][n] & 1);
if (count == 3 || count - board[i][j] == 3) // 当前为 0,周围为 3;or 当前为 1,周围为 2/3 here
board[i][j] |= 2;
}
}
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
board[i][j] >>= 1;
}

290 单词模式,给定一个模式 abba 等,判断单词是否是这个模式的。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
bool wordPattern(string pattern, string str) {
map<char, int> chars; // 使用两个 map 纪录
map<string, int> words;
istringstream in(str);
int i = 0, n = pattern.size(); // `i` is word count
for (string word; in >> word; i++) {
if (i == n || chars[pattern[i]] != words[word]) // 检查是否相等
return false;
chars[pattern[i]] = words[word] = i + 1; // distinct non zero
}

return i == n; // 检查长度是否相等
}

291 Locked

292 Nim 游戏,每个人可以选择丢掉 1,2,3,最后一个操作者获胜

显然,当我们遇到 4 的时候会输,其他情况都可以赢。

C 解答
1
2
3
bool canWinNim(int n) {
return n % 4 != 0;
}

300 最长递增子序列

最经典的动态规划题目

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return 1
dp = [1 for _ in range(len(nums))]
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(*dp)

344 翻转字符串

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
char* reverseString(char* s) {
char* start = s;
char* e = s;
while (*e) ++e;
e--;
char t;
while (s < e) {
t = *s;
*s = *e;
*e = t;
s++;
e--;
}
return start;
}

347 出现最多的几个数字

C 实在缺乏相关的基础数据结构,这道题用 JS 做了

JavaScript 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
let topKFrequent = function(nums, k) {
let counter = {};
for (let num of nums) {
if (num in counter) {
counter[num]++;
} else {
counter[num] = 0;
}
}

let bucket = [];
for (let num in counter) {
let rev_freq = nums.length - counter[num] + 1;
if (rev_freq in bucket) {
bucket[rev_freq].push(num);
} else {
bucket[rev_freq] = [num];
}
}

let rv = [];
for (let bc of bucket) {
if (! Array.isArray(bc)) continue;
for (let num of bc) {
if (rv.length == k)
return rv;
else
rv.push(parseInt(num))
}
}

return rv;
};

349 两个数组中都出现的元素

先排序,降低复杂度

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static int compare(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int* intersection(int* A, int m, int* B, int n, int* k) {
qsort(A, m, sizeof(int), compare);
qsort(B, n, sizeof(int), compare);
int* C = malloc((m + n) * sizeof(int));
*k = 0;
int i = 0;
int j = 0;
while (i < m && j < n) {
if (A[i] == B[j]) {
if (*k == 0)
C[(*k)++] = A[i];
else if (C[*k - 1] != A[i])
C[(*k)++] = A[i];
i++;
j++;
} else if (A[i] < B[j]) {
i++;
} else {
j++;
}
}
return C;
}

345 翻转一个字符串里面的元音字母

使用两个指针,不过需要注意元音字母包括了大小写

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def reverseVowels(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return s
vowels = set("AEIOUaeiou")
s = list(s)
i = 0
j = len(s) - 1
while True:
while s[i] not in vowels and i < j:
i += 1
while s[j] not in vowels and i < j:
j -= 1
if i >= j:
break
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
return ''.join(s)

371 两个数之和

这道题要求不用 + 和 - 来计算出两个数之和,显然应该使用位运算,使用异或计算每一位的值,在使用或计算是否需要进位

C 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int getSum(int a, int b) {
int rv = 0;
int carry = 0;

for (int i = 0; i < 32; i++) {
int last_bit_of_a = a & 1;
int last_bit_of_b = b & 1;

rv |= (last_bit_of_a ^ last_bit_of_b ^ carry) << i;
carry = (carry & last_bit_of_a) | (carry & last_bit_of_b) | (last_bit_of_a & last_bit_of_b);

a >>= 1;
b >>= 1;
}

return rv;
}

388

使用栈的一道简单题目, 其实计算长度部分还可以优化

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def lengthLongestPath(self, input: str) -> int:
path = []
ans = 0
for name in input.split("\n"):
l = 0
for c in name:
if c == "\t":
l += 1
else:
break
if len(path) > l:
for i in range(len(path) - l):
path.pop()
path.append(name.strip("\t"))
if "." in name:
length = sum([len(p) for p in path]) + len(path) - 1
ans = max(ans, length)
print(path)
return ans

435 无重叠区间

不要被题目迷惑,从反面开始思考,求去除多少个区间其实就是求最多有多少个有效区间

Python 解答
1
2
3
4
5
6
7
8
9
10
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
max_intervals = 0
end = float("-inf")
for interval in intervals:
if interval[0] >= end:
max_intervals += 1
end = interval[1]
return len(intervals) - max_intervals

482 注册码格式化

要求每 K 个字符添加一个 “-“, 如果不够的话,第一个分组可以不全。

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def licenseKeyFormatting(self, S: str, K: int) -> str:
key = []
i = 0
for c in reversed(S):
if c == "-":
continue
key.append(c.upper())
i += 1
if i % K == 0:
key.append("-")
if key and key[-1] == "-":
key = key[:-1]
return "".join(reversed(key))

547 朋友圈

UnionFind 的定义见第 200 题

Python 解答
1
2
3
4
5
6
7
8
9
class Solution:
def findCircleNum(self, M: List[List[int]]) -> int:
n = len(M)
uf = UnionFind(n)
for i in range(n):
for j in range(i):
if M[i][j] == 1:
uf.union(i, j)
return uf.count

739

单调栈的简单应用

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
stack = []
ans = [0] * len(T)
for i in range(len(T)-1, -1, -1):
# 如果当前温度大于当前最低温度
while stack and T[i] >= T[stack[-1]]:
stack.pop()
if stack:
ans[i] = stack[-1] - i
stack.append(i)
return ans

864 矩形重叠

Python 解答
1
2
3
4
5
6
class Solution:
def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
# 注意要包含等于号
x_overlap = not(rec1[0] >= rec2[2] or rec1[2] <= rec2[0])
y_overlap = not(rec1[1] >= rec2[3] or rec1[3] <= rec2[1])
return x_overlap and y_overlap

904 找出包含了两个不同数字的最长子序列

这道题的题目很坑爹,但是翻译过来其实要求很明确。解题思路也很简单,存储一下当前的最长序列
就好了。

C++ 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
```
</details>



<details>
<summary>Rust 解答</summary>

```Rust
use std::collections::HashMap;
use std::cmp::max;

impl Solution {
pub fn total_fruit(tree: Vec<i32>) -> i32 {
let mut i = 0;
let mut res = 0;
let mut counter = HashMap::new();
for (j, el) in tree.iter().enumerate() {
*counter.entry(el).or_insert(0) += 1;
while counter.len() > 2 {
*counter.get_mut(&tree[i]).unwrap() -= 1;
if let Some(x) = counter.get(&tree[i]) {
if *x == 0 {
counter.remove(&tree[i]);
}
}
i += 1;
}
res = max(res, j - i + 1);
}
res as i32
}
}

986 区间列表的交集

tags: #interval

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
i, j = 0, 0
ans = []
while i < len(A) and j < len(B):
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo <= hi:
ans.append((lo, hi))
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return ans

929 唯一邮件地址

类似 Gmail 的规则,. 去掉,+ 后面的也去掉。但是要注意域名中的 . 不能去掉

Python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def normalize(self, username: str) -> str:
username = username.replace('.', "")
# 使用 split 更好,懒得改了
username = re.sub(r"\+.*$", "", username)
return username

def numUniqueEmails(self, emails: List[str]) -> int:
unique_emails = set()
for email in emails:
username, domain = email.split("@")
username = self.normalize(username)
# print(username, domain)
unique_emails.add(f"{username}@{domain}")
return len(unique_emails)

970 强力数字

暴力解法

python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import math

class Solution:
def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
if bound <= 0:
return []
ans = set()
limit = int(math.log2(bound)) + 1
for i in range(limit):
for j in range(limit):
v = x ** i + y ** j
if v <= bound:
ans.add(v)
return list(ans)

1272 删除区间

python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
lo, hi = toBeRemoved
ans = []
for x, y in intervals:
if y < lo or x > hi:
ans.append([x, y])
else:
if lo > x:
ans.append([x, lo])
if hi < y:
ans.append([hi, y])
return ans

1317 将整数转换为两个无零整数的和

python 解答
1
2
3
4
5
6
7
class Solution:
def getNoZeroIntegers(self, n: int) -> List[int]:
for a in range(1, n):
b = n - a
if "0" not in str(a) and "0" not in str(b):
return [a, b]
return []

1389 按既定顺序创建目标数组

Python 解答
1
2
3
4
5
6
class Solution:
def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
target = []
for n, i in zip(nums, index):
target = target[:i] + [n] + target[i:]
return target

1390 四因数

解释见注释,这道题还是很坑的。不过其实也很简单,四个因数就是能够分解成两个质数乘积或者是立方数。

比如:

  1. 21 = 3 * 7
  2. 8 = 2 * 4
py 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:

def sumFourDivisors(self, nums) -> int:
if not nums:
return 0
if len(nums) == 1:
upper = nums[0]
else:
upper = max(*nums)
# 首先在这里筛选素数
isPrim = [True for _ in range(upper)]
i = 2
while i * i < upper:
if isPrim[i]:
j = i * i
while j < upper:
isPrim[j] = False
j += i
i += 1
# 把素数都提取出来
prims = [i for i in range(2, upper) if isPrim[i]]
ans = 0
for num in nums:
for prim in prims:
# 已经不可能了,后续不算了
if prim * prim > num:
break
# 立方数是符合的,这个比较坑,开始没想到,比如 8
if prim * prim * prim == num:
ans += (1 + num + prim + prim * prim)
break
# 可以分解成两个质数乘积
if num % prim == 0 and isPrim[num // prim] and prim * prim != num:
ans += (1 + num + prim + num // prim)
break
return ans