成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode刷題：283.Move Zeroes(Easy)

ckllj / 725人閱讀

摘要：解法目的就是把一個(gè)數(shù)組中所有為的數(shù)移動(dòng)到數(shù)組的尾部，并保證其他元素相對(duì)位置不變。要求是在原數(shù)組上修改，不要額外引入其他的數(shù)組盡量減少操作次數(shù)。在小游戲中，設(shè)置了和界面一致的二維數(shù)組，數(shù)組的每一位記錄了一個(gè)數(shù)字。

地址：https://leetcode.com/problems/move-zeroes/

應(yīng)用場景說明

這個(gè)題是很Easy的一道題，它的應(yīng)用場景是在我嘗試寫小游戲2048時(shí)，采用了二維數(shù)組存放數(shù)字占位，當(dāng)按上下左右鍵時(shí)，要把所有的數(shù)字靠在一邊，而所有為0的靠在另一邊，這時(shí)候用到這個(gè)題的解題思路很快能做出來。

解法

目的就是把一個(gè)數(shù)組中所有為0的數(shù)移動(dòng)到數(shù)組的尾部，并保證其他元素相對(duì)位置不變。要求是在原數(shù)組上修改，不要額外引入其他的數(shù)組；盡量減少操作次數(shù)。

輸入：

[0,1,0,3,12]

輸出

[1,3,12,0,0]

首先先引入額外數(shù)組的方式看如何來寫：

var moveZeroes = function(nums) {
    let nonZeroArr = [];  // 用來存放非0元素
    for(let i = 0; i < nums.length; i++) {
      if(nums[i]){
        nonZeroArr.push(nums[i])
      }
    }
    // 把新數(shù)組中的每一項(xiàng)對(duì)位的賦值給原數(shù)組
    for(let j = 0; j < nonZeroArr.length; j++){
      nums[j] = nonZeroArr[j]
    }

    // 把nums中之后的位置都補(bǔ)上0
    for(let k = nonZeroArr.length; k < nums.length; k++){
      nums[k] = 0;
    }
    
    return nums;
};

let arr = [0,1,0,3,0,9,0,12];

console.log(moveZeroes(arr)); // [ 1, 3, 9, 12, 0, 0, 0, 0 ]

思路很簡單，就是把不為0的數(shù)字存在一個(gè)新數(shù)組中，把新數(shù)組的每一項(xiàng)對(duì)位的重新賦值給原來數(shù)組的位置，然后把原數(shù)組剩余的位置一律替換為0；

這樣的寫法在時(shí)間復(fù)雜度上是 O(n) 級(jí)別的，在空間復(fù)雜度上也是O(n) 級(jí)別的，因?yàn)橐肓诵碌臄?shù)組。

可以在不引入新數(shù)組的情況下做位置的調(diào)整：

var moveZeroes = function(nums) {
  let lastZeroIndex = 0;  // 每一次最后找到的0的位置，初始是0
  for(let i = 0; i < nums.length; i++){
    if(nums[i]) {  // 不為0
      nums[lastZeroIndex++] = nums[i];  // 把遍歷到不為0的數(shù)字，替換在0的位置,替換的位置已經(jīng)不是0了，向后推一步;
    }
  }
  // 從k的位置開始之后的都應(yīng)該為0
  while(lastZeroIndex < nums.length){
    nums[lastZeroIndex++] = 0;
  }
  return nums;
};

let arr = [0,1,0,3,0,9,0,12];
console.log(moveZeroes(arr)); // [ 1, 3, 9, 12, 0, 0, 0, 0 ]

以上的做法只在一個(gè)數(shù)組中操作，用變量 repalceIndex 存一下要被非零數(shù)字替換的位置。在遍歷中遇到了非0數(shù)字，則替換在 repalceIndex的位置，再將repalceIndex向后推一位，等待下一次遇到非零數(shù)字來替換，等到遍歷結(jié)束，repalceIndex 實(shí)際上就是非零數(shù)字的個(gè)數(shù)，再從這個(gè)位置開始直到數(shù)組結(jié)束都替換為0。

這樣的寫法在時(shí)間復(fù)雜度上是 O(n) 級(jí)別的，在空間復(fù)雜度上也是O(1) 級(jí)別的，因?yàn)闆]有引入了新的數(shù)組。

這樣還不是最終答案，因?yàn)樵谧詈筮€需要一個(gè) for 循環(huán)將剩下的位置都替換為0，多了一步這樣的操作是沒必要的。

下面采用交換位置的方式。

var moveZeroes = function(nums) {
  let repalceIndex = 0;  // 記錄要被交換的位置
  let replaceElement; // 中間變量，用來存不為0的數(shù)字
  for(let i = 0; i < nums.length; i++){
    if(nums[i]) {  // 當(dāng)不為0
      if(i != repalceIndex) {  // 第i個(gè)和repalceIndex相同，說明要交換的是同一個(gè)元素，沒必要進(jìn)行交換操作
        replaceElement = nums[i];
        nums[i] = 0;
        nums[repalceIndex] = replaceElement;
      }
      repalceIndex++
    }
  }
  
  return nums;
};
let arr = [0,1,0,3,0,9,0,12];
console.log(moveZeroes(arr)); // [ 1, 3, 9, 12, 0, 0, 0, 0 ]

上面的思路是這樣的，repalceIndex 記錄了第一個(gè)是0的位置，當(dāng)遇到非0的數(shù)字時(shí)候，就把非0的數(shù)字和repalceIndex所在位置的0交換位置，然后 repalceIndex 向前推進(jìn)一位，繼續(xù)記錄的還是第一個(gè)0的位置，遍歷中再與非0數(shù)字交換，再推進(jìn)。。。重復(fù)這個(gè)過程直到遍歷結(jié)束。
判斷 i != repalceIndex 是一種優(yōu)化手段，只有非0位置的數(shù)字和要交換的位置不是同一個(gè)位置才進(jìn)行交換。

我自己在寫小游戲2048的時(shí)候用到了這個(gè)題的解題思路。在小游戲2048中，設(shè)置了和界面一致的二維數(shù)組，數(shù)組的每一位記錄了一個(gè)數(shù)字。

嘗試用在小游戲2048中

我在寫2048小游戲時(shí)，數(shù)據(jù)存放的是一個(gè) 4X4 的二維數(shù)組（當(dāng)然有很多的做法，可以采用別的方式），例如這樣：

let data = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]

這些0都是占位的，代表的是還未填充任何數(shù)據(jù)，隨著玩家玩的過程，會(huì)出現(xiàn)很多數(shù)字分散在不同的位置上，當(dāng)按上下左右時(shí)，總要把所有不為0的數(shù)字撥在同一邊，0的數(shù)字在另一邊，這時(shí)就用到上述這個(gè)題的解法即可。

let data = [
    [2, 0, 0, 0],
    [0, 4, 0, 0],
    [0, 0, 2, 4],
    [0, 2, 2, 0]
]
// 遍歷取出每一個(gè)數(shù)組
for(let i = 0; i < data.length; i++){
    moveZeroes(data[i])
}

如果掌握了上述的技巧，無論是向左向右還是向上向下都可以做到。

后記

在剛開始嘗試解這道題時(shí)，心里在想，出這道題的人是有多無聊，只是為了創(chuàng)造問題而創(chuàng)造，壓根想不到這道題的應(yīng)用場景在哪里，這也跟自己的眼界有關(guān)系。當(dāng)我在嘗試做2048小游戲時(shí)，設(shè)計(jì)出來存放數(shù)據(jù)結(jié)構(gòu)后，開始實(shí)現(xiàn)自己要實(shí)現(xiàn)的方式時(shí)，才意識(shí)到原來這么簡單的一道題不是沒有場景，而是自己沒遇到，當(dāng)遇到時(shí)豁然開朗。

這也給了我一個(gè)啟示，任何一道題存在必然是有原因的，它就是解決了某一個(gè)問題而存在的，當(dāng)我有了這樣的意識(shí)，在做每一道題的時(shí)候，會(huì)多問自己一下，這道題的應(yīng)用場景在哪里，我現(xiàn)在做的項(xiàng)目中有沒有類似的場景可以套用，如果沒有，去找一種案例應(yīng)用在場景中，這樣刷完提后不至于很快忘記，只要記住了案例，刷的題也自然而然的記住了。

以上如有偏差歡迎指正學(xué)習(xí)，謝謝。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/101523.html

相關(guān)文章

  • Leetcode PHP題解--D68 283. Move Zeroes

    摘要：題目鏈接題目分析給定一個(gè)整數(shù)數(shù)組，將值為的元素移動(dòng)到數(shù)組末尾，而不改動(dòng)其他元素出現(xiàn)的順序。再在去后的元素末尾填充到計(jì)算出的數(shù)組長度。最終代碼若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。 D68 283. Move Zeroes 題目鏈接 283. Move Zeroes 題目分析 給定一個(gè)整數(shù)數(shù)組，將值為0的元素移動(dòng)到數(shù)組末尾，而不改動(dòng)其他元素出現(xiàn)的順序。 思路 計(jì)算總共有多少個(gè)元素。 再...

    xiongzenghui 評(píng)論0 收藏0

  • leetcode 283 Move Zeroes

    題目詳情 Given an array nums, write a function to move all 0s to the end of it while maintaining the relative order of the non-zero elements.For example, given nums = [0, 1, 0, 3, 12], after calling your ...

    RobinQu 評(píng)論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...

    leo108 評(píng)論0 收藏0

  • LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

    摘要：每天會(huì)折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號(hào)上。三匯總返回目錄在月日月日這半個(gè)月中，做了匯總了數(shù)組知識(shí)點(diǎn)?；蛘呃奖疚淖钕旅?，添加的微信等會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

    tracy 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<