一、字符串反转:
1. 题目描述(改编版)
程序员小明买奶茶时突发奇想:把"珍珠奶茶"的后2个字符移到前面,变成"茶奶珍珠"。现在给你一个字符串s和整数k,请用代码实现这种"奶茶式反转"(保证k小于字符串长度)。
2. 思考
普通青年:新建字符串,先复制后k个字符,再拼接前面的字符
文艺青年:三次反转,比如"abcd"(k=2):
反转整个字符串 → "dcba"
反转前k个字符 → "cdba"
反转剩余字符 → "cdab"
3. 代码实现
二、递归算法:
1. 题目描述(改编版)
程序员要搬3个硬盘(A塔→C塔),每次只能搬1个,且大盘不能压小盘。但他的猫总把中间的B塔当猫抓板,导致B塔随时可能"崩溃"。请用递归计算:至少需要搬多少次才能完成?如果有n个硬盘呢?
2. 思考
生活类比:把n个硬盘搬家拆解为3步:
先把n-1个硬盘从A→B
把最大的硬盘从A→C
再把n-1个硬盘从B→C
数学公式:次数f(n) = 2*f(n-1) + 1,边界条件f(1)=1。
3. 代码实现
三、动态规划(dp):
1. 题目描述(改编版)
街机厅打地鼠游戏中,每个地鼠洞有分数(正或负,可能钻出炸弹扣100分)。你只有3次打地鼠机会,每次可打连续的多个洞(至少1个),但打过的洞不能重复打。**请计算最高得分(**比如洞的分数为[3, -1, 4, -2, 5])。
2. 思考
暴力陷阱:枚举所有可能的连续区间组合(如[3]、[4,5]),但n=100时会炸
DP思路:用dp[i][j]表示前i个洞用j次机会的最大得分,转移方程:
dp[i][j] = max(dp[k][j-1] + sum(k+1~i))
3. 代码实现
// 测试:nums = [3,-1,4,-2,5], k=3 → 3 + 4 +5 = 12分
四、实战小妙招:
递归:超过1e5规模就用迭代。
动态规划先画表格:把dp[i][j]的含义写在纸上。
字符串处理用STL:reverse/substr/stringstream能少写n行代码。