88. 合并两个有序数组

image.png
思路：
有点像合并两个有序链表，但是这道题如果从小到大依次比较，过程中会覆盖num1的值。
这道题有两个关键点

  • 应该从大到小，两两比较。

  • 当把nums2中的元素放置完毕后，循环就结束了。

    1. public void merge(int[] nums1, int m, int[] nums2, int n) {
    2.   if (m > nums1.length || n > nums2.length) throw new IllegalArgumentException();
    4.   int i =  m - 1, j = n - 1, k = m + n - 1;
    5.   while (j >= 0){
    6.       if (i >= 0 && nums1[i] >= nums2[j]){
    7.           nums1[k--] = nums1[i--];
    8.       }else{
    9.           nums1[k--] = nums2[j--];
    10.       }
    11.   }
    12. }

    75. 颜色分类

    image.png

    class Solution {
  public void sortColors(int[] nums) {
      //相当于双指针快排的一遍扫描，以元素1为分割点，小于1(也就是0)分在左边，大于1(也就是2)分在右边
      //定义nums[0,i] = 0 ,nums[j,num.length-1] = 2
      int i = -1, j = nums.length, k = 0;
      while (k < j){
          if (nums[k] < 1){
              swap(nums,++i,k++);
          }else if (nums[k] > 1){
              swap(nums,--j,k);
          }else {
              k++;
          }
      }
  }
  private void swap(int[] nums, int i, int j){
      int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
  }
}

    面试题 16.16. 部分排序

    image.png
    思路：
    该题就是要找到属于逆序对元素的左右边界，把这两个边界内的元素排序，整个数组就有序了。
    好了，现在问题拆分成两个子问题

  • 找出最右边属于逆序对元素的位置：从左往右正常情况下是依次增大，一旦有个元素比当前扫描过的最大的元素要小的话，说明该元素就是逆序对，就把位置记录下来，如果比当前元素要大的话，更新当前最大值就ok

  • 找出最左边属于逆序对的元素的位置：和上面思想一致。

    class Solution {
  public int[] subSort(int[] array) {
      if (array == null || array.length == 0) return new int[]{-1, -1};
      int r = -1, max = array[0];
      for (int i = 1; i < array.length; i++) {
          if (array[i] >= max) {
              max = array[i];
          } else {
              r = i;
          }
      }

      int l = -1, min = array[array.length - 1];
      for (int i = array.length - 2; i >= 0; i--) {
          if (array[i] <= min) {
              min = array[i];
          } else {
              l = i;
          }
      }

      return new int[]{l, r};
  }
}

    977. 有序数组的平方

    image.png
    一开始的思路是：从中间开始两个指针按照从小到大比较，然后填充到新的数组中。

    class Solution {
  public int[] sortedSquares(int[] nums) {
      int j = 0;
      while (j < nums.length && nums[j] < 0) j++;
      int i = j - 1;//i指向负数里最大的，j指向正数里最小的
      int[] res = new int[nums.length];
      for (int k = 0; k < nums.length; k++ ){
          if (i < 0) {
              res[k] = nums[j] * nums[j];
              j++;
          }else if (j > nums.length - 1){
              res[k] = nums[i] * nums[i];
              i--;
          }else if (nums[i] + nums[j] < 0){
              res[k] = nums[j] * nums[j];
              j++;
          }else {
              res[k] = nums[i] * nums[i];
              i--;
          }
      }
      return res;
  }
}

    妈的，后来想了想通过双指针也可以搞定，可以从大到小放置到数组啊。

    class Solution {
      public int[] sortedSquares(int[] nums) {
          int i = 0, j = nums.length - 1;
          int[] res = new int[j + 1];
          int k = res.length - 1;
          while (i <= j) {
              if (nums[i] * nums[i] < nums[j] * nums[j]) {
                  res[k--] = nums[j] * nums[j];
                  j--;
              } else {
                  res[k--] = nums[i] * nums[i];
                  i++;
              }
          }
          return res;
      }
  }

    15. 三数之和

    image.png

    class Solution {
  public List<List<Integer>> threeSum(int[] nums) {
      List<List<Integer>> res = new LinkedList();
      if (nums == null || nums.length < 3) return res;
      Arrays.sort(nums);
      for (int i = 0; i < nums.length; i++) {
          if (i > 0 && nums[i] == nums[i - 1]) continue;
          int j = i + 1, k = nums.length - 1;
          while (j < k) {
              int sum = nums[i] + nums[j] + nums[k];
              if (sum < 0) {
                  j++;
              } else if (sum > 0) {
                  k--;
              } else {
                  res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                  while (j < k && nums[j] == nums[j + 1]) {
                      j++;
                  }
                  while (j < k && nums[k - 1] == nums[k]) {
                      k--;
                  }
                  j++;
                  k--;
              }
          }
      }
      return res;
  }
}

    31. 下一个排列

    image.png
    题目描述有点坑爹，原意是:给定的数组中元素比如[1,2,3]，按顺序排列可以组成一个整数123，重新排列元素后可以组成很多整数(123,132,213,231,312,321)，要求返回一个重新排列后数组，正好比当前的整数大，比其他排列组成的数值又小，即下一个排列。
    思路：
    image.png

    class Solution {
  public void nextPermutation(int[] nums) {
      if (nums == null || nums.length < 2) return;
      int i = nums.length - 2;
      while (i >= 0 && nums[i] >= nums[i + 1]) {
          i--;
      }
      if (i >= 0) {
          int b = find(nums, i + 1);
          swap(nums, i, b);
      }
      //i后面的元素应该排列成最小元素，可以排序，但由于元素都是递减的，可以用双指针
      inverse(nums, i + 1);
  }
  private void inverse(int[] nums, int start) {
      int i = start, j = nums.length - 1;
      while (i < j) {
          swap(nums, i++, j--);
      }
  }
  private void swap(int[] nums, int a, int b) {
      int tmp = nums[a];
      nums[a] = nums[b];
      nums[b] = tmp;
  }
  //二分查找从右向左第一个大于target的元素
  private int find(int[] nums, int start) {
      int target = nums[start - 1];
      int l = start, r = nums.length - 1;
      while (l <= r) {
          int mid = l + (r - l) / 2;
          if (nums[mid] <= target) {
              r--;
          } else {
              l++;
          }
      }
      return r;
  }
}

    215. 数组中的第K个最大元素

    image.png

    class Solution {
  private Random random = new Random(System.currentTimeMillis());
  public int findKthLargest(int[] nums, int k) {
      if (nums == null || nums.length < k || k < 1) throw new IllegalArgumentException("Params error");
      int targetIdx = nums.length - k;
      int l = 0, r = nums.length - 1;
      while (l <= r) {
          int index = partition(nums, l, r);
          if (index < targetIdx) {
              l = index + 1;
          } else if (index > targetIdx){
              r = index - 1;
          } else {
              break;
          }
      }
      return nums[targetIdx];
  }
  private int partition(int[] nums, int l, int r) {
      int randomIdx = l + random.nextInt(r - l + 1);
      swap(nums, l, randomIdx);
      int v = nums[l];
      int lt = l;//[l+1,lt]<v
      for (int i = l + 1; i < r + 1; i++) {
          if (nums[i] < v) {
              swap(nums, ++lt, i);
          }
      }
      swap(nums, l, lt);
      return lt;
  }
  private void swap(int[] nums, int i, int j) {
      int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
  }
}

    56. 合并区间

    image.png

    class Solution {
  public int[][] merge(int[][] intervals) {
      if (intervals == null || intervals.length == 0 || intervals[0].length != 2) return new int[0][0];
      Arrays.sort(intervals, (a, b) -> {
          return a[0] - b[0];
      });
      List<int[]> res = new LinkedList();
      res.add(intervals[0]);
      for (int i = 1; i < intervals.length; i++) {
          int[] last = res.get(res.size() - 1);
          if (last[1] < intervals[i][0]) {
              res.add(intervals[i]);
          } else {
              last[1] = Math.max(last[1], intervals[i][1]);
          }
      }
      return res.toArray(new int[res.size()][]);
  }
}

    48. 旋转图像

    image.png
    思路：
    转换公式：matrix[i][j] = matrix[len-1-j][i]
    image.pngimage.png
    只要在遍历图上的4分之一区域，然后每一小块通过转换公式顺时针转4次就ok了。
    注意数组长度分奇数或偶数

    class Solution {
  public void rotate(int[][] matrix) {
      //matrix[i][j] = matrix[len-1-j][i]
      if (matrix == null || matrix.length < 2) return;
      int N = matrix.length;
      for (int i = 0; i < (N + 1) / 2; i++) {
          for (int j = 0; j < N / 2; j++) {
              int tmp = matrix[i][j];
              matrix[i][j] = matrix[N - 1 - j][i];
              matrix[N - 1 - j][i] = matrix[N - 1 - i][N - 1 - j];
              matrix[N - 1 - i][N - 1 - j] = matrix[j][N - 1 - i];
              matrix[j][N - 1 - i] = tmp;
          }
      }
  }
}

    283. 移动零

    image.png

    class Solution {
  public void moveZeroes(int[] nums) {
      if (nums == null || nums.length == 0) return;
      int l = -1;
      for (int i = 0; i < nums.length; i++) {
          if (nums[i] != 0) {
              nums[++l] = nums[i];
          }
      }
      for (int i = l + 1; i < nums.length; i++) {
          nums[i] = 0;
      }
  }
}

    或者借鉴快排里partition里面的方法

    class Solution {
  public void moveZeroes(int[] nums) {
      if (nums == null || nums.length == 0) return;
      //[0,l] != 0
      int l = -1;
      for (int i = 0; i < nums.length; i++) {
          if (nums[i] != 0) {
              swap(nums, ++l, i);
          }
      }
  }
  private void swap(int[] nums, int i, int j) {
      int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
  }
}