米哈游场

恰好移动k步到达某一位置的方法数目

Way One

• 链接：题目

赛时做的时候想到了DP，但是根本不知道咋搞状态转移方程，也就是中间少了一个作为转换的东西。

看题解才知道可以使用组合数来做。

• 我们想要从起点走到终点，设其距离为 a，则我们需要选择m步向右边走，选k-m步向左边走，距离之差为a，则公式可以写为

m - (k - m) = a => 2*m = k + a => m = ( k + a ) / 2

所以我们只需要找到 C(k, ( k + a ) / 2)就可以了，而

，所以我们可以用双重循环来解决这个题目。

var numberOfWays = function(startPos, endPos, k) {
  const a = Math.abs( endPos - startPos )
  const mod = 1e9 + 7
  if( a > k || ( k + a ) % 2 == 1 ) { return 0; }
     const dp = new Array( k + 1 ).fill(0).map(() => new Array( k + 1 ).fill(0)) // 一共是k步，从其中找出 m 步，所以第一项就是 k
  for(let i=0; i<=k; i++) {
    dp[i][0] = 1 // C(i, 0)本来就是 1
    for(let j=1;j<=i;j++) dp[i][j] = ( dp[i-1][j-1] + dp[i-1][j] ) % mod
  }
  return dp[k][ ( k + a ) / 2 ]
}

Way Two

• 第二种方法是记忆化搜索

很不幸，TLE了，估计会被hack掉。

var numberOfWays = function(startPos, endPos, k) {
  const cache = new Map() // cache是用来存走过的part
  const mod = 1e9 + 7
  // 传入位置和步骤
  getSum(pos, step) {
    const key = `${pos},${step}`
    //如果这个之前走过，那就直接拿之前的值
    if(cache.has(key)) return cache.get(key)
    // 如果不合法 ==> 当前位置即使所有的步数都往 target 走也不行
    if(Math.abs(pos - endPos) > step) return 0;
    // 如果ok了
    if(step == 0) return 1;
    const pre = getSum(pos - 1, step - 1);
    const later = getSum(pos + 1, step - 1);
    const sum = pre + later
    return sum
  }
  return getSum(startPos, k)
}

最长优雅子数组

• 链接：题目

赛时想用栈暴力给它搞出来，但是好像不行（

题解

• 你可以使用 & 运算来验证，用 | 运算来记录，双指针把所有的情况都写一遍，就ok了。

var longestNiceSubarray = function(nums) {
  const len = nums.length;
  let ans = 1
  for(let i=0;i<len;i++) {
    let cur = nums[i]
    let cnt = 1
    let j = i + 1
    while(j < len && ( ( cur & nums[j] )  == 0)) {
      cur |= nums[j]
      cnt += 1
      j ++
    }
    ans = Math.max(ans, cnt)
  }
  return ans
};

非常值得提一嘴的是： “&运算一定要打括号，否则就会寄。”

这个题目用来记录所有状态使用的就是二进制。

• 下面的式子String.fromCharCode()可以将数字转换为字母

let a = String.fromCharCode(96 + parseInt(i+1))