查找

发表于 更新于 分类于 阅读次数： 本文字数： 7.5k 阅读时长 ≈ 27 分钟

1. 二分查找及其应用

1.1 搜索二维矩阵 II

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

思路

直接查找：二重循环遍历，时间复杂度O(mn)。

二分查找：依次对每一行进行二分查找，时间复杂度O(mlogn)。

Z 字形查找：从矩阵右上角开始查找，若小于 target 则从下一行开始查找；若大于则从前一列开始查找，时间复杂度O(m + n)。

代码

Z 字形查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n=matrix.length,m=matrix[0].length;
        // 右上角开始查找
        int x=0,y=m-1;
        while(x<n&&y>=0){
            if(matrix[x][y]==target){
                return true;
            }
            // 大于target，y--
            if(matrix[x][y]>target){
                y--;
            }else{// 小于target，x++
                x++;
            }
        }
        return false;
    }
}

二分查找

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 boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length,n=matrix[0].length;
        int index=0;
        for(int i=0;i<m;i++){
            // 二分查找
            if(matrix[i][0]<=target&&target<=matrix[i][n-1]){
                int low=0,high=n-1;
                while(low<=high){
                    int mid=low+(high-low)/2;
                    if(matrix[i][mid]==target){
                        return true;
                    }else if(matrix[i][mid]<target){
                        low=mid+1;
                    }else{
                        high=mid-1;
                    }
                }
            }
        }
        return false;
    }
}

直接查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n=matrix.length,m=matrix[0].length;
        // 遍历矩阵
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }
}

1.2 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路

二分查找，比较中间元素与 target 的大小，然后更新区间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) {
        int low=0,high=nums.length-1;
        // 二分查找
        while(low<=high){
            int mid=(low+high)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                high=mid-1;
            }else{
                low=mid+1;
            }
        }
        return -1;
    }
}

1.3 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

思路

二分查找，维护一个pos指针指向第一个大于等于target的元素位置，初始化pos=-1，若最终pos==-1，说明数组中没有比target大的元素，即插入末尾。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int searchInsert(int[] nums, int target) {
        int low=0,high=nums.length-1,pos=-1;
        while(low<=high){
            int mid=(low+high)/2;
            // 找到target元素直接返回位置
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                pos=mid;
                high=mid-1;
            }else{
                low=mid+1;
            }
        }
        // 若pos==-1，返回nums.length
        // 若pos!=-1，返回pos
        return pos==-1?nums.length:pos;
    }
}

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

思路

两次二分查找，即要找到第一个大于 target 的位置和第一个大于等于 target 的位置。

代码

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 int[] searchRange(int[] nums, int target) {
        int low=0,high=nums.length-1;
        // 初始化left=-1，right=nums.length
        // 第一个大于等于target的位置，若无，则为-1
        // 第一个大于target的位置，若无，则为nums.length
        int left=-1,right=nums.length;
        // 寻找right
        while(low<=high){
            int mid=(low+high)/2;
            if(nums[mid]>target){
                high=mid-1;
                right=mid;
            }else{
                low=mid+1;
            }
        }
        low=0;
        high=nums.length-1;
        // 寻找left
        while(low<=high){
            int mid=(low+high)/2;
            if(nums[mid]>=target){
                high=mid-1;
                left=mid;
            }else{
                low=mid+1;
            }
        }
        return left!=-1&&nums[left]==target?new int[]{left,right-1}:new int[]{-1,-1};
    }
}

1.5 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

思路

二分查找，观察数组我们可以发现以数组中任意位置为分割点，将数组分为两个部分，总有一个部分是升序排列的。

判断哪个部分是升序我们只需比较nums[0]与当前位置的大小，若当前位置的数较大，说明前半部分为升序排列；反之后半部分为升序排列。

找到升序部分后，我们只需判断该部分最大值与target的大小，若大于或等于target，说明target出现在升序部分；反之，则出现在另一部分。

最终不断缩小区间，我们可以得到target的下标位置。

代码

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 {
    public int search(int[] nums, int target) {
        int low=0,high=nums.length-1;
        int n=nums.length;
        while(low<=high){
            int mid=(low+high)/2;
            // 找到target直接返回
            if(nums[mid]==target){
                return mid;
            }
            // nums[0]<=nums[mid]，说明前半段为升序排列
            if(nums[0]<=nums[mid]){
                if(nums[0]<=target&&target<=nums[mid]){
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }else{// 后半段为升序排列
                if(nums[mid]<=target&&target<=nums[n-1]){
                    low=mid+1;
                }else{
                    high=mid-1;
                }
            }
        }
        return -1;
    }
}

1.6 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

思路

相较于”搜索旋转排序数组“，变化是所给数组为非降序排列，同题解一，我们可以将其分为两个部分，并找到其中有序的部分，需要注意的是当左右区间端点都等于中间端点的值时，我们无法判断哪个部分为有序部分，此时将左边界加一，有边界减一，即缩小区间继续二分查找即可。

代码

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 boolean search(int[] nums, int target) {
        int low=0,high=nums.length-1;
        while(low<=high){
            int mid=(low+high)/2;
            if(nums[mid]==target){
                return true;
            }
            // 左右区间端点均等于中间端点，区间缩小
            if(nums[low]==nums[mid]&&nums[high]==nums[mid]){
                low++;
                high--;
            }else if(nums[low]<=nums[mid]){
                if(nums[low]<=target&&nums[mid]>=target){
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }else{
                if(nums[mid]<=target&&nums[high]>=target){
                    low=mid+1;
                }else{
                    high=mid-1;
                }
            }
        }
        return false;
    }
}

1.7 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

思路

二分查找，首先处理边界问题，若边界数已经为峰值，直接返回即可，若不为峰值，则进行二分查找，这样边界问题只需处理一次。

代码

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 int findPeakElement(int[] nums) {
        // 数组长度为1，直接返回
        if(nums.length==1) return 0;
        // 若nums[0]>nums[1]，则nums[0]为峰值
        if(nums[0]>nums[1]) return 0;
        // 若nums[nums.length-1]>nums[nums.length-2]，则nums[nums.length-1]为峰值
        if(nums[nums.length-1]>nums[nums.length-2]) return nums.length-1;
        // 边界问题处理完后，进行二分查找，无需再处理边界
        int low=1,high=nums.length-2;
        while(low<=high){
            int mid=(low+high)/2;
            if(nums[mid]>nums[mid-1]&&nums[mid]>nums[mid+1]){
                return mid;
            }else if(nums[mid]<nums[mid-1]){
                high=mid-1;
            }else{
                low=mid+1;
            }
        }
        return -1;
    }
}

1.8 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

思路

大佬题解：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/8999/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

二分解法

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 findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n=nums1.length,m=nums2.length;
        int low=(m+n+1)/2;
        int high=(m+n+2)/2;
        return (getKthNum(nums1,0,n-1,nums2,0,m-1,low)+getKthNum(nums1,0,n-1,nums2,0,m-1,high))*0.5;
    }
    public int getKthNum(int[] nums1,int s1,int e1,int[] nums2,int s2,int e2,int k){
        int len1=e1-s1+1;
        int len2=e2-s2+1;
        if(len1>len2) return getKthNum(nums2,s2,e2,nums1,s1,e1,k);
        if(len1==0) return nums2[s2+k-1];
        if(k==1) return Math.min(nums1[s1],nums2[s2]);
        int i=s1+Math.min(len1,k/2)-1;
        int j=s2+Math.min(len2,k/2)-1;
        if(nums1[i]>nums2[j]){
            return getKthNum(nums1,s1,e1,nums2,j+1,e2,k-(j-s2+1));
        }else{
            return getKthNum(nums1,i+1,e1,nums2,s2,e2,k-(i-s1+1));
        }
    }
}

2. 二叉排序树及其应用

2.1 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

思路

LeetCode 官方题解：https://leetcode.cn/problems/unique-binary-search-trees/solutions/329807/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numTrees(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}

数学

1
2
3
4
5
6
7
8
9
class Solution {
    public int numTrees(int n) {
        long ans=1;
        for(int i=0;i<n;i++){
            ans=2*(2*i+1)*ans/(i+2);
        }
        return (int) ans;
    }
}

2.2 不同的二叉搜索树 II

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

思路

对于1到n的每个数，以该数为根节点，其左节点为其左半部分构成的不同二叉树，右节点为右半部分构成的不同二叉树，然后左右各选取一棵树作为该数的子树即可。

由该过程可以得出本质上是一个长度缩小的子问题，采用回溯算法生成子树即可。

参考LeetCode官方题解：https://leetcode.cn/problems/unique-binary-search-trees-ii/solutions/339143/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode-solut/

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        return generate(1,n);
    }
    public List<TreeNode> generate(int start,int end){
        List<TreeNode> tree=new ArrayList<>();
        // 若该节点无效，加入null
        if(start>end){
            tree.add(null);
            return tree;
        }
        for(int i=start;i<=end;i++){
            // 左子树集合
            List<TreeNode> leftTree=generate(start,i-1);
            // 右子树集合
            List<TreeNode> rightTree=generate(i+1,end);
            // 每次从左右子树集合各取一棵，构成不同的二叉搜索树
            for(TreeNode left:leftTree){
                for(TreeNode right:rightTree){
                    TreeNode root=new TreeNode(i);
                    root.left=left;
                    root.right=right;
                    tree.add(root);
                }
            }
        }
        return tree;
    }
}

2.3 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

思路

递归或迭代搜索：

  • 若root==null||root.val==val，返回root
  • 若root.val<val，递归搜索root.right
  • 若root.val>val，递归搜索root.left

递归

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null||root.val==val){
            return root;
        }else if(root.val<val){
            return searchBST(root.right,val);
        }else{
            return searchBST(root.left,val);
        }
    }
}

迭代

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root!=null){
            if(root.val==val){
                return root;
            }
            root=root.val<val?root.right:root.left;
        }
        return null;
    }
}

2.4 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。

思路

递归思路：

  • root==null，直接返回null

  • root.val<key，递归删除左子树

  • root.val>key，递归删除右子树

  • root.val==key：

    • 左右子树均为空，直接删除，返回null

    • 左子树为空，返回右子树

    • 右子树为空，返回左子树

    • 左右子树均不为空

      寻找右子树中的最小节点，将其更新为新节点，然后删除它的原本位置

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // root==null,直接返回
        if(root==null){
            return null;
        }
        // 递归删除右子树
        if(root.val>key){
            root.left=deleteNode(root.left,key);
            return root;
        }
        // 递归删除左子树
        if(root.val<key){
            root.right=deleteNode(root.right,key);
            return root;
        }
        // 叶子节点直接删除
        if(root.left==null&&root.right==null){
            return null;
        }
        // 左子树为空，返回右子树
        if(root.left==null){
            return root.right;
        }
        // 右子树为空，返回左子树
        if(root.right==null){
            return root.left;
        }
        // 寻找右子树中的最小节点
        TreeNode successor=root.right;
        while(successor.left!=null){
            successor=successor.left;
        }
        // 更新为新节点
        root.right=deleteNode(root.right,successor.val);
        successor.right=root.right;
        successor.left=root.left;
        return successor;
    }
}

2.5 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路

遍历二叉搜索树：

  • 若p.val<root.val&&q.val<root.val，说明两个节点都在左子树中
  • 若p.val>root.val&&q.val>root.val，说明两个节点都在右子树中
  • 若不符合上面两种情况，说明两个节点分别在左右子树中，则当前节点即为最近公共祖先

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return root;
        }
        while(root!=null){
            // 递归遍历左子树
            if(p.val<root.val&&q.val<root.val){
                root=root.left;
            }else if(p.val>root.val&&q.val>root.val){// 递归遍历右子树
                root=root.right;
            }else{
                // 找到最近公共祖先，退出循环
                break;
            }
        }
        return root;
    }
}

2.6 验证二叉搜索树

给你一个二叉树的根节点 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
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // long类型处理临界问题
    long val=Long.MIN_VALUE;
    // 二叉搜索树标志位
    boolean flag=true;
    public boolean isValidBST(TreeNode root) {
        dfs(root);
        return flag;
    }
    public void dfs(TreeNode root){
        if(root!=null){
            dfs(root.left);
            if(root.val<=val){
                flag=false;
            }
            val=root.val;
            dfs(root.right);
        }
    }
}

2.7 二叉搜索树的范围和

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

思路

中序遍历的同时求出满足条件的节点和。

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum=0;
    int low;
    int high;
    public int rangeSumBST(TreeNode root, int low, int high) {
        this.low=low;
        this.high=high;
        dfs(root);
        return sum;
    }
    public void dfs(TreeNode root){
        if(root!=null){
            dfs(root.left);
            // 符合条件则累加
            if(root.val<=high&&root.val>=low) sum+=root.val;
            dfs(root.right);
        }
    }
}

3. 平衡二叉树及其应用

3.1 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思路

递归求解左右子树高度，判断其高度差是否超过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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root)>=0;
    }
    public int height(TreeNode root){
        // 空节点，高度为0
        if(root==null){
            return 0;
        }
        // 左子树高度
        int left=height(root.left);
        // 右子树高度
        int right=height(root.right);
        // 若左子树或右子树已经不满足条件，或当前左右子树高度差超过1，返回-1
        if(left==-1||right==-1||Math.abs(left-right)>1){
            return -1;
        }
        // 返回子树高度
        return Math.max(left,right)+1;
    }
}

3.2 将二叉搜索树变平衡

给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

思路

通过中序遍历得到一个递增序列，然后以中间节点为根节点重新构造平衡二叉树。

之后，每次都选取根节点两边的中间节点作为左右子树的根节点进行递归构造。

证明

以中间节点为根节点，则其两侧元素个数之差不超过1，即左右子树节点数量之差不会超过1，又因为我们是递归构造的，最终每个节点的左右子树节点数量之差都不会超过1，即保证了左右子树高度差都不会超过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
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> list=new ArrayList<>();
    public TreeNode balanceBST(TreeNode root) {
        traversal(root);
        return build(0,list.size()-1);
    }
    // 构造平衡二叉搜索树
    public TreeNode build(int start,int end){
        // 空节点
        if(start>end) return null;
        // 中间位置
        int mid=(start+end)/2;
        // 构造根节点
        TreeNode root=new TreeNode(list.get(mid));
        // 递归构造左子树
        root.left=build(start,mid-1);
        // 递归构造右子树
        root.right=build(mid+1,end);
        // 返回根节点
        return root;
    }
    // 中序遍历，将二叉搜索树转化为有序序列
    public void traversal(TreeNode root){
        if(root!=null){
            traversal(root.left);
            list.add(root.val);
            traversal(root.right);
        }
    }
}

3.3 安排工作以达到最大收益

你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

  • difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
  • worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。

  • 举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。

返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。

思路

先将profit与difficulty对应起来，以profit为key，difficulty为value，按照降序排序，对worker按照升序排序。（不对worker进行降序排列的原因是Java的Arrays.sort()对于Integer[]和int[]的排序有限制，若要降序排序，那么需要将int[]类型转化为Integer[]，浪费空间（弊端）。C++则不会有此问题。）

然后依次从worker末尾开始反向遍历，若值大于当前第一个profit对应的difficulty，则直接安排该项工作；否则寻找第一个difficulty不大于worker值的工作。

代码

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
class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        List<int[]> pro=new ArrayList<>();
        int n=profit.length,m=worker.length;
        // 以profit为键，difficulty为值对应
        for(int i=0;i<n;i++){
            pro.add(new int[]{profit[i],difficulty[i]});
        }
        // 降序排列pro
        Collections.sort(pro,(int[] a1,int[] a2) -> (a2[0]-a1[0]));
        // 升序排列worker
        Arrays.sort(worker);
        int i=0,sum=0;
        for(int j=m-1;j>=0;j--){
            int work=worker[j];
            // 当前worker能胜任工作，分派该工作
            if(work>=pro.get(i)[1]){
                sum+=pro.get(i)[0];
            }else{
                // 寻找第一个当前worker能胜任的工作
                while(i<n&&work<pro.get(i)[1]){
                    i++;
                }
                if(i<n){
                    sum+=pro.get(i)[0];
                }else{
                    // 未找到，说明worker及其之后的worker已经无法胜任任何工作
                    break;
                }
            }
        }
        return sum;
    }
}

3.4 第三大的数

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

思路

维护三个变量first、second和third，分别代表最大数、次大数和第三大的数，然后根据规则进行更新。

注意int边界判断。

代码

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 int thirdMax(int[] nums) {
        int first=Integer.MIN_VALUE,second=Integer.MIN_VALUE,third=Integer.MIN_VALUE;
        boolean flag=false;
        for(int num:nums){
            // 判断是否出现了Integer.MIN_VALUE
            if(num==Integer.MIN_VALUE){
                flag=true;
            }
            // 更新规则
            if(num>first){
                int tmp=second;
                second=first;
                third=tmp;
                first=num;
            }else if(num==first){
                continue;
            }else if(num>second){
                third=second;
                second=num;
            }else if(num==second){
                continue;
            }else if(num>third){
                third=num;
            }
        }
        // first!=second,说明first存在
        // second!=third,说明second存在
        // third!=Integer.MIN_VALUE说明third存在，或flag==true(表示数组中存在Integer.MIN_VALUE，此时即使third==Integer.MIN_VALUE，third也是存在的)
        return first!=second&&second!=third&&(third!=Integer.MIN_VALUE||flag)?third:first;
    }
}

4. 哈希表及其应用

4.1 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

  • void add(key) 向哈希集合中插入值 key 。
  • bool contains(key) 返回哈希集合中是否存在这个值 key 。
  • void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

思路

拉链法，参考官方题解以BASE=769作为基数进行哈希映射，遇到冲突元素则延长拉链。

宫水三叶大佬题解（「简单数组」&「链表」& 「分桶数组」）：https://leetcode.cn/problems/design-hashset/solutions/653184/yi-ti-san-jie-jian-dan-shu-zu-lian-biao-nj3dg/

代码

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
class MyHashSet {
    private static final int BASE = 769;
    private LinkedList[] set; 
    public MyHashSet() {
        set = new LinkedList[BASE];
        for(int i=0;i<BASE;i++){
            set[i]=new LinkedList<Integer>();
        }
    }
    
    public void add(int key) {
        int n_key=hash(key);
        Iterator<Integer> iterator=set[n_key].iterator();
        while(iterator.hasNext()){
            int val=iterator.next();
            if(val==key){
                return;
            }
        }
        set[n_key].offerLast(key);
    }
    
    public void remove(int key) {
        int n_key=hash(key);
        Iterator<Integer> iterator=set[n_key].iterator();
        while(iterator.hasNext()){
            int val=iterator.next();
            if(val==key){
                iterator.remove();
                return;
            }
        }
    }
    
    public boolean contains(int key) {
        int n_key=hash(key);
        Iterator<Integer> iterator=set[n_key].iterator();
        while(iterator.hasNext()){
            int val=iterator.next();
            if(val==key){
                return true;
            }
        }
        return false;
    }

    private int hash(int key){
        return key % BASE;
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */

4.2 LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

思路

双向链表+哈希表，也就是Java中LinkedHashMap的简单实现，链表节点中存储对应的键值对，链表节点的先后顺序表示访问的顺序，哈希表中存储键对应的链表节点，每次访问或添加键值对时，更新对应链表节点。

代码

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
class LRUCache {
    // 双向链表节点
    class Node{
        int key;
        int val;
        Node pre;
        Node next;
        Node(){}
        Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }
    // 哈希表
    Map<Integer,Node> map;
    // 头节点
    Node head;
    // 尾节点
    Node tail;
    // 容量
    int capacity;
    
    // 初始化
    public LRUCache(int capacity) {
        this.capacity=capacity;
        map=new HashMap<>();
        head=new Node();
        tail=new Node();
        head.next=tail;
        tail.pre=head;
    }
    
    public int get(int key) {
        // 若存在，则将其访问顺序移到头部
        if(map.containsKey(key)){
            Node node=map.get(key);
            moveToHead(node);
            return node.val;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            // 更新节点
            Node node=map.get(key);
            node.val=value;
            moveToHead(node);
        }else{
            Node node=new Node(key,value);
            // 容量为空则删除尾节点，否则容量减1
            if(capacity==0){
                Node cur=removeTail();
                map.remove(cur.key);
            }else{
                capacity--;
            }
            map.put(key,node);
            addToHead(node);
        }
    }
	
    // 删除节点
    private void remove(Node node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
    }

    // 在头部添加节点
    private void addToHead(Node node){
        node.pre=head;
        node.next=head.next;
        head.next.pre=node;
        head.next=node;
    }

    // 删除尾节点
    private Node removeTail(){
        Node node=tail.pre;
        remove(node);
        return node;
    }

    // 将当前节点移到头部
    private void moveToHead(Node node){
        remove(node);
        addToHead(node);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

4.3 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路

快速选择算法。参考快速排序算法的分治思想，我们并不需要将两个分治区间都进行排序，而只需判断当前位置在排序好的数组中是在第几个位置，因此我们只需递归一个区间即可。中间引入随机化思想，可使时间复杂度达到O(n)。

官方题解：https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/307351/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/

代码

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
class Solution {
    Random random=new Random();
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums,0,nums.length-1,nums.length-k);
    }
    public int quickSelect(int[] nums,int l,int r,int index){
     	// 对数组中的某个位置进行随机划分
        int n=randomPartition(nums,l,r);
        // n==index，说明找到了第K个最大元素
        if(n==index){
            return nums[n];
        }else{
            // 根据位置大小，递归左或右区间
            return n<index?quickSelect(nums,n+1,r,index):quickSelect(nums,l,n-1,index);
        }
    }
    public int randomPartition(int[] nums,int l,int r){
        // 随机选取一个位置，判断它在排序后数组中的位置
        int index=random.nextInt(r-l+1)+l;
        // 将需要判断的数转移到数组末尾
        swap(nums,index,r);
        // 划分区间
        return partition(nums,l,r);
    }
    public int partition(int[] nums,int l,int r){
        // 由于我们将index与r位置调换了，所以现在r位置即为我们要判断的随机数的位置
        int num=nums[r],i=l;
        for(int j=l;j<r;j++){
            // 不大于num的数移到左侧区间
            if(nums[j]<=num){
                swap(nums,i++,j);
            }
        }
        // 交换该数到最终位置
        swap(nums,i,r);
        // 该数在排序后数组中的最终位置
        return i;
    }
    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}

4.4 O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

  • RandomizedSet() 初始化 RandomizedSet 对象

  • bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。

  • bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。

  • int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class RandomizedSet {
    List<Integer> nums;
    Map<Integer,Integer> vis;
    Random random;
    // 初始化
    public RandomizedSet() {
        nums=new ArrayList<>();
        vis=new HashMap<>();
        random=new Random();
    }
    
    public boolean insert(int val) {
        // 若存在，返回false
        if(vis.containsKey(val)){
            return false;
        }
        // 插入元素
        nums.add(val);
        vis.put(val,nums.size()-1);
        return true;
    }
    
    public boolean remove(int val) {
        // 若不存在，返回false
        if(!vis.containsKey(val)){
            return false;
        }
        // 获取被删除元素在数组中的下标
        int index=vis.get(val);
        // 将数组中的最后一个元素下标更新为当前下标，即覆盖了当前下标的数，相当于删除
        nums.set(index,nums.get(nums.size()-1));
        // 更新数组中的最后一个元素的下标位置
        vis.put(nums.get(nums.size()-1),index);
        // 数组中的最后一个元素已经被更新，直接删除最后一个元素
        nums.remove(nums.size()-1);
        // 移除需要被删除元素的键值对
        vis.remove(val);
        return true;
    }
    
    public int getRandom() {
        // 获取随机下标
        int index=random.nextInt(nums.size());
        return nums.get(index);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */