LeetCode双周赛解题：字符串处理与动态规划实战-开发者社区

1. 比赛概述与解题思路

上周参加了LeetCode第179场双周赛，这次比赛题目质量不错，前三题涵盖了字符串处理、数学思维和贪心算法等典型考点。作为每周的固定训练，这类比赛对保持算法手感很有帮助。下面分享我的解题思路和实现细节，特别是一些容易踩坑的地方。

2. Q1：生成交替二进制字符串的最少操作数

2.1 题目分析

给定一个二进制字符串s，我们可以将任意'0'变为'1'或'1'变为'0'。要求计算出使字符串变成交替字符串（即相邻字符不相同）所需的最少操作次数。

示例：输入：s = "0100" 输出：1 解释：将最后一个字符改为'1'即可得到"0101"

2.2 解题思路

这道题关键在于认识到交替字符串只有两种可能形式：

以'0'开头：010101...
以'1'开头：101010...

因此只需要计算将原字符串转换成这两种形式各自需要的操作次数，取较小值即可。

2.3 代码实现

def minOperations(s): cnt1 = cnt2 = 0 for i in range(len(s)): # 第一种情况：偶数位为0，奇数位为1 if i % 2 == 0: if s[i] != '0': cnt1 += 1 else: if s[i] != '1': cnt1 += 1 # 第二种情况：偶数位为1，奇数位为0 if i % 2 == 0: if s[i] != '1': cnt2 += 1 else: if s[i] != '0': cnt2 += 1 return min(cnt1, cnt2)

2.4 优化技巧

可以观察到两种情况的计数是互补的，因此可以只计算一种情况，另一种情况用字符串长度减去已计算的结果：

def minOperations(s): cnt = 0 for i in range(len(s)): expected = '0' if i % 2 == 0 else '1' if s[i] != expected: cnt += 1 return min(cnt, len(s) - cnt)

注意：边界情况要考虑空字符串和单字符字符串，这两种情况操作数都是0。

3. Q2：统计美丽子数组数目

3.1 题目描述

给定一个二进制数组nums，如果一个子数组的异或结果为0，则称这个子数组是美丽的。要求统计美丽子数组的数目。

示例：输入：nums = [4,3,1,2,4] 输出：2 解释：美丽子数组为[4,3,1,2]和[2,4]

3.2 解题思路

这道题需要利用前缀异或和哈希表的技巧：

计算前缀异或数组prefix，其中prefix[i]表示nums[0]^nums[1]^...^nums[i-1]
使用哈希表记录每个异或值出现的次数
当某个异或值再次出现时，说明这两个位置之间的子数组异或结果为0

3.3 代码实现

from collections import defaultdict def countBeautifulSubarrays(nums): prefix = 0 count = defaultdict(int) count[0] = 1 # 初始状态 res = 0 for num in nums: prefix ^= num res += count[prefix] count[prefix] += 1 return res

3.4 复杂度分析

时间复杂度：O(n)，只需遍历数组一次
空间复杂度：O(n)，哈希表存储最多n个不同的异或值

关键点：初始状态count[0]=1的处理很重要，这表示空数组的异或结果为0。

4. Q3：最大化网格幸福感

4.1 题目描述

给定一个m×n的网格，可以在每个格子放置内向、外向的人或者不放置。放置规则：

内向人：初始幸福感120，每有一个邻居减少30
外向人：初始幸福感40，每有一个邻居增加20 求最大可能的网格总幸福感。

示例：输入：m=2, n=3, introvertsCount=1, extrovertsCount=2 输出：240

4.2 解题思路

这是一道典型的动态规划题目，需要考虑：

状态表示：dp[i][j][a][b]表示处理到第i行第j列时，剩余a个内向人和b个外向人时的最大幸福感
状态转移：对于每个格子，考虑三种选择（不放、放内向、放外向）带来的幸福感变化
边界条件：网格边界和人数限制

4.3 代码实现

def getMaxGridHappiness(m, n, introvertsCount, extrovertsCount): # 状态压缩：用三进制表示前n个格子的状态（0:空,1:内向,2:外向） state_size = 3 ** n dp = [[[[-1]*(extrovertsCount+1) for _ in range(introvertsCount+1)] for _ in range(n)] for _ in range(m)] def dfs(row, col, a, b, prev_state): if row == m: return 0 if col == n: return dfs(row+1, 0, a, b, prev_state) if dp[row][col][a][b] != -1: return dp[row][col][a][b] max_happiness = 0 # 选择1：不放人 new_state = (prev_state * 3) % state_size max_happiness = dfs(row, col+1, a, b, new_state) # 选择2：放内向人 if a > 0: happiness = 120 # 检查左边邻居 if col > 0 and (prev_state // (3 ** (n-1))) % 3 != 0: happiness -= 30 neighbor_type = (prev_state // (3 ** (n-1))) % 3 if neighbor_type == 1: # 内向邻居 happiness -= 30 else: # 外向邻居 happiness += 20 - 30 # 检查上边邻居 if row > 0 and prev_state % 3 != 0: happiness -= 30 neighbor_type = prev_state % 3 if neighbor_type == 1: happiness -= 30 else: happiness += 20 - 30 new_state = (prev_state * 3 + 1) % state_size current = happiness + dfs(row, col+1, a-1, b, new_state) max_happiness = max(max_happiness, current) # 选择3：放外向人 if b > 0: happiness = 40 # 检查左边邻居 if col > 0 and (prev_state // (3 ** (n-1))) % 3 != 0: happiness += 20 neighbor_type = (prev_state // (3 ** (n-1))) % 3 if neighbor_type == 1: # 内向邻居 happiness -= 30 else: # 外向邻居 happiness += 20 # 检查上边邻居 if row > 0 and prev_state % 3 != 0: happiness += 20 neighbor_type = prev_state % 3 if neighbor_type == 1: happiness -= 30 else: happiness += 20 new_state = (prev_state * 3 + 2) % state_size current = happiness + dfs(row, col+1, a, b-1, new_state) max_happiness = max(max_happiness, current) dp[row][col][a][b] = max_happiness return max_happiness return dfs(0, 0, introvertsCount, extrovertsCount, 0)