力扣-二维数组及滚动数组（118、119、661、598、419）_力扣 滚动数组

力扣-二维数组及滚动数组（118、119、661、598、419）

1. 滚动数组：
   这是动态规划问题中的一种编程思想，简单的说就是让一个数组可以动起来，因为动态规划问题是一个自底向上的一个连续的问题，我们常常需要用到的就是这个连续的解，而对于前面的解我们可以舍去，没必要存储，所以滚动数组就可以优化这个空间，达到一个压缩存储的作用。
2. 生成默认二维数组

# 生成一个5行10列 的二维数组
[[0 for i in range(10)] for j in range(5)]    
1
2

---

杨辉三角（118）

思路： 每一行除第一个和最后一个都满足以下条件：n[i][j]=n[i-1][j-1]+n[i-1][j]。设置一个prior作为n[i-1][j-1]，设置next作为n[i-1][j]，如果 j-1<0说明这是第一个元素，prior=0，其余情况prior=n[i-1][j-1]，如果 j>=len(n[i-1])，说明这是最后一个元素，next=0，其余情况next=n[i-1][j]。最后n[i][j]=prior+next 。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result=[]
        result.append([1])
        if numRows==1:
            return result
        for i in range(1,numRows):
            cur=[]
            result.append(cur)
            for j in range(i+1):
                if j-1<0:
                    prior=0
                else:
                    prior=result[i-1][j-1]
                if j==len(result[i-1]):
                    next=0
                else:
                    next=result[i-1][j]
                result[i].append(prior+next)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

杨辉三角II (119)

方法一思路： 参考杨辉三角I的方法，返回二维数组的最后一元素就行了。

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        result=[]
        result.append([1])
        if rowIndex==0:
            return result[0]
        for i in range(1,rowIndex+1):
            cur=[]
            result.append(cur)
            for j in range(i+1):
                if j-1<0:
                    prior=0
                else:
                    prior=result[i-1][j-1]
                if j==len(result[i-1]):
                    next=0
                else:
                    next=result[i-1][j]
                result[i].append(prior+next)
        return result[rowIndex]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法二思路： 滚动数组，先给出全 1 的数组，然后从第二行开始更新，每一行更新都为从右向左遍历 res[j]=res[j]+res[j-1]。
例如求第六行：
[1,1,1,1,1,1]
第一行[1,1,1,1,1,1] 不更新
第二行[1,1,1,1,1,1] 不更新
第三行[1,2,1,1,1,1] 更新数组下标为1的元素
第四行[1,3,3,1,1,1] 先更新数组下标为2的元素，再更新下标为1
第五行[1,4,6,4,1,1] 先下标3，再2，最后1
第六行[1,5,10,10,5,1] 先下标4，再3，再2，最后1

nrows=6  
res=[1]*nrows
for i in range(2,nrows+1):
    for j in range(i-1,1,-1):
        res[j-1]=res[j-1]+res[j-2]
print(res)
1
2
3
4
5
6

---

图片平滑器（661）

思路： 遍历这个二维数组，然后遍历 (i-1，i+1) 范围内的值，并判断取值是否合法（即是否超出二维数组的上界），若没有超出则加起来sum，并计算所有合法元素的个数count，最后计算sum / count 。

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        l=len(img)
        w=len(img[0])
        result=[[0 for i in range(w)] for j in range(l)]
        for i in range(l):
            for j in range(w):
                sum=0
                count=0
                for p in range(i-1,i+2):
                    for q in range(j-1,j+2):
                        if 0<=q<w and 0<=p<l:
                            sum+=img[p][q]
                            count+=1
                result[i][j]=sum//count
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

范围求和II(598)

思路： 根据ops中的每个操作来计算，求所有操作的第一列的最小值（min_x）以及第二列的最小值(min_y)，返回结果就为 min_x和min_y的乘积。

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        if ops==[]:
            return m*n
        min_x=m
        min_y=n
        for p in ops:
            if p[0]<min_x:
                min_x=p[0]
            if p[1]<min_y:
                min_y=p[1]              
        return min_x*min_y
1
2
3
4
5
6
7
8
9
10
11
12

---

甲板上的战舰（419）

思路： 首先就是题目给出的甲板都是有效的，我们无需去判断是否有空一行或空一列。所以呢，我们就去遍历二维数组去数战舰头部。头部满足的条件：
上方无战舰：board[i][j] == X 并且 i==0 或者 i !=0 但是上方没有战舰
左方无战舰：board[i][j] == X 并且 j==0 或者 j !=0 但是左边没有战舰
如果满足上面的条件则是战舰头部，其余全是空或者战舰的非头部分。

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        row=len(board)
        col=len(board[0])
        count=0
        for i in range(row):
            for j in range(col):
                if (board[i][j]=='X' and (i==0 or board[i-1][j]=='.') and (j==0 or board[i][j-1]=='.')):
                    count+=1
        return count

1
2
3
4
5
6
7
8
9
10
11