Datawhale 11月内容：https://algo.itcharge.cn/

2021.11.16 

1. 数组基础知识

1.1 数组定义

数组（Array）：一种线性表数据结构。它使用一组连续的内存空间，来存储一组具有相同类型的数据。

• 第一个方面是 「线性表」

  线性表逻辑结构就是所有数据元素排成像一条线一样的结构。

• 第二个方面是 「连续的内存空间」

  线性表有两种存储结构：「顺序存储结构」和「链式存储结构」。其中，「顺序存储结构」是指占用的内存空间是连续的，相邻数据元素之间，物理内存上的存储位置也相邻。

• 第三个方面是 「连续的内存空间」

  数组存储的数据都是相同类型的。

1.2 如何随机访问数据元素

数组的一个最大特点是：可以进行随机访问。即数组可以根据下标，直接定位到某一个元素存放的位置。

寻址公式如下：下标 i 对应的数据元素地址 = 数据首地址 + i * 单个数据元素所占内存大小

1.3 多维数组

二维数组是一个由m行 n 列数据元素构成的特殊结构，其本质上是以数组作为数据元素的数组，即 「数组的数组」。二维数组的第一维度表示行，第二维度表示列。可以将二维数组看做是一个矩阵

1.4 不同编程语言中数组的实现

C / C++

int arr[3][4] = {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}};

• 逻辑上存储是连续的
• 存储相同类型数据
• 无论什么数据类型，连续的内存空间（物理存储连续）

JAVA

int[][] arr = new int[3][]{ {1,2,3}, {4,5}, {6,7,8,9}};

• 逻辑上存储是连续的
• 存储相同类型数据的
• 物理上使用的内存空间却不一定是连续（多维数组中）。且如果是多维数组，其嵌套数组的长度也可以不同。

Python

arr = ['python', 'java', ['asp', 'php'], 'c']

• 原生 Python 中其实没有数组的概念，而是使用了类似 Java 中的 ArrayList 容器类数据结构，叫做列表
• 逻辑是连续的
• 但类型可以不一致
• 长度也可以不一致

2. 数组的基本操作

2.1 访问

访问数组中第i 个元素：只需要检查是否合法，访问操作不依赖于数组中元素个数，因此 时间复杂度为$O(1)$ 。

# 从数组 nums 中读取下标为 i 的数据元素值
def value(nums, i):
	if 0 <= i <= len(nums) - 1:
		print(nums[i])
		
arr = [0, 5, 2, 3, 7, 1, 6]
value(arr, 3)

2.2 查找元素

查找数组中元素值为val 的位置：能通过将 val 与数组中的数据元素逐一对比的方式进行检索，也称为线性查找。线性查找操作依赖于数组中元素个数，时间复杂度为$O(n)$ 。

# 从数组 nums 中查找元素值为 val 的数据元素第一次出现的位置
def find(nums, val):
    for i in range(len(nums)):
        if nums[i] == val:
            return i
    return -1

arr = [0, 5, 2, 3, 7, 1, 6]
print(find(arr, 5))

2.3 插入元素

插入元素操作分为两种：「在数组尾部插入值为 val 的元素」和「在数组第i 个位置上插入值为 val 的元素」。

• 在数组尾部插入值为 val 的元素

  

  Python 中的 list 直接封装了尾部插入操作，直接调用 append() 方法即可。访问操作不依赖于数组中元素个数，因此 时间复杂度为$O(1)$ 。

arr = [0, 5, 2, 3, 7, 1, 6]
val = 4
arr.append(val)
print(arr)

• 在数组第 i个位置上插入值为 val 的元素
  

  Python 中的 list 直接封装了中间插入操作，直接调用 insert ()方法即可。因为移动元素的操作次数跟元素个数有关，最坏和平均时间复杂度都是 $O(n)$。

arr = [0, 5, 2, 3, 7, 1, 6]
i, val = 2, 4
arr.insert(i, val)
print(arr)

2.4 改变元素

将数组中第i 个元素值改为 val：需要先检查i的范围是否在合法的范围区间;访问操作不依赖于数组中元素个数，因此 时间复杂度为$O(1)$ 。

def change(nums, i, val):
    if 0 <= i <= len(nums) - 1:
        nums[i] = val
        
arr = [0, 5, 2, 3, 7, 1, 6]
i, val = 2, 4
change(arr, i, val)
print(arr)

2.5 删除元素

删除元素分为三种情况：「删除数组尾部元素」、「删除数组第 i 个位置上的元素」、「基于条件删除元素」。

• 删除数组尾部元素

  Python 中的 list 直接封装了删除数组尾部元素的操作，只需要调用 pop() 方法即可。

arr = [0, 5, 2, 3, 7, 1, 6]
arr.pop()
print(arr)

>[0, 5, 2, 3, 7, 1]

• 删除数组第 i个位置上的元素
  

  只需要以下标作为参数调用 pop(i) 方法即可。删除中间位置元素的操作同样涉及移动元素，而移动元素的操作次数跟元素个数有关，因此删除中间元素的最坏和平均时间复杂度都是$O(n)$ 。

arr = [0, 5, 2, 3, 7, 1, 6]
i = 3
arr.pop(i)
print(arr)

>[0, 5, 2, 7, 1, 6]

• 基于条件删除元素

  给出一个条件要求删除满足这个条件的（一个、多个或所有）元素,用 pop(条件) ，时间复杂度都是$O(n)$

arr = [0, 5, 2, 3, 7, 1, 6]
arr.remove(5)
print(arr)

>[0, 2, 3, 7, 1, 6]

3 数组基础题目

• 数组操作题目

题号	标题	难度
0189	旋转数组	中等
0066	加一	简单
0724	寻找数组的中心下标	简单
0485	最大连续 1 的个数	简单
0238	除自身以外数组的乘积	中等

• 二维数组题目

题号	标题	标签	难度
面试题 01.07	旋转矩阵	数学、矩阵	中等
面试题 01.08	零矩阵	数组、哈希表、矩阵	中等
0498	对角线遍历	数组、矩阵、模拟	中等
0048	旋转图像	数组	中等
0118	杨辉三角	数组	简单
0119	杨辉三角 II	数组	简单
0073	矩阵置零	数组	中等
0054	螺旋矩阵	数组	中等
0289	生命游戏	数组、矩阵、模拟	中等

3.1 数组操作题目

LeetCode：189. 轮转数组

题目：https://leetcode-cn.com/problems/rotate-array/

• 方法1

  就是输入k，那么就是List末尾要移走K位，没移走1位，赋值给pop_num, 将其再添加到List的0号位置

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(k):
            pop_num = nums.pop()
            nums.insert(0, pop_num)

        print(nums)

• 方法2

  k = 3，【1, 2, 3, 4, 5, 6, 7】→【4, 3, 2, 1, 5, 6, 7】→【4, 3, 2, 1, 7, 6, 5】→【5,6,7,1,2,3,4】

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        
        self.reverse(nums, 0, n-k-1)
        
        self.reverse(nums, n-k, n-1)
        self.reverse(nums, 0, n-1)

        print(nums)


    def reverse(self, nums: List[int], left: int, right: int) -> None:
        while left < right :
            tmp = nums[left]
            nums[left] = nums[right]
            nums[right] = tmp
            left += 1
            right -= 1

• 超出长度的判断 k = k % n，方法1 规避掉了
• reverse内置的列表翻转只能从头到尾，比如nums.reverse()，所以这里重新定义了

LeetCode：66. 加一

题目：https://leetcode-cn.com/problems/plus-one/

本题意思就是将数组每位连起来当成一个数+1，再变成数组。eg:[1,2,3] ->123 +1->124 输出List:[1,2,4]

思路：

• 数组前补 0 位。（防止进位）
• 将个位数字进行 +1 计算。
• 遍历整个数组：
  如果这个数是10，那么说明这一位有进位，那么这位digits[i] = 0并前一位进1位；
  如果这个数不为10，那么没有进位，前面的位也不可能进位，所以直接跳出循环就好。
• 最后 再看看 list前面加的那个【0】还在不在 ，在的话去掉

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits = [0] + digits
        #print(digits)
        digits[len(digits)-1] += 1

        for i in range(len(digits)-1, 0, -1):
            if digits[i] != 10:
                break
            else:
                digits[i] = 0
                digits[i-1] += 1

        if digits[0] == 0:
            return digits[1:]
        else:
            return digits

LeetCode：724. 寻找数组的中心下标

题目：https://leetcode-cn.com/problems/find-pivot-index/

思路：
两次遍历，

• 第一次遍历先求出数组全部元素和。
• 第二次遍历找到左侧元素和恰好为全部元素和一半的位置。
  遍历 左边sumL = 0 右边sumR = 0

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        sum = 0
        for i in range(len(nums)):
            sum += nums[i]
        curr_sum = 0
        for i in range(len(nums)):
            if curr_sum * 2 + nums[i] == sum:
                return i
            curr_sum += nums[i]
        return -1

• 同样的思路 ，第一层循环用内置sum()函数，只需要一层循环

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:

        sum1 = sum(nums) #取代了第一层循环
        curr_sum = 0
        for i in range(len(nums)):
            if curr_sum * 2 + nums[i] == sum1:
                return i
            curr_sum += nums[i]
        return -1

LeetCode：485. 最大连续 1 的个数

题目：https://leetcode-cn.com/problems/find-pivot-index/
想法：

• 一层循环即可，当前遇到连续1用sum储存，用 max01来存储之前最大长度的1
• 当sum> max01 那么就替换max01
• 遇到0那么sum重新从0开始记

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        max01 = 0
        sum = 0
        for i in range(len(nums)):
            if nums[i] == 1:
                sum += 1
                if sum > max01:
                    max01 = sum
            else:
                sum = 0

        return max01

参考答案：优化命名，用max函数

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        ans = 0
        sum = 0
        for num in nums:
            if num == 1:
                sum += 1
                ans = max(ans, sum)
            else:
                sum = 0
        return ans

LeetCode：238. 除自身以外数组的乘积

题目：https://leetcode-cn.com/problems/product-of-array-except-self/

思路：

• 两层循环
• 第一层算出所有值的乘积all
• 第二层就是根据i算算nums[i] = all/i

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        #算所有乘积
        k = 0
        all = 1
        for i in nums:
            if i == 0:
               k = all
               all *= i
            else:
                all *= i
                k *= i


        output = []
        for i in range(len(nums)):
            if nums[i] != 0:
                output.append(int(all/nums[i]))
            else:
                output.append(int(k))

        return output

遇到了0的问题 比如：[-1,1,0,-3,3]

• 用了一个K来处理当i运行到0时的值，
• 那么整体乘积all就是总乘积，不受是不是0影响
• 但是如果遇到0，那么就转到用k计算

教程答案：

构造一个答案数组 res，长度和数组 nums 长度一致。先从左到右遍历一遍 nums 数组，将 nums[i] 左侧的元素乘积累积起来，存储到 res 数组中。再从右到左遍历一遍，将 nums[i] 右侧的元素乘积累积起来，再乘以原本 res[i] 的值，即为 nums 中除了 nums[i] 之外的其他所有元素乘积。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)
        res = [1 for _ in range(size)]

        left = 1
        for i in range(size):
            res[i] *= left
            left *= nums[i]

        right = 1
        for i in range(size-1, -1, -1):
            res[i] *= right
            right *= nums[i]
        return res

3.2 二维数组题目

LeetCode：面试题 01.07. 旋转矩阵

题目： https://leetcode-cn.com/problems/rotate-matrix-lcci/

思路： 题目要求不占用额外内存空间，就是要在原二维矩阵上直接进行旋转操作。我们可以用翻转操作代替旋转操作。具体可以分为两步：

• 上下翻转
• 对角线翻转
  

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 先对折
        size = len(matrix) 

        for i in range(size // 2):
            for j in range(size):
                matrix[i][j], matrix[size - i -1][j]    = matrix[size - i -1][j], matrix[i][j]

        for i in range(size):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

LeetCode: 面试题 01.08. 零矩阵

题目：https://leetcode-cn.com/problems/zero-matrix-lcci/
思路：两个两层数组遍历

• 如果有0 那么相应的第一行 第一列 修改为0
• 然后第二层遍历 根据第一行和第一列 有0的 这行这列都改为0

但我这个想法有个破绽，就是第一行（列）含有0 就会出错。

改进就是：

• 如果第一行（列）有0 先不变，但标记一下
  

• 针对内环进行 有0的，在第一行第一列上标记
  

• 最后再变化第一层的行（列），有0的全部修改为0：
  

• 看看标记：原数据第一行（列）如果有0的那么全部变0，否则不变

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rows = len(matrix)
        cols = len(matrix[0])
        flag_col0 = False
        flag_row0 = False
        for i in range(rows):
            if matrix[i][0] == 0:
                flag_col0 = True
                break

        for j in range(cols):
            if matrix[0][j] == 0:
                flag_row0 = True
                break

        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0

        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        if flag_col0:
            for i in range(rows):
                matrix[i][0] = 0

        if flag_row0:
            for j in range(cols):
                matrix[0][j] = 0

LeetCode 498. 对角线遍历

题目：https://leetcode-cn.com/problems/diagonal-traverse/

思路：这道题的关键是「找规律」和「考虑边界问题」。

方向：

• 当行号 + 列号为偶数时，遍历方向为从左下到右上。可以记为右上方向（-1, +1）。
• 当行号 + 列号为奇数时，遍历方向为从右上到左下。可以记为左下方向（+1, -1）。

向右上方向移动时边界：

• 如果在最后一列，列没法增加了，则向下方移动，即 x += 1 如3(2,0)-》6(2,1)
• 如果在第一行，行没法减小了，则向右方移动，即 y += 1。如1(0,0)-》2(1,0)

向左下方向移动时边界：

• 如果在最后一行，行没法再增加了，则向右方移动，即 y += 1，如8(2.1)-》9(2,2)
• 如果在第一列，列没法减小了则向下方移动，即x += 1。如4(1,0)-》7(2.0)

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        rows = len(mat)
        cols = len(mat[0])
        count = rows * cols
        x, y = 0, 0
        ans = []

        for i in range(count):
            ans.append(mat[x][y])

            if (x + y) % 2 == 0:
                # 最后一列
                if y == cols - 1:
                    x += 1
                # 第一行
                elif x == 0:
                    y += 1
                # 右上方向
                else:
                    x -= 1
                    y += 1
            else:
                # 最后一行
                if x == rows - 1:
                    y += 1
                # 第一列
                elif y == 0:
                    x += 1
                # 左下方向
                else:
                    x += 1
                    y -= 1
        return ans

LeetCode 48. 旋转图像

题目：https://leetcode-cn.com/problems/rotate-image/

方法同题一致 LeetCode：面试题 01.07. 旋转矩阵

LeetCode 118. 杨辉三角

https://leetcode-cn.com/problems/pascals-triangle/

两层循环：

• i 是 走的层数，j是走的列数，因为是杨辉三角，所以是个下三角
• 当i = 0 或者i = 层数时候 输出1

• 其余部分填充arr[i][j] = arr[i-1][j-1] + arr[i-1][j]

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = []
        for i in range(numRows):
            arr= list()
            for j in range(i+1):
                if j == 0 or j == i:
                    arr.append(1)
                else:
                    arr.append(ans[i-1][j-1]+ans[i-1][j])
            ans.append(arr)
        return ans

• 包括对角线，并且range是左闭右开，所以j要遍历到i+1而不是i

LeetCode 119. 杨辉三角 II

https://leetcode-cn.com/problems/pascals-triangle-ii/

顺着上提思路，只需要 输出的不是ans，输出的是arr即可

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        ans = []
        for i in range(rowIndex+1):
            arr= list()
            for j in range(i+1):
                if j == 0 or j == i:
                    arr.append(1)
                else:
                    arr.append(ans[i-1][j-1]+ans[i-1][j])
            ans.append(arr)
        return arr

参考答案思路

使用一个数组，进行两重循环遍历。先遍历k 行，再对每一行每个位置上的元素进行逆序赋值计算。每行遍历时，将数组两侧元素赋值为 1，即 ans[j] = 1。中间值为之前元素前两个位置之和，即 ans[j] = ans[j-1] + ans[j]。

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        ans = [0]*(rowIndex+1)
        for i in range(rowIndex+1):
            for j in range(i, -1, -1):
                if j == 0 or j == i:
                    ans[j] = 1
                else:
                    ans[j] = ans[j-1] + ans[j]
        return ans

• for j in range(4, -1, -1)输出是4,3,2,1,0
• for j in range(3, -1, -1)是3,2,1,0

rowIndex = 4

• 【0，0，0，0，0】
• i = 0, j=0 推出 ans[0] = 1 这时 ans = 【1，0，0，0，0】
• i=1时，当j=1 推出 ans[1] = 1 这时 ans = 【1，1，0，0，0】; 当j=0 推出 ans[0] = 1 这时 ans 没变化= 【1，1，0，0，0】;
• i=2时，当j=2，推出 ans[2] = 1 这时 ans = 【1，1，1，0，0】；当j=1 推出 ans[1] = ans[0] + ans[1] =2这时 ans = 【1，2，1，0，0】；当j=0 推出 ans[0] = 1 这时 ans没变化 = 【1，2，1，0，0】；
  …

LeetCode 73. 矩阵置零

https://leetcode-cn.com/problems/set-matrix-zeroes/

原地算法：是一种使用小的，固定数量的额外之空间来转换资料的算法。当算法执行时，输入的资料通常会被要输出的部份覆盖掉。

同 本章前面题：LeetCode: 面试题 01.08. 零矩阵

LeetCode：54. 螺旋矩阵

https://leetcode-cn.com/problems/spiral-matrix/

按照题意进行模拟。可以实现定义一下上（i-1, j）、下(i+1,j)、左(i,j-1)、右(i,j+1)的边界，然后按照逆时针的顺序从边界上依次访问元素。

当访问完当前边界之后，要更新一下边界位置，缩小范围，方便下一轮进行访问。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
         # 矩阵的范围坐标死了
        up, down, left, right = 0, len(matrix)-1, 0, len(matrix[0])-1

        ans = []

        # 一直循环 直到循环完
        while True:
             # 左到右
            for i in range(left, right + 1):
                ans.append(matrix[up][i])
            up += 1
            # 如果加完之后超出范围了 那么退出循环
            if up > down:
                break

            # 上到下   
            for i in range(up, down + 1):
                ans.append(matrix[i][right])
            right -= 1
            if right < left:
                break

             # 右到左   
            for i in range(right, left - 1, -1):
                ans.append(matrix[down][i])
            down -= 1
            if down < up:
                break

            #下到上
            for i in range(down, up - 1, -1):
                ans.append(matrix[i][left])
            left += 1
            if left > right:
                break

        return ans

LeetCode 289. 生命游戏

https://leetcode-cn.com/problems/game-of-life/

• 【方法一】暴力
• 弄个函数 把这四种情况 写一下
• 然后 弄个新数组，然后开始查周围八个位置的1，结果输入函数 输出

时间复杂度O(MN);空间复杂度O(MN)

• 【方法二】原地算法

类似于零矩阵题，用一个变量来标记 是否状态发生变化了。细胞的状态总共有四种情况：

• 死细胞 -> 死细胞，即 0 -> 0。
• 死细胞 -> 活细胞，即 0 -> 1。
• 活细胞 -> 活细胞，即 1 -> 1。
• 活细胞 -> 死细胞，即 1 -> 0。

我们只考虑两种 状态变化的情况：

• 我们把活细胞 -> 死细胞暂时标记为 -1：这样abs(-1)可以表示原来是活细胞；-1又可以当个标志，也就是实际上最后活细胞 -> 死细胞要-1变为0
• 然后把死细胞 -> 活细胞暂时标记为2，计算活细胞个数的时候，我们用abs（） == 1判断，统计原活细胞的时候正好排除这个2（本来就是死细胞）。2又是标记，最后将2 变为1(活细胞)即可

步骤：
① 计算周围活细胞数量
② 根据周围活细胞数，判断（不超边界；绝对值 ==1）：活细胞 -> 死细胞暂时标记为 -1；死细胞 -> 活细胞暂时标记为2
③ 最后原本矩阵里-1 的改为0； 2 改为1

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        #  右，右上，上，左上，左，左下，下，右下 八个方位
        directions = {(1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1)}

        rows = len(board)
        cols = len(board[0])

        for row in range(rows):
            for col in range(cols):
                lives = 0

                #8个方向
                for direction in directions:
                    new_row = row + direction[0]
                    new_col = col + direction[1]

                    # 边界判断并且计算周围综述
                    if 0 <= new_row < rows and 0 <= new_col < cols and abs(board[new_row][new_col]) == 1:
                        lives += 1


                if board[row][col] == 1 and (lives < 2 or lives > 3):
                    board[row][col] = -1
                if board[row][col] == 0 and lives == 3:
                    #这里面之所没有影响是因为abs(board[new_row][new_col]) == 1把2的情况屏蔽了，所以只起到了标记
                    board[row][col] = 2

        for row in range(rows):
            for col in range(cols):
                if board[row][col] == -1:
                    board[row][col] = 0
                elif board[row][col] == 2:
                    board[row][col] = 1

最后

以上就是等待鼠标为你收集整理的【LeetCode练习|算法通关手册：Python版】01. 数组篇_数组基础知识1. 数组基础知识2. 数组的基本操作3 数组基础题目的全部内容，希望文章能够帮你解决【LeetCode练习|算法通关手册：Python版】01. 数组篇_数组基础知识1. 数组基础知识2. 数组的基本操作3 数组基础题目所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。