Skip to main content

数组

704.二分查找​

力扣题目链接

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

解答：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        if(target == nums[right])
            return right;
        while(left < right){
            int i = (left+right)/2;
            if(nums[i] > target){
                right = i;
            } else if(nums[i] < target){
                left = i+1;
            } else{
                return i;
            }
        }
        return -1;
    }
}

35.搜索插入位置​

力扣题目链接

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

  • 输入: [1,3,5,6], 5
  • 输出: 2

示例 2:

  • 输入: [1,3,5,6], 2
  • 输出: 1

示例 3:

  • 输入: [1,3,5,6], 7
  • 输出: 4

示例 4:

  • 输入: [1,3,5,6], 0
  • 输出: 0

解答：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int i = (left+right)/2;
            if(nums[i] > target){
                right = i-1;
            } else if(nums[i] < target){
                left = i+1;
            } else {
                return i;
            }
        }
        return left;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置​

力扣链接

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：你可以设计并实现时间复杂度为 O(log⁡n)O(\log n) 的算法解决此问题吗？

示例 1：

  • 输入：nums = [5,7,7,8,8,10], target = 8
  • 输出：[3,4]

示例 2：

  • 输入：nums = [5,7,7,8,8,10], target = 6
  • 输出：[-1,-1]

示例 3：

  • 输入：nums = [], target = 0
  • 输出：[-1,-1]

解答：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left1 = 0;
        int left2 = 0;
        int right1 = nums.length;
        int right2 = nums.length;
        int[] index = new int[2];
        while(left1 < right1){
            int i = (left1+right1)/2;
            if(nums[i] > target){
                right1 = i;
            } else if(nums[i] < target){
                left1 = i+1;
            } else {
                if(left1 == i || nums[i-1] != nums[i]){
                    left1 = i;
                    right1 = i+1;
                    break;
                } else{
                    right1 = i-1;
                }
            }
        }
        while(left2 < right2){
            int i = (left2+right2)/2;
            if(nums[i] > target){
                right2 = i;
            } else if(nums[i] < target){
                left2 = i+1;
            } else {
                if(right2 == i+1 || nums[i+1] != nums[i]){
                    right2 = i;
                    left2 = i-1;
                    
                    break;
                } else{
                    left2 = i+1;
                }
            }
        }
        index[0] = left1;
        index[1] = right2;
        if(left1 >= right2 && (right1-left1)!=1 && (right2-left2)!=1){
            index[0] = -1;
            index[1] = -1;
        }
        return index;
    }
}

69.x 的平方根​

题目链接

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

  • 0 <= x <= 231 - 1

解答：

class Solution {
    public int mySqrt(int x) {
        if(x <= 1)
            return x;
        int temp =2;
        while(x/temp >= temp){
            temp = temp*2;
        }
        int left = temp/2;
        int right =temp;
        while(left < right){
            int i = (left+right)/2;
            if(i > x/i){
                right = i;
            } else if(i < x/i){
                left = i+1;
            } else {
                return i;
            }
        }
        return left-1;
    }
}

367.有效的完全平方数​

题目链接

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

  • 1 <= num <= 231 - 1

解答：

class Solution {
    public boolean isPerfectSquare(int num) {
        if(num == 1)
            return true;
        int temp =2;
        while(num/temp >= temp){
            temp = temp*2;
        }
        int left = temp/2;
        int right =temp;
        while(left < right){
            int i = (left+right)/2;
            if((long)i*i > num){
                right = i;
            } else if((long)i*i < num){
                left = i+1;
            } else {
                return true;
            }
        }
        return false;
    }
}

27. 移除元素​

力扣题目链接

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

解答：

class Solution {
    public int removeElement(int[] nums, int val) {
        int j = 0;
        for(int i = 0;i < nums.length; i++){
            if(nums[i] != val){
                nums[j] = nums[i];
                j++; 
            }

        }

        return j;
    }
}

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

题目链接

给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k .

解答：

class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 0;
        for(int fast = 1;fast < nums.length;fast++){
            if(nums[slow] != nums[fast]){
                nums[slow+1] = nums[fast];
                slow++; 
            }
        }
        return slow+1;
    }
}

283. 移动零​

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

解答：

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for(int fast = 0;fast < nums.length;fast++){
            int temp;
            if(nums[fast] != 0){
                temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
        }
    }
}

844. 比较含退格的字符串​

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

**注意：**如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

  • 1 <= s.length, t.length <= 200
  • s 和 t 只含有小写字母以及字符 '#'

进阶：

  • 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

解答：

class Solution {
    public boolean backspaceCompare(String s, String t) {
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        return helper(ss).equals(helper(tt));
    }
    private String helper(char[] c){
        int fast=0,slow=0;
        while(fast < c.length){
            if(c[fast] != '#'){
                c[slow++] = c[fast++];
            } else{
                if(slow > 0){
                    slow--;
                }
                fast++;
            }
        }
        return new String(c).substring(0,slow);
    }
}

977. 有序数组的平方​

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

解答：

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        int left = 0;
        int right = nums.length-1;
        int cnt = right;
        while(left <= right){
            if(nums[left]*nums[left] > nums[right]*nums[right] ){
                res[cnt--] = nums[left]*nums[left];
                left++;
            } else{
                res[cnt--] = nums[right]*nums[right];
                right--;
            }
            
        }
        return res;
    }
    private void QuickeSort(int[] nums,int low,int high){
        if(low >= high)
            return;
        int left = low;
        int right = high;
        int a = nums[left];
        int tempnum;
        while(left < right){
            while(nums[right] >= a && left < right){
                right--;
            }
            while(nums[left] <= a && left < right){
                left++;
            }
            if(left < right){
                tempnum = nums[right];
                nums[right] = nums[left];
                nums[left] = tempnum;
            }
        }
        nums[low] = nums[left];
        nums[left] = a;
        QuickeSort(nums,left+1,high);
        QuickeSort(nums,low,left-1);
    }
}

977.有序数组的平方​

力扣题目链接

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

示例 1：

  • 输入：nums = [-4,-1,0,3,10]
  • 输出：[0,1,9,16,100]
  • 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2：

  • 输入：nums = [-7,-3,2,3,11]
  • 输出：[4,9,9,49,121]

解答：

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        int left = 0;
        int right = nums.length-1;
        int cnt = right;
        while(left <= right){
            if(nums[left]*nums[left] > nums[right]*nums[right] ){
                res[cnt--] = nums[left]*nums[left];
                left++;
            } else{
                res[cnt--] = nums[right]*nums[right];
                right--;
            }
            
        }
        return res;
    }
    private void QuickeSort(int[] nums,int low,int high){
        if(low >= high)
            return;
        int left = low;
        int right = high;
        int a = nums[left];
        int tempnum;
        while(left < right){
            while(nums[right] >= a && left < right){
                right--;
            }
            while(nums[left] <= a && left < right){
                left++;
            }
            if(left < right){
                tempnum = nums[right];
                nums[right] = nums[left];
                nums[left] = tempnum;
            }
        }
        nums[low] = nums[left];
        nums[left] = a;
        QuickeSort(nums,left+1,high);
        QuickeSort(nums,low,left-1);
    }
}

209.长度最小的子数组​

力扣题目链接

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

  • 输入：s = 7, nums = [2,3,1,2,4,3]
  • 输出：2
  • 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

解答：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int left = 0;
        int right = 0;
        int minnum = nums.length + 1;
        for(; right < nums.length;right++){
            sum += nums[right];
            while(sum >= target){
                minnum = minnum < (right - left + 1) ? minnum : (right - left + 1);
                sum -= nums[left++];
            }
        }
        return minnum <= nums.length ? minnum : 0;
    }
}

904. 水果成篮​

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

  • 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
  • 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

  • 1 <= fruits.length <= 105
  • 0 <= fruits[i] < fruits.length

解答：

class Solution {
    public int totalFruit(int[] fruits) {
        if(fruits.length < 3)
            return fruits.length;
        int slow = 0,fast = 1;
        int cnt = 0;
        int[] temp = new int[]{fruits[slow],fruits[fast]};
        for(;fast < fruits.length;fast++){
            for(;fast < fruits.length && fruits[fast] != temp[0] && fruits[fast] != temp[1];){
                cnt = cnt > fast - slow ? cnt : fast - slow;
                slow = fast-1;
                temp[0] = fruits[slow];
                temp[1] = fruits[fast];
                
                while(slow != 0 && fruits[slow-1] == fruits[slow]){
                    slow--;
                }
            }
            if(fast == fruits.length-1)
                cnt = cnt > fast - slow + 1 ? cnt : fast - slow + 1;
        }
        return cnt;
    }
}

76. 最小覆盖子串​

提示

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

解答：

class Solution {
    public String minWindow(String s, String t) {
        char[] ss =s.toCharArray();
        int left = 0, right = 0;
        int sum = 0;
        int less = 0;
        int[] str1 = new int[128];
        int[] str2 = new int[128];
        String temp = s + "1";
        for(char c : t.toCharArray()){
            if(str1[c]++ == 0)
                less++;
        }
        for(;right < s.length();right++){
            char c = ss[right];
            if(++str2[c] == str1[c]){
                less--;
            }
            while(less <= 0){
                temp = temp.length() < right - left + 1 ? temp : s.substring(left,right+1);
                char x = ss[left++];
                if(str1[x] == str2[x]--){
                    less++;
                }
            }
        }

        return temp.length() == s.length() + 1 ? "" : temp;
    }
    private boolean arraycontains(int[] a,int[] b){
        for(int i=0;i < a.length;i++){
            if(a[i]-b[i] > 0)
                return false;
        }
        return true;
    }
}

59.螺旋矩阵II​

力扣题目链接

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

解答：

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums =  new int[n][n];
        int i = 0,j = 0;
        int loop = 0;
        int cnt = 1;
        while(loop < n/2){
            for(;j < n-loop-1;j++){
                nums[i][j] = cnt++;
            }
            for(;i < n-loop-1;i++){
                nums[i][j] = cnt++;
            }
            for(;j > loop;j--){
                nums[i][j] = cnt++;
            }

            for(;i > loop;i--){
                nums[i][j] = cnt++;
            }
            i++;
            j++;

            loop++;
        }
        if(n % 2 ==1){
            nums[n/2][n/2] = cnt;
        }
        return nums;
    }
}

54. 螺旋矩阵和LCR 146. 螺旋遍历二维数组​

提示

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

示例 1：

img

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

img

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

解答：

// t
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        int i = 0,j = 0;
        int m = matrix.length,n = matrix[0].length;
        int loop = 0;
        int cnt = 0;
        while(loop < n/2 && loop < m/2){
            for(;j < n - loop -1;j++){
                res.add(matrix[i][j]);
            }

            for(;i < m -loop -1;i++){
                res.add(matrix[i][j]);
            }

            for(;j > loop;j--){
                res.add(matrix[i][j]);
            }

            for(;i > loop;i--){
                res.add(matrix[i][j]);
            }
            i++;
            j++;
            loop++;

        }
        if(n >= m){
            while(j < n - loop && i < m - loop)
                res.add(matrix[i][j++]);
        } else{
            while(j < n - loop && i < m - loop)
                res.add(matrix[i++][j]);
        }
        return res;
    }
}

// 更改边界
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0) return new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        int left = 0, right = matrix[0].length-1, up = 0, down = matrix.length-1;
        while(left <= right && up <= down){
            for(int i = left; i <= right; i++){
                res.add(matrix[up][i]);
            }
            up++;
            if(!(left <= right && up <= down)) break;

            for(int i = up; i <= down; i++){
                res.add(matrix[i][right]);
            }

            right--;
            if(!(left <= right && up <= down)) break;

            for(int i = right; i >= left; i--){
                res.add(matrix[down][i]);
            }

            down--;
            if(!(left <= right && up <= down)) break;

            for(int i = down; i >= up; i--){
                res.add(matrix[i][left]);
            }
            left++;

            
        }

        return res;

    }
}

58. 区间和​

题目链接

题目描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述

输出每个指定区间内元素的总和。

输入示例

5
1
2
3
4
5
0 1
1 3

输出示例

3
9

数据范围：

0 < n <= 100000

解答：

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int n = scanner.nextInt();
        int[] vce = new int[n];
        int[] p = new int[n];
         
        int presum = 0;
        for(int i = 0;i < n; i++){
            vce[i] = scanner.nextInt();
            presum += vce[i];
            p[i] =presum;
        }
         
        while(scanner.hasNextInt()){
            int i = scanner.nextInt();
            int j = scanner.nextInt();
             
            int sum = i == 0 ? p[j] : p[j] - p[i-1];
            System.out.println(sum);
        }
        scanner.close();
    }
}

44. 开发商购买土地​

题目链接

【题目描述】

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。

现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。

然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。

为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。

注意：区块不可再分。

【输入描述】

第一行输入两个正整数，代表 n 和 m。

接下来的 n 行，每行输出 m 个正整数。

输出描述

请输出一个整数，代表两个子区域内土地总价值之间的最小差距。

输入示例

3 3
1 2 3
2 1 3
1 2 3

输出示例

0

【提示信息】

如果将区域按照如下方式划分：

1 2 | 3 2 1 | 3 1 2 | 3

两个子区域内土地总价值之间的最小差距可以达到 0。

【数据范围】：

  • 1 <= n, m <= 100；
  • n 和 m 不同时为 1。

解答：

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] arr = new int[n+1][m+1];
        for(int i = 1;i < n+1;i++){
            for(int j = 1;j < m+1;j++){
                arr[i][j] = arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1] + in.nextInt();
            }
        }
        int error = Math.abs(arr[n][m] - 2 * arr[1][m]);
        int temp = 0;
        for(int i = 2;i < n+1; i++){
            temp = Math.abs(arr[n][m] - 2 * arr[i][m]);
            if(error > temp){
                error = temp;
            }else{
                break;
            }
        }
        if(error == 0){
            System.out.println(error);
            return;
        }
        int error1 = Math.abs(arr[n][m] - 2 * arr[n][1]);
        for(int i = 2;i < m+1; i++){
            temp = Math.abs(arr[n][m] - 2 * arr[n][i]);
            if(error1 > temp){
                error1 = temp;
            }else{
                break;
            }
        }
        System.out.println(error < error1 ? error : error1);
        return;
        in.close();
    }
}

代码随想录汇总​

img

其他​

1365.有多少小于当前数字的数字​

力扣题目链接

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

解答：

//暴力
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for(int j = 0; j < nums.length; j++){
                if(nums[j] < nums[i]){
                    count++;
                }
            }
            res[i] = count;
        }
        return res;
    }
}

// map
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] res = Arrays.copyOf(nums, nums.length);
        Arrays.sort(res);
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < res.length; i++){
            if(!map.containsKey(res[i])){
                map.put(res[i], i);
            }
        }

        for(int i = 0; i < nums.length; i++){
            res[i] = map.get(nums[i]);
        }
        
        return res;
    }
}

// 计数排序
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] res = Arrays.copyOf(nums, nums.length);
        int[] fre = new int[101];
        for(int i = 0; i < nums.length; i++){
            fre[nums[i]]++;
        }

        for(int i = 1; i < fre.length; i++){
            fre[i] += fre[i-1];
        }

        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0) res[i] = fre[nums[i]-1]; // 注意nums[i] == 0的情况
        }

        return res;
    }
}

941.有效的山脉数组​

力扣题目链接

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

  • arr.length >= 3
  • 在 0 < i < arr.length - 1 条件下，存在 i 使得：
    • arr[0] < arr[1] < ... arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

2021072910360

解答：

// 数组
class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) return false;
        int i = 0;
        for(i = 1; i < arr.length; i++){
            if(arr[i] == arr[i-1]) return false;

            if(arr[i] < arr[i-1]) break;
        }

        i--;
        if(i == 0 || i == arr.length-1) return false;
        
        for(; i < arr.length-1; i++){
            if(arr[i] == arr[i+1] || arr[i] < arr[i+1]) return false;
        }

        return i == arr.length-1;
    }
}

//双指针
class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) return false;
        int left = 0, right = arr.length - 1;

        while(left < right && arr[left] < arr[left+1]) left++;
        while(right > left && arr[right] < arr[right-1]) right--;

        return left == right && left != 0 && left!= arr.length - 1;
    }
}

1207.独一无二的出现次数​

力扣题目链接

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

解答：

// 1.
class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        int[] fre = new int[2001];
        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < arr.length; i++){
            fre[arr[i]+1000]++;
        }

        for(int i = 0; i < fre.length; i++){
            if(fre[i] > 0){
                if(map.containsKey(fre[i])) return false;
                map.put(fre[i], 1);
            }
        }

        return true;
    }
}

// 2.
class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();

        for(int i : arr){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        return map.size() == new HashSet<>(map.values()).size();
    }
}

283. 移动零：动态规划：一样的套路，再求一次完全平方数​

力扣题目链接

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

解答：

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums == null || nums.length <= 1) return;

        int slow = 0, fast = 0;
        for(; fast < nums.length; fast++){
            if(nums[fast] != 0) nums[slow++] = nums[fast];
        }
        for(; slow < nums.length; slow++) nums[slow] = 0;
    }
}

189. 旋转数组​

力扣题目链接

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

解答：

// 1.
class Solution {
    public void rotate(int[] nums, int k) {
        if(nums == null || nums.length <= 1) return;
        k = k % nums.length;
        if(k == 0) return;
        

        int[] temp = new int[k];
        for (int i = nums.length - 1; i >= 0; i--){
            if(i > nums.length - k - 1){
                temp[i - nums.length + k] = nums[i];
            }
            else{
                nums[i + k] = nums[i];
            }
        }

        for(int i = 0; i < k; i++){
            nums[i] = temp[i];
        }
    }
}

// 2.
class Solution {
    private static void reverse(int[] nums, int start, int end){
        for(int i = start, j = end; i < j; i++, j--){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    
    public void rotate(int[] nums, int k) {
        if(nums == null || nums.length <= 1) return;
        k = k % nums.length;
        if(k == 0) return;
        

        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
}

724.寻找数组的中心下标​

力扣题目链接

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

解答：

class Solution {
    public int pivotIndex(int[] nums) {
        if(nums.length == 0 || nums == null) return -1;
        int rightSum = Arrays.stream(nums).sum();

        int leftSum = 0;
        for(int i = 0; i < nums.length; i++){
            if(i > 0) leftSum += nums[i-1];
            rightSum -= nums[i];
            if(leftSum == rightSum){
                return i;
            }
        }

        return -1;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置​

力扣链接

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：你可以设计并实现时间复杂度为 O(log⁡n)O(\log n) 的算法解决此问题吗？

解答：

// O(n)
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0 || nums == null) return new int[]{-1, -1};

        int left = 0, right = nums.length - 1;
        while(left <= right && nums[left] != nums[right]){
            if(nums[left] < target) left++;
            if(nums[right] > target) right--;
        }

        if(nums[left] == target && nums[right] == target) return new int[]{left, right};
        else return new int[]{-1, -1};
    }
}

// O(log n) e

301. 删除无效的括号​

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

// DFS 暴力
class Solution {
    public int max, len;
    public Set<String> set = new HashSet<>();
    public String ss;

    public List<String> removeInvalidParentheses(String s) {
        ss = s;
        int l = 0, r = 0;
        for(char i : s.toCharArray()){
            if(i == '(') l++;
            else if(i == ')') r++;
        }

        max = Math.min(l, r);

        dfs("", 0, 0);
        return new ArrayList<>(set);

    }

    public void dfs(String cur, int index, int score){
        if(index > ss.length() || score < 0 || score > max) return;

        if(index == ss.length()){
            if(score == 0){
                if(cur.length() > len){
                    set.clear();
                    set.add(cur);
                    len = cur.length();
                }
                else if(cur.length() == len){
                    set.add(cur);
                }
            }
            return;
        }

        if(ss.charAt(index) == '('){
            dfs(cur + "(", index + 1, score + 1);
            dfs(cur, index + 1, score);
        }
        else if(ss.charAt(index) == ')'){
            dfs(cur + ")", index + 1, score - 1);
            dfs(cur, index + 1, score);
        }
        else{
            dfs(cur + ss.charAt(index), index + 1, score);
        }

    }
}


// 剪枝
class Solution {
    public int max, len;
    public Set<String> set = new HashSet<>();
    public String ss;

    public List<String> removeInvalidParentheses(String s) {
        ss = s;

        int l = 0, r = 0; // l: 多余左括号的数量，r: 多余右括号的数量
        for(char i : s.toCharArray()){
            if(i == '(') l++;
            else if(i == ')'){
                if(l > 0) l--;
                else r++;
            }
        }
        len = s.length() - l - r;

        int cur_l = 0, cur_r = 0;
        for(char i : s.toCharArray()){
            if(i == '(') cur_l++;
            else if(i == ')') cur_r++;
        }
        max = Math.min(cur_l - l, cur_r - r);

        dfs("", 0, 0, l, r);
        return new ArrayList<>(set);

    }

    public void dfs(String cur, int index, int score, int l, int r){ 
        if(score < 0 || score > max || l < 0 || r < 0) return;

        if(index == ss.length()){
            if(score == 0 && cur.length() == len) set.add(cur);
            return;
        }

        if(ss.charAt(index) == '('){
            dfs(cur + "(", index + 1, score + 1, l, r);
            dfs(cur, index + 1, score, l - 1, r);
        }
        else if(ss.charAt(index) == ')'){
            dfs(cur + ")", index + 1, score - 1, l, r);
            dfs(cur, index + 1, score, l, r - 1);
        }
        else{
            dfs(cur + ss.charAt(index), index + 1, score, l, r);
        }

    }
}

528.按权重随机选择​

给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

解答：

// e
import java.util.Arrays;

class Solution {
    int[] w;
    int[] sum;

    public Solution(int[] w) {
        this.w = w;
        sum = new int[w.length];
        if(w != null){
            for(int i = 0; i < w.length; i++){
                sum[i] = (i == 0 ? 0 : sum[i-1]) + w[i];
            }
        }
    }

    public int pickIndex() {
        int target = (int)(Math.random() * sum[sum.length-1]);
        int left = 0, right = sum.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(target < sum[mid]) right = mid;
            else if(target > sum[mid]) left = mid + 1;
            else return mid + 1;
        }
        return left;
    }
}

922. 按奇偶排序数组 II​

给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案 。

解答：

// 太慢了
import java.util.*;

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++){
            if((nums[i] & 1) != (i & 1)){
                if((i & 1) == 0) deque.addFirst(i);
                else deque.addLast(i);
            }
        }
        while(!deque.isEmpty()){
            int i = deque.pollFirst();
            int j = deque.pollLast();
            swap(nums, i, j);
        }
        return nums;
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
// s
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int odd = 1, even = 0;
        for(;odd < nums.length && even < nums.length;){
            if(((nums[odd] & 1) != (odd & 1)) && ((nums[even] & 1) != (even & 1))){
                swap(nums, odd, even);
                odd += 2;
                even += 2;
            }
            else if((nums[odd] & 1) != (odd & 1)){
                even += 2;
            }
            else if((nums[even] & 1) != (even & 1)){
                odd += 2;
            }
            else{
                odd += 2;
                even += 2;
            }
        }
        return nums;
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

52. N皇后II​

题目链接：https://leetcode.cn/problems/n-queens-ii/

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

解答：

class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        backtracking(new int[n][n], 0, n);
        return count;
    }


    public void backtracking(int[][] queens, int row, int n){
        if(queens.length == 0) return;

        if(row == queens.length){
            count++;
            return;
        }

        for(int j = 0; j < queens.length; j++){
            if(isValid(queens, row, j, n)){
                queens[row][j] = 1;
                backtracking(queens, row + 1, n);
                queens[row][j] = 0;
            }
        }

    }

    public boolean isValid(int[][] queens, int row, int col, int n){
        if(queens.length == 0) return false;

        for(int i = 0; i < n; i++){ //做一次剪枝
            if(queens[i][col] == 1) return false;
        }

        int min = Math.min(row, col);
        for(int i = 0; i < n; i++){
            if((row - min + i) >= n) break;
            if((col - min + i) >= n) break;

            if(queens[row - min + i][col - min + i] == 1) return false;
        }

        min = Math.min(row, n - 1 - col);
        for(int i = 0; i < n; i++){
            if((row - min + i) >= n) break;
            if((col + min - i) < 0) break;

            if(queens[row - min + i][col + min - i] == 1) return false;
        }

        return true;
    }
}