leetcode刷題：283.Move Zeroes(Easy)

ckllj 發布于2019-08-23 15:06 / 714人閱讀

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

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

應用場景說明

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

解法

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

輸入：

[0,1,0,3,12]

輸出

[1,3,12,0,0]

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

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

    // 把nums中之后的位置都補上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的數字存在一個新數組中，把新數組的每一項對位的重新賦值給原來數組的位置，然后把原數組剩余的位置一律替換為0；

這樣的寫法在時間復雜度上是 O(n) 級別的，在空間復雜度上也是O(n) 級別的，因為引入了新的數組。

可以在不引入新數組的情況下做位置的調整：

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的數字，替換在0的位置,替換的位置已經不是0了，向后推一步;
    }
  }
  // 從k的位置開始之后的都應該為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 ]

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

這樣的寫法在時間復雜度上是 O(n) 級別的，在空間復雜度上也是O(1) 級別的，因為沒有引入了新的數組。

這樣還不是最終答案，因為在最后還需要一個 for 循環將剩下的位置都替換為0，多了一步這樣的操作是沒必要的。

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

var moveZeroes = function(nums) {
  let repalceIndex = 0;  // 記錄要被交換的位置
  let replaceElement; // 中間變量，用來存不為0的數字
  for(let i = 0; i < nums.length; i++){
    if(nums[i]) {  // 當不為0
      if(i != repalceIndex) {  // 第i個和repalceIndex相同，說明要交換的是同一個元素，沒必要進行交換操作
        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 記錄了第一個是0的位置，當遇到非0的數字時候，就把非0的數字和repalceIndex所在位置的0交換位置，然后 repalceIndex 向前推進一位，繼續記錄的還是第一個0的位置，遍歷中再與非0數字交換，再推進。。。重復這個過程直到遍歷結束。
判斷 i != repalceIndex 是一種優化手段，只有非0位置的數字和要交換的位置不是同一個位置才進行交換。

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

嘗試用在小游戲2048中

我在寫2048小游戲時，數據存放的是一個 4X4 的二維數組（當然有很多的做法，可以采用別的方式），例如這樣：

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

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

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

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

后記

在剛開始嘗試解這道題時，心里在想，出這道題的人是有多無聊，只是為了創造問題而創造，壓根想不到這道題的應用場景在哪里，這也跟自己的眼界有關系。當我在嘗試做2048小游戲時，設計出來存放數據結構后，開始實現自己要實現的方式時，才意識到原來這么簡單的一道題不是沒有場景，而是自己沒遇到，當遇到時豁然開朗。

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

以上如有偏差歡迎指正學習，謝謝。

GPU云服務器云服務器 Zeroes Leetcod LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/101523.html

Leetcode PHP題解--D68 283. Move Zeroes

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

xiongzenghui 2019-07-01 12:48 評論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 2019-08-15 13:54 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數組知識點。或者拉到本文最下面，添加的微信等會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0