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

解答：

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;
    }
}

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