企业官网建设流程全解析

1. 算法题解合集概述

今天想和大家分享三个经典算法问题的解题思路：回文子串统计、不相邻取数最大和、空调遥控器按键优化。这三个问题分别来自字符串处理、动态规划和模拟算法领域，都是面试和竞赛中的高频考点。我结合自己刷题和面试官的经验，整理出一套可复用的解题框架。

这三个问题看似独立，实则都体现了算法设计的核心思想：如何将复杂问题分解为可重复解决的子问题。回文子串考察对字符串特性的把握，不相邻取数考验动态规划的状态定义能力，空调遥控器则需要对模拟过程进行数学抽象。

2. 回文子串统计问题

2.1 问题定义与暴力解法

给定一个字符串s，统计其中回文子串的数量。回文子串指正读反读都相同的连续字符序列。例如"aaa"包含6个回文子串："a","a","a","aa","aa","aaa"。

最直观的解法是暴力枚举所有可能的子串，然后检查是否为回文。时间复杂度O(n³)：

def countSubstrings(s: str) -> int: count = 0 n = len(s) for i in range(n): for j in range(i, n): if s[i:j+1] == s[i:j+1][::-1]: count += 1 return count

2.2 中心扩散法优化

观察到回文串的中心可能是单个字符或两个相同字符，我们可以枚举所有可能的中心，然后向两侧扩展：

def countSubstrings(s: str) -> int: def expand(l, r): cnt = 0 while l >=0 and r < len(s) and s[l] == s[r]: cnt += 1 l -= 1 r += 1 return cnt res = 0 for i in range(len(s)): res += expand(i, i) # 奇数长度 res += expand(i, i+1) # 偶数长度 return res

时间复杂度优化到O(n²)，空间复杂度O(1)。这是处理回文问题的经典模式，Manacher算法可以进一步优化到O(n)，但实现较复杂。

注意：中心扩散时边界条件容易出错，特别是偶数长度情况下的初始位置设置。

3. 不相邻取数问题

3.1 问题建模

给定一个整数数组nums，要求选取若干不相邻的数使得和最大。例如[1,2,3,1]的最优解是1+3=4。

这是典型的动态规划问题，状态转移方程为： dp[i] = max(dp[i-1], dp[i-2]+nums[i])

3.2 动态规划实现

def rob(nums: List[int]) -> int: n = len(nums) if n == 1: return nums[0] dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, n): dp[i] = max(dp[i-1], dp[i-2] + nums[i]) return dp[-1]

可以进一步优化空间复杂度到O(1)：

def rob(nums: List[int]) -> int: prev, curr = 0, 0 for num in nums: prev, curr = curr, max(curr, prev + num) return curr

3.3 变种问题

如果数组首尾相连形成环形，需要分别计算[0,n-2]和[1,n-1]两种情况的最大值：

def rob(nums: List[int]) -> int: def helper(start, end): prev, curr = 0, 0 for i in range(start, end+1): prev, curr = curr, max(curr, prev + nums[i]) return curr n = len(nums) if n == 1: return nums[0] return max(helper(0, n-2), helper(1, n-1))

4. 空调遥控器问题

4.1 问题描述

空调遥控器有0-9数字键和上下键，初始显示0。给定目标温度T，求最少按键次数。按上下键每次±1，数字键直接输入。

例如T=18的最优操作： 按1→按8，共2次；比按↑18次更优。

4.2 解题思路

这个问题需要比较两种策略：

1. 纯按键：次数等于|T|
2. 数字输入：数字位数 + 最后调整（按↑或↓）

需要特别注意边界情况，如T=10时直接输入"10"比按↑10次更优。

4.3 代码实现

def minPresses(T: int) -> int: if T == 0: return 0 # 纯按键方案 pure_button = abs(T) # 数字输入方案 min_presses = float('inf') for num in range(max(0, T-5), T+6): # 搜索附近可能更优的数字 digits = list(str(abs(num))) presses = len(digits) + abs(T - num) if presses < min_presses: min_presses = presses return min(pure_button, min_presses)

4.4 优化思路

实际上最优解要么是纯按键，要么是直接输入T的绝对值（如果T>9），或者T附近±5范围内的数字。因此可以简化为：

def minPresses(T: int) -> int: T = abs(T) if T < 10: return min(T, 1 + (10 - T)) # 比较直接按和输入10再下调 digits = len(str(T)) return min(T, digits + abs(T - int(str(T)[:-1] + '9'))) # 比较纯按键和数字输入

5. 算法思想总结

这三个问题展示了不同的算法范式：

1. 回文子串：中心枚举与扩散思想
2. 不相邻取数：动态规划的状态设计与转移
3. 空调遥控器：模拟与数学优化的结合

在解决算法问题时，我通常遵循以下步骤：

1. 明确问题边界条件和特殊用例
2. 尝试暴力解法，找出重复计算部分
3. 设计更优的数据结构或算法模式
4. 考虑空间和时间复杂度的平衡
5. 验证边缘情况

动态规划问题尤其要注意状态定义是否完备，转移方程是否覆盖所有可能性。对于模拟类问题，要先理清所有操作规则，再寻找数学规律进行优化。