题目列表

  • 56. 合并区间
  • 169. 多数元素
  • 470. 用 Rand7() 实现 Rand10()
  • 31. 下一个排列

  • 48. 旋转图像

    具体实现

    56. 合并区间

    输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]]

    1. class Solution {
    2.   public int[][] merge(int[][] a) {
    3.        ArrayList<int[]> res = new ArrayList<>();
    4.       //1. 按照左端点排序
    5.       Arrays.sort(a,(o1,o2)->(o1[0]-o2[0]));
    6.       //2. 看下一个区间的左端点在是否在本区间右端点的左侧
    7.       int l = a[0][0], r = a[0][1];
    8.       for(int i = 1; i < a.length; i++){
    9.           //2.1 在则证明有交集，更新右端点
    10.           if(a[i][0] <= r){
    11.               r = Math.max(r, a[i][1]);
    12.           }else{
    13.               //2.2 不在证明没有交集，保留此区间即可
    14.               int[] tmp = new int[2];
    15.               tmp[0] = l;
    16.               tmp[1] = r;
    17.               res.add(tmp);
    18.               l = a[i][0]; r = a[i][1];
    19.           }
    20.       }
    21.       int[] tmp = new int[2];
    22.       //最后一个区间!!!!!!!
    23.       tmp[0] = l;
    24.       tmp[1] = r;
    25.       res.add(tmp);
    26.       return res.toArray(new int[0][]);
    27.   }
    28. }

    169. 多数元素

  • r为当前数

  • c为当前数的库存

    1. class Solution {
    2.   public int majorityElement(int[] nums) {
    3.       int r = nums[0], c = 1;
    4.       for(int i = 1; i < nums.length; i++){
    5.           if(nums[i] == r){
    6.               c++;
    7.           }else{
    8.               c--;
    9.               if(c == 0) {
    10.                   //一旦之前的数，消耗完了，就要更新新的候选数
    11.                   //r和c都要更新
    12.                   r = nums[i];
    13.                   c = 1;
    14.               }
    15.           }
    16.       }
    17.       return r;
    18.   }
    19. }

    470. 用 Rand7() 实现 Rand10()

    1. class Solution extends SolBase {
    2.   //1. 生成[1, 49]之间的随机数
    3.   //调用一次rand7()生成1-7之间的随机数
    4.   //rand7() - 1生成0-6之间的随机数
    5.   //(rand7() - 1) * 7 ->[0, 42]
    6.   //(rand7() - 1) * 7 + rand7() ->[1, 49]
    8.   //2. 如果生成的数是41 - 49则舍弃掉，重新生成一个小于等于40的随机数
    9.   //if (t > 40) return rand10();
    11.   //3. 
    12.   //t - 1 ->[0, 39]
    13.   //(t - 1) % 10 ->[0, 9]
    14.   //(t - 1) % 10 + 1; ->[1, 10]
    15.   public int rand10() {
    16.       int t = (rand7() - 1) * 7 + rand7();
    17.       if(t > 40) return rand10();
    18.       return (t - 1) % 10 + 1;
    19.   }
    20. }

    31. 下一个排列

    1. class Solution {
    2.   public void reverse(int[] nums, int l, int r){
    3.       while(l < r){
    4.           int tmp = nums[l];
    5.           nums[l] = nums[r];
    6.           nums[r] = tmp;
    7.           l++;
    8.           r--;
    9.       }
    10.   }
    11.   public void nextPermutation(int[] nums) {
    12.       //2 3 5 4 1
    13.       //  ↑   ↑      
    14.       //2 4 5 3 1
    15.       //2 4 1 3 5
    16.       int k = nums.length - 1;
    17.       //找到峰顶值
    18.       while(k > 0 && nums[k - 1] >= nums[k]) k--;
    19.       if(k == 0){
    20.           reverse(nums, 0, nums.length - 1);
    21.       }else{
    22.           //交换 k - 1和k后面大于k - 1的最小的数
    23.           int t = k;
    24.           while(t < nums.length && nums[t] > nums[k - 1]) t++;
    25.           int tmp = nums[k - 1];
    26.           nums[k - 1] = nums[t - 1];
    27.           nums[t - 1] = tmp;
    28.           reverse(nums, k, nums.length - 1);
    29.       }
    30.   }
    31. }

    上一个排列

  • 把上面的两个＞改成＜即可

    1. class Solution {
    2.   public void reverse(int[] nums, int l, int r){
    3.       while(l < r){
    4.           int tmp = nums[l];
    5.           nums[l] = nums[r];
    6.           nums[r] = tmp;
    7.           l++;
    8.           r--;
    9.       }
    10.   }
    11.   public void nextPermutation(int[] nums) {
    12.       //2 4 1 3 5
    13.       //  ↑ k ↑
    14.       //2 3 1 4 5
    15.       //2 3 5 4 1
    16.       int k = nums.length - 1;
    17.       //找到低点值
    18.       while(k > 0 && nums[k - 1] <= nums[k]) k--;
    19.       if(k == 0){
    20.           reverse(nums, 0, nums.length - 1);
    21.       }else{
    22.           //交换 k - 1和k后面小于k - 1的最小的数
    23.           int t = k;
    24.           while(t < nums.length && nums[t] < nums[k - 1]) t++;
    25.           int tmp = nums[k - 1];
    26.           nums[k - 1] = nums[t - 1];
    27.           nums[t - 1] = tmp;
    28.           reverse(nums, k, nums.length - 1);
    29.       }
    30.   }
    31. }

    48. 旋转图像

  • 左斜对角线交换

  • 沿中轴交换
    1. class Solution {
    2.   public void rotate(int[][] matrix) {
    3.       int m = matrix.length, n = matrix[0].length;
    4.       for(int i = 0; i < m; i++){
    5.           for(int j = 0; j < i; j++){
    6.               int tmp = matrix[i][j];
    7.               matrix[i][j] = matrix[j][i];
    8.               matrix[j][i] = tmp;
    9.           }
    10.       }
    11.       for(int i = 0; i < m; i++){
    12.           for(int j = 0, k = n - 1; j < k; j++, k--){
    13.               int tmp = matrix[i][j];
    14.               matrix[i][j] = matrix[i][k];
    15.               matrix[i][k] = tmp;
    16.           }
    17.       }
    18.   }
    19. }