《程序员模拟器》生涯困难1~12关攻略(上)

修改于昨天 01:0328 浏览攻略
这份攻略整理的是一些过关思路,不是唯一解,更不是标准答案。很多关卡我自己也卡过,后来翻论坛、看别人分享才慢慢摸清楚。本人非专业人士,如果有写错的地方,欢迎大家指出![表情_比心]游戏有自己的规则,哪怕你写过 JavaScript,也得重新适应——比如游戏键盘里打不出冒号、分号和问号等,常见的 for 循环、对象字面量还有简洁的判断也就用不上。如果你是第一次接触困难难度,建议先自己试试。这部分的题目已经逐渐变态了——不只是动动脑子就可以的事情了,还得靠集思广益,实在卡住再来看攻略也不迟。
最后还是那句话:解法没有高下之分,能跑通就是好代码,享受琢磨的过程就好。
PS如果想单独复制某一关的代码,建议用手机浏览器打开此攻略,而不是客户端
horizontal linehorizontal line
生涯模式攻略导航:
horizontal linehorizontal line
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就成了空白。因为是只有黑白黑三步,所以白棋只有四连才能赢,黑棋就遍历模拟下一子,再看看有没有四连,没有就恢复棋盘。总之,能过关就行[表情_吃瓜]
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 )
休息一下,下篇继续挑战困难难度
1
2