Re: [閒聊] 每日LeetCode

[ZooseWu (動物園 公告)]

1269. Number of Ways to Stay in the Same Place After Some Steps

你有一個指標在陣列上移動，指標起點在0

每次操作可以進行下列三種選擇:往左一格、往右一格、待命。

指標操作後必須不能超出陣列範圍


求在arrLen長度的陣列進行steps次操作下

指標最後回到0 一共的可能次數


例題1: steps = 3, arrLen = 2,   答: 4

所有可能如下: 右停左、停停停、右左停、停右左


例題2: steps = 2, arrLen = 4,   答: 2

所有可能如下: 停停、右左


例題3: steps = 4, arrLen = 2,   答:8




First think:
排列組合的問題，所有可能 - 超出陣列長度 - 指針移動到負 + 超出陣列且移動到負

所有可能:

  右的次數從0次到steps/2次去排列 然後左永遠=右

  例如例題一 右=0:停停停 右=1:右停左、右左停、停右左

超出陣列長度:

  右的次數 > 陣列長度/2

指針移動到負:

  任何左先出現的次數>右  例如左停右


仔細研究了一下後 發現超難 很難用簡單的算式去列出解答

所以這應該不是解決方法


後來發現移動問題有另一種解法

就是高中的捷徑問題

每次走路可以往上或往右走，求左下走到右上的所有可能

隨便找一張高中例題的圖: https://i.imgur.com/XcRGvey.png



同樣的這一題也可以用類似的概念去解決

我們畫出一個寬=陣列長度 長=步驟數+1的方格

然後從左上開始走

每次操作可以往下(停住) 或是往左下(指針往左) 或是往右下(指針往右)

把例題1畫圖出來的話是這樣: https://i.imgur.com/mFy0nqK.png

還沒有開始走的時候指針只可能會在起點

所以起始陣列列出來是100



走第一步的可能是右或停

這時候指針的位置可能會在0或1

因此第零步的起點1就要往下加、往右下加

第一步的陣列就會是110

之後都以此類推

舉例來說圖片中第三步[4,5,3]裡面的5

就是第二步的2+2+1(左邊一格往右走 或是停 或是右邊一格往左走)

https://i.imgur.com/boSrR7b.png


把數字全部列出來之後

最左下的數字就是走到最後一步之後 指針在0的可能次數

第一題的答案我們就可以得出是4



到這邊就可以解答了

不過還有可以優化的地方
https://i.imgur.com/rCnETTd.png

圖片中藍色線的右上以及紅色線的右下都是可以不用計算的地方

在路剛開始走的時候右上角一定不會有數字

非0的數字跟走的步驟數成正比 所以藍色線的右上一定都是0

然後我們想知道最後指針在0的可能性

所以紅線以右的數字都是不可能會回到0的數字就可以不用計算

把這兩邊排除之後計算量可以變成原本的一半左右



最後還有一點

題目要求的數字可能會太大

所以要求答案要輸出可能次數除以10^9+7的餘數

本來我想說全部算完取餘丟出去就好

但是發現好像數字太大會溢位 沒辦法得出正確答案

所以就改成每次算完就取一次餘

相加取餘 = 取餘之後相加再取餘

自己算式列一下就能證明了

(這好像跟輾轉相除法是類似的東西)


TS code:

function numWays(steps: number, arrLen: number): number {

  const results: number[][] = new Array(2)
  let arrIndex = 1
  for (let index = 0; index < 2; index++) {
    results[index] = new Array(steps + 1).fill(0)
    results[index][0] = 1
  }

  for (let time = 1; time <= Math.ceil(steps / 2); time++) {
    const prevArr = results[arrIndex]
    arrIndex = (arrIndex + 1) % 2
    const currentArr = results[arrIndex]
    for (
      let index = 0;
      (index < steps &&
        index < time + 1 &&
        index < arrLen);
      index++) {
      currentArr[index] = prevArr[index] + prevArr[index + 1]
      if (index > 0) currentArr[index] += prevArr[index - 1]
      if (currentArr[index] >= 1000000007) currentArr[index] %= 1000000007
    }
  }

  for (let time = Math.floor(steps / 2); time > 0; time--) {
    const prevArr = results[arrIndex]
    arrIndex = (arrIndex + 1) % 2
    const currentArr = results[arrIndex]
    for (
      let index = 0;
      (index < steps &&
        index < time + 1 &&
        index < arrLen);
      index++) {
      currentArr[index] = prevArr[index] + prevArr[index + 1]
      if (index > 0) currentArr[index] += prevArr[index - 1]
      if (currentArr[index] >= 1000000007) currentArr[index] %= 1000000007
    }
  }

  return results[arrIndex][0]
}

--
                                                                    Zoosewu
                              Yoututbe顯示PTT推文
                       可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png https://i.imgur.com/WqbLNV3.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1697398926.A.217.html
→ ZooseWu: 看了一下別人寫的 超簡潔 我這輩子就大便了
推 wwndbk: 大
※ 編輯: ZooseWu (114.32.229.33 臺灣), 10/16/2023 03:45:10
推 JerryChungYC: 大師
推 SiranuiFlare: 大師
推 smart0eddie: ：0