hi,你好!欢迎访问本站!登录
本站由简数采集腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

LeetCode刷题总结-数组篇(中)

2019-11-18杂谈搜奇网38°c
A+ A-

    本文接着上一篇文章《LeetCode刷题总结-数组篇(上)》,继承讲第二个常考问题:矩阵问题

    矩阵也能够称为二维数组。在LeetCode相干习题中,作者总结的考点有:矩阵元素的遍历、矩阵位置的扭转、矩阵行或列序次的交流、空间复杂度为O(1)等。本期共12道题,2道简朴题,8道中等题,2道困难题。

  • 例1是杨辉三角的一个延申题,是一道异常典范的矩阵习题,本题抱负解法是动态计划,然则也能够采纳递返来求解。
  • 例2是一道顺时针接见矩阵元素的习题,在不少面试题中有见到。
  • 例3、例4和例5则强调怎样运用矩阵自身的空间,来变更矩阵中的元素,即空间复杂度为O(1)。用到了元素间交流和位运算战略,个中相干解法很奇妙。
  • 例6是一道怎样挪动矩阵的问题。
  • 例7和例8则是考核我们疾速明白题意,并在较短时候内完成较高质量代码的才能。即编写的代码争夺一次性经由过程。
  • 例9考核我们怎样把二分查找的运用场景由一维数组转换到二维数组。
  • 例10是一道动态计划连系矩阵的典范习题,而且还能够延申出求最短途径的问题。
  • 例11则很有意义,该题是上篇例6中《和为K的子数组》的一个升级版,把一维数组的场景变更成了二维的场景,并连系了动态头脑,因而问题难度由中等变成了难题。
  • 例12是一道难题级别的习题,该题重要考核我们的数学剖析才能,怎样天真变更矩阵的行和列,以及细节的处置惩罚才能。

 

例1 杨辉三角 II

题号:119,难度:简朴(可参考 杨辉三角,题号:118,难度:简朴)

问题形貌:

 

解题思绪:

根据杨辉三角的规律,当前行的数据和上一行的数据有着递推关联:dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。根据该递推公式能够写一个较为清楚的动态计划解法,其空间复杂度为O(k)。然则,也能够采纳递归的头脑来处理。此处供应一个运用递归头脑来处理该问题的代码。

详细代码:

class Solution {
    
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<>();
        if(rowIndex + 1 <= 0)
            return result;
        dfs(result, rowIndex+1);
        return result;
    }
    
    public void dfs(List<Integer> result, int rowIndex) {
        if(rowIndex == 1) {
            result.add(1);
            return;
        }
        dfs(result, rowIndex - 1);
        int len = result.size();
        int temp = 1;
        for(int i = 1;i < len;i++) {
            int t = result.get(i);
            result.set(i, temp+result.get(i));
            temp = t;
        }
        result.add(1);
    }
}

实行效果:

 

例2 螺旋矩阵

题号:54,难度:中等

问题形貌:

 

解题思绪:

这题只须要不停的往内顺时针扭转接见即可。然则,在完成代码时须要注重边境的问题。别的,根据LeetCode上批评的解答思绪,能够给接见过的元素做一个标记,或许统计当前已接见的元素个数,如许越发有利于推断接见完毕的时候节点。

详细代码:

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix.length == 0)
            return new ArrayList<Integer>();
        List<Integer> result = new ArrayList<>();
        int start_x = 0, start_y = 0;
        int max_x = matrix.length, max_y = matrix[0].length;
        int len = matrix.length * matrix[0].length;
        
        while(result.size() < len) {
            int x = start_x, y = start_y;
            
            for(;y < max_y && result.size() < len;y++)
                result.add(matrix[x][y]);  // 向右
            y = y -1;
            for(x = x + 1;x < max_x && result.size() < len;x++)
                result.add(matrix[x][y]);  // 向下
            x = x - 1;
            for(y = y -1;y >= start_y && result.size() < len;y--)
                result.add(matrix[x][y]);  // 向左
            y = y + 1;
            for(x = x - 1;x > start_x && result.size() < len;x--)
                result.add(matrix[x][y]);  // 向上
            
            max_x--;
            max_y--;
            start_x++;
            start_y++;  
        }
        
        return result;
    }
}

实行效果:

 

例3 扭转图象

题号:48,难度:中等

问题形貌:

 

解题思绪:

这题能够明白为是例2的一个演变版。问题意义说明为n*n的矩阵,所以不必斟酌长方形矩阵的状况。下面代码给出的解答思绪为根据正方形矩阵不停往内举行扭转转圈,每次迁移转变的步数为边长长度减去1的大小,每往内扭转一步,正方形边长减2。别的,看到LeetCode批评的解答思绪,有一个很有意义:把矩阵翻转两次,第一次沿着主对角线翻转,第二次沿着垂直中线翻转。

详细代码:

class Solution {
    
    public void rotate(int[][] matrix) {
        for(int i = 0;i < matrix.length;i++) {
            int len = matrix.length - i * 2;
            while(--len > 0) {
                int temp = matrix[i][i];
                // 左移
                for(int j = i + 1;j < matrix.length - i;j++) 
                    temp = swap(matrix, i, j, temp);
                // 下移
                for(int j = i + 1;j < matrix.length - i;j++) 
                    temp = swap(matrix, j, matrix.length - i -1, temp);
                }
                // 右移
                for(int j = matrix.length - i - 2;j >= i;j--)
                    temp = swap(matrix, matrix.length - i -1, j, temp);          
                // 上移
                for(int j = matrix.length - i - 2;j >= i;j--) 
                    temp = swap(matrix, j, i, temp);
            }
        }
    }
    
    public int swap(int[][] matrix, int i, int j, int temp) {
        int t = matrix[i][j];
        matrix[i][j] = temp;
        return t;
    }
}

实行效果:

 

例4 矩阵置零

题号:73,难度:中等

问题形貌:

 

解题思绪:

先说一下空间复杂度为O(m+n)的思绪(PS:该思绪不符合题意的原地算法请求)。请求两个一维数组,一个示意矩阵行,一个示意矩阵列。然后,遍历矩阵中一切元素,一旦涌现零,把该零对应行和对应列的一维数组的值标记为常数1。末了,离别按行和按列给原始矩阵赋值零。

如今参考LeetCode上一个批评的思绪,空间复杂度为O(2)。请求两个布尔变量cow和col,离别纪录原矩阵第0行和第0列中是不是存在零,假如存在标记为True,不然标记为False。然后,接下来的思绪就是上面O(m+n)的处理思绪,唯一差别的是此时的空间是采纳原始矩阵的空间。

详细代码:

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean row = false, col = false;
        for(int i = 0;i < matrix.length;i++) {
            if(matrix[i][0] == 0) {
                row = true;
                break;
            }
        }
        
        for(int j = 0;j < matrix[0].length;j++) {
            if(matrix[0][j] == 0) {
                col = true;
                break;
            }
        }
        
        for(int i = 1;i < matrix.length;i++) {
            for(int j = 1;j < matrix[0].length;j++) {
                if(matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        for(int i = 1;i < matrix.length;i++) {
            if(matrix[i][0] == 0) {
                for(int j = 1;j < matrix[0].length;j++)
                    matrix[i][j] = 0;
            }
        }
        
        for(int j = 1;j < matrix[0].length;j++) {
            if(matrix[0][j] == 0) {
                for(int i = 1;i < matrix.length;i++)
                    matrix[i][j] = 0;
            }
        }
        
        if(row) {
            for(int i = 0;i < matrix.length;i++)
                matrix[i][0] = 0;
        }
        
        if(col) {
            for(int j = 0;j < matrix[0].length;j++)
                matrix[0][j] = 0;
        }
        
    }
}

实行效果:

 

例5 生命游戏

题号:289,难度:中等

问题形貌:

 

解题思绪:

此题在请求采纳原地算法,即不能运用分外的空间来更新原始的矩阵元素。此题的处理方案须要运用位运算来处理。

先视察问题对活细胞和死细胞的定义,然后把它们转化为二进制示意。

活细胞:1变更为二进制01,假如活细胞变成死细胞,只须要把01变成11,即1变成3,其末了一名依旧能够识别为活细胞。

死细胞:0变更为二进制00,假如死细胞变成活细胞,只须要把00变成10,即0变成2,其末了一名依旧能够识别为死细胞。

末了,采纳board[i][j]&1举行位运算的轨则来求取一个细胞四周的活细胞数目,并更新当前细胞的状况。

详细代码:

class Solution {
    
    public void gameOfLife(int[][] board) {
       // 01示意活细胞,01——>11变成死细胞,即由1变成3
       // 00示意死细胞,00——>10变成活细胞,即由0变成2
        for(int i = 0;i < board.length;i++) {
            for(int j = 0;j < board[0].length;j++) {
                int count = countLive(board, i, j);
                if((board[i][j] & 1) == 1) {
                    if(count < 2 || count > 3)
                        board[i][j] = 3;
                } else {
                    if(count == 3)
                        board[i][j] = 2;
                }
            }
        }
        
        for(int i = 0;i < board.length;i++) {
            for(int j = 0;j < board[0].length;j++) {
                if(board[i][j] == 3)
                    board[i][j] = 0;
                if(board[i][j] == 2)
                    board[i][j] = 1;
            }
        }
    }
    
    public int countLive(int[][] board, int x, int y) {
        int[][] step = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        int count = 0;
        for(int i = 0;i < step.length;i++) {
            int temp_x = x + step[i][0];
            int temp_y = y + step[i][1];
            if(temp_x >= 0 && temp_x < board.length && temp_y >= 0 && temp_y < board[0].length) {
                if((board[temp_x][temp_y] & 1) == 1)
                    count++;
            }
        }
        
        return count;
    }
}

实行效果:

 

例6 图象堆叠

题号:835,难度:中等

问题形貌:

 

解题思绪:

此题注重怎样处置惩罚矩阵的挪动,使得挪动后两个矩阵举行婚配。直接采纳两个for轮回示意个中一个矩阵挪动后的位置。详细变更情势参考代码。

详细代码:

class Solution {
    
    public int largestOverlap(int[][] A, int[][] B) {
        int result = 0, len = A.length;
        for(int i = 0;i < len;i++) {
            for(int j = 0;j < len;j++) {
                int count1 = 0, count2 = 0;
                for(int m = 0;m < len - i;m++) {
                    for(int n = 0;n < len - j;n++) {
                        count1 += (A[m][n] & B[m+i][n+j]);
                        count2 += (B[m][n] & A[m+i][n+j]);
                    }
                }
                result = Math.max(result, count1);
                result = Math.max(result, count2);
            }
        }
        return result;
    }
}

实行效果:

 

例7 车的可用捕获量

题号:999,难度:简朴

问题形貌:

 

解题思绪:

本题较为简朴,直接遍历矩阵找到车的位置,然后在车能行走的四个方向顺次遍历即可。(放入此题的企图,问题比较长,读懂题意须要消耗一些时候,别的编写代码须要注重边境问题)

详细代码:

class Solution {
    
    public int numRookCaptures(char[][] board) {
        for(int i = 0;i < board.length;i++) {
            for(int j = 0;j < board[0].length;j++) {
                if(board[i][j] == 'R') 
                    return getResult(board, i, j);
            }
        }
        
        return 0;
    }
    
    public int getResult(char[][] board, int x, int y) {
        int count = 0;
        int tempX = x, tempY = y;
        //向上
        while(--tempX >= 0) {
            if(board[tempX][y] == 'B')
                break;
            else if(board[tempX][y] == 'p') {
                count++;
                break;
            }
        }
        tempX = x;
        //向下
        while(++tempX < board.length) {
            if(board[tempX][y] == 'B')
                break;
            else if(board[tempX][y] == 'p') {
                count++;
                break;
            }
        }
        //向左
        while(--tempY >= 0) {
            if(board[x][tempY] == 'B')
                break;
            else if(board[x][tempY] == 'p') {
                count++;
                break;
            }
        }
        tempY = y;
        //向右
        while(++tempY < board[0].length) {
            if(board[x][tempY] == 'B')
                break;
            else if(board[x][tempY] == 'p') {
                count++;
                break;
            }
        }
        
        return count;
    }
}

实行效果:

 

例8 能够进击国王的皇后

题号:1222,难度:中等

问题形貌:

 

解题思绪:

此题是例7的一个小小的升级版,重点照样处置惩罚边境问题,以及疾速编写代码和一次经由过程的才能。

详细代码:

class Solution {
    private int[][] used;
    
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        used = new int[8][8];
        used[king[0]][king[1]] = 2;
        for(int i = 0;i < queens.length;i++)
            used[queens[i][0]][queens[i][1]] = 1;
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0;i < queens.length;i++) {
            if(judgeQ(queens[i][0], queens[i][1])) {
                List<Integer> temp = new ArrayList<>();
                temp.add(queens[i][0]);
                temp.add(queens[i][1]);
                result.add(temp);
            }
        }
        return result;
    }
    
    public boolean judgeQ(int x, int y) {
        int x1 = x;
        while(--x1 >= 0) {
            if(used[x1][y] == 2)
                return true;
            if(used[x1][y] == 1)
                break;
        }
        int x2 = x;
        while(++x2 < 8) {
            if(used[x2][y] == 2)
                return true;
            if(used[x2][y] == 1)
                break;
        }
        int y1 = y;
        while(--y1 >= 0) {
            if(used[x][y1] == 2)
                return true;
            if(used[x][y1] == 1)
                break;
        }
        int y2 = y;
        while(++y2 < 8) {
            if(used[x][y2] == 2)
                return true;
            if(used[x][y2] == 1)
                break;
        }
        int x3 = x, y3 = y;
        while(--x3 >= 0 && --y3 >= 0) {
            if(used[x3][y3] == 2)
                return true;
            if(used[x3][y3] == 1)
                break;
        }
        int x4 = x, y4 = y;
        while(++x4 < 8 && ++y4 < 8) {
            if(used[x4][y4] == 2)
                return true;
            if(used[x4][y4] == 1)
                break;
        }
        int x5 = x, y5 = y;
        while(--x5 >= 0 && ++y5 < 8) {
            if(used[x5][y5] == 2)
                return true;
            if(used[x5][y5] == 1)
                break;
        }
        int x6 = x, y6 = y;
        while(++x6 < 8 && --y6 >= 0) {
            if(used[x6][y6] == 2)
                return true;
            if(used[x6][y6] == 1)
                break;
        }
        return false;
    }
}

实行效果:

 

例9 搜刮二维矩阵

题号:74,难度:中等

问题形貌:

 

解题思绪:

一般的主意是把矩阵设想成一个一维数组,然后采纳二分查找的思绪来完成。然则,这类要领能够须要处置惩罚(1,m)和(m,1)这两种特别的二维矩阵边境问题(PS:在LeetCode上看到过直接运用二分查找很快处理的代码)。因为矩阵根据行是有序的,无妨采纳每行末了一个值作为边境与目标值举行比较大小,每次增添一行或许削减一列的数据,详细完成可参考代码。

详细代码:

class Solution {
    
    /* 二分查找的代码
      public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return false;
        int begin, mid, end;
        begin = mid = 0;
        int len1 = matrix.length, len2 = matrix[0].length;
        end = len1 * len2 - 1;
        while (begin < end) {
            mid = (begin + end) / 2;
            if (matrix[mid / len2][mid % len2] < target)
                begin = mid + 1;
            else
                end = mid;
        }
        return matrix[begin / len2][begin % len2] == target;
    } */
   
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0)
            return false;
        int row = 0, col = matrix[0].length-1;
        while(row < matrix.length && col >= 0){
            if(matrix[row][col] < target)
                row++;
            else if(matrix[row][col] > target)
                col--;
            else
                return true;
        }
        return false;
    }
    
}

实行效果:

 

例10 最小途径和

题号:64,难度:中等

问题形貌:

 

解题思绪:

此题最直接的思绪是采纳递归举行深度搜刮遍向来处理,然则提交代码后发明会涌现超时的问题。此时,须要斟酌运用动态计划的头脑来解题。动态计划的转换方程:dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j],别的须要斟酌矩阵边境的问题。

详细代码:

class Solution {
   
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length + 1][grid[0].length + 1];
        for(int i = 1;i < dp.length;i++) {
            for(int j = 1;j < dp[0].length;j++) {
                if(i == 1)
                    dp[i][j] = dp[i][j-1] + grid[i-1][j-1];
                else if(j == 1)
                    dp[i][j] = dp[i-1][j] + grid[i-1][j-1];
                else
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        
        return dp[grid.length][grid[0].length];
    }
    
}

实行效果:

 

例11 元素和为目标值的子矩阵数目

题号:1074,难度:难题

问题形貌:

 

解题思绪:

这道题实际上是《和为K的子数组,题号:560,难度:中等》的一个升级版,560题是一维数组,本题是二维数组,其和变成了一个子矩阵的情势。此处我们能够采纳把矩阵每行的元素变更成从该行最先道当前元素的和,别的零丁选两列求矩阵和,如许就把二维数组变成了列情势的一维数组乞降。此时,解题思绪就和560题一样。

详细代码:

class Solution {
    
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        for(int i = 0;i < matrix.length;i++)
            for(int j = 1;j < matrix[0].length;j++)
                matrix[i][j] += matrix[i][j-1];
        
        int result = 0;
        for(int j1 = 0;j1 < matrix[0].length;j1++) {
            for(int j2 = j1;j2 < matrix[0].length;j2++) {
                Map<Integer, Integer> map = new HashMap<>();
                map.put(0,1);
                int pre = 0;
                for(int i = 0;i < matrix.length;i++) {
                    int val = pre + (j1 == 0 ? matrix[i][j2] : matrix[i][j2] - matrix[i][j1-1]);
                    result += map.getOrDefault(val - target, 0);
                    map.put(val, map.getOrDefault(val, 0)+1);
                    pre = val;
                }
            }
        }
        
        return result;
    }
}

实行效果:

 

例12 变成棋盘

题号:782,难度:难题

问题形貌:

 

解题思绪:

本题剖析一下01涌现的规律,可知假如n为偶数,那末每行每列中0和1的个数必定相称;假如n为奇数,那末0和1个数差的绝对值为1。因为矩阵只能交流行和列,效果要涌现0和1不停相间分列,那末一切行中只能涌现两种形式的01分列体式格局,而且这两种分列体式格局互补。比方,n=4, 第一行排序:1001,那末其他行要不即是1001,要么即是0110,不然就不能够转换为棋盘,直接输出-1即可。关于列的状况,和行一样。(PS:此题须要处置惩罚最小变更次数的边境问题,分奇偶议论行或许列的最小交流次数)

详细代码:

class Solution {
    public int movesToChessboard(int[][] board) {
        if(check(board)) {
            int row = 0, start = board[0][0];
            for(int i = 1;i < board.length;i++) {
                if(board[i][0] == start)
                    row++;
                start = 1 - start;
            }
            int col = 0; 
            start = board[0][0];
            for(int j = 1;j < board[0].length;j++) {
                if(board[0][j] == start)
                    col++;
                start = 1 - start;
            }
            if(board.length % 2 == 0) { // 分奇数偶数议论行和列最小交流次数
                row = Math.min(board.length-row, row);
                col = Math.min(board.length-col, col);
            } else {
                if(row % 2 == 1)
                    row = board.length-row;
                if(col % 2 == 1)
                    col =  board.length-col;
            }
            return row / 2 + col / 2;
        }
        
        return -1;
    }
    
    public boolean judgeEqual(int[][] board, int i, int j) {
        for(int k = 0;k < board[0].length;k++) {
            if(board[i][k] != board[j][k])
                return false;
        }
        
        return true;
    }
    
    public boolean judgeNotEqual(int[][] board, int i, int j) {
        for(int k = 0;k < board[0].length;k++) {
            if(board[i][k] == board[j][k])
                return false;
        }
        
        return true;
    }
     
    public boolean check(int[][] board) {
        int row_0 = 0, row_1 = 0, col_0 = 0, col_1 = 0;
        for(int i = 0;i < board[0].length;i++) {
            if(board[0][i] == 0)
                row_0++;
            else if(board[0][i] == 1)
                row_1++;
            if(board[i][0] == 0)
                col_0++;
            else if(board[i][0] == 1)
                col_1++;
        }
        
        if(Math.abs(row_0 - row_1) > 1 || row_0+row_1 != board[0].length)
            return false;
        if(Math.abs(col_0 - col_1) > 1 || col_0+col_1 != board.length)
            return false;
        
        row_0 = 0;
        row_1 = 0;
        for(int j = 1;j < board[0].length;j++) {
            if(judgeEqual(board, 0, j))
                row_0++;
            else if(judgeNotEqual(board, 0, j))
                row_1++;
            else
                return false;
        }
        
        return true;
    }

}

实行效果:

 

 

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
LeetCode刷题总结-数组篇(中)

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282404.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>