LeetCode刷题笔记——HOT100面试题（1）

算法
,

数组

1. 两数之和

用哈希表存储出现过的数字，空间换时间。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            if (map.containsKey(target-nums[i])) return new int[]{map.get(target-nums[i]), i};
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

4. 寻找两个正序数组的中位数

可以将本题扩展到求两个有序数组中第K大的值。可以比较两个数组中的第K/2大的值（设为mid1和mid2），如果mid1<mid2，那么nums1中位于mid1及其之前的所有数都不可能是第K大的数，这样就排除掉了K/2个数，下次讨论的范围为nums1[K/2:], nums2[:]（下标从0开始算）。直到K==1为止，只需要比较两个数组的头部元素大小即可找到所求的值。属于二分查找，时间复杂度$O(log(m+n))$。

特殊情况：

  • 如果两个数组中有一个数组为空，只需返回另一个数组的第K大的值。
  • 如果一个数组长度小于K/2，就排除另一个数组前K/2个数。
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 double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        // 计算中位数，避免分别讨论奇偶
        int mid1 = (len1+len2+1)/2;
        int mid2 = (len1+len2+2)/2;
        return (getKthNum(nums1, 0, nums2, 0, mid1) + getKthNum(nums1, 0, nums2, 0, mid2))/2.0;
    }

    public int getKthNum(int[] nums1, int i, int[] nums2, int j, int k) {
        // 一个数组为空时，返回另一个数组的第K大的值
        if (nums1.length<=i) return nums2[j+k-1];
        if (nums2.length<=j) return nums1[i+k-1];
        // 递归终止条件：K==1
        if (k==1) return Math.min(nums1[i], nums2[j]);
        // 如果一个数组不存在第K/2大的数，就除去另外一个数组的前K/2个数，这里用最大值来简化代码
        int num1 = i+k/2-1>=nums1.length? Integer.MAX_VALUE: nums1[i+k/2-1];
        int num2 = j+k/2-1>=nums2.length? Integer.MAX_VALUE: nums2[j+k/2-1];
        if (num1<=num2) return getKthNum(nums1, i+k/2, nums2, j, k-k/2);
        else return getKthNum(nums1, i, nums2, j+k/2, k-k/2);
    }
}

11. 盛最多水的容器

前后双指针，计算并更新最大容积，并更新较矮的一侧。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxArea(int[] height) {
        int res = 0, i = 0, j = height.length - 1;
        while (i < j) {
            res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
            if (height[i] < height[j])
                i++;
            else
                j--;
        }
        return res;
    }
}

15. 三数之和

先排序数组，固定一个数，然后用前后双指针的方法找到三数之和为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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        if (n<3) return res;
        Arrays.sort(nums);
        for (int i=0; i<n-2; i++) {
            if (nums[i]>0) break;//最小的数必须小于等于0才能使和为0
            if (i>0 && nums[i-1]==nums[i]) continue;//避免重复
            int j = i+1, k = n-1;
            while (j<k) {
                int sum = nums[i]+nums[j]+nums[k];
                if (sum==0) {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], nums[k])));
                    while (j<k && nums[j]==nums[++j]);
                    while (j<k && nums[k]==nums[--k]);
                } else if (sum<0) {
                    while (j<k && nums[j]==nums[++j]);
                } else {
                    while (j<k && nums[k]==nums[--k]);
                }
            }
        }
        return res;
    }
}

31. 下一个排列

  1. 从后往前找到第一个升序数对，记数对中第一个数的下标为k；
  2. 在k之后找到最大的j使得nums[k] < nums[j]；
  3. 交换nums[j]和nums[k]；
  4. 翻转nums[k+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
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        // 从后往前找到第一个升序序列，其开始下标为k
        int k = -1;
        for (int i=n-2; i>=0; i--) {
            if (nums[i] < nums[i+1]) {
                k = i;
                break;
            }
        }
        // 如果数组完全逆序，返回升序排序后的结果
        if (k==-1) {
            reverse(nums, 0, n-1);
            return;
        }
        // 在nums[k+1:]找到最大的j使nums[j]>nums[k]
        int j = -1;
        for (int i=n-1; i>k; i--) {
            if (nums[i] > nums[k]) {
                j = i;
                break;
            }
        }
        // 交换nums[k], nums[j]
        swap(nums, j, k);
        // 翻转nums[k+1:]
        reverse(nums, k+1, n-1);
        return;
    }

    public void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public void reverse(int[] arr, int i, int j) {
        while (i < j) {
            swap(arr, i++, j--);
        }
    }
}

48. 旋转图像

先将图像按照左对角线翻转，再按照垂直中线翻转，其效果等同于将图像顺时针旋转90°。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 按照左对角线翻转
        for (int i=0; i<n-1; i++) {
            for (int j=i+1; j<n; j++) {
                int t = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = t;
            }
        }
        // 按照垂直中线翻转
        for (int i=0; i<n; i++) {
            for (int j=0; j<n/2; j++) {
                int t = matrix[i][j];
                matrix[i][j] = matrix[i][n-j-1];
                matrix[i][n-j-1] = t;
            }
        }
    }
}

55. 跳跃游戏

如果一个点可以到达，那么它之前的所有点都可以到达。遍历数组，更新可以到达的最远距离，如果当前位置超过了最远距离则返回false。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean canJump(int[] nums) {
        int farest = 0;
        for (int i=0; i<nums.length; i++) {
            if (i > farest) return false;
            farest = Math.max(i + nums[i], farest);
        }
        return true;
    }
}

75. 颜色分类

荷兰国旗问题。使用p0、p2两个指针分别从前后搜索0和2，以及一个指针从左往右遍历。遇到0就与p0指向的地址交换；遇到2就与p2指向的地址交换，但此时指针不前进，继续比较新值是否处在合适的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, p2 = nums.length-1;
        for (int i=0; i<=p2; i++) {
            if (nums[i]==0) {
                nums[i] = nums[p0];
                nums[p0] = 0;
                p0++;
            } else if (nums[i]==2) {
                nums[i] = nums[p2];
                nums[p2] = 2;
                p2--;
                i--;
            }
        }
    }
}

128. 最长连续序列

使用一个哈希表来保存数组中出现过的数字，其值为该元素所在连续序列的长度。如果某个数字的前一位和后一位也存在哈希表中，说明可以组成一段连续序列，更新这个序列端点对应的长度，并更新最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int longestConsecutive(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int num: nums) {
            if (map.containsKey(num)) continue;
            int left = map.getOrDefault(num-1, 0);
            int right = map.getOrDefault(num+1, 0);
            int len = left+right+1;
            map.put(num, len);
            map.put(num-left, len);
            map.put(num+right, len);
            res = Math.max(res, len);
        }
        return res;
    }
}

169. 多数元素

参见《剑指Offer》数组中出现次数超过一半的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int majorityElement(int[] nums) {
        int vote = 1, num = nums[0];
        for (int i=1; i<nums.length; i++) {
            if (num==nums[i]) vote++;
            else vote--;
            if (vote==0) {
                num = nums[i];
                vote = 1;
            }
        }
        return num;
    }
}

238. 除自身以外数组的乘积

参见《剑指Offer》构建乘积数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        res[0] = 1;
        for (int i=1; i<nums.length; i++) {
            res[i] = res[i-1] * nums[i-1];
        }
        int p = 1;
        for (int i=nums.length-1; i>=0; i--) {
            res[i] *= p;
            p *= nums[i];
        }
        return res;
    }
}

240. 搜索二维矩阵 II

参见《剑指offer》二维数组中的查找。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length-1;
        int j = 0;
        while (i>=0 && j<matrix[0].length) {
            if (matrix[i][j]==target) return true;
            else if (matrix[i][j]>target) i--;
            else j++;
        }
        return false;
    }
}

283. 移动零

双指针，一个指针顺序遍历，另一个指针保存所有不为0的数，然后将这个指针之后的位置填充0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void moveZeroes(int[] nums) {
        int j=0;
        for (int i=0; i<nums.length; i++) {
            if (nums[i]!=0) {
                nums[j] = nums[i];
                j++;
            }
        }
        for (; j<nums.length; j++) {
            nums[j] = 0;
        }
    }
}

287. 寻找重复数

由于数组元素位于1~n之间，可以把数组当作链表，将本题转化成寻找有环链表的环入口问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findDuplicate(int[] nums) {
        int fast = 0, slow = 0;
        while (true) {
            fast = nums[nums[fast]];
            slow = nums[slow];
            if (fast==slow) break;
        }
        fast = 0;
        while (true) {
            fast = nums[fast];
            slow = nums[slow];
            if (fast==slow) break;
        }
        return slow;
    }
}

347. 前 K 个高频元素

先使用哈希表把元素及其出现的次数保存起来，再使用小顶堆获取出现次数最多的K个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num: nums) map.put(num, map.getOrDefault(num, 0)+1);
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o2) - map.get(o1);
            }
        });
        for (int num: map.keySet()) {
            minHeap.offer(num);
        }
        int[] res = new int[k];
        for (int i=0; i<k; i++) {
            res[i] = minHeap.poll();
        }
        return res;
    }
}

448. 找到所有数组中消失的数字

将原数组中所有正数作为数组的索引值，将这些索引值对应数组值取相反数，仍为正数的索引值即为消失的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i=0; i<nums.length; i++) {
            int index = Math.abs(nums[i])-1;
            if (nums[index]>0) {
                nums[index] *= -1;
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i=0; i<nums.length; i++) {
            if (nums[i]>0) res.add(i+1);
        }
        return res;
    }
}

560. 和为K的子数组

一段连续子数组（nums[i:j]）的和可以用sum(nums[j]) - sum(nums[i])得到。使用哈希表来保存前缀和及相等的前缀和出现的次数，判断是否存在前缀和之差为k的情况。哈希表中插入(0, 1)用于处理第一个数等于k的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0, sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int num: nums) {
            sum += num;
            if (map.containsKey(sum-k)) {
                res += map.get(sum-k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}

581. 最短无序连续子数组

一个指针从左到右遍历，不断与当前最大值比较，发现逆序就更新右边界；一个指针从右到左遍历，不断与当前最小值比较，发现逆序就更新左边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int max = nums[0], min = nums[nums.length-1];
        int left = 0, right = -1;
        for (int i=0; i<nums.length; i++) {
            if (nums[i]>=max) max = nums[i];
            else right = i;
            if (nums[nums.length-1-i]<=min) min = nums[nums.length-1-i];
            else left = nums.length-1-i;
        }
        return right-left+1;
    }
}

621. 任务调度器

不妨设A为需要做最多次的任务，计数为k。以A为分界点安排任务，如果其他任务恰好能全部插入到这个任务的冷却期中，此时总时间为(k-1) * (n+1) + 1。但若有复数个任务出现次数最多，则在最后一轮需要加上那些任务数。如果冷却时间少而任务多，间隔期间已经插满任务时还有剩余的任务，此时所花费时间就是任务总数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char c: tasks) {
            count[c-'A']++;
        }
        Arrays.sort(count);
        int most = count[25];
        int last = 1;
        for (int i=24; i>=0; i--) {
            if (most==count[i]) last++;
            else break;
        }
        int res = (n+1) * (most-1) + last;
        return Math.max(res, tasks.length);
    }
}