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