Ryker‘s

  • {{ item.name }}
  • 主页
  • 前端
  • 后端
  • 算法
  • 随笔
  • 关于博主
  • 文章归档
  • 友情链接

LC周赛补题

  • Ryker
  • 2022-09-04
  • 1

米哈游场

恰好移动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))
© 2023 Ryker‘s
Theme by Wing
鄂ICP备2022010847号-1