LeetCode-数组与矩阵专题

1.移动零

  1. move-zeroes(easy)
    LeetCode

思路:
1、建立两个指针,前置指针负责判断当前的值是否是0,如果为0,对下一位进行判断;如果不为零,则把当前的值放到cur指针指向的位置,cur++

//2020年11月9日
class Solution {
    public void moveZeroes(int[] nums) {
        int pre = 0;
        int cur = 0;
        while(pre != nums.length){
            if(nums[pre] == 0){
                pre++;
            }else{
                nums[cur++] = nums[pre++];
            }
        }
        while(cur != nums.length){
            nums[cur++] = 0;
        }
    }
}

2、一次遍历,利用快排的思想

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

    }
}

2.重塑矩阵

  1. reshape-the-matrix(easy)
    LeetCode

思路:
1、对给出的二维数组进行遍历,将遍历到的元素放到队列中,再遍历生成的数组,将队列中的元素放进去

class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int[][] matrix = new int[r][c];
        if(nums == null || r * c != nums.length * nums[0].length){
            return nums;
        }
        int count = 0;
        Queue <Integer> queue = new LinkedList < > ();
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<nums[0].length;j++){
                queue.add(nums[i][j]);
            }
        }
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                matrix[i][j] = queue.remove();
            }
        }
        return matrix;
    }
}

2、

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[][] reshapedNums = new int[r][c];
        int index = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                reshapedNums[i][j] = nums[index / n][index % n];
                index++;
            }
        }
        return reshapedNums;
    }
}

3.最大连续1的个数

  1. max-consecutive-ones(easy)
    LeetCode

思路:
1、设置一个pre保存当前1的个数,每往下走一步就把当前的pre和要返回的count进行比较,取最大值

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int pre = 0;
        int count = 0;
        for(int i=0;i<nums.length;i++){
            pre = nums[i] == 0 ? 0 : pre+1;
            count = Math.max(count,pre);
        }
        return count;
    }
}

4.搜索二维矩阵 II

  1. search-a-2d-matrix-ii(Medium)
    LeetCode

思路:
1、因为矩阵的特性,我们可以从右上角开始走,当当前值比target大时就往左走,比target小时就往下走

    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length <= 0 || matrix[0].length <=0) return false;
        int curX = 0;
        int curY = matrix[0].length - 1;
        while(curX >=0 && curX < matrix.length && curY >= 0 && curY < matrix[0].length){
            if(matrix[curX][curY] < target){
                curX++;
            }else if(matrix[curX][curY] > target){
                curY--;
            }else{
                return true;
            }
        }
        return false;
    }

2、遍历

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j] == target) return true;
            }
        }
        return false;
    }
}

5.有序矩阵中第K小的元素

  1. kthSmallest(Medium)
    LeetCode

思路:
1、二分查找
二维数组本质上是一个一维数组,可以用二分查找来解决问题
设二维数组的左上角节点为left,右下角节点为right,
用两者的值求中间值,去check函数中进行判断当前数组比mid小的值是否比k多,
如果比k多,说明右边界需要移动到mid;如果小于等于k的话,就移动左边界
直到left等于right等于mid,返回left

//2020年11月11日
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int len = matrix.length;
        int left = matrix[0][0];
        int right = matrix[len-1][len-1];
        while(left<right){
            int mid = (left + right) / 2;
            if(check(matrix,mid,k,len)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean check(int[][] arr,int mid,int k,int len){
        int num = 0;
        int i = len -1;
        int j = 0;
        while(i >= 0 && j < len){
            if(arr[i][j] <= mid){
                num += i+1;
                j++;
            }else{
                i--;
            }
        }
        return num >= k;
    }
}

6.错误的集合

  1. set-mismatch(easy)
    LeetCode

思路:
1、本来想用HashMap的,但是一想如果数值在N以内的话好像数组更方便

//2020年11月12日
    public int[] findErrorNums(int[] nums) {
        int[] res = new int[2];
        int len = nums.length;
        if(nums.length < 1) return res;
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            if(arr[nums[i]-1] >= 1){
                arr[nums[i]-1]++;
            }else{
                arr[nums[i]-1]=1;
            }
        }
        for(int i=0;i<len;i++){
            if(arr[i] > 1){
                res[0] = i+1;
            }else if(arr[i] == 0){
                res[1] = i+1;
            }
        }
        return res;
    }

7. 寻找重复数

  1. find-the-duplicate-number(Medium)
    LeetCode
  • 不能更改原数组(假设数组是只读的)。
  • 只能使用额外的 O(1) 的空间。
  • 时间复杂度小于 O(n2) 。
  • 数组中只有一个重复的数字,但它可能不止重复出现一次。

思路:
1、这题要是没有这限制条件的话,我TM直接双重循环/两次循环+数组就解出来了,但是它要求使用额外的 O(1) 的空间,且时间复杂度小于 O(n2),突然感觉被针对了。
这题其实有个很关键的条件,其数字都在 1 到 n 之间(包括 1 和 n),这样我们就可以用二分查找的变式来解决这个问题。
数组的下标作为左右边界,求mid,遍历整个数组找到小于等于mid的数,
如果得到的count与mid相等,则重复的数不在左边界到mid之间,移动左边界
如果得到的count>mid,则重复的数不在右边界到mid之间,移动右边界
一直移动移动,当left == right时,最后就不动了,得到的left就是我们要的值

//2020年11月13日
   public int findDuplicate(int[] nums) {
        int left = 1;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            int count = 0;
            for(int i=0;i<nums.length;i++){
                if(nums[i] <= mid){
                    count++;
                }
            }
            if(count > mid){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

8. 数组的度

  1. Degree of an Array (Easy)
    LeetCode

思路:
一开始我是想设置一个求数组的degree的函数,然后双重循环求出每一个数组的度,得到与其相等的那个最小的长度
但是结果就是超时了,可能这个解法实在是太笨了吧
看了别人的解析,主要的思路如下:
设置三个HashMap,left用来存当前数字第一次出现的位置,right存当前数组最后一次出现的位置,count用来存数字的个数(度)
然后求出整个数组的度,再次遍历这个数组,如果当前的数字个数与整个数组的度不一样,直接跳出进行下一次循环,
如果相等,则用right-left+1与len进行比较,取最小

//2020年11月15日
   public int findShortestSubArray(int[] nums) {
        HashMap<Integer,Integer> left = new HashMap();
        HashMap<Integer,Integer> right = new HashMap();
        HashMap<Integer,Integer> count = new HashMap();
        for(int i=0;i<nums.length;i++){
            int num = nums[i];
            count.put(num,count.getOrDefault(num,0)+1);
            right.put(num,i);
            if(!left.containsKey(num)){
                left.put(num,i);
            }
        }
        int degree = 0;
        for(int i=0;i<nums.length;i++){
            degree = Math.max(degree,count.get(nums[i]));
        }

        int len = nums.length;
        for(int i=0;i<nums.length;i++){
            if(count.get(nums[i]) != degree) continue;
            len = Math.min(len,right.get(nums[i])-left.get(nums[i])+1);
        }
        return len;
    }

9. 托普利茨矩阵

  1. toeplitz-matrix (Easy)
    LeetCode

思路:
双重循环,每遍历到一个数,去检查当前元素与其左上角元素是否一致,如果不一致,就不托普利茨矩阵,否则就是

//2020年11月17日
public boolean isToeplitzMatrix(int[][] matrix) {
        for (int r = 0; r < matrix.length; ++r)
            for (int c = 0; c < matrix[0].length; ++c)
                if (r > 0 && c > 0 && matrix[r-1][c-1] != matrix[r][c])
                    return false;
        return true;
    }

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 16:38
江苏大学_2023
点赞 评论 收藏
转发
1 收藏 评论
分享

全站热榜

正在热议