【每日一題】(27題)算法題:如何使用多種解決方案來實(shí)現(xiàn)跳一跳游戲？

關(guān)注「松寶寫代碼」，精選好文，每日一題

作者：saucxs ｜ songEagle

2020，實(shí)「鼠」不易

2021，「?！罐D(zhuǎn)乾坤

風(fēng)勁潮涌當(dāng)揚(yáng)帆，任重道遠(yuǎn)須奮蹄！

一、前言

2020.12.23 立的 flag，每日一題，題目類型不限制，涉及到JavaScript，Node，Vue，React，瀏覽器，http，算法等領(lǐng)域。

本文是：【每日一題】(27題)算法題:如何使用多種解決方案來實(shí)現(xiàn)跳一跳游戲？

昨天發(fā)了文章【每日一題】(26題)算法題:最長公共前綴？被人一頓吐槽，槽點(diǎn)太多了，比如：

  • 能不能給出最優(yōu)解？
  • 不講基礎(chǔ)題目，能不能講一下稍微難點(diǎn)的算法題？

哈哈，我以為沒有人看呢？原來還是有人在看哈，簡單說明一下：

  • 每一個(gè)問題背后有多種解決方案，我們可以從最初的解決方案出發(fā)，逐步優(yōu)化，找出問題所在。
  • 基礎(chǔ)題目有一定的道理，每一個(gè)算法可以融入到千變?nèi)f化的場景中，從而就有了成千上萬的題目，你需要從場景中抓住重點(diǎn)，提取信息，匹配到合適的算法，最終解決。

[圖片上傳失敗...(image-cb8894-1611071808563)]

二、題目

昨天我們還談了很多基礎(chǔ)問題，我們先來看一下我們說的基礎(chǔ)題目，也就是常說的「爬樓梯問題」或者「跳一跳游戲」。

問題描述：

給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達(dá)最后一個(gè)位置。

例子1：

輸入: [2,3,1,1,4]
輸出: true
解釋: 我們可以先跳 1 步，從位置 0 到達(dá) 位置 1, 然后再從位置 1 跳 3 步到達(dá)最后一個(gè)位置。

例子2:

輸入: [3,2,1,0,4]
輸出: false
解釋: 無論怎樣，你總會(huì)到達(dá)索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 所以你永遠(yuǎn)不可能到達(dá)最后一個(gè)位置。

三、解決方案

1、回溯方法

這是一個(gè)效率低的方案，其中我們嘗試從第一個(gè)位置跳到最后一個(gè)位置上的跳躍方式。我們第一個(gè)位置開始，跳到所有可能達(dá)到的步數(shù)。我們重復(fù)這個(gè)過程，直到達(dá)到最后一個(gè)位置。當(dāng)達(dá)不到的時(shí)候我們回溯。

var backtrackingJumpLittle = function (numbers, startIndex = 0, currentJumps = []) {
  if (startIndex === numbers.length - 1) {
    return true;
  }

  const maxJumpLength = Math.min(
    numbers[startIndex],
    numbers.length - 1 - startIndex,
  );

  for (let jumpLength = maxJumpLength; jumpLength > 0; jumpLength -= 1) {
    const nextIndex = startIndex + jumpLength;
    currentJumps.push(nextIndex);
    const isJumpSuccessful = backtrackingJumpLittle(numbers, nextIndex, currentJumps);
    if (isJumpSuccessful) {
      return true;
    }
    currentJumps.pop();
  }
  return false;
}

我們來分析一下時(shí)間復(fù)雜度和空間復(fù)雜度：

  • 時(shí)間復(fù)雜度：O(2^n)。從第一個(gè)位置到最后一個(gè)位置有2的n次方跳躍方式，其中narray的長度為nums。

  • 空間復(fù)雜度：O(n)。遞歸需要額外的內(nèi)存用于堆棧。

2、自頂向下動(dòng)規(guī)方法

自上而下的動(dòng)態(tài)規(guī)劃可以被認(rèn)為是優(yōu)化的回溯。它依賴于這樣的觀察：一旦我們確定某個(gè)臺(tái)階是可以達(dá)到終點(diǎn)，還是不能達(dá)到終點(diǎn)，那么這個(gè)結(jié)果將永遠(yuǎn)不會(huì)改變。這意味著我們可以存儲(chǔ)結(jié)果，而不必每次都重新計(jì)算。

因此，對(duì)于數(shù)組中的每個(gè)位置，我們都記住該位置是好是壞。我們將這個(gè)其值設(shè)為以下之一：good，bad，unknow。

var dpTopDownJumpLittle = function (
  numbers,
  startIndex = 0,
  currentJumps = [],
  cellsGoodness = [],  // 用來存當(dāng)前臺(tái)階的狀態(tài)
) {
  if (startIndex === numbers.length - 1) {
    return true;
  }

  const currentCellsGoodness = [...cellsGoodness];
  if (!currentCellsGoodness.length) {
    numbers.forEach(() => currentCellsGoodness.push(undefined));
    currentCellsGoodness[cellsGoodness.length - 1] = true;
  }

  const maxJumpLength = Math.min(
    numbers[startIndex],
    numbers.length - 1 - startIndex,
  );

  for (let jumpLength = maxJumpLength; jumpLength > 0; jumpLength -= 1) {
    const nextIndex = startIndex + jumpLength;
    if (currentCellsGoodness[nextIndex] !== false) {
      currentJumps.push(nextIndex);
      const isJumpSuccessful = dpTopDownJumpLittle(
        numbers,
        nextIndex,
        currentJumps,
        currentCellsGoodness,
      );
      if (isJumpSuccessful) {
        return true;
      }
      currentJumps.pop();
      currentCellsGoodness[nextIndex] = false;
    }
  }
  return false;
}

  • 時(shí)間復(fù)雜度：：O(n^2)。對(duì)于數(shù)組中的每個(gè)元素，例如i，我們正在尋找nums[i]其右邊的下一個(gè)元素，目的是尋找一個(gè)良好的索引。

  • 空間復(fù)雜度：O(2 * n) = O(n)。首先n起源于遞歸。其次n來自存儲(chǔ)當(dāng)前步數(shù)狀態(tài)的用法。

3、自下向上動(dòng)規(guī)方法

這一步驟為將來的優(yōu)化打開了可能。通常通過嘗試從上至下的方法顛倒步驟的順序來消除遞歸。

var dpBottomUpJumpLittle = function(numbers) {
  const cellsGoodness = Array(numbers.length).fill(undefined);
  cellsGoodness[cellsGoodness.length - 1] = true;
  for (let cellIndex = numbers.length - 2; cellIndex >= 0; cellIndex -= 1) {
    const maxJumpLength = Math.min(
      numbers[cellIndex],
      numbers.length - 1 - cellIndex,
    );

    for (let jumpLength = maxJumpLength; jumpLength > 0; jumpLength -= 1) {
      const nextIndex = cellIndex + jumpLength;
      if (cellsGoodness[nextIndex] === true) {
        cellsGoodness[cellIndex] = true;
        break;
      }
    }
  }
  return cellsGoodness[0] === true;
}

  • 時(shí)間復(fù)雜度:: O(n^2)

  • 空間復(fù)雜度：O(n)

[圖片上傳失敗...(image-a3c869-1611071808563)]

4、貪心算法

一旦我們的代碼處于自下而上的狀態(tài)，我們就可以做最后一個(gè)重要的觀察。從一個(gè)給定的位置，當(dāng)我們?cè)噲D看看是否能跳到一個(gè)好的位置時(shí)，我們只使用第一個(gè)。換句話說，最左邊的一個(gè)。如果我們把這個(gè)最左邊的好位置作為一個(gè)單獨(dú)的變量來跟蹤，我們可以避免在數(shù)組中搜索它。不僅如此，我們還可以完全停止使用數(shù)組。

var greedyJumpLittle = function(numbers) {
  let leftGoodPosition = numbers.length - 1;
  for (let numberIndex = numbers.length - 2; numberIndex >= 0; numberIndex -= 1) {
    const maxCurrentJumpLength = numberIndex + numbers[numberIndex];
    if (maxCurrentJumpLength >= leftGoodPosition) {
      leftGoodPosition = numberIndex;
    }
  }
  return leftGoodPosition === 0;
}

  • 時(shí)間復(fù)雜度：：O(n)。我們正在遍歷nums數(shù)組，因此要遍歷n，其中n的長度是array的長度nums。

  • 空間復(fù)雜度：O(1)。我們沒有使用任何額外的內(nèi)存。

我在leetcode上測試了一下，發(fā)現(xiàn)空間占用還是很大，運(yùn)行時(shí)間76ms左右，內(nèi)存消耗38MB左右。

[圖片上傳失敗...(image-c940fd-1611071808563)]

謝謝支持

1、文章喜歡的話可以「分享，點(diǎn)贊，在看」三連哦。

2、作者昵稱：saucxs，songEagle，松寶寫代碼。「松寶寫代碼」公眾號(hào)作者，每日一題，實(shí)驗(yàn)室等。一個(gè)愛好折騰，致力于全棧，正在努力成長的字節(jié)跳動(dòng)工程師，星辰大海，未來可期。內(nèi)推字節(jié)跳動(dòng)各個(gè)部門各個(gè)崗位。

3、長按下面圖片，關(guān)注「松寶寫代碼」，是獲取開發(fā)知識(shí)體系構(gòu)建，精選文章，項(xiàng)目實(shí)戰(zhàn)，實(shí)驗(yàn)室，每日一道面試題，進(jìn)階學(xué)習(xí)，思考職業(yè)發(fā)展，涉及到JavaScript，Node，Vue，React，瀏覽器，http等領(lǐng)域，希望可以幫助到你，我們一起成長～

[圖片上傳失敗...(image-24253e-1611071808564)]

字節(jié)內(nèi)推福利

  • 回復(fù)「校招」獲取內(nèi)推碼
  • 回復(fù)「社招」獲取內(nèi)推
  • 回復(fù)「實(shí)習(xí)生」獲取內(nèi)推

后續(xù)會(huì)有更多福利

學(xué)習(xí)資料福利

回復(fù)「算法」獲取算法學(xué)習(xí)資料

往期「每日一題」

1、JavaScript && ES6

2、瀏覽器

3、Vue

4、算法

5、Http

6、Node

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容