1、合并区间

将数组按照数组第一个值大小进行排序，然后遍历时比较临近数组的首尾数字 引入list ，用来存储结果

  1.      public static int[][] merge(int[][] intervals) {
  2.         List<int[]> lists = new ArrayList<int[]>();
  3.         Arrays.sort(intervals, new Comparator<int[]>() { //排序
  4.             @Override
  5.             public int compare(int[] o1, int[] o2) {
  6.                 return Integer.compare(o1[0], o2[0]);
  7.             }
  8.         });    表达式写法 Arrays.sort(intervals,(a,b)-> a[0] - b[0]);
  10.         for (int i = 0; i < intervals.length; i++) {
  11.             int left = intervals[i][0];
  12.             int right = intervals[i][1];
  13.             if (lists.size() == 0 || lists.get(lists.size() - 1)[1] < left) {
  14.                 lists.add(new int[]{left, right}); //如果第一个，且遍历较大数字
  15.             } else {
  16.                 //取当前遍历数字和上一个存储的数字最大值。
  17.                 lists.get(lists.size() - 1)[1] = Math.max(lists.get(lists.size() - 1)[1], right);
  18.             }
  19.         }
  20.         return lists.toArray(new int[lists.size()][]);
  21.     }

2、轮转数组

模拟运算

  1. nums = "----->-->"; k =3
  2. result = "-->----->";
  4. reverse "----->-->" we can get "<--<-----"
  5. reverse "<--" we can get "--><-----"
  6. reverse "<-----" we can get "-->----->"
  7. this visualization help me figure it out :)

实际运算

  1.     public void rotate(int[] nums, int k) {
  2.         int len = nums.length;
  3.         k = k % nums.length;
  4.         reverse(nums, 0, len - 1);
  5.         reverse(nums, 0, k-1);
  6.         reverse(nums, k, len - 1);
  8.     }
  10.     public void reverse(int[] nums, int start, int end) {
  11.         while (start < end) {
  12.             int temp = nums[start];
  14.             nums[start] = nums[end];
  15.             nums[end] = temp;
  16.                 start+=1;
  17.             end -= 1;
  18.         }
  19.     }

3、除自身以外数组的乘积

基础版

由于是算除自身以外数组的乘积，因此以当前遍历的为中心，算出当前数字的左右两边的乘积和，然后将左右两边的乘积进行相乘

  1. class Solution {
  2.     public int[] productExceptSelf(int[] nums) {
  3.         int len = nums.length;
  4.         int[] answer = new int[nums.length];
  5.         int[] right = new int[len]; // 存储从当前位置右侧的所有元素的乘积
  6.         int[] left = new int[len]; // 存储从当前位置左侧的所有元素的乘积
  8.         int leftSum = 1;
  9.         int rightSum = 1;
  10.         left[0] = 1; // 初始化左侧乘积为1
  11.         for (int i = 1; i < len; i++) {
  12.             left[i] = left[i - 1] * nums[i - 1]; // 计算左侧乘积
  13.         }
  14.         right[len - 1] = 1; // 初始化右侧乘积为1
  15.         for (int i = len - 2; i >= 0; i--) {
  16.             right[i] = right[i + 1] * nums[i + 1]; // 计算右侧乘积
  17.         }
  19.         for (int i = 0; i < len; i++) {
  20.             answer[i] = left[i] * right[i]; // 将左侧乘积和右侧乘积相乘得到答案
  21.         }
  22.         return answer;
  23.     }
  24. }

优化

由于在计算左右两边的乘积和时，会申请2n的空间，因此，在计算过程各种可以复用answer 由于没有右侧乘积，因此需要定义一个变量来记录右侧的乘积

  1.     public int[] productExceptSelf(int[] nums) {
  2.         int len = nums.length;
  3.         int[] answer = new int[len];
  5.         answer[0] = 1;
  7.         for (int i = 1; i < len; i++) {
  8.             answer[i] = answer[i - 1] * nums[i-1];
  9.         }
  10.         int rightSum = 1; //右侧乘积之和
  11.         for (int i = len-1; i >= 0; i--) {
  12.             answer[i] = answer[i] * rightSum;
  13.             rightSum *= nums[i]; 
  15.         }
  16.         return answer;
  17.     }

其他

思想同二，不过更加简洁，但是由于fill操作更占时间，所以时间耗时更长，且for中难以理解记忆。

  1. public int[] productExceptSelf(int[] nums) {
  2.         int n=nums.length;
  3.         int[] ans=new int[n];
  4.         Arrays.fill(ans,1);
  5.         int beforeSum=1;
  6.         int afterSum=1;
  7.         for(int i=0,j=n-1;i<n;i++,j--){
  8.             ans[i]*=beforeSum;
  9.             ans[j]*=afterSum;
  10.             beforeSum*=nums[i];
  11.             afterSum*=nums[j];
  12.         }
  13.         return ans;
  14.     }