leetcode算法

Leetcode刷

TopKElements and KthElements

这两个问题都可以通过快速排序和堆排序来解决

KthElements问题

  • 快速排序:利用快速排序进行Partition,返回j的值。比较j的值与K值得大小,如果j<K,那么在[j+1,h之间]。很多时候,快排书写得一些细节需要注意一下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    private int Partition(int[] nums,int l,int h){
    int i=l+1;
    int j=h;
    while(true){
    while(nums[i++]<nums[l]&&i<h);
    while(nums[j--]>nums[l]&&j>l);
    if(i>=j){
    break;
    }
    swap(nums,i,j)
    }
    swap(nums,j,l);
    return j;
    }
  • 堆排序:创建最小堆,最后堆中剩下得元素中堆顶元素为要求的值

    1
    2
    3
    4
    堆得创建用优先队列:
    PriorityQueue<Integer> heap=new PriorityQueue<>();这是创建了小顶堆
    PriorityQueue<Integer> heap2=new PriorityQueue<>(((o1, o2) -> o2-o1));这是创建大顶堆
    为什么是大顶堆?后面返回值为负数时(即o2-o1小于0),传入的o1放在前面,o2放在后面。因为o1是比o2大的,所以o1放在前面相当于把**大的值放在前面**
    1
    2
    3
    4
    5
    6
    如何维护堆的大小?不断往堆中插入数据,每次都要检测优先队列的size是否大于K值
    for (int val : nums) {
    pq.add(val);
    if (pq.size() > k) // 维护堆的大小为 K
    pq.poll();
    }

TopKElements问题

  • 快速排序:上述找到KthElements后,在位置K后面的所有元素是TopK的元素
  • 堆排序:堆中最后剩下的元素即为要求的解

拓展

栈的创建:Stack容器即可,可以private Stack in = new Stack<>();创建

队列的创建如下:

1
2
Queue<Integer> queue=new LinkedList<>();
Queue是一个父类,LinkedList可以继承自Queue或者叫做LinkedList实现了Queue

最长子序列

524. Longest Word in Dictionary through Deleting (Medium)

1
2
3
4
5
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output:
"apple"

题目描述:删除 s 中的一些字符,使得它构成字符串列表 d 中的一个字符串,找出能构成的最长字符串。如果有多个相同长度的结果,返回字典序的最大字符串。

这道题貌似没什么捷径,首先如何判断两字符串s与d[i]是否满足题意情况:双指针i和j,分别指向s与d[i]的第一个字符,i和j按情况自增,以此判断是否满足情况

那么如何输出字典序最大的字符串呢?String类有提供按照字典序比较两字符串的大小函数compareTo函数

桶排序:出现频率最多的K个数,按照字符出现次数对字符串排序

桶是什么:是一个数组,数组的每个维度装的是一个list,即桶是数组List[]

1
List<Integer>[] bucket=new ArrayList[nums.length+1];

每个下标对应的是一个桶,每个桶存储出现频率相同的数。并且桶的下标就代表桶中数出现的频率,即第i个桶中存储出现频率为i的数。把数据都放入桶之后,从后向前遍历,最先得到的k个数即为所求。

有关map的操作:

1
mymap.getOrDefault(num, 0)

这是什么意思?这是在map中寻找键为num对应的value,没有默认返回0

二分法

在二分法中有几个注意点:

  • 当h的赋值表达式子为h=m时,循环条件为l<h,不能取等号,否则会进入死循环

540. Single Element in a Sorted Array (Medium)

1
2
Input: [1, 1, 2, 3, 3, 4, 4, 8, 8]
Output: 2

题目描述:一个有序数组只有一个数不出现两次,找出这个数。要求以 O(logN) 时间复杂度进行求解。

经上述观察,假设单个数的索引为index,当m 为偶数的时候,假设m+1<index,那么有nums[m]==nums[m+1];当m+1>=index,有nums[m]!=nums[m+1]。用二分法解决上述问题:保证mid为偶数的情况下,如果nums[m]==nums[m+1],那么index所在的位置为[m+2,h]。如果nums[m]!=nums[m+1],那么index所在的位置为[l, m]

有以下注意点:

  • 每次计算出mid之后,需要将mid调整为偶数
  • 有赋值h=m,循环条件为l<h,不能取等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int singleNonDuplicate(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (m % 2 == 1) {
m--; // 保证 l/h/m 都在偶数位,使得查找区间大小一直都是奇数
}
if (nums[m] == nums[m + 1]) {
l = m + 2;
} else {
h = m;
}
}
return nums[l];
}

旋转数组的最小数字

对于一个旋转数组nums,当nums[mid]<nums[h],说明最小值在[l,mid]之间(正序的)。否则在[mid+1,h]之间。

  • 注意:因为赋值语句为h=m,所以循环条件不能取等

34. Search for a Range (Medium)

1
2
3
4
5
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

假设待查找的数据为K,二分法定义函数:找到第一个大于等于K的下标(也就是最左边)。

找到大于等于K的最左边的下标记为first,找到第一个大于等于K+1的下标记为last即可

分治法

241. Different Ways to Add Parentheses (Medium)

1
2
3
4
5
6
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output : [0, 2]

分治解法:遍历字符串input,当遇到运算符号如“+、-、*”的时候,分治求解出left和right,根据运算符号,遍历运算left和right的值并添加到结果列表中。

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
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ways = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (c == '+' || c == '-' || c == '*') {
List<Integer> left = diffWaysToCompute(input.substring(0, i));
List<Integer> right = diffWaysToCompute(input.substring(i + 1));
for (int l : left) {
for (int r : right) {
switch (c) {
case '+':
ways.add(l + r);
break;
case '-':
ways.add(l - r);
break;
case '*':
ways.add(l * r);
break;
}
}
}
}
}
if (ways.size() == 0) {
ways.add(Integer.valueOf(input));
}
return ways;
}

搜索

广度优先搜索

用途:搜索两节点最短路径,只能用于无权图最短路径。

例题:计算在网格中从原点到特定点的最短路径长度

1
2
3
4
[[1,1,0,1],
[1,0,1,0],
[1,1,1,1],
[1,0,1,1]]

1 表示可以经过某个位置,求解从 (0, 0) 位置到 (tr, tc) 位置的最短路径长度。

写广度优先遍历的时候,不需要写递归的程序,用队列实现。将第一层入队,第一层出队同时再将第二层入队,第二层出队的同时第三层入队。注意遍历过的元素实际标记0,以免重复访问。下面是详细代码

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
public int minPathLength(int[][] grids, int tr, int tc) {
final int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
final int m = grids.length, n = grids[0].length;
Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
queue.add(new Pair<>(0, 0));
int pathLength = 0;
while (!queue.isEmpty()) {
int size = queue.size();
pathLength++;
while (size-- > 0) {
Pair<Integer, Integer> cur = queue.poll();
int cr = cur.getKey(), cc = cur.getValue();
grids[cr][cc] = 0; // 标记
for (int[] d : direction) {
int nr = cr + d[0], nc = cc + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grids[nr][nc] == 0) {
continue;
}
if (nr == tr && nc == tc) {
return pathLength;
}
queue.add(new Pair<>(nr, nc));
}
}
}
return -1;
}

深度优先搜索

写程序的时候一般是递归写法,注意不是回溯写法。深度优先搜索一般会用来处理可达性的问题。因为从一个节点出发时,使用DFS对一个图进行遍历时,能够遍历到的节点都是从初始节点可达的。

如果非要写非递归写法,可以用栈来实现。

695. Max Area of Island (Easy)

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
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int maxArea = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxArea = Math.max(maxArea, dfs(grid, i, j));
}
}
return maxArea;
}

private int dfs(int[][] grid, int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
return 0;
}
grid[r][c] = 0;
int area = 1;
for (int[] d : direction) {
area += dfs(grid, r + d[0], c + d[1]);
}
return area;
}

连通分量数目相关问题:

普通矩阵连通分量和好友连通分量区分:好友连通分量中第二行和第二列都是与同一个人有关,是一个对称矩阵。

200. Number of Islands (Medium)

1
2
3
4
5
6
7
Input:
11000
11000
00100
00011

Output: 3

可以将矩阵表示看成一张有向图。

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
private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int islandsNum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != '0') {
dfs(grid, i, j);
islandsNum++;
}
}
}
return islandsNum;
}

private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
for (int[] d : direction) {
dfs(grid, i + d[0], j + d[1]);
}
}

好友关系的连通分量数目

547. Friend Circles (Medium)

1
2
3
4
5
6
7
8
9
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]

Output: 2

Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.

题目描述:好友关系可以看成是一个无向图,例如第 0 个人与第 1 个人是好友,那么 M[0][1] 和 M[1][0] 的值都为 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private int n;

public int findCircleNum(int[][] M) {
n = M.length;
int circleNum = 0;
boolean[] hasVisited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!hasVisited[i]) {
dfs(M, i, hasVisited);
circleNum++;
}
}
return circleNum;
}

private void dfs(int[][] M, int i, boolean[] hasVisited) {
hasVisited[i] = true;
for (int k = 0; k < n; k++) {
if (M[i][k] == 1 && !hasVisited[k]) {
dfs(M, k, hasVisited);
}
}
}

动态规划

递归和动态规划都是讲原问题拆成多个子问题然后求解,他们之间最本质的区别是:动态规划保存了子问题的解,避免重复计算

强盗在环形街区抢劫

213. House Robber II (Medium)

对于普通的HouseRobber,首先有一点需要明确,假设有n家可以抢劫,那么抢劫的最大收益一定是dp[n],因为dp[n]一定大于或者等一dp[n-1]和dp[n-2]。现在变成环形,那么最大收益在Math.max(抢劫[0,n-2],抢劫[1,n-1])

矩阵最短路径和

64. Minimum Path Sum (Medium)

1
2
3
4
[[1,3,1],
[1,5,1],
[4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

题目描述:求从矩阵的左上角到右下角的最小路径和,每次只能向右和向下移动。

这道题是有关最短路径的问题,但因为是有权图,不能用广度优先搜索。所以这道题采用动态规划。

整数分割

343. Integer Break (Medim)

题目描述:For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

解题思路:动态规划解法。数组dp[i]表示将数字i分割所能得到的最大乘积。对于dp[i]怎么求,对于拆出来的数j(其中j <= i - 1),那么剩下的i-j可以拆分,亦可以不拆分。如果拆分就是求dp[i-j]的最大值。

1
2
3
4
5
6
7
8
9
10
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i - 1; j++) {
dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
}
}
return dp[n];
}

按平方分割整数(完美平方数)

279. Perfect Squares(Medium)

题目描述:For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

解题思路:动态规划解法。先生成比n小的所有完全平方数列表。动态规划数组dp[i]表示将数据i分割为完全平方数的最小数目。那么如何求解dp[i]呢?遍历完全平方数列表,假设数据i先分裂为哪个平方数时为最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int numSquares(int n) {
List<Integer> squareList = generateSquareList(n);
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int square : squareList) {
if (square > i) {
break;
}
min = Math.min(min, dp[i - square] + 1);
}
dp[i] = min;
}
return dp[n];
}

对于内层for循环,因为数据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
public int numSquares(int n) {
List<Integer> squares = generateSquares(n);
Queue<Integer> queue = new LinkedList<>();
boolean[] marked = new boolean[n + 1];
queue.add(n);
marked[n] = true;
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
level++;
while (size-- > 0) {
int cur = queue.poll();
for (int s : squares) {
int next = cur - s;
if (next < 0) {
break;
}
if (next == 0) {
return level;
}
if (marked[next]) {
continue;
}
marked[next] = true;
queue.add(next);
}
}
}
return n;
}

分割整数构成字母字符串

91. Decode Ways (Medium)

题目描述:Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

1
因为dp数组是比str的长度大1。所以当对i=2进行遍历的时候,对应到字符串中应该是第一个字符,所以有subString(i,i-2)即subString(1,2)取出第一个字符

最长递增子序列

300. Longest Increasing Subsequence (Medium)

img

树的高度

104. Maximum Depth of Binary Tree (Easy)

1
2
3
4
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

注意这里的判断条件是节点是否为空,为空返回0,判断条件不是判断是否是叶子节点。叶子节点的深度默认为1,也不该返回0。

平衡树

110. Balanced Binary Tree (Easy)

递归计算左右子树的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private boolean result = true;

public boolean isBalanced(TreeNode root) {
maxDepth(root);
return result;
}

public int maxDepth(TreeNode root) {
if (root == null) return 0;
int l = maxDepth(root.left);
int r = maxDepth(root.right);
if (Math.abs(l - r) > 1) result = false;
return 1 + Math.max(l, r);
}

两节点的最长路径

543. Diameter of Binary Tree (Easy)

1
2
3
4
5
6
7
8
9
Input:

1
/ \
2 3
/ \
4 5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

对于每个节点,算出其左右子树的高度,然后求出最大路径,更新max值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int max = 0;

public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return max;
}

private int depth(TreeNode root) {
if (root == null) return 0;
int leftDepth = depth(root.left);
int rightDepth = depth(root.right);
max = Math.max(max, leftDepth + rightDepth);
return Math.max(leftDepth, rightDepth) + 1;
}

翻转树

226. Invert Binary Tree (Easy)

1
2
3
4
5
6
7
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = root.left; // 后面的操作会改变 left 指针,因此先保存下来
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
}

递归反转左右子树,右子树反转的结果赋给root.left。