【Leetcode题单】（01 数组篇）刷题关键点总结04【二维数组及滚动数组】

本文主要是介绍【Leetcode题单】（01 数组篇）刷题关键点总结04【二维数组及滚动数组】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大家好，这里是新开的LeetCode刷题系列，以后尽量一天更新一个小章节。此系列应超过400题。
数组篇04《二维数组及滚动数组》，共5道题，4简单题1中等题。
注意看重点部分，总结起来是这一类题的规律。

二维数组及滚动数组

118. 杨辉三角 Easy

118. 杨辉三角

    public List<List<Integer>> generate(int numRows) {List<List<Integer>> list = new ArrayList<List<Integer>>();for(int i = 0; i < numRows; i++){List<Integer> row = new ArrayList<Integer>();for(int j = 0; j < i + 1; j++){if(j == 0 || j == i){row.add(1);} else {row.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));}}list.add(row);}return list;}

重点

• List的嵌套使用
• 内层循环的设计
• List的add()和get()方法

119. 杨辉三角 II Easy

119. 杨辉三角 II

此题内含数学公式推导

    public List<Integer> getRow(int rowIndex) {List<Integer> row = new ArrayList<Integer>();row.add(1);for(int i = 1; i <= rowIndex; i++){row.add((int) ((long)row.get(i - 1) * (rowIndex - i + 1) / i));}return row;}

重点

• List的使用
• 循环中 i 的初始值设为 1 ，方便进行操作
• 为防止数据溢出，设为 long 后改为 int

661. 图片平滑器 Easy

661. 图片平滑器

    public int[][] imageSmoother(int[][] img) {int m = img.length, n = img[0].length;int[][] ans = new int[m][n];for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){int count = 0, sum = 0;for(int x  = i - 1; x <= i + 1; x++){for(int y = j - 1; y <= j + 1; y++){if(x >= 0 && x < m && y >= 0 && y < n){count++;sum += img[x][y];}}}ans[i][j] = sum / count;}}return ans;}

重点

• 内两层循环，界定9个数的范围，确定在数组内部，则相加计算
• 设定count值，计算范围内数字数
• int 类型本身的除法就是向下取整

598. 范围求和 II Easy

598. 范围求和 II

    public int maxCount(int m, int n, int[][] ops) {int len = ops.length;int minM = m, minN = n;for(int i = 0; i < len; i++){minM = Math.min(minM, ops[i][0]);minN = Math.min(minN, ops[i][1]);}return minM * minN;}

重点

• Math.min()的使用
• 最小值的初始值设置
• 问题转换为最小的option[i][0]与最小的option[i][1]之积

419. 甲板上的战舰 Medium

419. 甲板上的战舰


遍历法

    public int countBattleships(char[][] board) {int row = board.length;int col = board[0].length;int ans = 0;for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(board[i][j] == 'X'){board[i][j] = '.';for(int k = j + 1; k < col && board[i][k] == 'X'; k++){board[i][k] = '.';}for(int k = i + 1; k < row && board[k][j] == 'X'; k++){board[k][j] = '.';}ans++;}}}return ans;}

起点法

    public int countBattleships(char[][] board) {int row = board.length;int col = board[0].length;int ans = 0;for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(board[i][j] == 'X'){if(i > 0 && board[i-1][j] == 'X'){continue;}if(j > 0 && board[i][j-1] == 'X'){continue;}ans++;}}}return ans;}

重点

• 遍历法：避免重复计数
• 起点法：只计算起点数量
• 问题简化：continue 的用法，避免重复计数，则置空

这个系列希望能够帮助大家**
提高刷题效率**，发现系列算法题目的常规思路，更快a题，速通Leetcode
b站【软件柠檬】以后会不定期分享计算机领域基础知识，求职干货，为大家助力实习和春秋招offer，
❤️这里是 软件柠檬， 让我们一起学习进步~❤️

这篇关于【Leetcode题单】（01 数组篇）刷题关键点总结04【二维数组及滚动数组】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---