0%

剑指 Offer题解

剑指 Offer的题解,更新中

03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1:

输入: [2, 3, 1, 0, 2, 5, 3] 输出:2 或 3

限制:

2 <= n <= 100000

直接记录即可

Python

1
2
3
4
5
6
7
8
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
vis = [False] * len(nums)
for num in nums:
if vis[num]:
return num
vis[num] = True
return None

05. 替换空格

请实现一个函数,把字符串 s 中的每个空格替换成"%20"。

示例 1:

1
2
>输入:s = "We are happy."
>输出:"We%20are%20happy."

限制:

1
>0 <= s 的长度 <= 10000

c++稍微麻烦点,就是s[i]为空格push三个字符即可

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
string replaceSpace(string s) {
std::string ans;
for (std::size_t i = 0; i < s.size(); ++i) {
if (s[i] == ' ') {
ans.push_back('%');
ans.push_back('2');
ans.push_back('0');
} else {
ans.push_back(s[i]);
}
}
return ans;
}
};

Python:

1
2
3
class Solution:
def replaceSpace(self, s: str) -> str:
return s.replace(' ', '%20')

06. 从尾到头打印链表

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例 1:

输入:head = [1,3,2] 输出:[2,3,1]

限制:

0 <= 链表长度 <= 10000

c++

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> ans;
for (; head != nullptr; head = head->next) {
ans.push_back(head->val);
}
std::reverse(ans.begin(), ans.end());
return ans;
}
};

07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:

 3
  / \
 9  20
   /  \
  15   7

0 <= 节点个数 <= 5000

同105题

简单的切片:

Python

1
2
3
4
5
6
7
8
9
10
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder:
return None

root = TreeNode(preorder[0])
index = inorder.index(root.val)
root.left = self.buildTree(preorder[1 : index + 1], inorder[: index])
root.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])
return root

带上下标:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
TreeNode* buildTree(const vector<int>& preorder,
const vector<int>& inorder,
int p_s, int p_e, int i_s, int i_e) {
if (p_s >= p_e || i_s >= i_e) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[p_s]);
int index = std::find(inorder.begin() + i_s, inorder.begin() + i_e, root->val) - inorder.begin();
int length = index - i_s;
root->left = buildTree(preorder, inorder, p_s + 1, p_s + length + 1, i_s, index);
root->right = buildTree(preorder, inorder, p_s + length + 1, p_e, index + 1, i_e);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(preorder, inorder, 0, preorder.size(), 0, inorder.size());
}
};

09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTaildeleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

1
2
3
4
>输入:
>["CQueue","appendTail","deleteHead","deleteHead"]
>[[],[3],[],[]]
>输出:[null,null,3,-1]

示例 2:

1
2
3
4
>输入:
>["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
>[[],[],[5],[2],[],[]]
>输出:[null,-1,null,null,5,2]

提示:

  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

队列:先进先出;栈:后进先出

因此要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
class CQueue {
stack<int> s1;
stack<int> s2;
public:
CQueue() {}

void appendTail(int value) {
s1.push(value);
}

int deleteHead() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
if (s2.empty()) {
return -1;
}
int ans = s2.top();
s2.pop();
return ans;
}
};

10- I. 斐波那契数列

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2 输出:1 示例 2:

输入:n = 5 输出:5

提示:

0 <= n <= 100

直接迭代就完事了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int fib(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
const int MOD = 1000000007;
int first = 0, second = 1;
int third = 0;
for (int i = 2; i <= n; ++i) {
third = first + second;
third %= MOD;
first = second;
second = third;
}
return third;
}
};

10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

1
2
>输入:n = 2
>输出:2

示例 2:

1
2
>输入:n = 7
>输出:21

示例 3:

1
2
>输入:n = 0
>输出:1

提示:

  • 0 <= n <= 100

显然有dp[i] = dp[i - 1] + dp[i - 2],所以和斐波那契数列基本一样(初始0的时候为1就这点不同)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int numWays(int n) {
if (n == 0) return 1;
if (n == 1) return 1;
const int MOD = 1000000007;
int first = 1, second = 1;
int third = 0;
for (int i = 2; i <= n; ++i) {
third = first + second;
third %= MOD;
first = second;
second = third;
}
return third;
}
};

11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2][1,2,3,4,5] 的一个旋转,该数组的最小值为1。

示例 1:

1
2
>输入:[3,4,5,1,2]
>输出:1

示例 2:

1
2
>输入:[2,2,2,0,1]
>输出:0

与154题相同

  1. 分治法

如果num[left] < num[right]说明数组有序,返回num[left]

如果num[left] >= num[right]则左右两边查找取min即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def minArray(self, numbers: List[int]) -> int:
if not numbers: return 0
return self.find_min(numbers, 0, len(numbers) - 1)

def find_min(self, numbers, left, right):
if left == right:
return numbers[left]
if numbers[left] < numbers[right]:
return numbers[left]
else:
mid = (left + right) >> 1
return min(self.find_min(numbers, left, mid), self.find_min(numbers, mid + 1, right))
  1. 二分搜索

mid = (left + right) / 2

如果

  • nums[mid] < nums[right]:说明右半部分不可能有最小的元素,因此right = mid
  • nums[mid] > nums[right]:说明旋转的元素(最小值)一定在(mid, righth]之间,因此left = mid + 1
  • nums[mid] == nums[right]:无法确定最小值的范围,但是两个元素相等,可以让right - 1来缩小范围
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def minArray(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
while left < right:
mid = (left + right) >> 1
if nums[mid] > nums[right]:
left = mid + 1
elif nums[mid] < nums[right]:
right = mid
else:
right -= 1
return nums[left]

12. 矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

[["a","b","c","e"], ["s","f","c","s"], ["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

示例 1:

1
2
>输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
>输出:true

示例 2:

1
2
>输入:board = [["a","b"],["c","d"]], word = "abcd"
>输出:false

提示:

  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200

注意:本题与主站 79 题相同:https://leetcode-cn.com/problems/word-search/

直接dfs即可

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
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
vis = [[False for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
vis[i][j] = True
if self.dfs(i, j, 1, vis, board, word):
return True
vis[i][j] = False
return False

def dfs(self, x, y, word_index, vis, board, word):
if word_index == len(word):
return True

for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= len(board) or ny >= len(board[0]):
continue
if board[nx][ny] != word[word_index] or vis[nx][ny]:
continue
vis[nx][ny] = True
if self.dfs(nx, ny, word_index + 1, vis, board, word):
return True
vis[nx][ny] = False
return False

13. 机器人的运动范围

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

示例 1:

1
2
>输入:m = 2, n = 3, k = 1
>输出:3

示例 2:

1
2
>输入:m = 3, n = 1, k = 0
>输出:1

提示:

  • 1 <= n,m <= 100
  • 0 <= k <= 20

方法1

对于一个格子,只需要向下或者向右,bfs即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
ans = 0
dx = [1, 0]
dy = [0, 1]
q = deque([(0, 0)])
vis = [[False if i // 10 + i % 10 + j // 10 + j % 10 <= k else True for j in range(n)] for i in range(m)]
vis[0][0] = True
while q:
cur = q.popleft()
ans += 1
for i in range(2):
nx, ny = cur[0] + dx[i], cur[1] + dy[i]
if nx < 0 or ny < 0 or nx >= m or ny >= n or vis[nx][ny]:
continue
vis[nx][ny] = True
q.append((nx, ny))

return ans

方法2

一个位置能否达到取决于左边和上面的两个地方,因此有vis[i][j] = vis[i - 1][j] || vis[i][j - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
vis = [[False for j in range(n)] for i in range(m)]
vis[0][0] = True
ans = 1
for i in range(m):
for j in range(n):
if i // 10 + i % 10 + j // 10 + j % 10 > k:
continue
pre_row = i > 0 and vis[i - 1][j]
pre_col = j > 0 and vis[i][j - 1]
if pre_col or pre_row:
vis[i][j] = True
ans += 1
return ans

14- I. 剪绳子

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

1
2
3
>输入: 2
>输出: 1
>解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

1
2
3
>输入: 10
>输出: 36
>解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:

  • 2 <= n <= 58

注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/

  • n > 3的情况下,我们处理一个数拆分成2,要么拆分成3,(4的话相当于2个2 , 拆成1的话乘积太小了)
  • 弄得越多段,应该乘积越大

因此可以dp,见题解https://www.hrwhisper.me/leetcode-integer-break/

1
2
3
4
5
6
7
8
9
10
class Solution:
def cuttingRope(self, n: int) -> int:
if n <= 3: return n - 1
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
dp[3] = 3
for i in range(4, n + 1):
dp[i] = max(dp[i - 3] * 3, dp[i - 2] * 2)
return dp[n]

但是还可以进一步改进:

1
2
3
4
5
6
7
8
9
10
class Solution:
def cuttingRope(self, n: int) -> int:
if n <= 3: return n - 1
mod = n % 3
if mod == 0:
return 3 ** (n // 3)
elif mod == 1:
return 4 * 3 ** (n // 3 - 1)
else:
return 2 * 3 ** (n // 3)

14- II. 剪绳子 II

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

1
2
3
>输入: 2
>输出: 1
>解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

1
2
3
>输入: 10
>输出: 36
>解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:

  • 2 <= n <= 1000

注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/

和上面一样

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def cuttingRope(self, n: int) -> int:
if n <= 3: return n - 1
mod = n % 3
MOD = 1000000007
if mod == 0:
return 3 ** (n // 3) % MOD
elif mod == 1:
return 4 * 3 ** (n // 3 - 1) % MOD
else:
return 2 * 3 ** (n // 3) % MOD

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:
int cuttingRope(int n) {
if (n <= 3) { return n - 1; }
int mod = n % 3;
long long ans = 0;
if (mod == 0) {
ans = quick_pow(3, n / 3);
} else if (mod == 1) {
ans = quick_pow(3, n / 3 - 1) * 4;
} else {
ans = quick_pow(3, n / 3) * 2;
}
return ans % MOD;
}

long long quick_pow(long long x, int n) {
long long ans = 1;
while (n > 0) {
if (n & 1) {
ans = ans * x % MOD;
}
x = x * x % MOD;
n >>= 1;
}
return ans;
}

private:
long long MOD = 1000000007;
};

15. 二进制中1的个数

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

1
2
3
>输入:00000000000000000000000000001011
>输出:3
>解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

1
2
3
>输入:00000000000000000000000010000000
>输出:1
>解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

1
2
3
>输入:11111111111111111111111111111101
>输出:31
>解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

注意:本题与主站 191 题相同:https://leetcode-cn.com/problems/number-of-1-bits/

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int hammingWeight(uint32_t n) {
int cnt = 0;
while (n) {
if (n & 1) {
++cnt;
}
n >>= 1;
}
return cnt;
}
};

或者用n & (n - 1),见leetcode 位运算

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int hammingWeight(uint32_t n) {
int cnt = 0;
while (n) {
++cnt;
n = n & (n - 1);
}
return cnt;
}
};

16. 数值的整数次方

实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

示例 1:

1
2
>输入: 2.00000, 10
>输出: 1024.00000

示例 2:

1
2
>输入: 2.10000, 3
>输出: 9.26100

示例 3:

1
2
3
>输入: 2.00000, -2
>输出: 0.25000
>解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

注意:本题与主站 50 题相同:https://leetcode-cn.com/problems/powx-n/

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
double myPow(double x, int n) {
if (x < 1e-12 && x > -1e-12) { return 0;}
bool neg = false;
long long t = n;
if (t < 0) {
neg = true;
t = -t;
}
double ans = 1;
while (t) {
if (t & 1) ans = ans * x;
x *= x;
t >>= 1;
}
if (neg) {
ans = 1.0 / ans;
}
return ans;
}
};

17. 打印从1到最大的n位数

输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

1
2
>输入: n = 1
>输出: [1,2,3,4,5,6,7,8,9]

说明:

  • 用返回一个整数列表来代替打印
  • n 为正整数

直接打印。。

1
2
3
class Solution:
def printNumbers(self, n: int) -> List[int]:
return [i for i in range(1, 10 ** n)]

18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

注意:此题对比原题有改动

示例 1:

1
2
3
>输入: head = [4,5,1,9], val = 5
>输出: [4,1,9]
>解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:

1
2
3
>输入: head = [4,5,1,9], val = 1
>输出: [4,5,9]
>解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

说明:

  • 题目保证链表中节点的值互不相同
  • 若使用 C 或 C++ 语言,你不需要 freedelete 被删除的节点

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if not head:
return head
if head.val == val:
return head.next

p = head
q = head.next
while q:
if q.val == val:
p.next = q.next
break
p = q
q = q.next
return head

19. 正则表达式匹配

请实现一个函数用来匹配包含'. ''*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a""ab*ac*a"匹配,但与"aa.a""ab*a"均不匹配。

示例 1:

1
2
3
4
5
>输入:
>s = "aa"
>p = "a"
>输出: false
>解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
>输入:
>s = "aa"
>p = "a*"
>输出: true
>解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

1
2
3
4
5
>输入:
>s = "ab"
>p = ".*"
>输出: true
>解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

1
2
3
4
5
>输入:
>s = "aab"
>p = "c*a*b"
>输出: true
>解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

1
2
3
4
>输入:
>s = "mississippi"
>p = "mis*is*p*."
>输出: false
  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母以及字符 .*,无连续的 '*'

注意:本题与主站 10 题相同:https://leetcode-cn.com/problems/regular-expression-matching/

20. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值,但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

这题太恶心了,题目没说清楚,数字的表示应该是A.BEC这种形式,其中:

  • A为带符号整数部分, B为小数部分,C为指数部分
  • 有小数点的只要有A或者B其中一个都可以
  • A和C为可以带符号的整数,B为无符号的整数

因此可以写两个函数来匹配有无符号

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
class Solution:
def match_sign_num(self, s):
if self.index < len(s) and s[self.index] in ['+', '-']:
self.index += 1
return self.match_unsign_num(s)

def match_unsign_num(self, s):
before = self.index
while self.index < len(s) and s[self.index].isdigit():
self.index += 1
return before < self.index

def isNumber(self, s: str) -> bool:
if not s: return False
self.index = 0
while self.index < len(s) and s[self.index] == ' ':
self.index += 1
has_num = self.match_sign_num(s)
if self.index < len(s) and s[self.index] == '.':
self.index += 1
has_num = self.match_unsign_num(s) or has_num
if self.index < len(s) and s[self.index] in ['e', 'E']:
self.index += 1
has_num = has_num and self.match_sign_num(s)

while self.index < len(s) and s[self.index] == ' ':
self.index += 1
return has_num and self.index == len(s)

21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

示例:

1
2
3
>输入:nums = [1,2,3,4]
>输出:[1,3,2,4]
>注:[3,1,2,4] 也是正确的答案之一。

提示:

  1. 1 <= nums.length <= 50000
  2. 1 <= nums[i] <= 10000

双指针交换即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
odd = 0
even = len(nums) - 1
while odd < even:
if nums[odd] & 1:
odd += 1
continue
elif nums[even] & 1 == 0:
even -= 1
continue
else:
nums[odd], nums[even] = nums[even], nums[odd]
odd += 1
even -= 1
return nums

22. 链表中倒数第k个节点

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例:

1
2
3
>给定一个链表: 1->2->3->4->5, 和 k = 2.

>返回链表 4->5.

有了链表长度后,一切就很简单。。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
link_len = 0
p = head
while p:
p = p.next
link_len += 1

target = link_len - k
for i in range(target):
head = head.next
return head

假如不能获取长度呢?只需要遍历一遍

那么可以用双指针,一个指针先走k步即可

下面的代码假设k一定小于链表长度

1
2
3
4
5
6
7
8
9
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
p = q = head
for i in range(k):
q = q.next
while q:
p = p.next
q = q.next
return p

24. 反转链表

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

1
2
>输入: 1->2->3->4->5->NULL
>输出: 5->4->3->2->1->NULL

限制:

1
>0 <= 节点个数 <= 5000

注意:本题与主站 206 题相同:https://leetcode-cn.com/problems/reverse-linked-list/

方法1: 每次遍历到某个元素把它当作head

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head:
return head
p = head
q = head.next
while q:
p.next = q.next
q.next = head
head = q
q = p.next
return head

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) {
return head;
}
ListNode* p = head;
ListNode* q = head->next;
while (q != nullptr) {
p->next = q->next;
q->next = head;
head = q;
q = p->next;
}
return head;
}
};

方法2:

cur和pre双指针,每次pre为cur后面一个元素,遍历的时候将pre->next指向cur即可

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head:
return head
cur = None
pre = head
while pre:
temp = pre.next
pre.next = cur
cur = pre
pre = temp
return cur

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) {
return head;
}
ListNode* p = nullptr;
ListNode* q = head;
while (q != nullptr) {
ListNode* temp = q->next;
q->next = p;
p = q;
q = temp;
}
return p;
}
};

25. 合并两个排序的链表

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

1
2
>输入:1->2->4, 1->3->4
>输出:1->1->2->3->4->4

限制:

1
>0 <= 链表长度 <= 1000

注意:本题与主站 21 题相同:https://leetcode-cn.com/problems/merge-two-sorted-lists/

和插入排序类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode head, *p = &head;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = l1 ? l1 : l2;
return head.next;
}
};

26. 树的子结构

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

3 / \ 4 5 / \ 1 2 给定的树 B:

4 / 1 返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1:

1
2
>输入:A = [1,2,3], B = [3,1]
>输出:false

示例 2:

1
2
>输入:A = [3,4,5,1,2], B = [4,1]
>输出:true

限制:

1
>0 <= 节点个数 <= 10000

递归进行判断即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
bool dfs(TreeNode* A, TreeNode* B) {
if (!B) { return true;}
return A && A->val == B->val && dfs(A->left, B->left) && dfs(A->right, B->right);
}
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (B == nullptr || A == nullptr) {
return false;
}
return dfs(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
};

27. 二叉树的镜像

难度简单80

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

例如输入:

   4
 /   \
 2     7
/ \   / \

1 3 6 9

镜像输出:

     4
   /   \
 7     2
/ \   / \

9 6 3 1 示例 1:

1
2
>输入:root = [4,2,7,1,3,6,9]
>输出:[4,7,2,9,6,3,1]

限制:

1
>0 <= 节点个数 <= 1000

注意:本题与主站 226 题相同:https://leetcode-cn.com/problems/invert-binary-tree/

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if (!root) return root;
std::swap(root->left, root->right);
mirrorTree(root->left);
mirrorTree(root->right);
return root;
}
};

28. 对称的二叉树

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

   1
  / \
 2   2
/ \ / \

3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

  1
 / \
 2   2
  \   \
  3    3

示例 1:

1
2
>输入:root = [1,2,2,3,4,4,3]
>输出:true

示例 2:

1
2
>输入:root = [1,2,2,null,3,null,3]
>输出:false

限制:

1
>0 <= 节点个数 <= 1000

注意:本题与主站 101 题相同:https://leetcode-cn.com/problems/symmetric-tree/

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
bool dfs(TreeNode* t1, TreeNode* t2) {
if (!t1 && !t2) return true;
if (!t1 && t2 || t1 && !t2) return false;
if (t1->val != t2->val) return false;
return dfs(t1->left, t2->right) && dfs(t1->right, t2->left);
}

public:
bool isSymmetric(TreeNode* root) {
return !root || dfs(root->left, root->right);
}
};

29. 顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1:

1
2
>输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
>输出:[1,2,3,6,9,8,7,4,5]

示例 2:

1
2
>输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
>输出:[1,2,3,4,8,12,11,10,9,5,6,7]

限制:

  • 0 <= matrix.length <= 100
  • 0 <= matrix[i].length <= 100

注意:本题与主站 54 题相同:https://leetcode-cn.com/problems/spiral-matrix/

按层模拟,注意只有一行和一列的特殊情况即可。

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
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
if (matrix.empty()) return ans;
int left = 0;
int up = 0;
int down = matrix.size() - 1;
int right = matrix[0].size() - 1;
for (;left <= right && up <= down;) {
for (int i = left; i <= right; ++i) {
ans.push_back(matrix[up][i]);
}
++up;
for (int i = up; i <= down; ++i) {
ans.push_back(matrix[i][right]);
}
--right;
if (up > down) { break; }
for (int i = right; i >= left; --i) {
ans.push_back(matrix[down][i]);
}
--down;
if (left > right) { break; }
for (int i = down; i >= up; --i) {
ans.push_back(matrix[i][left]);
}
++left;
}
return ans;
}
};

30. 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

1
2
3
4
5
6
7
8
>MinStack minStack = new MinStack();
>minStack.push(-2);
>minStack.push(0);
>minStack.push(-3);
>minStack.min(); --> 返回 -3.
>minStack.pop();
>minStack.top(); --> 返回 0.
>minStack.min(); --> 返回 -2.

提示:

  1. 各函数的调用总次数不超过 20000 次

注意:本题与主站 155 题相同:https://leetcode-cn.com/problems/min-stack/

用两个栈,一个是正常的,一个是保存当前最小元素的栈min_s即可

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 MinStack {
std::stack<int> s;
std::stack<int> min_s;
public:
/** initialize your data structure here. */
MinStack() {}

void push(int x) {
s.push(x);
if (min_s.empty() || min_s.top() >= x) {
min_s.push(x);
}
}

void pop() {
int x = s.top();
s.pop();
if (x == min_s.top()) {
min_s.pop();
}
}

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

int min() {
return min_s.top();
}
};

31. 栈的压入、弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1:

1
2
3
4
5
>输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
>输出:true
>解释:我们可以按以下顺序执行:
>push(1), push(2), push(3), push(4), pop() -> 4,
>push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2:

1
2
3
>输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
>输出:false
>解释:1 不能在 2 之前弹出。

提示:

  1. 0 <= pushed.length == popped.length <= 1000
  2. 0 <= pushed[i], popped[i] < 1000
  3. pushedpopped 的排列。

注意:本题与主站 946 题相同:https://leetcode-cn.com/problems/validate-stack-sequences/

给定了Push的顺序和pop的顺序,因此可以直接模拟

如果pop的元素等于栈顶,那么就pop元素,如果是合法的pop序列,最后push数组一定为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
if(pushed.size() != popped.size()) return false;
if (pushed.empty()) return true;
std::size_t i = 0;
std::stack<int> q;
for (int num : pushed) {
q.push(num);
while (!q.empty() && i < pushed.size() && q.top() == popped[i]) {
++i;
q.pop();
}
}
return q.empty();
}
};

32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

例如: 给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回:

1
>[3,9,20,15,7]

提示:

  1. 节点总数 <= 1000

直接BFS即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root: return []
q = deque([root])
ans = []
while q:
cur = q[0]
ans.append(cur.val)
q.popleft()
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
return ans

32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。

例如: 给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
>[
[3],
[9,20],
[15,7]
>]

提示:

  1. 节点总数 <= 1000

注意:本题与主站 102 题相同:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

上面的代码改改即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
q = deque([root])
ans = []
while q:
len_q = len(q)
row = []
for _ in range(len_q):
cur = q[0]
row.append(cur.val)
q.popleft()
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
ans.append(row)
return ans

32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

例如: 给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
>[
[3],
[20,9],
[15,7]
>]

提示:

  1. 节点总数 <= 1000

和上面的不同就是多了个双数逆序打印的东西,判断即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
q = deque([root])
ans = []
h = 1
while q:
len_q = len(q)
row = []
for _ in range(len_q):
cur = q[0]
row.append(cur.val)
q.popleft()
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
ans.append(row if h & 1 else row[::-1])
h += 1
return ans

33. 二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树:

1
2
3
4
5
    5
/ \
2 6
/ \
1 3

示例 1:

1
2
>输入: [1,6,3,2,5]
>输出: false

示例 2:

1
2
>输入: [1,3,2,6,5]
>输出: true

提示:

  1. 数组长度 <= 1000

方法1

二叉树的后序遍历顺序为:左子树、右子树、根节点

因此数组的最后一个就是根节点,可以从后往前找,找到第一个小于根节点的下标index,则[s,index]必须是左子树,右子树为[index+1, e-1]:可以写出如下的代码,最后用中序遍历看看是否有序

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
class TreeNode:
def __init__(self, x):
self.val = x
self.left = self.right = None

class Solution:
def find_larger_index(self, nums, s, e, t):
for i in range(e, s - 1, -1):
if nums[i] < t:
return i
return -1

def dfs(self, nums: List[int], s: int, e: int) -> bool:
if s > e: return None
root = TreeNode(nums[e])
index = self.find_larger_index(nums, s, e, nums[e])
if index >= s:
root.left = self.dfs(nums, s, index)
root.right = self.dfs(nums, index + 1, e - 1)
else:
root.right = self.dfs(nums, s, e - 1)
return root

def inorder(self, nums, root):
if not root: return
self.inorder(nums, root.left)
nums.append(root.val)
self.inorder(nums, root.right)

def verifyPostorder(self, postorder: List[int]) -> bool:
root = self.dfs(postorder, 0, len(postorder) - 1)
inorder = []
self.inorder(inorder, root)
for i in range(1, len(inorder)):
if inorder[i] < inorder[i - 1]:
return False
return True

但其实可以改进一下,在递归过程直接判断左子树必须都小于根节点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def find_larger_index(self, nums, s, e, t):
for i in range(e, s - 1, -1):
if nums[i] < t:
return i
return s - 1

def dfs(self, nums: List[int], s: int, e: int) -> bool:
if s > e: return True
root = nums[e]
index = self.find_larger_index(nums, s, e, root)
for i in range(s, index + 1):
if nums[i] > root:
return False
return self.dfs(nums, s, index) and self.dfs(nums, index + 1, e - 1)

def verifyPostorder(self, postorder: List[int]) -> bool:
return self.dfs(postorder, 0, len(postorder) - 1)

方法2

二叉树的后序遍历顺序为:左子树、右子树、根节点,而后续遍历的逆序为:根节点、右子树、左子树

因此,对于逆序的后续遍历:

  • nums[i] < nums[i + 1]:说明nums[i + 1]nums[i]的右子树
  • nums[i] > nums[i + 1]:说明nums[i + 1]nums[1...i]中某个元素的左子树

因此我们可以维护一个单调递增的栈,若发现栈顶的元素大于当前的nums[i],说明进了左子树,我们可以不断的pop元素来找它的父节点

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def verifyPostorder(self, nums: List[int]) -> bool:
q = []
parent = float("+inf")
for i in range(len(nums) - 1, -1, -1):
while q and q[-1] > nums[i]:
parent = q.pop()

if nums[i] > parent:
return False
q.append(nums[i])
return True

34. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例: 给定如下二叉树,以及目标和 sum = 22

1
2
3
4
5
6
7
      5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

返回:

1
2
3
4
>[
[5,4,11,2],
[5,8,4,5]
>]

提示:

  1. 节点总数 <= 10000

注意:本题与主站 113 题相同:https://leetcode-cn.com/problems/path-sum-ii/

dfs即可

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def dfs(self, cur, cur_sum, root, target, ans):
if not root:
return

cur_sum += root.val
cur.append(root.val)
if cur_sum == target and not root.left and not root.right:
ans.append(cur[:])
else:
self.dfs(cur, cur_sum, root.left, target, ans)
self.dfs(cur, cur_sum, root.right, target, ans)
cur.pop()

def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
ans = []
cur = []
self.dfs(cur, 0, root, target, ans)
return an

35. 复杂链表的复制

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null

示例 1:

img
img
1
2
>输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
>输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

img
img
1
2
>输入:head = [[1,1],[2,1]]
>输出:[[1,1],[2,1]]

示例 3:

img

1
2
>输入:head = [[3,null],[3,0],[3,null]]
>输出:[[3,null],[3,0],[3,null]]

示例 4:

1
2
3
>输入:head = []
>输出:[]
>解释:给定的链表为空(空指针),因此返回 null。

提示:

  • -10000 <= Node.val <= 10000
  • Node.random 为空(null)或指向链表中的节点。
  • 节点数目不超过 1000 。

用个hash表保存即可

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
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
p = head
node_dict = {}
new_head = Node(-1)
q = new_head
while p:
if p not in node_dict:
node_dict[p] = Node(p.val)
q.next = node_dict[p]
q = q.next
p = p.next

p = head
q = new_head.next
while p:
if p.random:
q.random = node_dict[p.random]
p = p.next
q = q.next
return new_head.next

也可以递归的写,更简单一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
std::unordered_map<Node*, Node*> _map;
public:
Node* copyRandomList(Node* head) {
if (!head) return head;
if (_map.find(head) != _map.end()) return _map[head];

Node* new_node = new Node(head->val);
_map[head] = new_node;
new_node->next = copyRandomList(head->next);
new_node->random = copyRandomList(head->random);
return new_node;
}
};

36. 二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

为了让您更好地理解问题,以下面的二叉搜索树为例:

img
img

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

img
img

特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

利用中序遍历即可

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
"""
# Definition for a Node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution:
def dfs(self, root):
if not root: return
self.dfs(root.left)
if not self.head:
self.head = self.p = root
else:
self.p.right = root
root.left = self.p
self.p = root
self.dfs(root.right)


def treeToDoublyList(self, root: 'Node') -> 'Node':
self.head = self.p = None
self.dfs(root)
if self.head:
self.head.left = self.p
self.p.right = self.head
return self.head

37. 序列化二叉树

请实现两个函数,分别用来序列化和反序列化二叉树。

示例:

1
2
3
4
5
6
7
8
>你可以将以下二叉树:
1
/ \
2 3
/ \
4 5

>序列化为 "[1,2,3,null,null,4,5]"

注意:本题与主站 297 题相同:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

序列化就是标准BFS

反序列化用一个i指向当前的子节点,一个队列来维护当前节点即可

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
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
if not root: return "[]"
ans = []
q = deque([root])
while q:
cur = q[0]
q.popleft()
if cur:
q.append(cur.left)
q.append(cur.right)
ans.append(str(cur.val))
else:
ans.append("null")
return '[{}]'.format(','.join(ans))

def deserialize(self, data):
"""Decodes your encoded data to tree.

:type data: str
:rtype: TreeNode
"""
if data == '[]': return None
data = data[1:-1].split(',')
root = TreeNode(int(data[0]))
i = 1
q = deque([root])
while q:
cur = q.popleft()
if i >= len(data):
break

if data[i] != 'null':
cur.left = TreeNode(int(data[i]))
q.append(cur.left)
i += 1
if data[i] != 'null':
cur.right = TreeNode(int(data[i]))
q.append(cur.right)
i += 1
return root

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

38. 字符串的排列

难度中等132

输入一个字符串,打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

示例:

1
2
>输入:s = "abc"
>输出:["abc","acb","bac","bca","cab","cba"]

限制:

1
>1 <= s 的长度 <= 8

可以类似STL的写个next_permutation的函数

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 next_permutation(self, nums):
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i < 0:
return False

j = len(nums) - 1
while j > i and nums[i] >= nums[j]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1:] = nums[i + 1:][::-1]
return True

def permutation(self, s: str) -> List[str]:
if not s: return []
nums = sorted([c for c in s])
ans = [''.join(nums)]
while self.next_permutation(nums):
ans.append(''.join(nums))
return ans

39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

1
2
>输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
>输出: 2

限制:

1
>1 <= 数组长度 <= 50000

进行投票即可,如果当前元素与element相同,cnt+=1,否则cnt -= 1。 当Cnt= 0的时候,设置element为当前的元素

这是因为超过一半次数的元素,其cnt必然大于长度的一半

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def majorityElement(self, nums: List[int]) -> int:
cnt = 1
element = nums[0]
for i in range(1, len(nums)):
if nums[i] == element:
cnt += 1
else:
cnt -= 1
if cnt == 0:
element = nums[i]
cnt += 1
return element

40. 最小的k个数

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

示例 1:

1
2
>输入:arr = [3,2,1], k = 2
>输出:[1,2] 或者 [2,1]

示例 2:

1
2
>输入:arr = [0,1,2,1], k = 1
>输出:[0]

限制:

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

方法1:排序

1
2
3
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
return sorted(arr)[:k]

方法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
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if (!k) return {};
priority_queue<int> q;
for (int v : arr) {
if (q.size() < k) {
q.push(v);
continue;
} else if (q.top() > v) {
q.pop();
q.push(v);
}
}
vector<int> ans;
ans.reserve(k);
while (!q.empty()) {
ans.push_back(q.top());
q.pop();
}
return ans;
}
};

python的heapq是最小堆

1
2
3
4
5
6
7
8
9
10
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if not k: return []
q = [-x for x in arr[:k]]
heapq.heapify(q)
for i in range(k, len(arr)):
if arr[i] < -q[0]:
heapq.heappop(q)
heapq.heappush(q, -arr[i])
return [-x for x in q]

方法3. 利用快排的思想, 如果想要达到期望O(n)还需要加上随机的操作

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 {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if (k == 0) return {};
srand((unsigned)time(NULL));
quick_sort(arr, 0, arr.size() - 1, k);
vector<int> ans(arr.begin(), arr.begin() + k);
return ans;
}

void quick_sort(vector<int>& arr, int l, int r, int k) {
if (l >= r) return;
int i = partition(arr, l, r);
int left_num = i - l + 1;
if (k == left_num) {
return;
} else if (k < left_num) {
quick_sort(arr, l, i - 1, k);
} else { // k > left_num
quick_sort(arr, i + 1, r, k - left_num);
}
}

void random_choose(vector<int>& arr, int l, int r) {
int t = rand() % (r - l + 1) + l;
swap(arr[r], arr[r]);
}

int partition(vector<int>& arr, int l, int r) {
random_choose(arr, l, r);
int temp = arr[r];
int left = l - 1;
for (int i = l; i < r; ++i) {
if (arr[i] < temp) {
left++;
swap(arr[left], arr[i]);
}
}
swap(arr[left + 1], arr[r]);
return left + 1;
}
};

41. 数据流中的中位数

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例 1:

1
2
3
4
>输入:
>["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
>[[],[1],[2],[],[3],[]]
>输出:[null,null,null,1.50000,null,2.00000]

示例 2:

1
2
3
4
>输入:
>["MedianFinder","addNum","findMedian","addNum","findMedian"]
>[[],[2],[],[3],[]]
>输出:[null,null,2.00000,null,2.50000]

限制:

  • 最多会对 addNum、findMedian 进行 50000 次调用。

注意:本题与主站 295 题相同:https://leetcode-cn.com/problems/find-median-from-data-stream/

想想一个排好序的数组,中位数就是中间的元素。如何动态的维护中间的元素呢?

维护一个最大堆和最小堆,最大堆保存数组左边的,最小堆保存数组右边的,保证左边的个数比右边的多,但不多于1个。

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
class MedianFinder {
priority_queue<int> left;
priority_queue<int> right;
public:
MedianFinder() {}

void addNum(int num) {
if (left.empty() || num <= left.top()) {
left.push(num);
if (right.size() + 1 < left.size()) {
int temp = left.top();
left.pop();
right.push(-temp);
}
} else { // num > left.top()
right.push(-num);
if (right.size() > left.size()) {
int temp = right.top();
right.pop();
left.push(-temp);
}
}
}

double findMedian() {
return (left.size() + right.size()) & 1? left.top() : (left.top() - right.top()) * 0.5;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MedianFinder:
def __init__(self):
self.left = []
self.right = []

def addNum(self, num: int) -> None:
if not self.left or -self.left[0] > num:
heapq.heappush(self.left, -num)
if len(self.right) + 1 < len(self.left):
temp = heapq.heappop(self.left)
heapq.heappush(self.right, -temp)
else:
heapq.heappush(self.right, num)
if len(self.right) > len(self.left):
temp = heapq.heappop(self.right)
heapq.heappush(self.left, -temp)

def findMedian(self) -> float:
return -self.left[0] if (len(self.left) + len(self.right)) & 1 else (-self.left[0] + self.right[0]) * 0.5
请我喝杯咖啡吧~