《程序员模拟器》生涯困难1~12关攻略(上)
修改于昨天 01:0328 浏览攻略
这份攻略整理的是一些过关思路,不是唯一解,更不是标准答案。很多关卡我自己也卡过,后来翻论坛、看别人分享才慢慢摸清楚。本人非专业人士,如果有写错的地方,欢迎大家指出!游戏有自己的规则,哪怕你写过 JavaScript,也得重新适应——比如游戏键盘里打不出冒号、分号和问号等,常见的 for 循环、对象字面量还有简洁的判断也就用不上。如果你是第一次接触困难难度,建议先自己试试。这部分的题目已经逐渐变态了——不只是动动脑子就可以的事情了,还得靠集思广益,实在卡住再来看攻略也不迟。
最后还是那句话:解法没有高下之分,能跑通就是好代码,享受琢磨的过程就好。
PS如果想单独复制某一关的代码,建议用手机浏览器打开此攻略,而不是客户端


生涯模式攻略导航:


1. 数组最大值
这关和普通第7关一样,和当前难度格格不入
解法一(遍历比较)
变量a=输入
变量b=变量a[0]
变量c=1
while ( 变量c<变量a.length ){
if (变量b<变量a[变量c] ){
变量b=变量a[变量c]
}
变量c+=1
}
return 变量b
解法二(max函数配合扩展运算符)
return Math.max(...输入)
2. 打印机
第二关直接上强度了,解法思路是区间动态规划。首先用map创建二维数组,表明从字符的第i位打到j的最少次数。dp[i][i]=1即单个字符只需要打1次。后面按子串长度从小到大遍历,也就是打印区间。通过三种状态转移来得到最小打印次数:最坏、分割和两端。
我用abb来举个例子,初始化[0,0][1,1][2,2]都是1;然后sublen区间从2开始:
[0,1] = "ab"
· 最坏:dp[0][0] + 1 = 1 + 1 = 2
· 分割:i=0 → dp[0][0] + dp[1][1] = 1 + 1 = 2
· 两端:a ≠ b,不触发
dp[0][1] = 2
[1,2] = "bb"
· 最坏:dp[1][1] + 1 = 1 + 1 = 2
· 分割:i=1 → 1 + 1 = 2
· 两端:b = b √ → min(2, dp[1][1]) = min(2, 1) = 1
dp[1][2] = 1
解释:一次打印 'b' 覆盖位置1和2,得到 "bb"
---
sublen为3:
[0,2] = "abb" 整个字符串
①最坏情况
dp[0][2] = dp[0][1] + 1 = 2 + 1 = 3
意思:先打好 "ab"(2次),再单独打最后一个 'b'(1次),总共3次
②分割点尝试
· i=0:dp[0][0] + dp[1][2] = 1 + 1 = 2
· i=1:dp[0][1] + dp[2][2] = 2 + 1 = 3
发现 i=0 这个分割点更好:左边 "a" 打1次,右边 "bb" 打1次,合起来2次
③两端相同检查
str[0]=a,str[2]=b,不同,不触发
取最小值:min(3, 2) = 2
因此得到dp[0][2] = 2。
实际情况就是先全打a,接着后面两个位置打b,需要两次。再之后比如abba就是abb通过两端相同转移过去,同样是2次。
str=输入
len=str.length
dp=[...Array(len)].map(()=>{
return [...Array(len)].fill('')
})
i=0
while ( i<len ){
dp[i][i]=1
i+=1
}
subLen=2
while ( subLen<=len ){
start=0
while ( (start+subLen)<=len ){
end=start+subLen-1
dp[start][end]
=dp[start][end-1]+1
i=start
while ( i<end ){
dp[start][end]
=Math.min(
dp[start][end],
dp[start][i]
+dp[i+1][end])
i+=1
}
if ( str[start]==str[end] ){
dp[start][end]
=Math.min(
dp[start][end],
dp[start][end-1])
}
start+=1
}
subLen+=1
}
return dp[0][len-1]
3. 接雨水
对于任意位置i,能接的水量取决于左边最高和右边最高的较小值,减去当前高度。双指针的巧妙之处:不需要同时知道两边最高,只需要知道当前指针这一侧的最高,以及另一侧有一个更高的柱子兜底,哪边低就动哪边,不断填水坑,直到两个指针都移动到最高处跳出循环。
pillar=输入
left=0
right=pillar.length-1
leftMax=0
rightMax=0
water=0
while ( left<right ){
leftMax=Math.max(
leftMax, pillar[left])
rightMax=Math.max(
rightMax, pillar[right])
if (pillar[left]<pillar[right]) {
water+=leftMax-pillar[left]
left+=1
} else {
water+=rightMax-pillar[right]
right-=1
}
}
return water
4. 五子棋
这关的难度有点超出当前章节了。我用的是比较简化并且不能覆盖真实五子棋所有情况的,只用chk4判断了横竖两个方向上是否会出现四连。棋盘简化成7×7,足够解题用了,判断时只看中间5×5的区域。注意初始化棋盘时,把黑白棋加了1,这样0就成了空白。因为是只有黑白黑三步,所以白棋只有四连才能赢,黑棋就遍历模拟下一子,再看看有没有四连,没有就恢复棋盘。总之,能过关就行![[表情_吃瓜]](https://img.tapimg.com/market/images/d07b262774c8a022a7dddbc39683da6b.png)
![[表情_吃瓜]](https://img.tapimg.com/market/images/d07b262774c8a022a7dddbc39683da6b.png)
pieces=输入
board=[...Array(7)].map(()=>{
return [...Array(7)].map(()=>0)
})
i=0
while ( i<pieces.length ){
p=pieces[i]
board[p[0]][p[1]]=p[2]+1
i+=1
}
if ( chk4(2) ) return 'white'
m=1
while ( m<6 ){
n=1
while ( n<6 ){
if ( board[m][n]==0 ){
board[m][n]=1
if ( chk4(1) ) return 'black'
board[m][n]=0
}
n+=1
}
m+=1
}
return 'none'
function chk4(player){
x=1
while ( x<6 ){
y=1
while ( y<3 ){
win=true
i=0
while ( i<4 ){
if ( board[x][y+i]!=player ){
win=false
break
}
i+=1
}
if ( win ) return true
y+=1
}
x+=1
}
y=1
while ( y<6 ){
x=1
while ( x<3 ){
win=true
i=0
while ( i<4 ){
if ( board[x+i][y]!=player ){
win=false
break
}
i+=1
}
if ( win ) return true
x+=1
}
y+=1
}
return false
}
5. 反转字符串
首先用展开运算符把字符串变成字符数组,Math.floor(长度/2)只需要遍历前半部分,解构赋值交换镜像的两个元素,最后join('')将数组拼回字符串
解法一
变量a=[...输入]
变量b=变量a.length
变量c=Math.floor( 变量b/2 )
变量d=0
while ( 变量d<变量c ){
[变量a[变量d],变量a[变量b-1-变量d]]=
[变量a[变量b-1-变量d],变量a[变量d]]
变量d+=1
}
return 变量a.join('')
解法二(手敲reverse)
return [...输入].reverse().join('')
6. 完美数
因数遍历,因为因数成对出现,所以只遍历到平方根,并且平方根只需要算一次。循环内一旦累和超过输入就返回非完美数
解法一
变量a=输入
变量b=1
变量c=输入**(1/2)
变量d=2
while ( 变量d<变量c ){
if ( 变量a%变量d==0 ){
变量b+=变量d
变量b+=变量a/变量d
if ( 变量b>变量a ){
return false
}
}
变量d+=1
}
if ( 变量d==变量c ){
变量b+=变量d
}
return 变量a==变量b
解法二(欧几里得-欧拉定理:偶完美数一定可以表示为 2^(p-1)×(2^p - 1))
变量a=输入
if ( 变量a%2==1 ){
return false
}
变量b=2
while ( true ){
变量c=Math.pow( 2,变量b )-1
变量d=Math.pow( 2,变量b-1 )*变量c
if ( 变量d>变量a ){
return false
}
if ( 变量d==变量a ){
return true
}
变量b+=1
}
解法三(究极打表,32位以内只有这5个完美数)
return [6,28,496,8128,33550336].includes(输入)
7. 无重复子串
字符串作为滑动窗口。遇上重复字母,就把重复的字母截取掉
str = 输入
maxLen = 0
crtStr = ''
i=0
while ( i<str.length ){
char = str[i]
charIndex = crtStr.indexOf(char)
if (charIndex !== -1) {
crtStr = crtStr.slice(charIndex + 1)
}
crtStr += char
maxLen = Math.max(
maxLen,crtStr.length)
i+=1
}
return maxLen
8. 排序
经典冒泡排序方法,双重while循环,每次将最大的元素冒泡排到最后
解法一
变量a=输入
变量b=变量a.length
变量c=0
while ( 变量c<变量b-1 ){
变量d=0
while ( 变量d<变量b-1-变量c ){
if ( 变量a[变量d]>变量a[变量d+1] ){
[变量a[变量d],变量a[变量d+1]]=
[变量a[变量d+1],变量a[变量d]]
}
变量d+=1
}
变量c+=1
}
return 变量a
解法二(用sort函数排序,默认排序是字母排序,10会排在2之前,因此需要定义a-b升序)
return 输入.sort((a,b)=>a-b)
9. 最长连续序列
先排序,把无序数组变成有序,连续的数就会挨在一起。从第二个数开始遍历,看它是不是前一个数+1。如果有重复数字,直接跳过(不影响连续)。记录当前连续长度,不断更新最大值,非连续就把当前连续长度重置为1。
变量a=输入
变量b=变量a.length
if ( 变量b==0 ){
return 0
}
变量a.sort((a,b)=>a-b)
变量c=1
变量d=1
变量e=1
while ( 变量e<变量b ){
if ( 变量a[变量e]!=变量a[变量e-1] ){
if ( 变量a[变量e]==
变量a[变量e-1]+1 ){
变量d+=1
变量c=Math.max( 变量c,变量d )
} else {
变量d=1
}
}
变量e+=1
}
return 变量c
10. 最大收益
遍历每一天,假设当天卖出。想要利润最大,必须在之前最低的那天买入。所以只需要记住遍历到当前为止的最低价格。每天计算一次“如果当天卖”的利润,更新最大值
变量a=输入
变量b=变量a[0]
变量c=0
变量d=1
while ( 变量d<变量a.length ){
变量e=变量a[变量d]-变量b
变量c=Math.max( 变量c,变量e )
变量b=Math.min( 变量b,变量a[变量d] )
变量d+=1
}
return 变量c
11. 数字组合
这里提供的思路是按位比较,分类计数:
①位数比 target 短的数:全部合法
比如 target 是 3 位数,那么 1 位数和 2 位数的所有组合都小于它
1 位数:lenN 种
2 位数:lenN² 种
总和 = lenN¹ + lenN² + ... + lenN^(lenT-1)
②位数和 target 一样长:逐位比较
· 当前位选一个比 target 对应位小的数 → 后面位任意选
· 当前位相等 → 继续看下一位
· 当前位没有相等的数 → 直接结束,因为后面的位再大都超不过了
③最后如果每一位都能对上:说明 target 本身也是一个合法数,要加 1
---
举个例子:numSet = [1,2,3], target = 213
· 位数比 3 短的数:
1 位数:3 种 (1,2,3)
2 位数:3² = 9 种
小计:12 个
· 逐位比较 target = "213":
第1位('2'):
可选数字中 <2 的有 [1] → 1 × 3² = 9 个(后面两位任意)
可选数字中 =2 的有 [2] → 标记 isSame=true,继续
第2位('1'):
可选数字中 <1 的有没有?没有([1,2,3] 都 ≥1)
可选数字中 =1 的有 [1] → 标记 isSame=true,继续
第3位('3'):
可选数字中 <3 的有 [1,2] → 1×1 + 1×1?等一下,这里要仔细算
其实第三位是最后一位,<3 的有 [1,2] 两种,每种后面没有位了,所以直接加 2
加上前面 9 个,现在 powers = 12 + 9 + 2 = 23
· 每一位都能对上?是,213 本身可以用 [2,1,3] 组成,所以再加 1
最终结果 = 24
numSet=输入[0]
target=输入[1]+''
lenN=numSet.length
lenT=target.length
powers=0
i=1
while ( i<lenT ){
powers+=Math.pow( lenN,i )
i+=1
}
i=0
while ( i<lenT ){
isSame=false
j=0
while ( j<lenN ){
if ( numSet[j]<target[i] ){
powers+=Math.pow( lenN,
lenT-i-1 )
} else if ( numSet[j]==target[i] ){
isSame=true
break
}
j+=1
}
i+=1
if ( !isSame ){
return powers
}
}
return powers+1
12. 任务调度器
贪心+数学解法,核心公式:最少时间 = max(任务总数, (最大次数-1)*(冷却+1) + 最大次数种类数)
推导过程:假设出现次数最多的任务有 maxc 个,比如 'A' 出现了 4 次,冷却时间 n=2。
我们先把这些 'A' 排好:
A _ _ A _ _ A _ _ A
每个 'A' 后面需要留出 n 个空位(最后一个是例外),所以需要的总长度是:
(maxc - 1) * (n + 1) + 1
但如果有多个任务都出现了 maxc 次,比如 'A' 和 'B' 都出现了 4 次,那最后的 +1 要变成 +2:
(maxc - 1) * (n + 1) + maxct
这个长度可能比任务总数小,也可能大。如果比总数小,说明空位可以被其他任务填满,实际总时间就是任务总数;如果比总数大,说明空位填不满,需要用这个公式算出的长度。
所以最终取两者的最大值。
list=输入[0]
cd=输入[1][0]-0
type=[]
count=[]
i=0
while ( list[i] ){
task=type.indexOf(list[i])
if ( task==-1 ){
type.push( list[i] )
count.push(1)
} else {
count[task]+=1
}
i+=1
}
maxc=Math.max( ...count )
maxct=0
i=0
while ( count[i] ){
if ( count[i]==maxc ){
maxct+=1
}
i+=1
}
total=(maxc-1)*(cd+1)+maxct
len=list.length
return Math.max( len,total )
休息一下,下篇继续挑战困难难度


![[表情_比心]](https://img.tapimg.com/market/images/a272560c8c816575cd8af72d0df6bbf1.png)