LeetCode - 二维数组及滚动数组

1. 二维数组及滚动数组总结

在二维数组num[j]中，每个元素都是一个数组。有时候，二维数组中的某些元素在整个运算过程中都需要用到；但是有的时候我们只需要用到前一个或者两个数组，此时我们便可以用几个数组来代替原来的二维数组来降低空间消耗。这个思维就是：滚动数组。
滚动数组就是使用k个一维数组来保存原来二维数组的后k个数组，在使用的过程中通过不断更新这k个数组来达到与二维数组相同的效果。
注意：滚动数组的目的是：减少空间消耗；滚动数组能够使用的前提是：每次处理时不需要访问二维数组中的所有元素，只与当前处理元素的前一个或两个数组有关，如：num[j] = num[i-1][j] + num[i-2][j]类似情况，我们就可以使用滚动数组。

滚动数组在动态规划过程中经常使用，此处我们先提前了解一下。

2. 题目记录

118. 杨辉三角

分析题意

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
思路分析

关键在于理解：杨辉三角是如何生成的。即：对于第i行元素来说，除了第一个和最后一个，对于任意一个元素 j都有nums[j] = nums[i-1][j-1] + nums[i-1][j]

1. class Solution {
2.     public List<List<Integer>> generate(int numRows) {
3.         List<List<Integer>> ans = new ArrayList<>();
5.         for(int row = 1; row <= numRows; row++){
6.             List<Integer> temp = new ArrayList<Integer>();
7.             for(int col = 1; col <= row; col++){
8.                 if(col == 1 || col == row){
9.                     temp.add(1);
10.                 }else{
11.                     // row - 1 对应的idx 为 row-1-1
12.                     List<Integer> pre = ans.get(row - 2);
13.                     // col 对应的idx为col-1
14.                     temp.add(pre.get(col-2) + pre.get(col-1));
15.                 }
16.             }
18.             ans.add(temp);
19.         }
20.         return ans;
21.     }
22. }

复制代码

简化的代码如下：

1. class Solution {
2.     public List<Integer> getRow(int rowIndex) {
3.         int[] pre = new int[rowIndex + 1];
4.         int[] cur = new int[rowIndex + 1];
6.         for(int idx = 0; idx <= rowIndex; idx++){
7.             for(int j = 0; j < idx + 1; j++){
8.                 if(j == 0 || j == idx){
9.                     cur[j] = 1;
10.                 }else{
11.                     cur[j] = pre[j-1] + pre[j];
12.                 }
13.             }
14.             int[] temp = pre;
15.             pre = cur;
16.             cur = temp;
17.         }
19.         List<Integer> ans = new ArrayList<>();
20.         for(int i = 0; i < pre.length; i++){
21.             ans.add(pre[i]);
22.         }
23.         return ans;
24.     }
25. }

复制代码

复杂度分析

时间复杂度：\(O(n^2)\)
空间复杂度：\(O(1)\)  返回数组占用空间不计入
598. 范围求和 II

分析题意

注意关键词：初始化时所有的 0 ，也就是说所有数值在操作之前都是0。
思路分析

这道题看似是需要创建一个二维数组，然后一次一次模拟操作，最后遍历查出最大的数据的个数。其实，并不需要这样。我们想一下：因为二维数组初始化时都是0，所以在所有操作完成之后，二维数组中每个单元格内的数字其实就是有多少个操作包含了这个单元格。又因为所有操作都是从(0, 0)开始的，所以我们要求最大的整数出现的频次，那其实就是求：所有操作的的最小交集。

1. [1, 3, 3, 1, 0]

复制代码

复杂度分析

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)
419. 甲板上的战舰

分析题意

这道题就是一道语文题，能不能做出来完全取决于你有没有理解题目在说什么。
首先，明确一个：题目是要统计board上的军舰数量，而不是要你计算军舰的数量。我第一次做的时候就是以为要模拟计算军舰的数量，所以一直没有做出来。
其次，要明确战舰的定义，战舰或者是横着摆放或者是竖着摆放。也就是说一个战舰，他要么占一行的很多列，要么站一列的很多行；不可能同时占用很多行和很多列。
上述两个红框就是两个战舰，所以此时答案为2。
思路分析

其实我们只需要找到战舰的头就可以了，那么战舰的头怎么寻找呢？其实就是它的左侧和上侧都没有战舰，那么这个战舰一定是战舰头部。

1. [1, 4, 3, 1, 0]

复制代码

复杂度分析

时间复杂度：\(O(m \times n)\)
空间复杂度：\(O(1)\)

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！