LeetCode 解題練習:Plus One

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/plus-one/

中文描述

給定一個用陣列 digits 表示大整數 large integer,digits[i] 代表大整數的第 i 位數之值。例如 12345 會以 digits = [1, 2, 3, 4, 5] 來表示。請將 digits 的數值加一。


範例一:

輸入 digits = [9,9,9,9] 

輸出  [1, 0, 0, 0, 0]

說明:整數 9999  加一後為 10000。


範例二:

輸入 digits = [2, 2, 3, 4, 5] 

輸出  [2, 2, 3, 4, 6]

說明:整數 22345  加一後為 22346。


解法:

若目前 digits[i] 為 9 ,將 digits[i] 設定為 0;否則 digits[i] 加一並回傳 digits。若每位數都是9,在最左邊補1。


Python Code

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1, -1, -1): # 從最右邊位置開始判斷
            if digits[i] == 9: # digits[i]為9,要進位
                digits[i] = 0
            else:
                digits[i] += 1 # digits[i] 加一
                return digits

        return [1] + digits # 全部數字皆為 9,在最左邊補 1。

LeetCode 解題練習:Largest Number At Least Twice of Others

 若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/largest-number-at-least-twice-of-others/

中文描述

給定一個有唯一最大值的整數陣列 nums ,請判斷此最大值元素是否為其他陣列元素值的兩倍以上,若有成立,請回傳此最大值在陣列中的索引位置。


範例一:

輸入 nums = [1, 2, 3, 6, 2, 3, 1]

輸出 3

因為 6 是最大值,且都為其他陣列元素[1, 2, 3]的兩倍以上。


範例二:

輸入 nums = [1, 2, 3, 4, 6]

輸出 -1

因為 6 是最大值,但 6 不是 4 的兩倍以上。


解法一:

Two Pass。

先找出最大值 largestNum 與索引位置 largestIdx。

判斷陣列中所有非最大值之元素是否有 largestNum 小於 nums[i] * 2,若有,回傳 -1。


Python Code

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        largestNum = -1 # 最大值
        largestIdx = -1 # 最大值位置
       
        # 找最大值與索引位置
        for i in range(len(nums)):
            if nums[i] > largestNum:
                largestNum = nums[i]
                largestIdx = i
       
        for n in nums:
            if n != largestNum and 2*n > largestNum: # 非最大值元素的兩倍是否大於最大值
                return -1
       
        return largestIdx


解法二:

One Pass。

找出第一大值 largestNum、第二大值 secondNum,判斷 largestNum 是否有小於兩倍的 secondNum。


Python Code

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        largestNum = nums[0] # 最大值設定為第一個陣列元素
        secondNum = 0 # 第二大值
        largestIdx = 0 # 最大值位置
       
        # 找最大值與索引位置
        for i in range(1, len(nums)):
            if nums[i] > largestNum:
                secondNum = largestNum
                largestNum = nums[i]
                largestIdx = i
            elif nums[i] > secondNum:
                secondNum = nums[i]
       
        if largestNum < 2 * secondNum:
            return -1

        return largestIdx

LeetCode 解題:Find Pivot Index

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/find-pivot-index/

中文描述

給定一個整數陣列 nums ,找出某目標索引位置 Pivot Index,讓目標索引位置的左邊元素陣列元素總和等於目標索引位置的右邊陣列元素總和,總和不包含目標索引位置之值。


範例一:

輸入 nums = [1, 2, 3, 4, 2, 2, 2] 

輸出  3

因為  [1, 2, 3] 總和等於 6 等於 [2, 2, 2]總和


範例二:

輸入 nums = [3, -3, 3] 

輸出  0

因為  [] 總和等於 0 等於 [-3, 3] 總和


解法一:

暴力法。對每一個索引位置算出左邊元素陣列元素總和 leftSum 與右邊元素陣列元素總和 rightSum 是否相等。


Python Code

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums) # 陣列總和
        leftSum = 0 # 左邊總和
        for i in range(len(nums)): # 從左邊索引0開始找起
            rightSum = sum(nums[i+1:]) # 右邊總和
            leftSum = total - rightSum - nums[i] # 左邊總和

            if leftSum == rightSum: # 若一樣
                return i # 找到 Pivot Index

        return -1


解法二:

算出右邊總和 rightSum,與 leftSum 等於零。從索引位置0開始依序從 rightSum 刪除 nums[i] 數值,判斷 leftSum 是否等於 rightSum,若有,則找到。leftSum 開始依序加入 nums[i] 數值。



Python Code

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        rightSum = sum(nums) # 右邊總和
        leftSum = 0 # 左邊總和
        for i in range(len(nums)): # 從左邊索引0開始找起
            rightSum -= nums[i]
            if leftSum == rightSum: # 若一樣
                return i # 找到 Pivot Index
           
            leftSum += nums[i]

        return -1


LeetCode 解題練習:Find All Numbers Disappeared in an Array

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

中文描述

給定一個含有[1, n] 之間的n個元素之整數陣列 nums (陣列長度為 n),找出[1, n] 之間沒有出現在 陣列 nums 元素中的整數。 


範例一:

輸入 nums = [2, 2] 

輸出 [1]


範例二:

輸入 nums = [1, 2, 2] 

輸出 [3]


範例三:

輸入 nums = [1, 2, 1, 2, 1, 3, 4] 

輸出 [5, 6, 7]


解法一:

使用計數的方式記錄[1,n]每一個數字出現在 nums 的次數,再統計出現次數為0的數字有哪些。


Python Code

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        counts = [0] * n # 計算 [1,n] 數字出現的次數
       
        for i in nums:
            counts[i - 1] += 1 # 出現一次就增加1
       
        missingNumbers = [] # 沒出現在 nums 的數字
       
        for i in range(n):
            if counts[i] == 0: # 若出現次數為0次
                missingNumbers.append(i+1) # 加入到未出現之數字清單
       
        return missingNumbers


解法二:

使用不包含重複資料的資料結構,例如集合 set、字典 dictionary 來存放 nums 陣列中的數字,再找出沒有出現的數字。 


Python Code

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        uniquedNumbers = set(nums) # 去除重複的數字
        disappearedNumbers = [] # 存放 [1, n] 中沒有在 nums 出現的數字

        for n in range(1, len(nums) + 1): # 走訪 [1,n] 數字
            if n not in uniquedNumbers: # 若沒有出現在 nums 中
                disappearedNumbers.append(n) # 加入沒有出現的數字清單中
       
        return disappearedNumbers


解法三:

讓有出現在 nums 的數字 i ,當成索引後,變更 nums[i] 為有負號,在統計 nums[i] 中有哪些 nums[i] 值為大於零,i 值為未出現在 nums 的數字。

Python Code

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
       
        for i in nums:
            idx = abs(i) - 1 # 索引為 i 之正值減去 1
            if nums[idx] > 0: # 若大於零
                nums[idx] = -nums[idx] # 變成負數, i 標記為有出現
       
        missingNumbers = [] # 沒出現在 nums 的數字
       
        for i in range(len(nums)):
            if nums[i] > 0: # 若大於零,代表 i 未出現在 nums 中
                missingNumbers.append(i+1) # 加入到未出現之數字清單
       
        return missingNumbers

LeetCode 解題練習:Height Checker

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/height-checker/ 

中文描述

給定一個整數陣列 heights ,請算出 heights 中沒有依照由小到大之順序的元素個數。


範例一:

輸入 heights = [3, 1, 2] 

輸出 3

因為依照小到大的陣列為 [1, 2, 3] ,heights 每個元素皆不再所屬的排序位置上。


範例二:

輸入 heights = [1, 3, 2] 

輸出 2

因為依照小到大的陣列為 [1, 2, 3] ,heights[0]有在排序的位置上,其餘元素皆不在所屬的排序位置上。


範例三:

輸入 heights = [1, 2, 3] 

輸出 0

因為依照小到大的陣列為 [1, 2, 3] ,heights所有元素皆在所屬的排序位置上。


解法:

先用內建排序函式產生由小排到大的 expected 陣列,依照索引位置 i 算出 heights[i] != expected[i] 有多少個。


Python Code

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        expected = sorted(heights)
        notMatch = 0

        for i in range(len(heights)):
            if heights[i] != expected[i]:
                notMatch += 1

        return notMatch


LeetCode 解題練習:Sort Array By Parity

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/sort-array-by-parity/

中文描述

給定一個整數陣列 nums ,產生一個陣列將nums中所有偶數放在陣列開頭,放完偶數後再放奇數。


範例一:

輸入 nums = [5, 2, 4, 1] 

輸出 [2, 4, 5, 1] 或 [4, 2, 1, 5] 或 [2, 4, 1, 5] 或 [4, 2, 5, 1] 皆可為答案


範例二:

輸入 nums = [5, 2, 1] 

輸出 [2, 5, 1] 或 [2, 1, 5] 皆可為答案



解法一:

建立一個陣列 parityArr ,迴圈走訪 nums 陣列,若 nums[i] 為偶數,加到 parityArr 最前面;若 nums[i] 為奇數,加到 parityArr 最後面。


Python Code

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        parityArr = []
       
        for n in nums:
            if n % 2 == 0:
                parityArr.insert(0, n) # 偶數加到parityArr最前面
            else:
                parityArr.append(n) # 奇數加到parityArr最後面

        return parityArr


解法二:

同解法一,但用 Python List Comprehension 語法。


Python Code

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        parityArr = [n for n in nums if n % 2 == 0] + [n for n in nums if n % 2 == 1]
       
        return parityArr


解法三:

雙指標。當 even 小於 odd時,even 從左開始找非偶數的位置, odd 從右邊開始找非奇數位置,將 nums[even] 與 nums[odd] 互換。參考底下圖片說明



Python Code

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        even = 0
        odd = len(nums) - 1
       
        while even < odd:
            while even < odd and nums[even] % 2 == 0: even += 1
            while even < odd and nums[odd] % 2 == 1: odd -= 1

            nums[even], nums[odd] = nums[odd], nums[even]
       
        return nums


LeetCode 解題練習:Move Zeroes

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/move-zeroes/

中文描述

給定一個整數陣列 nums ,將所有的 0 移到陣列結尾處,並保持原先非零整數的順序。請修改原本陣列 nums 的內容來完成。


範例一:

輸入 nums = [0, 1, 0, 5, 0, 0, 3] 

輸出 nums = [1, 5, 3, 0, 0, 0, 0]


範例二:

輸入 nums = [0, 0, 1] 

輸出 nums = [1, 0, 0]


範例三:

輸入 nums = [1] 

輸出 nums = [1]


範例四:

輸入 nums = [0] 

輸出 nums = [0]


解法一:

left = 0,從左邊開始往右移動,如果陣列元素 nums[i] 不等於零 ,則將此元素複製到 nums[left],再將 left 加 1。走訪完陣列後,left 為非零整數的數量,從left索引位置之後的元素通通設為零。

Python Code

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left = 0
        for i in range(len(nums)): # 從左邊開始往右移動
            if nums[i] != 0: # 陣列元素 nums[i] 不等於零
                nums[left] = nums[i] # 將此元素複製到 nums[left]
                left += 1 # 將 left 加 1
       
        # left 為非零整數的數量
        while left < len(nums): # 將 left 索引位置之後的元素通通設為零。
            nums[left] = 0
            left += 1

解法二:

找出數字零 zeroPos 的位置,然後開始往後找非零數字 nums[i] != 0 位置,將 nums[i] 與 nums[zeroPos] 交換,並更新 zeroPos 的位置。

Python Code

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zeroPos = 0
       
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[zeroPos], nums[i] = nums[i], nums[zeroPos] # 交換
                zeroPos += 1      


LeetCode 解題練習:Replace Elements with Greatest Element on Right Side

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/

中文描述

給定一個整數陣列 arr,將每個元素用該元素的右邊所有元素中之最大值來取代,並將最後一個元素用-1取代。


範例一:

輸入  arr = [45, 333, 2, 1, 9, 17]

輸出 [333, 17, 17, 17, 17, -1]

因為 45 右邊元素 [333, 2, 1, 9, 17] 最大值為 333。

因為 333 右邊元素 [2, 1, 9, 17] 最大值為 17。

因為 2 右邊元素 [1, 9, 17] 最大值為 17。

因為 1 右邊元素 [9, 17] 最大值為 17。

因為 9 右邊元素 [17] 最大值為 17。


範例二:

輸入  arr = [333]

輸出 [-1]

 

解法:

以 curMax = -1 當目前最大值,t暫存目前陣列元素。從陣列的右邊開始以curMax替代,若 t 大於 curMax,則更新 curMax 為 t。


可參考底下圖片動畫說明:



Python Code

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        curMax = -1 # 目前最大值
        for i in range(len(arr)-1, -1, -1): # 從右邊開始替代
            t = arr[i] # 暫存目前陣列元素
            arr[i] = curMax # 以目前最大值替代陣列元素
            if t > curMax: # 若此陣列元素比目前最大值大
                curMax = t # 更新目前最大值
       
        return arr


LeetCode 解題練習:Guess Number Higher or Lower

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/guess-number-higher-or-lower/

中文描述

電腦從 1 到 n 選一個數字,當玩家猜數字時,電腦會給予太高或太低的提示。請使用以定義的函式 int guess(int num),此函式回傳值得意義如下:

  • -1 ,代表玩家猜的數字比電腦選的大。
  • 1 ,代表玩家猜的數字比電腦選的小。
  • 0 ,代表玩家猜中電腦選的數字。

請輸出電腦所選的數字為何。


範例一:

輸入 n = 10, 電腦選 4

輸出 4


範例二:

輸入 n = 100, 電腦選 93

輸出 93


解法:

使用二分搜尋法 Binary Search 解即可。


Python Code

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        l = 1
        r = n
        g = (l + r) // 2

        ans = guess(g)
        while ans != 0:
            if ans == -1:
                r = g - 1
            else:
                l = g + 1
           
            g = (l + r) // 2
            ans = guess(g)
   
        return g


LeetCode 解題練習:Valid Mountain Array

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/valid-mountain-array/

中文描述

給定一個整數陣列 arr,檢查此陣列是否為一個合格的山脈陣列(Valid Mountain Array)。Valid Mountain Array 的定義如下:

  • 陣列長度大於等於3。
  • 存在一個整數 i ,且 0 < i < 陣列長度,使得底下條件成立:
    • arr[0] < arr[1] < arr[2] < ... < arr[i-2] < arr[i-1] < arr[i]
    • arr[arr.length - 1] < arr[arr.length - 2] < arr[arr.length - 3] < .... < arr[i + 2] < arr[i + 1] < arr[i]
 

範例一:

輸入 arr = [1, 2]

輸出 false

因為陣列長度小於 3


範例二:

輸入 arr = [1, 2, 1]

輸出 true


範例三:

輸入 arr = [1, 2, 2, 3, 1]

輸出 false

因為 arr[1] = 2 = arr[2],非嚴格遞增。 


範例四:

輸入 arr = [1, 2, 3, 3, 2, 1]

輸出 false

因為 arr[2] = 3 = arr[3],非嚴格遞減。 


解法一:

left 從左邊開始往右找,找到非嚴格遞增的位置。

right = left + 1,繼續往右找,找到非嚴格遞減的位置。

回傳 left != 0 and left < len(arr) - 1 and right == len(arr)。


Python Code 

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        left = 0

        while left < len(arr) - 1:
            if arr[left] >= arr[left + 1]: # 若找到非嚴格遞增
                break
            left += 1

        right = left + 1
        while right < len(arr):
            if arr[right - 1] <= arr[right]: # 若找到非嚴格遞減
                break
            right += 1
       
        return left != 0 and left < len(arr) - 1 and right == len(arr)
       


解法二:

left 從左邊開始往右找,找到非嚴格遞增的位置。

right 從右邊開始往左找,找到非嚴格遞減的位置。

回傳 left != 0 and left == right and right != len(arr) - 1


Python Code

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        left = 0

        while left < len(arr) - 1:
            if arr[left] >= arr[left + 1]: # 若找到非嚴格遞增
                break
            left += 1

        right = len(arr) - 1
        while right > 0:
            if arr[right - 1] <= arr[right]: # 若找到非嚴格遞減
                break
            right -= 1
       
        return left != 0 and left == right and right != len(arr) - 1
       


LeetCode 解題練習:Check If N and Its Double Exist

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/check-if-n-and-its-double-exist/

中文描述

給定一個整數陣列 arr,找出陣列中兩個不一樣位置的元素是不是符合 arr[i] * 2 = arr[j],其中 i != j。 


範例一:

輸入 arr = [-1, 8, 2, 1, 4]

輸出 true

因為元素 4 是元素 2 * 2。



範例一:

輸入 arr = [-1, 8, 3, 1, 4]

輸出 false

因為沒有任一兩個元素符合 arr[i] * 2 = arr[j],其中 i != j。


解法一:

先排序,在用二分搜尋法找有沒有目前陣列元素兩倍的數字出現在不同的索引位置。


Python Code

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        arr.sort()
        count = len(arr)
        for i in range(count):
            pro = arr[i] * 2
            left = 0
            right = len(arr) - 1
            while left <= right:
                middle = (left + right) // 2
                if arr[middle] == pro and i != middle:
                    return True
                elif arr[middle] > pro:
                    right = middle - 1
                else:
                    left = middle + 1
           
        return False


解法二:

使用 hastTable 來儲存陣列的每一個元素 ele,在每次加入一個元素時檢查 ele * 2 與 ele / 2 是否有在 hashTable 出現過,若有,回傳 true。在加完陣列的每一個元素之後,回傳 false。


Python Code

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        hashTable = {}
        for ele in arr:
            if ele * 2 in hashTable or ele / 2 in hashTable:
                return True
            hashTable[ele] = 0
       
        return False


LeetCode 解題練習:Binary Search

 若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/binary-search/

中文描述

給定一個由小排到大的整數陣列 nums ,與一個整數 target,請在陣列中尋找 target 所在的索引位置。若找不到,請傳回 -1。必須用演算法時間複雜度為 O(log n) 的方法來解。


範例一:

輸入  nums = [1, 2, 3, 4, 5, 6, 7], target = 5

輸出 4

因為 5 在陣列 nums 索引位置 4。


範例二:

輸入  nums = [1, 2, 3, 4, 5, 6, 7], target = 8

輸出 -1

因為 8 不在陣列 nums 裡。


解法一:

二分搜尋法的演算法如下:

  • 設定 left = 0, right = 陣列長度 - 1。
  • 當 left <= right 時
    • middle = (left + right) / 2。
    • 判斷 target 與 nums[middle] 的大小關係。
    • 若相等,回傳 middle。
    • 若 nums[middle] 大於 target,right = middle - 1。
    • 若 nums[middle] 小於 target,left = middle  + 1。
  • 若 left > right 結束迴圈時,回傳 -1。

可參考下圖動畫說明:


Python Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            middle = (left + right) // 2
            if nums[middle] == target:
                return middle
            elif nums[middle] > target:
                right = middle - 1
            else:
                left = middle + 1
       
        return -1


LeetCode 解題練習:Sqrt(x)

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/sqrtx/

中文描述

給一個非負整數 x ,求出最接近但不大於  x 平方根的整數。注意,不能使用內建函式。


範例一:

輸入 x = 9

輸出 3


範例二:

輸入 x = 22 

輸出  4

因為 x 的平方根為 4.69041575982,取整數部分為 4 。


解法一:線性搜尋

r  = 1 開始判斷到 r * r <= x,傳回 r - 1。 


Python Code

class Solution:
    def mySqrt(self, x: int) -> int:
        r = 1
        while r * r <= x:
            r += 1
       
        return r - 1


解法二:二分搜尋

此部分可參考此教學影片的說明 https://www.youtube.com/watch?v=1_4xlky3Y2Y


Python Code

class Solution:
    def mySqrt(self, x: int) -> int:
        left = 1
        right = x

        while left <= right:
            middle = (left + right) // 2
            pow2 = middle * middle

            if pow2 == x:
                return middle
            elif pow2 < x:
                left = middle + 1
            else:
                right = middle - 1
           
        return right
           


LeetCode 解題練習:Remove Duplicates from Sorted Array

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/remove-duplicates-from-sorted-array/

中文描述

給定一個由小排到大的整數陣列 nums ,將陣列中重複的數字給刪除,並回傳不重複的元素個數k值。


範例一:

輸入 nums = [1, 1, 1, 2, 2, 3, 3]

輸出 k = 3, nums = [1, 2, 3, x, x, x, x]

因為 nums 有 3 個不重複的數字 [1, 2, 3]


解法:

設定兩個變數 left = 0 與 right = 0,從陣列左邊開始判斷,若 nums[left] != nums[right] 時,將 left 加 1 ,並將 nums[left] 設為 nums[right]。請參考底下圖片:


Python Code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        left = 0
   
        for right in range(len(nums)):
            if nums[left] != nums[right]:
                left += 1
                nums[left] = nums[right]
       

        return left + 1



LeetCode 解題練習:Remove Element

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/remove-element/

中文描述

給定一個整數陣列 nums 與一個整數 val,將 nums 中的所有 val 給移除,並回傳 nums 中不等於 val 的個數k有多少個。


範例一:

輸入 nums = [1, 1, 2, 5, 3, 1, 4], val = 1

輸出 k = 4, nums [2, 5, 3, 4, x, x, x]

因為 nums 不等於 1 的總共有 4 個。


範例二:

輸入 nums = [1, 1, 2, 2, 5, 3, 1, 4], val = 2

輸出 k = 5, nums [1, 1, 5, 3, 1, 4, x, x]

因為 nums 不等於 2 的總共有 5 個。


解法一:

用 Python List 的內建函式 remove。


Python Code

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums:
            nums.remove(val)
       
        return len(nums)


解法二:

將變數 k 設為 0,用來判斷 nums 內有幾個元素是不等於 val。

若陣列元素不等於 val,就將 k 當成 nums 的索引,並更新元素的值。

可參考底下圖片動畫說明



Python Code

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0
   
        for n in nums:
            if n != val:
                nums[k] = n
                k += 1

        return k