《程序员模拟器》生涯困难13～23关攻略（下）
修改于1 小时前8 浏览攻略
这份攻略整理的是一些过关思路，不是唯一解，更不是标准答案。很多关卡我自己也卡过，后来翻论坛、看别人分享才慢慢摸清楚。本人非专业人士，如果有写错的地方，欢迎大家指出！游戏有自己的规则，哪怕你写过 JavaScript，也得重新适应——比如游戏键盘里打不出冒号、分号和问号等，常见的 for 循环、对象字面量还有简洁的判断也就用不上。如果你是第一次接触困难难度，建议先自己试试。这部分的题目已经逐渐变态了——不只是动动脑子就可以的事情了，还得靠集思广益，实在卡住再来看攻略也不迟。
最后还是那句话：解法没有高下之分，能跑通就是好代码，享受琢磨的过程就好。
PS如果想单独复制某一关的代码，建议用手机浏览器打开此攻略，而不是客户端
生涯模式攻略导航：
13. 最长公共子序列
二维动态规划。dp[i][j] 表示：str1 的前 i 个字符 和 str2 的前 j 个字符 的最长公共子序列长度。
· 如果 str1[i-1] == str2[j-1]：这两个字符可以加入子序列，长度 = dp[i-1][j-1] + 1
· 如果不等：要么不要 str1 的这个字符，要么不要 str2 的这个字符，取两者最大值
为了保证不会有负数下标，二维矩阵创建为m+1乘n+1大小，让递推公式在边界上也能统一处理，不用写额外的 if 判断。
用 str1 = "abc"，str2 = "bcd" 举个例子
长度：m = 3，n = 3
所以建一个 4×4 的矩阵（m+1, n+1）
空 b c d
空 [0, 0, 0, 0]
a [0, ?, ?, ?]
b [0, ?, ?, ?]
c [0, ?, ?, ?]
开始填表
i=1（str1 的 'a'）
· j=1（str2 的 'b'）：'a' ≠ 'b'
dp[1][1] = max(dp[0][1]=0, dp[1][0]=0) = 0
· j=2（str2 的 'c'）：'a' ≠ 'c'
dp[1][2] = max(dp[0][2]=0, dp[1][1]=0) = 0
· j=3（str2 的 'd'）：'a' ≠ 'd'
dp[1][3] = max(dp[0][3]=0, dp[1][2]=0) = 0
第1行全是 0，因为 'a' 在 "bcd" 里找不到。
i=2（str1 的 'b'）
· j=1（str2 的 'b'）：'b' = 'b' ✅
dp[2][1] = dp[1][0] + 1 = 0 + 1 = 1
· j=2（str2 的 'c'）：'b' ≠ 'c'
dp[2][2] = max(dp[1][2]=0, dp[2][1]=1) = 1
· j=3（str2 的 'd'）：'b' ≠ 'd'
dp[2][3] = max(dp[1][3]=0, dp[2][2]=1) = 1
i=3（str1 的 'c'）
· j=1（str2 的 'b'）：'c' ≠ 'b'
dp[3][1] = max(dp[2][1]=1, dp[3][0]=0) = 1
· j=2（str2 的 'c'）：'c' = 'c' ✅
dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2
· j=3（str2 的 'd'）：'c' ≠ 'd'
dp[3][3] = max(dp[2][3]=1, dp[3][2]=2) = 2
填完的表格
空 b c d
空 [0, 0, 0, 0]
a [0, 0, 0, 0]
b [0, 1, 1, 1]
c [0, 1, 2, 2]
最终结果：dp[3][3] = 2
最长公共子序列是 "bc"，长度为2。
str1 = 输入[0]
str2 = 输入[1]
m = str1.length
n = str2.length
dp = [...Array(m + 1)].map(() => {
return [...Array(n + 1)].fill(0)
})
i = 1
while (i <= m) {
j = 1
while (j <= n) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = Math.max(
dp[i - 1][j], dp[i][j - 1])
}
j += 1
}
i += 1
}
return dp[m][n]
14. 翻转链表
这题实际上应该叫数组分段反转。输入一个数组和一个步长 step，将数组按每 step 个元素一组进行翻转，最后一组如果元素不足 step 个则保持原样。
这题的关键是组内索引的镜像映射。
在一个长度为 step 的组里，索引从 0 到 step-1：
· 位置 0 应该取原位置 step-1
· 位置 1 应该取原位置 step-2
· ...
· 位置 step-1 应该取原位置 0
也就是说：新位置 i 对应原位置 (step-1-i)
用数学表达就是：
新位置 = 原位置 + (step-1) - 2*(原位置 % step)
也就是代码里的 offset = step - 1 - 2*(i%step)
str=输入[0]
step=输入[1][0]
result=[]
i=0
while ( i<str.length ){
offset=step-1-2*(i%step)
flipIndex=i+offset
if ( flipIndex<str.length ){
result.push(str[flipIndex])
} else {
result.push(str[i])
}
i+=1
}
return result
15. 乘积最大子数组
解法一（暴力枚举）
穷举所有可能的连续子数组，计算乘积，取最大值
num=输入
len=num.length
maxPro=num[0]
i=0
while ( i<len ){
pro=1
j=i
while ( j<len ){
pro*=num[j]
maxPro=Math.max( maxPro,pro )
j+=1
}
i+=1
}
return maxPro
解法二（动态规划）
乘积最大子数组和“最大子数组和”不一样，因为有负数——负数可能变正数。
需要同时维护两个值：
· maxCurr：以当前元素结尾的最大乘积
· minCurr：以当前元素结尾的最小乘积（因为负数乘负数可能变最大）
nums=输入
maxPro = nums[0]
currMax = nums[0]
currMin = nums[0]
i=1
while ( i < nums.length ){
candi = [nums[i],currMax*nums[i],
currMin*nums[i]]
currMax = Math.max(...candi)
currMin = Math.min(...candi)
maxPro = Math.max(
maxPro, currMax)
i+=1
}
return maxPro
16. 矩阵置零
使用额外矩阵来存储结果，避免在原矩阵上直接修改导致的连锁反应
origin=输入
m=origin.length
n=origin[0].length
result=origin.map(a=>[...a])
i=0
while ( i<m ){
j=0
while ( j<n ){
if ( origin[i][j]==0 ){
x=0
while ( x<m ){
result[x][j]=0
x+=1
}
y=0
while ( y<n ){
result[i][y]=0
y+=1
}
}
j+=1
}
i+=1
}
return result
17. 螺旋矩阵
剥洋葱法，逐层剥离，一圈一圈地遍历，每走完一条边就收缩对应的边界。每次移动前检查result.length < rows*cols，防止在最后一步多推元素。比如单行矩阵，向右走完就满了，后面的向下/向左/向上都不会执行。
边界收缩的顺序为
· 向右走完 → 上边界 +1
· 向下走完 → 右边界 -1
· 向左走完 → 下边界 -1
· 向上走完 → 左边界 +1
mtx=输入
rows=mtx.length
cols=mtx[0].length
upMax=0
leftMax=0
downMax=rows-1
rightMax=cols-1
result=[]
while ( result.length<rows*cols ) {
j = leftMax
while ( j<=rightMax&&
result.length<rows*cols ){
result.push(mtx[upMax][j])
j+=1
}
upMax+=1
i = upMax
while ( i<=downMax&&
result.length<rows*cols ){
result.push(mtx[i][rightMax])
i+=1
}
rightMax-=1
j = rightMax
while ( j>=leftMax&&
result.length<rows*cols ){
result.push(mtx[downMax][j])
j-=1
}
downMax-=1
i = downMax
while ( i>=upMax&&
result.length<rows*cols ){
result.push(mtx[i][leftMax])
i-=1
}
leftMax+=1
}
return result
18. 烂橘子
轮次标记法。初始轮次设为2，遍历找到当前轮次橘子，并将四周未感染橘子标记为+1的轮次。当infectedCount==0本轮没有新感染橘子跳出循环，若此时还有未感染橘子hasFresh便返回-1，否则返回轮次-3便是分钟数（因为初始是2，并且最后一轮无感染并没有走分钟数）。
grid=输入
rows=grid.length
cols=grid[0].length
hasFresh=false
turn=2
infectedCount=1
while (infectedCount){
infectedCount=0
hasFresh=false
i=0
while ( i<rows ){
j=0
while ( j<cols ){
if ( grid[i][j]==turn ){
if (i>0&&grid[i-1][j]==1){
grid[i-1][j]=turn+1
infectedCount+=1
}
if (i<rows-1&&grid[i+1][j]==1){
grid[i+1][j]=turn+1
infectedCount+=1
}
if (j>0&&grid[i][j-1]==1){
grid[i][j-1]=turn+1
infectedCount+=1
}
if (j<cols-1&&grid[i][j+1]==1){
grid[i][j+1]=turn+1
infectedCount+=1
}
} else if ( grid[i][j]==1 ){
hasFresh=true
}
j+=1
}
i+=1
}
turn+=1
}
if ( hasFresh ){
return -1
} else {
return turn-3
}
19. 字符串编码
双栈法。numStk数字栈，存重复次数。strStk字符串栈，存之前拼接好的部分。num当前解析的数字。str当前正在构建的字符串。
· 遇到数字：累加解析（因为可能是多位数）
· 遇到 [：把当前数字和当前字符串压栈，然后重置，准备处理括号内的内容
· 遇到 ]：弹出数字和之前的字符串，把当前字符串重复repeat数字次，再拼回之前的字符串
· 遇到字母：直接追加到当前字符串
origin=输入
numStk=[]
strStk=[]
num=0
str=''
i=0
while ( i<origin.length ){
if ( origin[i]>='0'
&&origin[i]<='9'){
num=num*10+(origin[i]-0)
} else if ( origin[i]=='[' ){
numStk.push( num )
strStk.push( str )
num=0
str=''
} else if ( origin[i]==']' ){
rp=numStk.pop( )
str=strStk.pop()+str.repeat(rp)
} else {
str+=origin[i]
}
i+=1
}
return str
20. 完全平方数
四平方定理。拉格朗日四平方和定理即任何正整数都可以表示为4个整数的平方和（包含0），因此，不含0的完全平方数的最少数量有以下4种：
· 一个数如果是完全平方数 → 答案是 1
· 一个数如果形如 4^k*(8m+7) → 答案是 4
· 否则，如果能拆成两个平方数之和 → 答案是 2
· 剩下的情况 → 答案是 3
num=输入
if ( sq(num) ){
return 1
}
if ( sq4(num) ){
return 4
}
i=1
while ( i*i<=num ){
if ( sq(num-i*i) ){
return 2
}
i+=1
}
return 3
function sq(x){
sqrt=Math.floor(Math.sqrt(x))
return x==sqrt*sqrt
}
function sq4(x){
while ( x%4==0 ){
x/=4
}
return x%8==7
}
21. 零钱兑换
动态规划。dp[i] 表示凑成金额 i 所需的最少硬币数。dp[i] = min(dp[i], dp[i - coins[j]] + 1)，意思就是如果选择了当前硬币 coins[j]，那么凑齐金额 i 的最少硬币数可以通过凑齐金额 i - coins[j] 的最少硬币数再加上一个硬币 coins[j] 来得到。 硬币从大到小排序：这样先尝试大面额硬币，更容易快速达到 dp[i]==1，提前退出循环
coins=输入[0]
amount=输入[1][0]
coins.sort((a, b)=>b-a)
dp=Array(amount+1).fill(amount+1)
dp[0]=0
i=1
while ( i<=amount) {
j=0
while ( j<coins.length ){
if ( coins[j]<=i ){
dp[i] = Math.min(
dp[i], dp[i-coins[j]]+1)
if (dp[i]==1) break
}
j+=1
}
i+=1
}
if ( dp[amount]>amount ) return -1
return dp[amount]
22. 不同路径
解法一：组合数公式法。问题等价于：总共需要走(m-1)+(n-1) = m+n-2 步，其中向下走 m-1 步，向右走 n-1 步，所以答案是组合数 C(m+n-2, m-1)。因为组合数有个性质是C(n, k) = C(n, n-k)，所以取最小值k进行计算，减少循环数
m=输入[0]
n=输入[1]
total=m+n-2
k=Math.min(m-1,n-1)
result=1
i=1
while ( i<=k ){
result*=(total-k+i)/i
i+=1
}
return result
解法二：二维动态规划。定义 dp[i][j] 为到达网格中第 i 行第 j 列的不同路径数
· 初始化：第一行和第一列的所有格子都只有 1 条路径（一直向右或一直向下）
· 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]（因为只能从上方或左方过来）
m=输入[0]
n=输入[1]
dp=[...Array(m)].map(( )=>{
return [...Array(n)].map(( )=>1)
})
i=1
while ( i<m ){
j=1
while ( j<n ){
dp[i][j] = dp[i-1][j] + dp[i][j-1]
j+=1
}
i+=1
}
return dp[m-1][n-1]
解法三（解法二的空间优化，一维动态规划，计算当前行只需要上一行的数据）
m=输入[0]
n=输入[1]
dp = Array(n).fill(1)
i = 1
while (i < m) {
j = 1
while (j < n) {
dp[j] += dp[j-1]
j += 1
}
i += 1
}
return dp[n-1]
23. 最小路径和
解法一：二维动态规划。dp[i][j] 表示从 (0,0) 走到 (i,j) 的最小路径和。
状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + mtk[i][j]。因为只能从上方或左方过来。
边界条件：
· 起点 dp[0][0] = mtk[0][0]
· 第一行：只能从左边来，所以 dp[0][j] = dp[0][j-1] + mtk[0][j]
· 第一列：只能从上边来，所以 dp[i][0] = dp[i-1][0] + mtk[i][0]
最终答案是 dp[m-1][n-1]。另外，也可以原地修改矩阵，不用额外的dp数组。
mtx=输入
m=mtx.length
n=mtx[0].length
dp=[...Array(m)].map(()=>{
return [...Array(n)].map(()=>0)
})
dp[0][0]=mtx[0][0]
i=1
while ( i<m ){
dp[i][0]=dp[i-1][0]+mtx[i][0]
i+=1
}
j=1
while ( j<n ){
dp[0][j]=dp[0][j-1]+mtx[0][j]
j+=1
}
i=1
while ( i<m ){
j=1
while ( j<n ){
dp[i][j]=Math.min(dp[i-1][j],
dp[i][j-1])+mtx[i][j]
j+=1
}
i+=1
}
return dp[m-1][n-1]
解法二：解法一的空间优化，因为每一行只依赖上一行和当前行左边，可以用一维数组优化
mtx=输入
m=mtx.length
n=mtx[0].length
dp=Array(n).fill(0)
dp[0]=mtx[0][0]
j=1
while ( j<n ){
dp[j]=dp[j-1]+mtx[0][j]
j+=1
}
i=1
while ( i<m ){
dp[0]+=mtx[i][0]
j=1
while ( j<n ){
dp[j]=Math.min(dp[j],
dp[j-1])+mtx[i][j]
j+=1
}
i+=1
}
return dp[n-1]
至此，你已打败了99%的人！🎉