devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode：数组（遍历数组，数组操作，区间问题，数学运算）_数学上如何表示遍历区间

作者：小丑西瓜9 | 2024-04-21 18:54:03

赞

踩

数学上如何表示遍历区间

1，遍历数组

45，把数组排成最小的数

 题目：输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

思路：

  1. class Solution {
  2.     public String minNumber(int[] nums) {
  3.         String[] strs = new String[nums.length];
  4.         for (int i = 0; i < nums.length; i++) {
  5.             strs[i] = String.valueOf(nums[i]);
  6.         }
  7.         Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
  8.         StringBuilder sb = new StringBuilder();
  9.         for (String str : strs) {
  10.             sb.append(str);
  11.         }
  12.         return sb.toString();
  13.     }
  14. }
  1. class Solution {
  2.     public String minNumber(int[] nums) {
  3.         String[] strs = new String[nums.length];
  4.         for(int i = 0; i < nums.length; i++)
  5.             strs[i] = String.valueOf(nums[i]);
  6.         quickSort(strs, 0, strs.length - 1);
  7.         StringBuilder res = new StringBuilder();
  8.         for(String s : strs)
  9.             res.append(s);
  10.         return res.toString();
  11.     }
  12.     void quickSort(String[] strs, int l, int r) {
  13.         if(l >= r) return;
  14.         int i = l, j = r;
  15.         String tmp = strs[i];
  16.         while(i < j) {
  17.             while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
  18.             while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
  19.             tmp = strs[i];
  20.             strs[i] = strs[j];
  21.             strs[j] = tmp;
  22.         }
  23.         strs[i] = strs[l];
  24.         strs[l] = tmp;
  25.         quickSort(strs, l, i - 1);
  26.         quickSort(strs, i + 1, r);
  27.     }
  28. }

51，数组中的逆序对

题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

思路：力扣

  1. class Solution {
  2.     int[] nums, tmp;
  3.     public int reversePairs(int[] nums) {
  4.         this.nums = nums;
  5.         tmp = new int[nums.length];
  6.         return mergeSort(0, nums.length - 1);
  7.     }
  8.     private int mergeSort(int l, int r) {
  9.         // 终止条件
  10.         if (l >= r) return 0;
  11.         // 递归划分
  12.         int m = (l + r) / 2;
  13.         int res = mergeSort(l, m) + mergeSort(m + 1, r);
  14.         // 合并阶段
  15.         int i = l, j = m + 1;
  16.         for (int k = l; k <= r; k++)
  17.             tmp[k] = nums[k];
  18.         for (int k = l; k <= r; k++) {
  19.             if (i == m + 1)
  20.                 nums[k] = tmp[j++];
  21.             else if (j == r + 1 || tmp[i] <= tmp[j])
  22.                 nums[k] = tmp[i++];
  23.             else {
  24.                 nums[k] = tmp[j++];
  25.                 res += m - i + 1; // 统计逆序对
  26.             }
  27.         }
  28.         return res;
  29.     }
  30. }

76，部分排序

题目：给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

  1. class Solution {
  2.     public int[] subSort(int[] array) {
  3.         int N = array.length, start = -1, end = -1;
  4.         int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
  5.         
  6.         // 从前往后找目标末位，使得从该位到最后，数组保持递增
  7.         for (int i = 0; i < N; i++) {
  8.             if (array[i] >= max) max = array[i];
  9.             else end = i;
  10.         }
  11.         
  12.         // 数组恒递增，说明数组是有序的，直接返回
  13.         if (end == -1) return new int[] {-1, -1};
  14.         
  15.         // 从后往前找目标首位，使得从该位到最前，数组保持递减
  16.         for (int i = end; i >= 0; i--) {
  17.             if (array[i] <= min) min = array[i];
  18.             else start = i;
  19.         }
  20.         return new int[] {start, end};
  21.     }
  22. }

135，分发糖果

题目：n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

  1. class Solution {
  2.     public int candy(int[] ratings) {
  3.         if(ratings == null || ratings.length == 0){
  4.             return 0;
  5.         }
  6.         int[] nums = new int[ratings.length];//记录每一位孩子得到的糖果数
  7.         nums[0] = 1;
  8.         //先正序遍历，如果后一位比前一位高分，就给比前一位多1的糖果，否则给1
  9.         for(int i = 1; i < ratings.length; i++){
  10.             if(ratings[i] > ratings[i-1]){
  11.                 nums[i] = nums[i-1] + 1;        
  12.             }else {
  13.                 nums[i] = 1;
  14.             }
  15.         }
  16.         //在倒叙遍历，如果前一位比后一位高分并且得到的糖果小于或等于后一位，就给前一位孩子比后一位孩子多一个糖果
  17.         for(int i = ratings.length -2 ; i >= 0; i--){
  18.             if(ratings[i] > ratings[i+1] && nums[i] <= nums[i+1]){
  19.                 nums[i] = nums[i+1] +1;
  20.             }
  21.         }
  22.         int count = 0;
  23.         for(int i : nums){
  24.             count +=i;
  25.         }
  26.         return count;
  27.     }
  28. }

139，单词拆分

题目：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

  1. class Solution {
  2.      public boolean wordBreak(String s, List<String> wordDict) {
  3.         int n = s.length();
  4.         boolean[] dp = new boolean[n + 1];
  5.         // 初始化
  6.         dp[0] = true;
  7.         for(int i=1;i<=n;i++){
  8.             for(int j=0;j<i;j++){
  9.                 // 右半部分存在于单词字典中
  10.                 String word = s.substring(j,i);
  11.                 // 左半部分由dp递推得到
  12.                 if(wordDict.contains(word) && dp[j]){
  13.                     dp[i] = true;
  14.                 }
  15.             }
  16.         }
  17.         return dp[n];
  18.     }
  19. }

283，移动零

题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。

思路：从左边开始找到第一个0的位置，从右边开始找到第一个不为0的位置，交换元素。

  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.         int left = 0;
  4.         int right = 0;
  5.         int start = 0;
  6.         int count = 0;
  7.         for (int i = 0; i < nums.length; i++) {
  8.             if (nums[i] != 0) {
  9.                 count++;
  10.             }
  11.         }
  12.         if (count != nums.length) {
  13.             while (true) {
  14.                 for (int i = 0; i < nums.length; i++) {
  15.                     if (nums[i] == 0) {
  16.                         left = i;
  17.                         break;
  18.                     }
  19.                 }
  20.                 for (int i = start; i < nums.length; i++) {
  21.                     if (nums[i] != 0) {
  22.                         right = i;
  23.                         break;
  24.                     }
  25.                 }
  26.                 if (left < right) {
  27.                     int temp = nums[right];
  28.                     nums[right] = nums[left];
  29.                     nums[left] = temp;
  30.                 }
  31.                 start++;
  32.                 int finish_left = 0;
  33.                 int finish_right = 0;
  34.                 for (int i = 0; i < nums.length; i++) {
  35.                     if (nums[i] == 0) {
  36.                         finish_left = i;
  37.                         break;
  38.                     }
  39.                 }
  40.                 for (int i = 0; i < nums.length; i++) {
  41.                     if (nums[i] != 0) {
  42.                         finish_right = i;
  43.                     }
  44.                 }
  45.                 if (finish_right <= finish_left) {
  46.                     break;
  47.                 }
  48.             }
  49.         }
  50.     }
  51. }

525，连续数组

题目：给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

思路：将0变为-1，当遍历前缀和出现同样元素a时，说明第一个a到第二个a中间的0,1数目相同。

  1. class Solution {
  2.     public int findMaxLength(int[] nums) {
  3.          /**
  4.         将数组中的0换成-1， 求和为0的最长子数组 转换成前缀和问题
  5.          */
  6.         for(int i = 0; i < nums.length; ++i){
  7.             if(nums[i] == 0) nums[i] = -1;
  8.         }
  9.         Map<Integer, Integer> map = new HashMap<>();
  10.         map.put(0, -1);
  11.         int ans = 0, sum = 0;
  12.         for(int i = 0; i < nums.length; ++i){
  13.             sum += nums[i];
  14.             if(map.containsKey(sum)){
  15.                 ans = Math.max(ans, i - map.get(sum));
  16.             }else map.put(sum, i);
  17.         }
  18.         return ans;
  19.     }
  20. }

1184，公交站间的距离

题目：环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。环线上的公交车都可以按顺时针和逆时针的方向行驶。返回乘客从出发点 start 到目的地 destination 之间的最短距离。

  1. class Solution {
  2.     public int distanceBetweenBusStops(int[] distance, int start1, int destination1) {
  3.         int sum1 = 0;
  4.         int sum2 = 0;
  5.         int start = Math.min(start1, destination1);
  6.         int destination = Math.max(start1, destination1);
  7.         for (int i = start; i < destination; i++) {
  8.             sum1 += distance[i];
  9.         }
  10.         for (int i = start-1; i >= 0; i--) {
  11.             sum2 += distance[i];
  12.         }
  13.         for (int i = distance.length - 1; i >= destination; i--) {
  14.             sum2 += distance[i];
  15.         }
  16.         return Math.min(sum1, sum2);
  17.     }
  18. }

1331，数组序号转换

题目：给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。序号代表了一个元素有多大。序号编号的规则如下：

  • 序号从 1 开始编号。一个元素越大，那么序号越大。
  • 如果两个元素相等，那么它们的序号相同。
  • 每个数字的序号都应该尽可能地小。
  1. class Solution {
  2.     public int[] arrayRankTransform(int[] arr) {
  3.         if (arr.length == 0) {
  4.             return new int[]{};
  5.         }
  6.         int[] c = arr.clone();
  7.         int[] result = new int[c.length];
  8.         int x = 0;
  9.         Arrays.sort(c);
  10.         int index = 1;
  11.         HashMap<Integer, Integer> b = new HashMap();
  12.         for (int j = 0; j < c.length; j++) {
  13.             if (!b.containsKey(c[j])) {
  14.                 b.put(c[j], index);
  15.                 index++;
  16.             }
  17.         }
  18.         ArrayList<Integer> a = new ArrayList();
  19.         for (int i = 0; i < arr.length; i++) {
  20.             result[i] = b.get(arr[i]);
  21.         }
  22.         return result;
  23.     }
  24. }

1508，子数组和排序后的区间和

题目：给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。

请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

  1. class Solution {
  2.     public int rangeSum(int[] nums, int n, int left, int right) {
  3.         int length = (1 + n) * n / 2;
  4.         final int MOD = 1000000000 + 7;
  5.         int[] result = new int[length];
  6.         result = continuousSubList(nums, length);
  7.         Arrays.sort(result);
  8.         long sum = 0;
  9.         for (int i = left - 1; i < right; i++) {
  10.             sum += result[i];
  11.         }
  12.         return (int) (sum % MOD);
  13.     }
  14.      public int[] continuousSubList(int[] arr, int length) {
  15.         int[] result = new int[length];
  16.         List<Integer> resultList = new ArrayList<>();
  17.         if (arr == null || arr.length < 1) {
  18.             return null;
  19.         }
  20.         // 对于每个位置都求包含他本身在内的所有连续子数组
  21.         for (int i = 0; i < arr.length; i++) {
  22.             for (int j = i; j < arr.length; j++) {
  23.                 // 从 i ~ j位置求得一个子数组
  24.                 int temp = 0;
  25.                 for (int k = i; k <= j; k++) {
  26.                     temp += arr[k];
  27.                 }
  28.                 resultList.add(temp);
  29.             }
  30.         }
  31.         for (int i = 0; i < length; i++) {
  32.             result[i] = resultList.get(i);
  33.         }
  34.         // 返回最终结果
  35.         return result;
  36.     }
  37. }

1588，所有奇数长度子数组的和

题目：给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。子数组 定义为原数组中的一个连续子序列。请你返回 arr 中 所有奇数长度子数组的和 。

  1. 输入：arr = [1,4,2,5,3]
  2. 输出：58
  3. 解释：所有奇数长度子数组和它们的和为：
  4. [1] = 1
  5. [4] = 4
  6. [2] = 2
  7. [5] = 5
  8. [3] = 3
  9. [1,4,2] = 7
  10. [4,2,5] = 11
  11. [2,5,3] = 10
  12. [1,4,2,5,3] = 15
  13. 我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
  1. class Solution {
  2.     public int sumOddLengthSubarrays(int[] arr) {
  3.         int result = 0;
  4.         for (int i = 1; i <= arr.length; i += 2) {
  5.             int temp = 0;
  6.             for (int j = 0; j <= arr.length - i; j++) {
  7.                 for (int k = 0; k < i; k++) {
  8.                     temp += arr[j+k];
  9.                 }
  10.             }
  11.             result+=temp;
  12.         }
  13.         return result;
  14.     }
  15. }

2，数组操作

26，删除有序数组中的重复项

题目：给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

提示：一项一项删除会超时。

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         if (nums.length == 1) {
  4.             return 1;
  5.         }
  6.         Set s = new HashSet();
  7.         for (int i = 0; i < nums.length; i++) {
  8.             s.add(nums[i]);
  9.         }
  10.         int temp = s.size();
  11.         int q = 0;
  12.         for (int i = 0; i < nums.length  && q < temp; i++) {
  13.             int start = 0;
  14.             for (int j = i; j < nums.length - 1; j++) {
  15.                 if (nums[j] == nums[j + 1]) {
  16.                     start++;
  17.                 } else {
  18.                     break;
  19.                 }
  20.             }
  21.             for (int j = i + 1; j < nums.length - start; j++) {
  22.                 nums[j] = nums[j + start];
  23.             }
  24.             q++;
  25.         }
  26.         return q;
  27.     }
  28. }

48，旋转图像

题目：给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

  1. class Solution {
  2.     public void rotate(int[][] matrix) {
  3.         int n = matrix.length - 1;
  4.         for (int i = 0; i < matrix.length / 2; i++) {
  5.             for (int j = i; j < n - i; j++) {
  6.                 // 获取各顶点的值
  7.                 int a = matrix[i][j]; // 左上角
  8.                 int b = matrix[j][n - i]; // 右上角
  9.                 int c = matrix[n - i][n - j]; // 右下角
  10.                 int d = matrix[n - j][i]; // 左下角
  11.                 // 交换各顶点的值
  12.                 matrix[i][j] = d; // 左上角
  13.                 matrix[j][n - i] = a; // 右上角
  14.                 matrix[n - i][n - j] = b; // 右下角
  15.                 matrix[n - j][i] = c; // 左下角
  16.             }
  17.         }
  18.     }
  19. }

54，螺旋矩阵

题目：给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

思路1：有限制，需要找到一个原本数组不存在的数。

  1. class Solution {
  2.     public List<Integer> spiralOrder(int[][] matrix) {
  3.         List result = new ArrayList();
  4.         int maxNum = matrix.length * matrix[0].length;
  5.         int curNum = 1;
  6.         int row = 0, column = 0;
  7.         int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
  8.         int directionIndex = 0;
  9.         while (curNum <= maxNum) {
  10.             result.add(matrix[row][column]);
  11.             matrix[row][column] = 0;
  12.             curNum++;
  13.             int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
  14.             if (nextRow < 0 || nextRow >= matrix.length || nextColumn < 0 || nextColumn >= matrix[0].length || matrix[nextRow][nextColumn] == 0) {
  15.                 directionIndex = (directionIndex + 1) % 4; // 顺时针旋转至下一个方向
  16.             }
  17.             row = row + directions[directionIndex][0];
  18.             column = column + directions[directionIndex][1];
  19.         }
  20.         return result;
  21.     }
  22. }

思路2：按层模拟。

  1. class Solution {
  2.     public int[] spiralOrder(int[][] matrix) {
  3.         //边界条件判断
  4.         if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
  5.             return new int[0];
  6.         }
  7.         int m = matrix.length,n = matrix[0].length;
  8.         int num = 0;
  9.         int[] arr = new int[m*n];
  10.         int left = 0,right = n - 1;
  11.         int up = 0,down = m - 1;
  12.         while(num < m * n){
  13.             //最上面一行
  14.             for(int i = left;i <= right && num < m * n;i++){
  15.                 arr[num++] = matrix[up][i];
  16.             }
  17.             up++;
  18.             //最右边一列
  19.             for(int i = up;i <= down && num < m * n;i++){
  20.                 arr[num++] = matrix[i][right];
  21.             }
  22.             right--;
  23.             //最下面一行
  24.             for(int i = right;i >= left && num < m * n;i--){
  25.                 arr[num++] = matrix[down][i];
  26.             }
  27.             down--;
  28.             //最左边一列
  29.             for(int i = down;i >= up && num < m * n;i--){
  30.                 arr[num++] = matrix[i][left];
  31.             }
  32.             left++;
  33.         }
  34.         return arr;
  35.     }
  36. }

59，螺旋矩阵II

题目：给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

  1. class Solution {
  2.     public int[][] generateMatrix(int n) {
  3.         int maxNum = n * n;
  4.         int curNum = 1;
  5.         int[][] matrix = new int[n][n];
  6.         int row = 0, column = 0;
  7.         int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
  8.         int directionIndex = 0;
  9.         while (curNum <= maxNum) {
  10.             matrix[row][column] = curNum;
  11.             curNum++;
  12.             int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
  13.             if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] != 0) {
  14.                 directionIndex = (directionIndex + 1) % 4; // 顺时针旋转至下一个方向
  15.             }
  16.             row = row + directions[directionIndex][0];
  17.             column = column + directions[directionIndex][1];
  18.         }
  19.         return matrix;
  20.     }
  21. }

189：轮转数组

题目：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         int newNums[] = nums.clone();
  4.         for (int i = 0; i < newNums.length; i++) {
  5.             nums[k % nums.length] = newNums[i];
  6.             k++;
  7.         }
  8.     }
  9. }

1706，球会落在何处

题目：用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。

  • 将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
  • 将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。

在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。

  1. class Solution {
  2.     public int[] findBall(int[][] grid) {
  3.         int hight = grid.length;
  4.         int weight = grid[0].length;
  5.         int[] result = new int[weight];
  6.         for (int i = 0; i < weight; i++) {
  7.             result[i] = i;
  8.         }
  9.         for (int i = 0; i < hight; i++) {
  10.             for (int j = 0; j < weight; j++) {
  11.                 if (result[j] != -1 && grid[i][result[j]] == 1) {
  12.                     if (result[j] < weight - 1 && grid[i][result[j] + 1] == -1) {
  13.                         result[j] = -1;
  14.                     } else {
  15.                         result[j] += 1;
  16.                     }
  17.                 } else if (result[j] != -1 && grid[i][result[j]] == -1) {
  18.                     if (result[j] > 0 && grid[i][result[j] - 1] == 1) {
  19.                         result[j] = -1;
  20.                     } else {
  21.                         result[j] -= 1;
  22.                     }
  23.                 }
  24.                 if (result[j] > weight - 1 || result[j] < 0) {
  25.                     result[j] = -1;
  26.                     continue;
  27.                 }
  28.             }
  29.         }
  30.         return result;
  31.     }
  32. }

1886，判断矩阵经轮转后是否一致

题目：给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。

  1. class Solution {
  2.     public boolean findRotation(int[][] matrix, int[][] target) {
  3.         for (int i = 0; i < 4; i++) {
  4.             boolean flag = rotate(matrix, target);
  5.             if (flag == true) {
  6.                 return true;
  7.             }
  8.         }
  9.         return false;
  10.     }
  11.     public boolean rotate(int[][] matrix, int[][] target) {
  12.         int n = matrix.length - 1;
  13.         for (int i = 0; i < matrix.length / 2; i++) {
  14.             for (int j = i; j < n - i; j++) {
  15.                 // 获取各顶点的值
  16.                 int a = matrix[i][j]; // 左上角
  17.                 int b = matrix[j][n - i]; // 右上角
  18.                 int c = matrix[n - i][n - j]; // 右下角
  19.                 int d = matrix[n - j][i]; // 左下角
  20.                 // 交换各顶点的值
  21.                 matrix[i][j] = d; // 左上角
  22.                 matrix[j][n - i] = a; // 右上角
  23.                 matrix[n - i][n - j] = b; // 右下角
  24.                 matrix[n - j][i] = c; // 左下角
  25.             }
  26.         }
  27.         for (int i=0;i<matrix.length;i++){
  28.             for (int j=0;j<matrix[0].length;j++){
  29.                 if (matrix[i][j]!=target[i][j]){
  30.                     return false;
  31.                 }
  32.             }
  33.         }
  34.         return true;
  35.     }
  36. }

3，区间问题

11，盛水最多的容器

题目：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。

思路：初始底最大，然后缩短，比较两边高，修改低边。

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

42，接雨水

题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路：双指针

  1. class Solution {
  2.     public int trap(int[] height) {
  3.         int ans = 0;
  4.         int left = 0, right = height.length - 1;
  5.         int leftMax = 0, rightMax = 0;
  6.         while (left < right) {
  7.             leftMax = Math.max(leftMax, height[left]);
  8.             rightMax = Math.max(rightMax, height[right]);
  9.             if (height[left] < height[right]) {
  10.                 ans += leftMax - height[left];
  11.                 ++left;
  12.             } else {
  13.                 ans += rightMax - height[right];
  14.                 --right;
  15.             }
  16.         }
  17.         return ans;
  18.     }
  19. }

84，柱形图中最大的矩形

题目：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

思路：中心发散

  1. class Solution {
  2.     public int largestRectangleArea(int[] heights) {
  3.  
  4.        if (heights.length == 1) {
  5.             return heights[0];
  6.         }
  7.         int area = 0;
  8.         for (int i = 0; i < heights.length; i++) {
  9.             if (i != 0 && heights[i] == heights[i - 1]) {
  10.                 continue;
  11.             }
  12.             int left = i;
  13.             int right = i;
  14.             while (left > 0 && heights[i] <= heights[left - 1]) {
  15.                 left--;
  16.             }
  17.             while (right < heights.length - 1 && heights[i] <= heights[right + 1]) {
  18.                 right++;
  19.             }
  20.             area = Math.max(area, (right - left + 1) * heights[i]);
  21.         }
  22.         return area;
  23.     }
  24. }

56，合并区间

题目：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

  1. class Solution {
  2.    public int[][] merge(int[][] intervals) {
  3.         int n = intervals.length;
  4.         if (n == 0) {
  5.             return null;
  6.         }
  7.         //先按起点升序，再按终点降序
  8.         Arrays.sort(intervals, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
  9.         List<int[]> res = new ArrayList<>();
  10.         int left = intervals[0][0];
  11.         int right = intervals[0][1];
  12.         for (int i = 1; i < n; i++) {
  13.             if (intervals[i][0] > right) {
  14.                 //无交集
  15.                 res.add(new int[]{left, right});
  16.                 left = intervals[i][0];
  17.                 right = intervals[i][1];
  18.             } else if (intervals[i][1] < right) {
  19.                 //被覆盖
  20.             } else if (intervals[i][1] >= right && intervals[i][0] <= right) {
  21.                 //相交
  22.                 right = intervals[i][1];
  23.             }
  24.         }
  25.         res.add(new int[]{left, right});
  26.  
  27.         return res.toArray(new int[0][]);
  28.     }
  29. }

57，插入区间

题目：给你一个 无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

思路：不采用规则判断是因为过于麻烦，而且需要考虑横跨多个区间的问题。

  1. class Solution {
  2.     public int[][] insert(int[][] intervals, int[] newInterval) {
  3.         int n = intervals.length;
  4.         int[][] temp = new int[n + 1][2];
  5.         for (int i = 0; i < n; i++) {
  6.             temp[i] = intervals[i];
  7.         }
  8.         temp[n] = newInterval;
  9.         Arrays.sort(temp, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
  10.         //先按起点升序，再按终点降序
  11.         List<int[]> res = new ArrayList<>();
  12.         int left = temp[0][0];
  13.         int right = temp[0][1];
  14.         for (int i = 0; i <= n; i++) {
  15.             if (temp[i][0] > right) {
  16.                 //无交集
  17.                 res.add(new int[]{left, right});
  18.                 left = temp[i][0];
  19.                 right = temp[i][1];
  20.             } else if (temp[i][1] < right) {
  21.                 //被覆盖
  22.             } else if (temp[i][1] >= right && temp[i][0] <= right) {
  23.                 //相交
  24.                 right = temp[i][1];
  25.             }
  26.         }
  27.         res.add(new int[]{left, right});
  28.         return res.toArray(new int[0][]);
  29.     }
  30. }

218，天际线问题

题目：城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

  • lefti 是第 i 座建筑物左边缘的 x 坐标。
  • righti 是第 i 座建筑物右边缘的 x 坐标。
  • heighti 是第 i 座建筑物的高度。

你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。

  1. // 把每栋房子看作矩形，首先把矩形(Li，-Hi)和(Ri，Hi)插入到multiset st中，自动排序
  2. // 遍历multiset st，同时用另一个multiset height保存当前位置左边的历史高度，height.rbegin()即其最大值
  3. // 遍历过程中，如果发现是Li，则插入到height，否则是Ri，删除Ri在height中对应的Li
  4. // 如果height的最大值发生了变化，则该i元素就是返回结果之一
  5. class Solution {
  6.     public List<List<Integer>> getSkyline(int[][] buildings) {
  7.         PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[1] - a[1]);
  8.         List<Integer> boundaries = new ArrayList<Integer>();
  9.         for (int[] building : buildings) {
  10.             boundaries.add(building[0]);
  11.             boundaries.add(building[1]);
  12.         }
  13.         Collections.sort(boundaries);
  14.  
  15.         List<List<Integer>> ret = new ArrayList<List<Integer>>();
  16.         int n = buildings.length, idx = 0;
  17.         for (int boundary : boundaries) {
  18.             while (idx < n && buildings[idx][0] <= boundary) {
  19.                 pq.offer(new int[]{buildings[idx][1], buildings[idx][2]});
  20.                 idx++;
  21.             }
  22.             while (!pq.isEmpty() && pq.peek()[0] <= boundary) {
  23.                 pq.poll();
  24.             }
  25.  
  26.             int maxn = pq.isEmpty() ? 0 : pq.peek()[1];
  27.             if (ret.size() == 0 || maxn != ret.get(ret.size() - 1).get(1)) {
  28.                 ret.add(Arrays.asList(boundary, maxn));
  29.             }
  30.         }
  31.         return ret;
  32.     }
  33. }

228，汇总区间

题目：给定一个  无重复元素 的 有序 整数数组 nums 。返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。列表中的每个区间范围 [a,b] 应该按如下格式输出：

  • "a->b" ，如果 a != b
  • "a" ，如果 a == b
  1. class Solution {
  2.     public List<String> summaryRanges(int[] nums) {
  3.         ArrayList<String> result = new ArrayList<String>();
  4.         if (nums.length == 0) {
  5.             return result;
  6.         }
  7.         int index = 0;
  8.         int temp = nums[index];
  9.         int length = nums.length;
  10.         for (int i = 1; i < length; i++) {
  11.             if (nums[i] - nums[i - 1] == 1) {
  12.  
  13.             } else {
  14.                 if (nums[index] == nums[i - 1]) {
  15.                     result.add(nums[index] + "");
  16.                 } else {
  17.                     result.add(nums[index] + "->" + nums[i - 1]);
  18.                 }
  19.                 index = i;
  20.             }
  21.         }
  22.         if (nums[index] == nums[length - 1]) {
  23.             result.add(nums[index] + "");
  24.         } else {
  25.             result.add(nums[index] + "->" + nums[length - 1]);
  26.         }
  27.         return result;
  28.     }
  29. }

349，两个数组的交集

题目：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

  1. class Solution {
  2.     public int[] intersection(int[] nums1, int[] nums2) {
  3.         Arrays.sort(nums1);
  4.         Arrays.sort(nums2);
  5.         ArrayList<Integer> arrayList = new ArrayList();
  6.         int left = 0;
  7.         int right = 0;
  8.         while (left < nums1.length && right < nums2.length) {
  9.             if (nums1[left] == nums2[right]) {
  10.                 if (!arrayList.contains(nums1[left])){
  11.                    arrayList.add(nums1[left]);
  12.                }
  13.                 left++;
  14.                 right++;
  15.             } else if (nums1[left] > nums2[right]) {
  16.                 right++;
  17.             } else {
  18.                 left++;
  19.             }
  20.         }
  21.         int[] result = new int[arrayList.size()];
  22.         for (int i = 0; i < result.length; i++) {
  23.             result[i] = arrayList.get(i);
  24.         }
  25.         return result;
  26.     }
  27. }

350，两个数组的交集II

题目：给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

  1. class Solution {
  2.     public int[] intersect(int[] nums1, int[] nums2) {
  3.         int length1 = nums1.length;
  4.         int length2 = nums2.length;
  5.         ArrayList<Integer> a = new ArrayList();
  6.         if (length1 > length2) {
  7.             for (int i = 0; i < length2; i++) {
  8.                 for (int j = 0; j < length1; j++) {
  9.                     if (nums2[i] == nums1[j]) {
  10.                         a.add(nums2[i]);
  11.                         nums1[j] = -1;
  12.                         break;
  13.                     }
  14.                 }
  15.             }
  16.         } else {
  17.             for (int i = 0; i < length1; i++) {
  18.                 for (int j = 0; j < length2; j++) {
  19.                     if (nums1[i] == nums2[j]) {
  20.                         a.add(nums1[i]);
  21.                         nums2[j] = -1;
  22.                         break;
  23.                     }
  24.                 }
  25.             }
  26.         }
  27.         int result[] = new int[a.size()];
  28.         for (int i = 0; i < a.size(); i++) {
  29.             result[i] = a.get(i);
  30.         }
  31.         return result;
  32.     }
  33. }

435，无重复区间

题目：给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

思路：升序排列，然后如果最小的有区间大于下一个的左端，说明相交，剔除下一区间（因为下一区间的右端大于该区间的右端），如果小于，说明不相交，右端换为新右端。

  1. class Solution {
  2.     public int eraseOverlapIntervals(int[][] intervals) {
  3.         Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[1], o2[1]));
  4.         int cur = intervals[0][1];
  5.         int res = 0;
  6.         for (int i = 1; i < intervals.length; i++) {
  7.             if (cur > intervals[i][0]) {
  8.                 res++;
  9.             }
  10.             else {
  11.                 cur = intervals[i][1];
  12.             }
  13.         }
  14.         return res;
  15.     }
  16. }

452，用最小数量的箭引爆气球

题目：有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

  1. class Solution {
  2.     public int findMinArrowShots(int[][] points) {
  3.         if (points.length == 0) {
  4.             return 0;
  5.         }
  6.         Arrays.sort(points, new Comparator<int[]>() {
  7.             public int compare(int[] point1, int[] point2) {
  8.                 if (point1[1] > point2[1]) {
  9.                     return 1;
  10.                 } else if (point1[1] < point2[1]) {
  11.                     return -1;
  12.                 } else {
  13.                     return 0;
  14.                 }
  15.             }
  16.         });
  17.         int pos = points[0][1];
  18.         int ans = 1;
  19.         for (int[] balloon: points) {
  20.             if (balloon[0] > pos) {
  21.                 pos = balloon[1];
  22.                 ++ans;
  23.             }
  24.         }
  25.         return ans;
  26.     }
  27. }

729，我的日程安排表I

题目：实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end 。

实现 MyCalendar 类：

  • MyCalendar() 初始化日历对象。
  • boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。
  1. class MyCalendar {
  2.     List<int[]> booked;
  3.     public MyCalendar() {
  4.         booked = new ArrayList<int[]>();
  5.     }
  6.  
  7.     public boolean book(int start, int end) {
  8.         for (int[] arr : booked) {
  9.             int l = arr[0], r = arr[1];
  10.             if (l < end && start < r) {
  11.                 return false;
  12.             }
  13.         }
  14.         booked.add(new int[]{start, end});
  15.         return true;
  16.     }
  17. }

986，区间列表的交集

题目：给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

返回这 两个区间列表的交集 。形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

  1. class Solution {
  2.     public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
  3.         ArrayList<int[]> arrayList = new ArrayList();
  4.         int left = 0;
  5.         int right = 0;
  6.         while (left < firstList.length && right < secondList.length) {
  7.             int a = firstList[left][0];
  8.             int b = firstList[left][1];
  9.             int c = secondList[right][0];
  10.             int d = secondList[right][1];
  11.             if (a < c && b > d) {
  12.                 arrayList.add(new int[]{c, d});
  13.                 right++;
  14.             } else if (c < a && d > b) {
  15.                 arrayList.add(new int[]{a, b});
  16.                 left++;
  17.             } else if (a <= c && b <= d && b > c) {
  18.                 arrayList.add(new int[]{c, b});
  19.                 left++;
  20.             } else if (c <= a && d <= b && a < d) {
  21.                 arrayList.add(new int[]{a, d});
  22.                 right++;
  23.                 
  24.             } else if (a <= c && b <= d && b < c) {
  25.                 left++;
  26.             } else if (c <= a && d <= b && a > d) {
  27.                 right++;
  28.             } else if (b == c) {
  29.                 arrayList.add(new int[]{b, c});
  30.                 left++;
  31.             } else if (a == d) {
  32.                 arrayList.add(new int[]{a, d});
  33.                 right++;
  34.             }
  35.         }
  36.         return arrayList.toArray(new int[arrayList.size()][]);
  37.     }
  38. }

4，数学运算

1，两数之和

题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

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

2，对数和

题目：设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。

思路1：HashMap，把出现过的元素当成key，元素出现的次数当成value存到map中，如果遍历到某一个元素num，查看target - num元素是否出现过，如果出现过，那么可以组成一个整数对，注意这里一个数只能属于一个数对，所以判断target - num元素出现的次数，如果为1，直接remove即可，否则更新target - num元素出现的次数-1。

  1. class Solution {
  2.     public List<List<Integer>> pairSums(int[] nums, int target) {
  3.         //key:数组的元素;value:该元素出现的次数
  4.         Map<Integer, Integer> map = new HashMap<>();
  5.         
  6.         List<List<Integer>> ans = new ArrayList<>();
  7.         for (int num : nums) {
  8.             Integer count = map.get(target - num);
  9.             if (count != null) {
  10.                 ans.add(Arrays.asList(num, target - num));
  11.                 if (count == 1)
  12.                     map.remove(target - num);
  13.                 else
  14.                     map.put(target - num, --count);
  15.             } else 
  16.                 map.put(num, map.getOrDefault(num, 0) + 1);
  17.         }
  18.         
  19.         return ans;
  20.     }
  21. }

思路2：使用双指针实现，注意要先对数组进行排序处理。

  1. class Solution {
  2.     public List<List<Integer>> pairSums(int[] nums, int target) {
  3.         //对数组进行排序
  4.         Arrays.sort(nums);
  5.         
  6.         List<List<Integer>> ans = new LinkedList<>();
  7.         int left = 0, right = nums.length - 1;
  8.         while (left < right) {
  9.             //两个指针所指的两个元素和
  10.             int sum = nums[left] + nums[right];
  11.             //如果两个的和小于目标值，那么left指针向右走一步继续寻找
  12.             if (sum < target)
  13.                 ++left;
  14.             //如果两个的和大于目标值，那么right指针向左走一步继续寻找
  15.             else if (sum > target)
  16.                 --right;
  17.             //如果刚好等于要找的target值，那么加入结果集中，并且left指针和right指针分别向右和向左走一步(因为一个数只能属于一个数对)
  18.             else 
  19.                 ans.add(Arrays.asList(nums[left++], nums[right--]));
  20.             
  21.         }
  22.         
  23.         return ans;
  24.     }
  25. }

15，三数之和

题目：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

思路：遍历数组每个元素，利用-c=a+b，其中a,b为双指针，根据大小移动。

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {// 总时间复杂度：O(n^2)
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         if (nums == null || nums.length <= 2) return ans;
  5.  
  6.         Arrays.sort(nums); // O(nlogn)
  7.  
  8.         for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
  9.             if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
  10.             if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
  11.             int target = -nums[i];
  12.             int left = i + 1, right = nums.length - 1;
  13.             while (left < right) {
  14.                 if (nums[left] + nums[right] == target) {
  15.                     ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
  16.                     
  17.                     // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = -2, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
  18.                     left++; right--; // 首先无论如何先要进行加减操作
  19.                     while (left < right && nums[left] == nums[left - 1]) left++;
  20.                     while (left < right && nums[right] == nums[right + 1]) right--;
  21.                 } else if (nums[left] + nums[right] < target) {
  22.                     left++;
  23.                 } else {  // nums[left] + nums[right] > target
  24.                     right--;
  25.                 }
  26.             }
  27.         }
  28.         return ans;
  29.     }
  30. }

16，最接近的三数之和

题目：给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。

思路：排序，然后遍历（双指针，减少复杂度）。

  1. class Solution {
  2.     public int threeSumClosest(int[] nums, int target) {
  3.         Arrays.sort(nums);
  4.         int result = Integer.MAX_VALUE;
  5.         int f = 0;
  6.         for (int i = 0; i < nums.length - 2; i++) {
  7.             int left = i + 1;
  8.             int right = nums.length - 1;
  9.             while (left < right) {
  10.                 int temp = nums[i] + nums[left] + nums[right];
  11.                 if (result > Math.abs(target - temp)) {
  12.                     result = Math.abs(target - temp);
  13.                     f = temp;
  14.                 }
  15.                 if (temp > target) {
  16.                     right--;
  17.                 } else if (temp < target) {
  18.                     left++;
  19.                 } else {
  20.                     return target;
  21.                 }
  22.             }
  23.         }
  24.         return f;
  25.     }
  26. }

18，四数之和

题目：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n

  • a、b、c 和 d 互不相同

  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

  1. class Solution {
  2.     public List<List<Integer>> fourSum(int[] nums, int a) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         if (nums == null || nums.length <= 2) return ans;
  5.         Arrays.sort(nums); // O(nlogn)
  6.         long target = a;
  7.         for (int i = 0; i < nums.length - 3; i++) { // O(n^2)
  8.             if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
  9.             for (int j = i + 1; j < nums.length - 2; j++) {
  10.                 if (j > i + 1 && nums[j] == nums[j - 1])
  11.                     continue;
  12.                 long newtarget = target - nums[i] - nums[j];
  13.                 int left = j + 1, right = nums.length - 1;
  14.                 while (left < right) {
  15.                     int cur = nums[left] + nums[right];
  16.                     if (cur == newtarget) {
  17.                         ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
  18.                         while (left < right && nums[left] == nums[left + 1]) left++;
  19.                         while (left < right && nums[right] == nums[right - 1]) right--;
  20.                         left++;
  21.                         right--; // 首先无论如何先要进行加减操作
  22.                     } else if (cur < newtarget) {
  23.                         left++;
  24.                     } else {
  25.                         right--;
  26.                     }
  27.                 }
  28.             }
  29.         }
  30.         return ans;
  31.     }
  32. }

53，最大子数组和

题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

思路1：对于含有正数的序列而言，最大子序列肯定是正数，所以头尾肯定都是正数，我们可以从第一个正数开始算起，每往后加一个数便更新一次和的最大值；当当前和成为负数时,则表明此前序列无法为后面提供最大子序列和，因此必须重新确定序列首项。

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int res = nums[0];
  4.         int sum = 0;
  5.         for (int num : nums) {
  6.             if (sum > 0)
  7.                 sum += num;
  8.             else
  9.                 sum = num;
  10.             res = Math.max(res, sum);
  11.         }
  12.         return res;
  13.     }
  14. }

思路2：动态规划

  1. class Solution {
  2.    public int maxSubArray(int[] nums) {
  3.         int m = nums[0];
  4.         for (int i = 1; i < nums.length; i++) {
  5.             nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
  6.             m = Math.max(m, nums[i]);
  7.         }
  8.         return m;
  9.     }
  10. }

57，和为s的连续正数序列

题目：输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

  1. class Solution {
  2.     public int[][] findContinuousSequence(int target) {
  3.         //思路，双指针
  4.         //刚开始 left 在位置 1， right 在位置 2， 定义左右指针之间的数字和为 sum = n*(a1+an)/2
  5.         //1.类似二分查找的逻辑，当 sum 等于 target 时，将左右指针之间的这种数组加入结果，然后左指针右移
  6.         //2.当 sum 小于 target 时，右指针右移增大 sum
  7.         //3.当 sum 大于 target 时，说明以 left 为起点组成的数组不符要求，左指针右移
  8.  
  9.         //创建结果数组
  10.         List<int[]> list = new ArrayList<>();
  11.  
  12.         int left = 1;
  13.         int right = 2;
  14.         //终止条件是左指针移动到右指针位置，说明此时已经不存在两个数之和能小于 target 了
  15.         while (left < right) {
  16.             int sum = (right - left + 1) * (left + right) / 2;
  17.             if (sum == target) {
  18.                 //创建数组存储左右指针之间的数组组合
  19.                 int[] tmp = new int[right - left + 1];
  20.  
  21.                 for (int i = 0; i < right - left + 1; i++) {
  22.                     tmp[i] = left + i;
  23.                 }
  24.  
  25.                 //将临时数组结果存储入List
  26.                 list.add(tmp);
  27.  
  28.                 //继续探索下一种方案
  29.                 ++left;
  30.             }else if (sum<target){
  31.                 ++right;
  32.             }else {
  33.                 ++left;
  34.             }
  35.         }
  36.         //掌握此种二维list转数组方法
  37.         return list.toArray(new int[list.size()][]);
  38.     }
  39. }

81，交换和

题目：给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。

思路：A-B=diff，A-diff/2=B+diff/2；

  1. class Solution {
  2.    public int[] findSwapValues(int[] array1, int[] array2) {
  3.         int sum1 = 0, sum2 = 0;
  4.         for (int num : array1) {
  5.             sum1 += num;
  6.         }
  7.         for (int num : array2) {
  8.             sum2 += num;
  9.         }
  10.         int diff = sum1 - sum2;
  11.         if (diff % 2 != 0) { // 如果两个数组的总和之差为奇数，则不可能找到符合条件的数值
  12.             return new int[0];
  13.         }
  14.         diff /= 2; // 将差值除以2，这样就可以在第二个数组中找到一个数值，使得交换后两个数组的总和相等
  15.         Set<Integer> set = new HashSet<>();
  16.         for (int num : array2) {
  17.             set.add(num);
  18.         }
  19.         for (int num : array1) {
  20.             if (set.contains(num - diff)) {
  21.                 return new int[]{num, num - diff};
  22.             }
  23.         }
  24.         return new int[0];
  25.     }
  26. }

152，乘积最大子数组

题目：给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。子数组 是数组的连续子序列。

思路：求最大值，可以看成求被0拆分的各个子数组的最大值。当一个数组中没有0存在，则分为两种情况：

  • 负数为偶数个，则整个数组的各个值相乘为最大值；
  • 负数为奇数个，则从左边开始，乘到最后一个负数停止有一个“最大值”，从右边也有一个“最大值”，比较，得出最大值。
  1. class Solution {
  2.     public int maxProduct(int[] nums) {
  3.         int a=1;  
  4.         int max=nums[0];
  5.         
  6.         for(int num:nums){
  7.             a=a*num;
  8.             if(max<a)max=a;
  9.             if(num==0)a=1;
  10.  
  11.         }
  12.         a=1;
  13.         for(int i=nums.length-1;i>=0;i--){
  14.             a=a*nums[i];
  15.             if(max<a)max=a;
  16.             if(nums[i]==0)a=1;
  17.         }  
  18.         return max;
  19.     }
  20. }

167，两数之和II-输入有序数组

题目：给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。

  1. class Solution {
  2.     public int[] twoSum(int[] numbers, int target) {
  3.         int left = 0;
  4.         int right = numbers.length-1;
  5.         while (left < right) {
  6.             int sum = numbers[left] + numbers[right];
  7.             if (sum == target) {
  8.                 return new int[]{left+1, right+1};
  9.             } else if (sum > target) {
  10.                 right--;
  11.             } else {
  12.                 left++;
  13.             }
  14.         }
  15.         return new int[]{left+1, left + 2};
  16.     }
  17. }
  1. class Solution {
  2.     public int[] twoSum(int[] numbers, int target) {
  3.         int middle = target / 2;
  4.         int left = 0;
  5.         int right = 0;
  6.         for (int i = 0; i < numbers.length-1; i++) {
  7.             if (numbers[i]==middle&&numbers[i+1]==middle){
  8.                 return new int[]{i+1 , i + 2};
  9.             }
  10.         }
  11.         for (int i = 0; i < numbers.length; i++) {
  12.             if (numbers[i]<=target / 2.0&&numbers[i+1]>=target / 2.0){
  13.                 left = i;
  14.                 right = i+1;
  15.                 break;
  16.             }
  17.         }
  18.         int sum = numbers[left]+numbers[right];
  19.         while (sum!=target){
  20.             if (sum<target){
  21.                 right++;
  22.             }else {
  23.                 left--;
  24.             }
  25.             sum = numbers[left]+numbers[right];
  26.         }
  27.         int[] newNum  = {left+1,right+1};
  28.         return newNum;
  29.     }
  30. }

209，长度最小的子数组

题目：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

  1. class Solution {
  2.     public int minSubArrayLen(int target, int[] nums) {
  3.         int n = nums.length;
  4.         if (n == 0) {
  5.             return 0;
  6.         }
  7.         int ans = Integer.MAX_VALUE;
  8.         int start = 0, end = 0;
  9.         int sum = 0;
  10.         while (end < n) {
  11.             sum += nums[end];
  12.             while (sum >= target) {
  13.                 ans = Math.min(ans, end - start + 1);
  14.                 sum -= nums[start];
  15.                 start++;
  16.             }
  17.             end++;
  18.         }
  19.         return ans == Integer.MAX_VALUE ? 0 : ans;
  20.     }
  21. }

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

题目：给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。

  1. class Solution {
  2.     public int[] productExceptSelf(int[] nums) {
  3.         int n = nums.length;
  4.         int[] left = new int[n];
  5.         int[] right = new int[n];
  6.         int temp = 1;
  7.         left[0] = 1;
  8.         for (int i = 1; i < n; i++) {
  9.             temp *= nums[i - 1];
  10.             left[i] = temp;
  11.         }
  12.         temp = 1;
  13.         right[n-1] = 1;
  14.         for (int i = n - 2; i >= 0; i--) {
  15.             temp *= nums[i + 1];
  16.             right[i] = temp;
  17.         }
  18.         int result[] = new int[n];
  19.         for (int i = 0; i < n; i++) {
  20.             result[i] = left[i] * right[i];
  21.         }
  22.         return result;
  23.     }
  24. }

239，滑动窗口最大值

题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

思路1：单调队列模板题，求滑动窗口的最值。

  1. class Solution {
  2.     public int[] maxSlidingWindow(int[] nums, int k) {
  3.         if(nums == null || nums.length == 0) {
  4.             return new int[0];
  5.         }
  6.         int[] res = new int[nums.length - k + 1];
  7.         Deque<Integer> queue = new ArrayDeque<>();
  8.         for(int i = 0, j = 0; i < nums.length; i++) {
  9.             if(!queue.isEmpty() && i - queue.peek() >= k) {
  10.                 queue.poll();
  11.             }
  12.             while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
  13.                 queue.pollLast();
  14.             }
  15.             queue.offer(i);
  16.             if(i >= k - 1) {
  17.                 res[j++] = nums[queue.peek()];
  18.             }
  19.         }
  20.  
  21.         return res;
  22.     }
  23. }

思路2：暴力加速

  1. class Solution {
  2.     public int[] maxSlidingWindow(int[] nums, int k) {
  3.         // 加速原理：每次滑动窗口向右移动时，判断
  4.         // a. 新加入的值 是否比上一个窗口最大值大，若是，则直接返回 新加入的值
  5.         // b. 待移除的值 是否比上一个窗口最大值小，若是，则返回 上一窗口最大值
  6.         if(k==0)return new int[0];
  7.         int ans[] = new int[nums.length-k+1];   // 记录每一窗口的最大值
  8.         for(int i=0;i+k-1<nums.length;i++){
  9.             if(i>0 && nums[i+k-1]>ans[i-1])ans[i] = nums[i+k-1];    // 新值比上一窗口最大值大，返回 新值
  10.             else if(i>0 && nums[i-1]<ans[i-1])ans[i] = ans[i-1];    // 旧值比上一窗口最大值小，返回 上一窗口最大值
  11.             else{   // 遍历滑动窗口，找到最大值
  12.                 int max = Integer.MAX_VALUE+1;
  13.                 for(int j=i;j<i+k;j++){
  14.                     max = Math.max(max,nums[j]);
  15.                     ans[i] = max;
  16.                 }
  17.             }
  18.         }
  19.         return ans;
  20.     }
  21. }

494，目标和

题目：给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

  1. class Solution {
  2.     public int findTargetSumWays(int[] nums, int t) {
  3.         int n = nums.length;
  4.         int sum = Arrays.stream(nums).sum();
  5.         if (sum < Math.abs(t)) return 0;
  6.         int[][] dp = new int[n][sum * 2 + 1];
  7.         dp[0][nums[0] + sum] = 1;
  8.         dp[0][sum - nums[0]] += 1;
  9.         for (int i = 1; i < n; i++) {
  10.             int num = nums[i];
  11.             for (int j = -sum; j <= sum; j++) {
  12.                 int res = 0;
  13.                 if (j + sum - num >= 0) res += dp[i - 1][j + sum - num];
  14.                 if (j + sum + num <= 2 * sum) res += dp[i - 1][j + sum + num];
  15.                 dp[i][j + sum] = res;
  16.             }
  17.         }
  18.         return dp[n - 1][t + sum];
  19.     }
  20. }

560，和为K的子数组

题目：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

  1. class Solution {
  2.     public int subarraySum(int[] nums, int k) {
  3.         if (nums == null || nums.length == 0) {
  4.             return 0;
  5.         }
  6.         int N = nums.length;
  7.         int ans = 0;
  8.         for (int i = 0; i < N; i++) {
  9.             int sum = 0;
  10.             for (int j = i; j < N; j++) {
  11.                 sum += nums[j];
  12.                 if (sum == k) {
  13.                     ans++;
  14.                 }
  15.             }
  16.         }
  17.         return ans;
  18.     }
  19. }

633，平方数之和

题目：给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

  1. class Solution {
  2.     public boolean judgeSquareSum(int c) {
  3.         if (c == 1 || c == 2) {
  4.             return true;
  5.         }
  6.         int left = 0;
  7.         int right = (int) Math.sqrt(c);
  8.         while (left <= right) {
  9.             int left2 = left * left;
  10.             int right2 = right * right;
  11.             int left3 = c-right2;
  12.             if (left2 < left3) {
  13.                 left++;
  14.             } else if (left2 > left3) {
  15.                 right--;
  16.             } else {
  17.                 return true;
  18.             }
  19.         }
  20.         return false;
  21.     }
  22. }

713，乘积小于k的子数组

题目：给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

  1. class Solution {
  2.     public int numSubarrayProductLessThanK(int[] nums, int k) {
  3.         // 滑动窗口：寻找以每个 right 指针为右边界的有效连续子树组的个数
  4.         int length = nums.length;
  5.         int product = 1;
  6.         int cnt = 0;
  7.         int left = 0, right = 0;
  8.         while (right < length) {
  9.             product *= nums[right++];
  10.             
  11.             while (left < right && product >= k) {
  12.                 product /= nums[left++];
  13.             }
  14.  
  15.             cnt += (right - left);
  16.         }
  17.  
  18.         return cnt;
  19.     }
  20. }

910，最小差值II

题目：给你一个整数数组 nums，和一个整数 k 。对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。nums 的 分数 是 nums 中最大元素和最小元素的差值。在更改每个下标对应的值之后，返回 nums 的最小 分数 。

  1. class Solution {
  2.     public int smallestRangeII(int[] A, int K) {
  3.         if(A==null||A.length==0){
  4.             return 0;
  5.         }
  6.         Arrays.sort(A);//排序
  7.         int ans=A[A.length-1]-A[0];
  8.         int min,max;
  9.         for(int i=1;i<A.length;i++){//每次划分将A[i]前面的数全部+K,A[i]后面的数全部-K
  10.            min=Math.min(A[0]+K,A[i]-K);//最小值可能是第一个值+K,也可能是划分后右边第一个数-K
  11.            max=Math.max(A[A.length-1]-K,A[i-1]+K);//最大值同理
  12.            ans=Math.min(ans,max-min);
  13.         }
  14.         return ans;
  15.     }
  16. }

977，有序数的平方

题目：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

  1. class Solution {
  2.     public int[] sortedSquares(int[] nums) {
  3.         int left = 0;
  4.         int right = nums.length-1;
  5.         int newNums[] = new int[nums.length];
  6.         int index = right;
  7.         while (left < right) {
  8.             boolean flag = nums[left] * nums[left] >= nums[right] * nums[right];
  9.             if (flag) {
  10.                 newNums[index] = nums[left] * nums[left];
  11.                 left += 1;
  12.             } else {
  13.                 newNums[index] = nums[right] * nums[right];
  14.                 right--;
  15.             }
  16.             index--;
  17.         }
  18.         newNums[index] = nums[left] * nums[left];
  19.         return newNums;
  20.     }
  21. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/464611
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号