Leetcode刷

TopKElements and KthElements

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

KthElements问题

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

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

堆排序：创建最小堆，最后堆中剩下得元素中堆顶元素为要求的值

堆得创建用优先队列：
PriorityQueue<Integer> heap=new PriorityQueue<>();这是创建了小顶堆
PriorityQueue<Integer> heap2=new PriorityQueue<>(((o1, o2) -> o2-o1));这是创建大顶堆
为什么是大顶堆？后面返回值为负数时（即o2-o1小于0），传入的o1放在前面，o2放在后面。因为o1是比o2大的，所以o1放在前面相当于把**大的值放在前面**

如何维护堆的大小？不断往堆中插入数据，每次都要检测优先队列的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)

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，不能取等

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)

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)

Input: "2-1-1".

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

Output : [0, 2]

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

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,1,0,1],
 [1,0,1,0],
 [1,1,1,1],
 [1,0,1,1]]

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

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

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)

[[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)

Input:
11000
11000
00100
00011

Output: 3

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

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)

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。

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,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]的最大值。

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先分裂为哪个平方数时为最优解。

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第一次分裂可以划分出任何一个完全平方数，我们要求哪种划分最小。

法二：利用广度优先搜索也可以完成。如果两个数之间差一个平方数，那么这两个数之间存在一条边。

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)

树

树的高度

104. Maximum Depth of Binary Tree (Easy)

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)

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

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)

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值

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)

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。