LeetCode 数组和矩阵

发布于 2023-08-25 15:23:22 字数 17439 浏览 27 评论 0

剑指 51.构建乘积数组

给定一个数组 A[0,1,...,n-1],请构建一个数组 B[0,1,...,n-1],其中 B 中的元素 B[i]=A[0]A[1]...*A[i-1]A[i+1]...*A[n-1]。不能使用除法。（注意：规定 B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

思路：

假设：

left[i] = A[0]*...*A[i-1]
right[i] = A[i+1]*...*A[n-1]

所以：

B[i] = left[i] * right[i]

可知：

left[i+1] = left[i] * A[i]
right[i] = right[i+1] * A[i+1]

B[0]没有左，B[n-1]没有右。

import java.util.Arrays;
public class Solution {
    public int[] multiply(int[] A) {
        int n = A.length;
        int[] B = new int[n];
        if(n == 0) return B;
        Arrays.fill(B,1);
        for(int i = 1; i < n; i++){
            B[i] = B[i-1]*A[i-1];
        }
        int temp = 1;
        for(int i = n-2; i >= 0; i--){
            temp *= A[i+1];
            B[i] *= temp;
        }
        return B;
    }
}

剑指 13.调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路：

需要一个辅助数组来保存数据。

public class Solution {
    public void reOrderArray(int [] array) {
        int n = array.length;
        int[] aux = new int[n];
        for(int k = 0; k < n; k++){
            aux[k] = array[k];
        }
        int i = 0;
        for(int k = 0; k < n; k++){
            if(aux[k]%2 == 1){
                array[i++] = aux[k];
            }
        }
        for(int k = 0; k < n; k++){
            if(aux[k]%2 == 0){
                array[i++] = aux[k];
            }
        }
    }
}

剑指 19.顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下 4 X 4 矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路：

定义四个边界。注意：退出应该在每次移动后判定。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0) return null;
        int top = 0;
        int down = matrix.length-1;
        int left = 0;
        int right = matrix[0].length-1;
        ArrayList<Integer> result = new ArrayList<>();
        while(true){
            //向右移动
            for(int i = left; i <= right; i++){
                result.add(matrix[top][i]);
            }
            top++;
            if(top>down) break;
            //向下移动
            for(int i = top; i <= down; i++){
                result.add(matrix[i][right]);
            }
            right--;
            if(left>right) break;
            //向左移动
            for(int i = right; i>= left; i--){
                result.add(matrix[down][i]);
            }
            down--;
            if(top>down) break;
            //向上移动
            for(int i = down; i>= top; i--){
                result.add(matrix[i][left]);
            }
            left++;
            if(left>right) break;
        }
        return result;
    }
}

1. 把数组中的 0 移到末尾

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

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

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

思路：

将非 0 数移到前面，然后将后面全变 0.

class Solution {
    public void moveZeroes(int[] nums) {
        int index = 0;
        for(int num : nums){
            if(num != 0){
                nums[index] = num;
                index++;
            }
        }
        for(int i = index; i < nums.length; i++){
            nums[i] = 0;
        }
    }
}

2. 改变矩阵维度

566.在 MATLAB 中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。

给出一个由二维数组表示的矩阵，以及两个正整数 r 和 c，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

输入: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
输出: 
[[1,2,3,4]]
解释:
行遍历 nums 的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。

思路：

遍历。

class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int m = nums.length;//原矩阵的行数
        int n = nums[0].length;//原矩阵的列数
        if(m * n != r * c) return nums;
        int index = 0;
        int[][] result = new int[r][c];
        for(int i = 0; i < r; i++)
            for(int j = 0; j < c; j++){
                result[i][j] = nums[index/n][index%n];
                index++;
            }
        return result;
    }
}

3. 找出数组中最长的连续 1

485.给定一个二进制数组，计算其中最大连续 1 的个数。

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续 1，所以最大连续 1 的个数是 3.

思路：

使用两个变量存储，一个存当前连续个数，一个存最大连续个数。

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0;
        int cur = 0;
        for(int num : nums){
            if(num == 1){
                cur++;
                max = Math.max(max,cur);
            }
            else cur = 0;
        }
        return max;

    }
}

4. 有序矩阵查找

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
给定 target = 5，返回 true。给定 target = 20，返回 false。

思路：

从[0][n-1]的位置开始寻找，若目标值大于该值，则行数加，若目标值小于该值，则列数减。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int row = matrix.length; // 行
        int colmn = matrix[0].length;//列
        int m = 0, n = colmn - 1;
        while(m < row && n >= 0){
            if(target == matrix[m][n]) return true;
            if(target > matrix[m][n]) m++; //行数加
            else n--; //列数减
        }
        return false;
    }
}

5. 有序矩阵的 Kth Element

378.给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。

思路：

二分查找。

通过统计数量来查找。

找使其成立的最左边界。

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int l = matrix[0][0], h = matrix[n-1][n-1];
        while(l < h){
            int mid = l + (h - l)/2;
            int cnt = 0;
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n && matrix[i][j] <= mid; j++){
                    cnt++;
                }
            if(cnt >= k) h = mid;
            else l = mid + 1;
        }
        return l;

    }
}

6. 一个数组元素在 [1, n] 之间，其中一个数被替换为另一个数，找出重复的数和丢失的数

645.集合 S 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

输入: nums = [1,2,2,4]
输出: [2,3]

思路：

排序，先寻找重复的。

缺失的通过比较前后两个值的差值是否大于 1.

有两种特殊情况，缺失第一个和缺失最后一个。

class Solution {
    public int[] findErrorNums(int[] nums) {
        Arrays.sort(nums);
        int dup = -1;
        int miss = 1;//如果缺失的是 1，则该值不会更改
        for(int i = 1; i < nums.length; i++){
			//寻找重复的值
            if(nums[i] == nums[i-1]){
                dup = nums[i];
            }
			//寻找缺失的值
            if(nums[i] - nums[i-1] > 1){
                miss = nums[i] - 1;
            }

        }
        //判断缺失的是否为最后一个
        if(nums[nums.length-1] != nums.length){
            miss = nums.length;
        }
        return new int[]{dup,miss};
    }
}

7. 找出数组中重复的数，数组值在 [1, n] 之间

输入: [1,3,4,2,2]
输出: 2

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

思路：

二分查找，如果小于等于 mid 的数的数量大于 mid 的，则重复的数在[l,mid]里，也可能是 mid。

这里二分查找是通过统计数量来查找的与第 5 题相似。

class Solution {
    public int findDuplicate(int[] nums) {
        int l = 0, h = nums.length - 1;
        while(l < h){
            int m = l+(h-l)/2;
            int cnt = 0;
            for(int i = 0; i < nums.length; i++){
                if(nums[i]<=m) cnt++;
            }
            if(cnt>m) h = m;
            else l = m+1;
        }
        return l;

    }
}

8. 数组相邻差值的个数

667.给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：

① 如果这个数组是 [a1, a2, a3, ... , an] ，那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数；.

② 如果存在多种答案，你只需实现并返回其中任意一种.

输入: n = 3, k = 1
输出: [1, 2, 3]
解释: [1, 2, 3] 包含 3 个范围在 1-3 的不同整数， 并且 [1, 1] 中有且仅有 1 个不同整数 : 1

输入: n = 3, k = 2
输出: [1, 3, 2]
解释: [1, 3, 2] 包含 3 个范围在 1-3 的不同整数， 并且 [2, 1] 中有且仅有 2 个不同整数: 1 和 2

思路：

让前 k+1 个元素构建出 k 个不相同的差值，序列为：1, k+1, 2, k, 3, k-1, ... k/2, k/2+1.

class Solution {
    public int[] constructArray(int n, int k) {
        int[] result = new int[n];
        result[0] = 1;
        for(int i = 1, interval = k; i < k+1; i++, interval--){
            result[i] = i % 2 == 1 ? result[i-1] + interval : result[i-1] - interval;
        }
        for(int i = k+1; i < n; i++){
            result[i] = i+1;
        }
        return result;
    }
}

9. 数组的度

697.给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

输入: [1,2,2,3,1,4,2]
输出: 6

思路：使用三个 Hashmap，一个储存各个数值出现次数，一个储存一个数的最左坐标，一个储存一个数的最右坐标

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> left = new HashMap<>();
        Map<Integer, Integer> right = new HashMap<>();
        Map<Integer, Integer> cnt = new HashMap<>();

        for(int i = 0; i<nums.length; i++){
            int x = nums[i];
            if(left.get(x) == null) left.put(x, i);
            right.put(x, i);
            cnt.put(x, cnt.getOrDefault(x,0)+1);
        }

        int max = 0;
        for(int num : nums){
            max = Math.max(cnt.get(num), max);
        }
        int result = nums.length;
        for(int i = 0; i < nums.length; i++){
            int x = nums[i];
            if(cnt.get(x)!=max) continue;

            int l = left.get(x);
            int r = right.get(x);
            
            result = Math.min(result, r-l+1);
        }
        return result;

    }
}

10. 对角元素相等的矩阵

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。

给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。

输入: 
matrix = [
  [1,2,3,4],
  [5,1,2,3],
  [9,5,1,2]
]
输出: True
解释:
在上述矩阵中, 其对角线为:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。
各条对角线上的所有元素均相同, 因此答案是 True。

思路：

最左列与最上行都是第一个元素，无需验证，只需要验证其他元素是否等于上一个对角元素。

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++){
                if(matrix[i][j] != matrix[i-1][j-1]) return false;
            }
        return true;
    }
}

11. 嵌套数组

565.索引从 0 开始长度为 N 的数组 A，包含 0 到 N - 1 的所有整数。找到最大的集合 S 并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。

假设选择索引为 i 的元素 A[i]为 S 的第一个元素，S 的下一个元素应该是 A[A[i]]，之后是 A[A[A[i]]]... 以此类推，不断添加直到 S 出现重复的元素。

输入: A = [5,4,0,3,1,6,2]
输出: 4
解释: 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

思路：

因为每次生成的链都是循环的，对访问过的元素进行标记，下一次不再访问该元素，以免冗余。

class Solution {
    public int arrayNesting(int[] nums) {
        int max = 0;
        for(int i = 0; i < nums.length; i++){
            int cnt = 0;
            for(int j = i; nums[j] != -1;){
                int t = nums[j];
                nums[j] = -1;//对访问过的数值进行标记
                j = t;
                cnt++;
            }
            max = Math.max(max,cnt);
        }
        return max;
    }
}

12. 分隔数组

769.数组 arr 是[0, 1, ..., arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成 2 块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。

输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。

思路：

记录排序后能在原位置或者本身就在原位置元素的数量。

class Solution {
    public int maxChunksToSorted(int[] arr) {
        if(arr == null) return 0;
        int result = 0;
        int right = arr[0];
        for(int i = 0; i < arr.length; i++){
            right = Math.max(right, arr[i]);//排序后能在原位置或者本身就在原位置
            if(right == i) result++;
        }
        return result;
    }
}

13.两个正序数组的中位数

4.给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

思路：

数组划分。

将两个数组划分成两部分，前者最大值小于后者最小值，且长度相等。

即可找到中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m, ansi = -1;
        // median1：前一部分的最大值
        // median2：后一部分的最小值
        int median1 = 0, median2 = 0;

        while (left <= right) {
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;

            // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);

            if (nums_im1 <= nums_j) {
                ansi = i;
                median1 = Math.max(nums_im1, nums_jm1);
                median2 = Math.min(nums_i, nums_j);
                left = i + 1;
            }
            else {
                right = i - 1;
            }
        }

        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
}

14.旋转数组

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

思路：

原地翻转。

class Solution {
    public void rotate(int[] nums, int k) {
        int start = 0, end = nums.length - 1;
        k = k%nums.length;
        reverse(nums, start, end);
        reverse(nums, start, k - 1);
        reverse(nums, k, end);
    }
    private void reverse(int[] nums, int start, int end){
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

15.旋转图像

48.给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

思路：

与顺时针打印图像相似。

从外到内每层旋转。

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        if(n == 0) return;
        int left = 0, top = 0, right = n-1, down = n-1;
        while(left < right && top < down){
            rotate2(matrix, left, right, top, down);
            left++;
            right--;
            top++;
            down--;
        }
    }
    private void rotate2(int[][] matrix, int left, int right, int top, int down)    {
        for(int i = 0; i < right-left; i++){
            int temp = matrix[top][left+i];
            matrix[top][left+i] = matrix[down-i][left];
            matrix[down-i][left] = matrix[down][right-i];
            matrix[down][right-i] = matrix[top+i][right];
            matrix[top+i][right] = temp;
        }
    }
}

16.缺失的第一个正数

41.给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

输入: [3,4,-1,1]
输出: 2

输入: [7,8,9,11,12]
输出: 1

你的算法的时间复杂度应为 O(n)，并且只能使用常数级别的额外空间。

思路：

原地交换，将值对应数组相应底标。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

分享到QQ

分享到微博