day-02数组题目总结笔记

数组题目总结笔记（二）

目录

• 最长公共前缀
• 加一
• 杨辉三角
• 买卖股票的最佳时机
• 多数元素

6. 最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。

示例：

输入：strs = ["flower", "flow", "flight"] 输出："fl" 输入：strs = ["dog", "racecar", "car"] 输出："" 解释：输入不存在公共前缀。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]如果非空，则仅由小写英文字母组成

解法：横向扫描

classSolution:deflongestCommonPrefix(self,strs:List[str])->str:# 处理空数组情况ifnotstrs:return""# 以第一个字符串作为基准prefix=strs[0]# 遍历剩余的字符串foriinrange(1,len(strs)):# 关键：不断缩短前缀，直到找到公共前缀whilenotstrs[i].startswith(prefix):prefix=prefix[:-1]# 如果前缀为空，说明没有公共前缀ifnotprefix:return""returnprefix

代码注释

• if not strs: return "": 处理空数组的边界情况，如果没有字符串，直接返回空字符串
• prefix = strs[0]: 将第一个字符串作为初始前缀，这是我们的基准字符串
• for i in range(1, len(strs)): 从第二个字符串开始遍历，与基准前缀进行比较
• while not strs[i].startswith(prefix): **这是核心逻辑！**当当前字符串不以prefix开头时，说明prefix太长了
• prefix = prefix[:-1]: **关键操作！**每次将前缀缩短一个字符（去掉最后一个字符）
• if not prefix: return "": 如果前缀被缩短到空字符串，说明没有任何公共前缀，直接返回
• return prefix: 遍历完所有字符串后，prefix就是最长公共前缀

知识点讲解

1. 横向扫描法（逐字符串比较）

• 核心思想：以第一个字符串为基准，依次与其他字符串比较，不断缩短前缀直到找到公共部分
• 时间复杂度：O(S)，其中S是所有字符串中字符的总数
• 空间复杂度：O(1)，只使用了几个变量
• 优势：思路直观，代码简洁

2. 为什么用 startswith() 方法？

• startswith(prefix)检查字符串是否以指定前缀开头，时间复杂度 O(m)，其中m是前缀长度
• 这是Python字符串的内置方法，比手动逐个字符比较更高效
• 示例：strs[i].startswith("fl")检查 “flower” 是否以 “fl” 开头，返回 True

3. 执行过程示例

初始：strs = ["flower", "flow", "flight"] prefix = "flower" 第1次循环（i=1, strs[1]="flow"）： "flow".startswith("flower") = False prefix = "flowe"（去掉最后一个字符'r'） "flow".startswith("flowe") = False prefix = "flow"（去掉最后一个字符'e'） "flow".startswith("flow") = True ✓ 此时 prefix = "flow" 第2次循环（i=2, strs[2]="flight"）： "flight".startswith("flow") = False prefix = "flo"（去掉最后一个字符'w'） "flight".startswith("flo") = False prefix = "fl"（去掉最后一个字符'o'） "flight".startswith("fl") = True ✓ 此时 prefix = "fl" 最终返回："fl"

4. 其他解法思路

• 纵向扫描：逐个字符位置比较所有字符串，遇到不同字符就停止
• 分治法：将数组分成两部分，分别求公共前缀，再合并
• 二分查找：对最短字符串的长度进行二分，检查某个长度是否满足公共前缀

5. 边界情况处理

• 空数组：返回 “”
• 只有一个字符串：返回该字符串本身
• 存在空字符串：如果数组中存在空字符串，公共前缀一定是 “”
• 所有字符串完全相同：返回任意一个字符串

7. 加一

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例：

输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。加 1 后得到 123 + 1 = 124。因此，结果应该是 [1,2,4]。 输入：digits = [4,3,2,1] 输出：[4,3,2,2] 解释：输入数组表示数字 4321。加 1 后得到 4321 + 1 = 4322。因此，结果应该是 [4,3,2,2]。 输入：digits = [9] 输出：[1,0] 解释：输入数组表示数字 9。加 1 后得到了 9 + 1 = 10。因此，结果应该是 [1,0]。

解法：模拟加法进位

classSolution:defplusOne(self,digits:List[int])->List[int]:# 从最后一位开始，加1foriinrange(len(digits)-1,-1,-1):# 关键：当前位加1后，如果小于10，直接返回digits[i]+=1digits[i]%=10# 如果当前位不是0，说明没有进位，直接返回ifdigits[i]!=0:returndigits# 如果所有位都是0，说明需要增加一位（如999+1=1000）return[1]+digits

代码注释

• for i in range(len(digits) - 1, -1, -1): 从数组末尾开始向前遍历，模拟从个位到高位的加法
• digits[i] += 1: **关键操作！**当前位加1
• digits[i] %= 10: **关键操作！**取模运算，如果当前位是10，则变为0（进位），否则保持原值
• if digits[i] != 0: return digits: 如果当前位不是0，说明没有产生进位，加法完成，直接返回
• return [1] + digits: **特殊情况！**如果所有位都变成了0（如999+1），需要在最前面添加一个1

知识点讲解

1. 模拟手工加法的过程

• 核心思想：从最低位（数组末尾）开始，逐位加1，处理进位
• 就像我们手工计算一样：个位加1，如果等于10就进位，十位加1，以此类推
• 时间复杂度：O(n)，最坏情况需要遍历整个数组
• 空间复杂度：O(1)，除了结果数组外只使用了常数空间

2. 为什么用 %= 10（取模运算）？

• digits[i] %= 10等价于digits[i] = digits[i] % 10
• 当digits[i] = 10时，10 % 10 = 0（表示进位）
• 当digits[i] < 10时，digits[i] % 10 = digits[i]（保持不变）
• 这是处理进位的简洁方法，避免了 if-else 判断

3. 执行过程示例

示例1：digits = [1,2,3]

初始：digits = [1,2,3] i=2（个位）： digits[2] += 1 → digits[2] = 4 digits[2] %= 10 → digits[2] = 4 digits[2] != 0 → 返回 [1,2,4] ✓

示例2：digits = [1,9,9]

初始：digits = [1,9,9] i=2（个位）： digits[2] += 1 → digits[2] = 10 digits[2] %= 10 → digits[2] = 0（进位） digits[2] == 0 → 继续循环 i=1（十位）： digits[1] += 1 → digits[1] = 10 digits[1] %= 10 → digits[1] = 0（进位） digits[1] == 0 → 继续循环 i=0（百位）： digits[0] += 1 → digits[0] = 2 digits[0] %= 10 → digits[0] = 2 digits[0] != 0 → 返回 [2,0,0] ✓

示例3：digits = [9,9,9]

初始：digits = [9,9,9] i=2：digits[2] = 0（进位） i=1：digits[1] = 0（进位） i=0：digits[0] = 0（进位） 所有位都是0 → 返回 [1] + [0,0,0] = [1,0,0,0] ✓

4. 关键技巧：提前返回优化

• if digits[i] != 0: return digits这行代码非常关键！
• 一旦某一位加1后不是0，说明没有产生进位，后面的高位不需要再处理
• 这大大提高了效率，避免了不必要的遍历
• 例如：[1,2,3] 加1时，个位变成4后就可以直接返回，不需要检查十位和百位

5. 特殊情况：全9的情况

• 当所有位都是9时（如999），加1后所有位都变成0，需要在最前面添加1
• return [1] + digits巧妙地处理了这种情况
• [1] + [0,0,0] = [1,0,0,0]，正确表示了1000

6. 为什么从后往前遍历？

• 因为加法是从最低位（个位）开始的
• 如果从前往后遍历，无法正确处理进位
• 例如：199 + 1，必须先处理个位，产生进位后再处理十位

8. 杨辉三角

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例：

输入：numRows = 5 输出：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 输入：numRows = 1 输出：[[1]]

解法：动态规划（逐行构建）

classSolution:defgenerate(self,numRows:int)->List[List[int]]:# 初始化结果列表result=[]# 遍历每一行foriinrange(numRows):# 创建当前行，初始化为全1row=[1]*(i+1)# 关键：从第2行开始（i>=1），计算中间的值forjinrange(1,i):# 核心公式：当前值 = 上一行的左上方 + 上一行的右上方row[j]=result[i-1][j-1]+result[i-1][j]# 将当前行添加到结果中result.append(row)returnresult

代码注释

• result = []: 初始化结果列表，用于存储所有行
• for i in range(numRows): 遍历每一行，i表示行号（从0开始）
• row = [1] * (i + 1): **关键初始化！**创建长度为(i+1)的列表，全部初始化为1
  • 第0行有1个元素，第1行有2个元素，第i行有(i+1)个元素
  • 首尾都是1，所以先全部设为1，再修改中间的值
• for j in range(1, i): 从第2行开始（i>=1），遍历中间的元素（不包括首尾）
  • j从1开始，到i-1结束，正好是中间的元素
• row[j] = result[i - 1][j - 1] + result[i - 1][j]:核心公式！
  • result[i - 1]是上一行
  • result[i - 1][j - 1]是上一行的左上方元素
  • result[i - 1][j]是上一行的右上方元素（同一列）
• result.append(row): 将当前行添加到结果中

知识点讲解

1. 杨辉三角的数学性质

• 杨辉三角是二项式系数的三角形排列
• 第n行第k个数 = C(n,k) = n! / (k! * (n-k)!)
• 每个数等于它上方两个数的和（除了首尾的1）
• 对称性：第n行从左到右和从右到左是对称的

2. 动态规划思想

• 状态定义：result[i][j]表示第i行第j列的值
• 状态转移：result[i][j] = result[i-1][j-1] + result[i-1][j]
• 边界条件：每行的首尾都是1
• 核心思想：利用上一行的结果计算当前行，避免重复计算

3. 为什么先初始化为全1？

• row = [1] * (i + 1)这行代码非常巧妙！
• 杨辉三角的每一行首尾都是1，中间的值需要计算
• 先全部设为1，然后只修改中间的值，代码更简洁
• 避免了分别处理首尾和中间的复杂逻辑

4. 执行过程示例

numRows = 5 i=0（第1行）： row = [1] * 1 = [1] j循环不执行（因为range(1,0)为空） result = [[1]] i=1（第2行）： row = [1] * 2 = [1,1] j循环不执行（因为range(1,1)为空） result = [[1], [1,1]] i=2（第3行）： row = [1] * 3 = [1,1,1] j=1: row[1] = result[1][0] + result[1][1] = 1 + 1 = 2 row = [1,2,1] result = [[1], [1,1], [1,2,1]] i=3（第4行）： row = [1] * 4 = [1,1,1,1] j=1: row[1] = result[2][0] + result[2][1] = 1 + 2 = 3 j=2: row[2] = result[2][1] + result[2][2] = 2 + 1 = 3 row = [1,3,3,1] result = [[1], [1,1], [1,2,1], [1,3,3,1]] i=4（第5行）： row = [1] * 5 = [1,1,1,1,1] j=1: row[1] = result[3][0] + result[3][1] = 1 + 3 = 4 j=2: row[2] = result[3][1] + result[3][2] = 3 + 3 = 6 j=3: row[3] = result[3][2] + result[3][3] = 3 + 1 = 4 row = [1,4,6,4,1] result = [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]

5. 索引关系详解

• result[i-1][j-1]：上一行的左上方元素（第i-1行第j-1列）
• result[i-1][j]：上一行的正上方元素（同一列，第i-1行第j列）
• 这两个元素在杨辉三角中正好是当前元素的上方两个数

6. 时间复杂度与空间复杂度

• 时间复杂度：O(numRows²)，需要计算O(numRows²)个元素
• 空间复杂度：O(numRows²)，需要存储所有行的数据
• 优化空间：如果只需要返回第n行，可以优化到O(n)空间

7. 边界情况处理

• numRows = 0：返回空列表 []
• numRows = 1：返回 [[1]]
• 每行的首尾元素：始终为1，不需要计算

9. 买卖股票的最佳时机

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例：

输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。 注意利润不能是 7-1 = 6，因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 10^5

解法：一次遍历（贪心算法）

classSolution:defmaxProfit(self,prices:List[int])->int:# 初始化最小买入价格和最大利润min_price=float('inf')max_profit=0# 遍历每一天的价格forpriceinprices:# 关键：更新最小买入价格min_price=min(min_price,price)# 关键：计算当前卖出能获得的利润，并更新最大利润max_profit=max(max_profit,price-min_price)returnmax_profit

代码注释

• min_price = float('inf'): 初始化最小买入价格为无穷大，确保第一次比较时能正确更新
• max_profit = 0: 初始化最大利润为0，如果无法盈利则返回0
• for price in prices: 遍历每一天的股票价格
• min_price = min(min_price, price): **关键操作！**记录到目前为止的最低买入价格
  • 如果今天的价格更低，更新最小买入价格
  • 这样我们总是用历史最低价作为买入价格
• max_profit = max(max_profit, price - min_price):核心逻辑！
  • 计算如果今天卖出能获得的利润 = 今天价格 - 历史最低买入价
  • 如果这个利润大于之前记录的最大利润，就更新最大利润
• return max_profit: 返回整个过程中能获得的最大利润

知识点讲解

1. 贪心算法思想

• 核心思想：在遍历过程中，维护两个关键变量
  • 历史最低买入价格（min_price）
  • 到目前为止的最大利润（max_profit）
• 贪心策略：对于每一天，我们考虑如果在这一天卖出，能获得的最大利润
  • 利润 = 今天价格 - 历史最低买入价
  • 我们只需要记录最大的利润即可

2. 为什么只需要一次遍历？

• 关键 insight：要获得最大利润，必须在历史最低价买入
• 如果我们知道历史最低价是 min_price
• 那么在第i天卖出的利润就是prices[i] - min_price
• 我们只需要遍历一次，同时更新最低价和最大利润
• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：O(1)，只使用了两个变量

3. 执行过程示例

prices = [7,1,5,3,6,4] 初始：min_price = inf, max_profit = 0 第1天（price=7）： min_price = min(inf, 7) = 7 max_profit = max(0, 7-7) = max(0, 0) = 0 第2天（price=1）： min_price = min(7, 1) = 1 ← 更新最低价 max_profit = max(0, 1-1) = max(0, 0) = 0 第3天（price=5）： min_price = min(1, 5) = 1 ← 保持最低价 max_profit = max(0, 5-1) = max(0, 4) = 4 ← 更新最大利润 第4天（price=3）： min_price = min(1, 3) = 1 max_profit = max(4, 3-1) = max(4, 2) = 4 第5天（price=6）： min_price = min(1, 6) = 1 max_profit = max(4, 6-1) = max(4, 5) = 5 ← 更新最大利润 第6天（price=4）： min_price = min(1, 4) = 1 max_profit = max(5, 4-1) = max(5, 3) = 5 最终返回：5

4. 为什么用 float(‘inf’)？

• float('inf')表示正无穷大
• 初始化 min_price 为无穷大，确保第一次比较时 prices[0] 一定能更新 min_price
• 如果初始化为 prices[0]，代码也能工作，但使用 inf 更通用
• Python中也可以用sys.maxsize或prices[0]（如果数组非空）

5. 关键理解：为什么这样能保证"先买后卖"？

• 虽然我们在遍历过程中同时更新买入价和卖出价
• 但逻辑上：min_price 记录的是"到目前为止"的最低价
• max_profit 记录的是"如果今天卖出"能获得的最大利润
• 由于我们是从前往后遍历，min_price 总是在当前 price 之前出现的价格
• 所以price - min_price一定是"先买后卖"的利润

6. 边界情况处理

• 空数组：如果 prices 为空，循环不执行，返回 0
• 价格一直下跌：max_profit 始终保持为 0，返回 0
• 价格一直上涨：min_price 是第一个价格，max_profit 是最后一个价格减去第一个价格

7. 动态规划视角（扩展理解）

这个问题也可以用动态规划解决：

• dp[i][0]：第i天持有股票的最大利润（买入）
• dp[i][1]：第i天不持有股票的最大利润（卖出）
• 但贪心算法更简洁高效，空间复杂度O(1)

10. 多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例：

输入：nums = [3,2,3] 输出：3 输入：nums = [2,2,1,1,1,2,2] 输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

解法：Boyer-Moore 投票算法

classSolution:defmajorityElement(self,nums:List[int])->int:# 初始化候选人和计数器candidate=Nonecount=0# 第一阶段：找出可能的多数元素fornuminnums:# 关键：如果计数器为0，选择当前元素作为候选人ifcount==0:candidate=num# 关键：如果当前元素等于候选人，计数器加1；否则减1ifnum==candidate:count+=1else:count-=1# 第二阶段：验证（本题可以省略，因为题目保证存在多数元素）# 由于题目保证存在多数元素，candidate 就是答案returncandidate

代码注释

• candidate = None: 初始化候选人为None，表示还没有选择候选人
• count = 0: 初始化计数器为0
• for num in nums: 遍历数组中的每个元素
• if count == 0: candidate = num:关键操作！
  • 当计数器归零时，说明之前的候选人"被抵消完了"
  • 选择当前元素作为新的候选人
  • 这保证了我们总是有一个候选人在"竞争"
• if num == candidate: count += 1: 如果当前元素等于候选人，支持票+1
• else: count -= 1: 如果当前元素不等于候选人，反对票-1（抵消一票）
• return candidate: 遍历结束后，candidate 就是多数元素

知识点讲解

1. Boyer-Moore 投票算法的核心思想

• 算法原理：多数元素的出现次数 > n/2，所以它比其他所有元素加起来还多
• 如果把多数元素看作+1，其他元素看作-1
• 那么所有元素的和一定 > 0
• 算法通过"抵消"的思想，最终剩下的就是多数元素

2. 为什么这个算法有效？

• 关键 insight：多数元素的数量 > n/2
• 假设多数元素有 k 个，其他元素有 n-k 个
• 由于 k > n/2，所以 k > n-k
• 即使所有非多数元素都用来"抵消"多数元素
• 多数元素仍然会有剩余（k - (n-k) = 2k - n > 0）

3. 执行过程示例

示例1：nums = [3,2,3]

初始：candidate = None, count = 0 num=3： count == 0 → candidate = 3 num == candidate → count = 1 num=2： count != 0 → 不更新candidate num != candidate → count = 0（抵消） num=3： count == 0 → candidate = 3 num == candidate → count = 1 最终：candidate = 3 ✓

示例2：nums = [2,2,1,1,1,2,2]

初始：candidate = None, count = 0 num=2：candidate=2, count=1 num=2：candidate=2, count=2 num=1：candidate=2, count=1（抵消） num=1：candidate=2, count=0（抵消） num=1：count==0 → candidate=1, count=1 num=2：candidate=1, count=0（抵消） num=2：count==0 → candidate=2, count=1 最终：candidate = 2 ✓

4. 为什么 count == 0 时要更新 candidate？

• 当 count == 0 时，说明之前的候选人和非候选人"完全抵消"了
• 前面的元素中，候选人和非候选人的数量相等
• 这些元素对后续的结果没有影响，可以"丢弃"
• 从当前位置开始，重新选择候选人
• 这保证了算法能正确找到多数元素

5. 时间复杂度与空间复杂度

• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：O(1)，只使用了两个变量（candidate 和 count）
• **这是最优解！**比哈希表方法（O(n)空间）更优

6. 与其他方法的对比

7. 算法正确性证明（简化版）

• 设多数元素为 x，出现次数为 k（k > n/2）
• 其他元素总数为 n-k（n-k < n/2）
• 算法过程中：
  • 每个 x 贡献 +1
  • 每个非 x 贡献 -1
• 最终计数 = k - (n-k) = 2k - n > 0
• 所以最终 candidate 一定是 x

8. 边界情况处理

• 数组只有一个元素：candidate 就是该元素，count = 1
• 所有元素相同：candidate 始终保持不变，count 一直增加
• 题目保证存在多数元素：不需要验证阶段

9. 扩展：如果需要验证 candidate 是否是真正的多数元素？

如果题目不保证存在多数元素，需要第二阶段验证：

count=0fornuminnums:ifnum==candidate:count+=1ifcount>len(nums)//2:returncandidateelse:returnNone# 或抛出异常

总结：数组题目的核心技巧（续）

6. 字符串处理技巧

• startswith()方法：检查前缀，用于最长公共前缀问题
• 字符串切片：prefix[:-1]用于缩短字符串
• 时间复杂度：字符串操作通常是 O(m)，m 是字符串长度

7. 模拟运算

• 模拟手工计算过程：如加一问题，从低位到高位处理
• 取模运算：用于处理进位，digits[i] %= 10
• 提前返回优化：一旦确定结果就可以返回，避免不必要的计算

8. 动态规划

• 状态定义：明确dp[i]或dp[i][j]的含义
• 状态转移：找到当前状态与之前状态的关系
• 边界条件：处理初始状态和特殊情况
• 杨辉三角：典型的二维动态规划问题

9. 贪心算法

• 局部最优：每一步都做出当前最优的选择
• 全局最优：局部最优的选择最终导致全局最优
• 买卖股票：维护历史最低价和最大利润
• 关键：证明贪心策略的正确性

10. 投票算法

• Boyer-Moore 算法：用于找多数元素
• 核心思想：抵消 + 重新选择
• 优势：O(1) 空间复杂度，O(n) 时间复杂度
• 适用场景：找出现次数超过一半的元素

思考题

1. 最长公共前缀的变种

题目：如果要求找到最长公共后缀，如何修改代码？

提示：可以从后往前比较，或者反转字符串后使用相同的方法。

2. 加一的扩展

题目：如果不是加1，而是加一个任意的数字 k，如何实现？

提示：需要处理更复杂的进位情况，可能需要额外的变量来存储进位值。

3. 杨辉三角的变种

题目：如果只需要返回第 n 行（从0开始），如何优化空间复杂度到 O(n)？

提示：只需要维护上一行的结果，不需要存储所有行。

4. 买卖股票的扩展

题目：如果可以多次买卖（但必须先卖后买），如何计算最大利润？

提示：贪心策略：只要后一天价格高于前一天，就进行交易。

5. 多数元素的扩展

题目：如果数组中不存在多数元素，如何修改代码来返回 None？

提示：需要添加验证阶段，统计 candidate 的实际出现次数。

推荐练习顺序

• 入门：最长公共前缀、加一
• 进阶：杨辉三角、多数元素
• 提高：买卖股票的最佳时机

版权声明：本文为原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。