LeetCode 解題練習：Find Numbers with Even Number of Digits

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

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-numbers-with-even-number-of-digits/

中文描述

給一個整數陣列 nums ，找出這些整數中有多少個數字的位數是偶數。

限制條件：

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 100000

範例一：

輸入 nums = [1, 12, 123, 1234, 11111, 13579] 

輸出  2

因為 

1 有一位數

12 有兩位數

123 有三位數

1234 有四位數

11111 有五位數

13579 有五位數

只有 12 和 1234 有偶數位數。

解法一：

用整數除法除以 10 算出每個數字的位數。

Python Code

class Solution:

    # count the number's digits

    def countDigits(self, n):

        digits = 0

        while n > 0:

            digits = digits + 1

            n = n // 10 # 整數除法

       

        return digits

    def findNumbers(self, nums: List[int]) -> int:

        evenCnt = 0

        for n in nums:

            if self.countDigits(n) % 2 == 0:

                evenCnt = evenCnt + 1

       

        return evenCnt

解法二：

將數字轉換成字串，判斷字串的長度是否為偶數。

Python Code

class Solution:

    def findNumbers(self, nums: List[int]) -> int:

        evenCnt = 0

        for n in nums:

            n = str(n) # 轉成字串

            if len(n) % 2 == 0: # 取得字串長度

                evenCnt = evenCnt + 1

       

        return evenCnt

解法三：

對整數 n 取對數 log10 後再加 1 ，再取此值的整數部分。

Python Code

import math

class Solution:

    def findNumbers(self, nums: List[int]) -> int:

        evenCnt = 0

        for n in nums:

            n = int(math.log10(n)) + 1 # 取對數 log10

            if n % 2 == 0:

                evenCnt = evenCnt + 1

       

        return evenCnt

解法四：

使用條件範圍限制。因為此題數值的範圍為 1 <= nums[i] <= 100000，所以可以用 if/elif/else 來計算位數。

數字範圍在底下之一：

• 10 <= n <= 99
• 1000 <= n <= 9999
• 100000 <= n

皆符合題目要求。

Python Code

class Solution:

    def findNumbers(self, nums: List[int]) -> int:

        evenCnt = 0

        for n in nums:

            if n == 100000 \

            or (n >= 10 and n <= 99) \

            or (n >= 1000 and n <= 9999):

                evenCnt = evenCnt + 1

       

        return evenCnt

LeetCode 解題練習：Max Consecutive Ones

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

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/max-consecutive-ones/

中文描述

給一個二進位陣列 nums ，找出最大連續出現 1 的次數。

範例一：

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

輸出 4

範例二：

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

輸出 3

解法：

使用一個變數 curOnes 紀錄目前連續出現 1 的次數，若目前的數字為 0 ，將 curOnes 歸零。

每次將 curOnes 加 1 時，與 maxOnes 比較，若 curOnes 比 maxOnes 大，則 maxOnes 等於 curOnes。

Python Code

class Solution:

    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:

        curOnes = 0

        maxOnes = 0

        for n in nums:

            if n == 0:

                curOnes = 0

           

            curOnes += n

            if curOnes > maxOnes:

                    maxOnes = curOnes

        return maxOnes

Leet 解題練習：Ransom Note

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

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/ransom-note/

中文描述

給定兩個字串 ransomNote 與 magazine。判斷 ransomNote 是否可由 magazine 中的英文字母所組成。 magazine 中的每一個英文字母只能使用一次。

範例一：

輸入 ransomNote = "c", magazine = "d"

輸出 false

範例二：

輸入 ransomNote = "bb", magazine = "bc"

輸出 false

範例三：

輸入 ransomNote = "aabc", magazine = "cbaa"

輸出 true

範例四：

輸入 ransomNote = "bb", magazine = "bcb"

輸出 true

解法一：

判斷 ransomNote 的一個字母是否有在 magazine 出現，若沒有輸出 false。

若有，則將此字母從 magazine 移除。

ransomNote 每個字母都判斷完畢後，即可輸出 true。

Python Code

class Solution:

    def canConstruct(self, ransomNote: str, magazine: str) -> bool:

        for ch in ransomNote:

            if ch not in magazine:

                return False

           

            magazine = magazine.replace(ch, '', 1)

        return True

解法二：

使用 key 和 value 的資料結構 letterDic，將 magazine 的每個字母出現的個數統計起來。

判斷 ransomNote 的一個字母是否有在 letterDic 的所有 key 值中出現，若沒有，輸出 false。

若有，將此 key 的 value 減去 1，若此 value 值為零時，從 letterDic 刪除此 key。

ransomNote 每個字母都判斷完畢後，即可輸出 true。

Python Code

class Solution:

    def canConstruct(self, ransomNote: str, magazine: str) -> bool:

        letterDic = {}

        for ch in magazine:

            if ch in letterDic:

                letterDic[ch] = letterDic[ch] + 1

            else:

                letterDic[ch] = 1

       

        for ch in ransomNote:

            if ch not in letterDic:

                return False

           

            letterDic[ch] = letterDic[ch] - 1

            if letterDic[ch] == 0:

                del letterDic[ch]

       

        return True

LeetCode 解題練習：Middle of the Linked List

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

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/middle-of-the-linked-list/

中文描述

指定一個單向鏈結串列 head，找出此鏈結串列的中間節點。如果有兩個中間節點(串列大小為偶數時)，請顯示第二個。

範例一：

輸入  head = [1, 3, 5, 7, 9]

輸出 [5, 7, 9]

因為 5 是中間節點。

範例二：

輸入  head = [1, 3, 5, 7, 9, 11]

輸出 [7, 9, 11]

因為 5 與 7 是中間節點，選擇第二個 7。

解法一：

用迴圈與掃過串列一次，算出串列大小 size， 之後再用從節點開頭逐一走訪至 size // 2 來找出中間節點。

Python Code

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:

        size = 0

        t = head

        while t != None:

            t = t.next

            size += 1

       

        size = size // 2

        i = 0

        while i < size:

            head = head.next

            i += 1

       

        return head

解法二：

使用指標的方式，在走訪串列時，一個指標 middle 指到中間節點，一個指標 end 指到結尾節點。底下以圖解說明：

Python Code

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:

        middle = head

        end = head

        while end != None and end.next != None:

            middle = middle.next

            end = end.next.next

       

        return middle

程式語言如何產生不重複的數字(Non-Repeated Number)

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

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

在固定範圍的數字內，要產生不重複的數字通常有兩種方法：抽牌與洗牌。

抽牌

利用陣列標記已經抽到的牌。若亂數取到被抽走的數字，則重新取亂數。

C++ Code

#include <iostream>

#include <cmath>

#include <ctime>

using namespace std;

int main() {

    srand(time(NULL));

    int a = 0, b = 0;

    cout << "請輸入數字範圍[a, b](注意 a < b)：";

    cin >> a >> b;

    int range = b - a + 1;

    int marked[range];

    int i = 0;

    while(i < range)

    {

        int randNum = rand() % range;

        if(marked[randNum] == 1) // 若亂數取到被抽走的數字，則重新取亂數。

            continue;

        marked[randNum] = 1; // 抽走的數字標記為 1

        cout << randNum + a << ", ";

        i++;

    }

    return 0;

}

Python Code

import random

nums = input("請輸入數字範圍[a, b](注意 a < b，並以,區分數字)：")

nums = nums.split(",")

a, b = map(int, nums)

count = b - a + 1

marked = [0] * count

i = 0

while i < count:

    randNum = random.randint(0, count - 1)

    if marked[randNum] == 1: # 若亂數取到被抽走的數字，則重新取亂數。

        continue

   

    marked[randNum] = 1 # 抽走的數字標記為 1

    print(randNum + a, end=", ")

    i = i + 1

洗牌

此方法會建立一個陣列，存放所有要被抽的數字，每次隨機選出兩個數字，將兩個數字的位置(索引)交喚。交換次數可自行定義。

C++ Code

#include <iostream>

#include <cmath>

#include <ctime>

using namespace std;

int main() {

    srand(time(NULL));

    int a = 0, b = 0;

    cout << "請輸入數字範圍[a, b](注意 a < b)：";

    cin >> a >> b;

    int numOfExchange = 1000; // 洗牌次數

    int range = b - a + 1;

    int numbers[range];

    for(int i = 0; i < range; i++) // 指定陣列的數字

        numbers[i] = a + i;

    for(int i = 0; i < numOfExchange; i++) {

        int iIdx = rand() % range; // 隨機抽兩個數字

        int jIdx = rand() % range;

        // 交換兩個數字的索引位置

        int temp = numbers[iIdx];

        numbers[iIdx] = numbers[jIdx];

        numbers[jIdx] = temp;

    }

    for(int i = 0; i < range; i++) {

        cout << numbers[i] << ", ";

    }

   

    return 0;

}

Python Code

import random

nums = input("請輸入數字範圍[a, b](注意 a < b，並以,區分數字)：")

nums = nums.split(",")

a, b = map(int, nums)

count = b - a + 1

numbers = [0] * count

for i in range(1, count + 1):

    numbers[i - 1] = i # 指定陣列的數字

numOfExchange = 1000 # 洗牌次數

for i in range(numOfExchange):

    # 隨機抽兩個數字

    iIdx = random.randint(0, count - 1)

    jIdx = random.randint(0, count - 1)

   

    # 交換兩個數字的索引位置

    temp = numbers[iIdx]

    numbers[iIdx] = numbers[jIdx]

    numbers[jIdx] = temp

print(numbers)

LeetCode 解題練習：Number of Steps to Reduce a Number to Zero

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

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/number-of-steps-to-reduce-a-number-to-zero/

中文描述

給定一個整數 num ，算出需要幾步驟才能減至為零。一個步驟定義如下：若現在數字是偶數，請除以 2，否則請減去 1 。

範例一：

輸入 4 

輸出 3

因為 

步驟一：4 / 2 = 2。

步驟二：2 / 2 = 1。

步驟三：1 - 1 = 0。

範例二：

輸入 7

輸出 5

因為 

步驟一：7 - 1 = 6。

步驟二：6 / 2 = 3。

步驟三：3 - 1 = 2。

步驟四：2 / 2  =1。

步驟五：1 - 1 = 0。

解法一：

使用迴圈、if、取餘數運算子。

Python Code

class Solution:

    def numberOfSteps(self, num: int) -> int:

        steps = 0

        while num > 0:

            if num % 2 == 0:

                num /= 2

            else:

                num -= 1

            steps += 1

       

        return steps

解法二：

使用位元運算子。

Python Code

class Solution:

    def numberOfSteps(self, num: int) -> int:

        steps = 0

        bitmask = 1

        while num > 0:

            if num & bitmask == 0:

                num = num >> 1

            else:

                num -= 1

            steps += 1

       

        return steps

LeetCode 解題練習：Fizz Buzz

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

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/fizz-buzz/

中文描述

給一個整數 n，產生一個一維字串陣列 answer，此陣列須根據下列條件產生：

1. 如果 i 被 3 且也被 5 整除，answer[i] 等於 "FizzBuzz"。

2. 如果 i 被 3，answer[i] 等於 "Fizz"。

3. 如果 i 被 5 整除，answer[i] 等於 "Buzz"。

4. 其餘狀況 answer[i] 等於 i。

範例一：

輸入 n = 4

輸出 ['1', '2', 'Fizz', '4']

 

範例二：

輸入 n = 8

輸出 ['1', '2', 'Fizz', '4', 'Buzz', 'Fizz', '7', '8']

 

範例三：

輸入 n = 12

輸出 ['1', '2', 'Fizz', '4', 'Buzz', 'Fizz', '7', '8', 'Fizz', 'Buzz', '11', 'Fizz']

 

解法：

用 if 與取餘數運算子，迴圈的數值 i 從 1 開始到 n 來判斷即可。

Python Code

class Solution:

    def fizzBuzz(self, n: int) -> List[str]:

        answer = []

        for i in range(1, n + 1):

            if i % 15 == 0:

                answer.append("FizzBuzz")

            elif i % 3 == 0:

                answer.append("Fizz")

            elif i % 5 == 0:

                answer.append("Buzz")

            else:

                answer.append(str(i))

       

        return answer

LeetCode 解題練習：Richest Customer Wealth

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

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/richest-customer-wealth/description/

中文描述

給定一個 m * n 的陣列 accounts ，accounts[i][j] 是第 i 個客戶在第 j 個銀行裡的存款金額。請找出最富有的客戶。客戶的財富是將每間銀行的存款加總起來。

範例一：

輸入 accounts = [ [2, 3, 5], [7, 1, 9] ]

輸出 17 

因為第一個客戶財富為 2 + 3 + 5 = 10

因為第二個客戶財富為 7 + 1 + 9 = 17

範例：

輸入 accounts = [ [2, 3, 5], [7, 1, 9], [11, 13, 2]

輸出  26

因為第一個客戶財富為 2 + 3 + 5 = 10

因為第二個客戶財富為 7 + 1 + 9 = 17

因為第三個客戶財富為 11 + 13 + 2 = 26

解法：

使用迴圈將每一列的數值加總存到 wealth，並與目前最大財富 maxWealth 比較，若大於 maxWealth 則 maxWealth 等於 wealth 。

Python Code

class Solution:

    def maximumWealth(self, accounts: List[List[int]]) -> int:

        maxWealth = 0

        for account in accounts:

            wealth = 0

            for w in account:

                wealth = wealth + w

           

            if wealth > maxWealth:

                maxWealth = wealth

       

        return maxWealth

LeetCode 解題練習：Running Sum of 1d 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/running-sum-of-1d-array/

中文描述

指定一個整數陣列 nums ，與定義 runningSum[i] = nums[0] + nums[1] + nums[2] + ... nums[i-1] + nums[i] 。

範例一：

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

輸出 runningSum[i] = [1, 4, 9, 18] 

因為 runningSum[i] = [1, 1 + 3, 1 + 3 + 5, 1 + 3 + 5 + 9]

範例二：

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

輸出 runningSum[i] = [2, 4, 6, 8] 

因為 runningSum[i] = [2, 2 + 2, 2 + 2 + 2, 2 + 2 + 2 + 2]

解法：

因為從陣列的第二個元素開始，就是前一個陣列元素 nums[i-1] 加上自己本身 nums[i]，可導出公式為 nums[i] = nums[i-1] + nums[i] ，i 從 1 開始。於是使用迴圈來更新 nums[i] 的值即可。

Python Code

class Solution:

    def runningSum(self, nums: List[int]) -> List[int]:

        for i in range(1, len(nums)):

            nums[i] = nums[i] + nums[i-1]

       

        return nums

LeetCode 解題練習：Two Sum (Easy)

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

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/two-sum/description/

中文描述

指定一個整數陣列 nums 以及一個整數 target，找出在陣列中的兩個整數總合為 target 之索引位置。可以假設每組測試資料剛好只有一組不重複的答案，且一個陣列元素只會使用一次。

範例一：

輸入 nums = [1, 3, 5, 9], target = 8

輸出 [1, 2]

因為 nums[1] + nums[2] = 3 + 5 = 8

範例二：

輸入 nums = [1, 3, 5, 2, 9], target = 10

輸出 [0, 4]

因為 nums[0] + nums[4] = 1 + 9 = 10

解法一：暴力法 Brute Force

使用迴圈找出陣列中任兩個元素 nums[i] + nums[j] 的總和是否等於 target 。

Python Code

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        eleLen = len(nums)

        for i in range(eleLen):

            for j in range(i + 1, eleLen):

                if nums[i] + nums[j] == target:

                    return [i, j]

C++ Code

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> ret;

        for(int i = 0; i < nums.size(); i++) {

            for(int j = i + 1; j < nums.size(); j++) {

                if( nums[i] + nums[j] == target ) {

                    ret.push_back(i);

                    ret.push_back(j);

                    return ret;

                }

            }

        }

        return ret;

    }

};

解法二：兩階段查表法 ( two-pass hash table)

第一階段將陣列元素的值當成查詢的鍵值 key，陣列元素的索引當成查詢的值 value。以 nums = [1, 3, 5, 9] 為例，將會建立一個如下的 hash table：

key	value
1	0
3	1
5	2
9	3

然後檢查  target - nums[i] 是否存在此 hask table 的鍵值中。

Python Code

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        hashTable = {}

        eleLen = len(nums)

       

        # First Pass

        for i in range(eleLen):

            hashTable[nums[i]] = i

       

        # Second Pass

        for i in range(eleLen):

            diff = target - nums[i]

            if diff in hashTable and hashTable[diff] != i:

                return [i, hashTable[diff]]

解法三：一階段查表法 ( one-pass hash table)

在建立 hash table 時，可以先檢查  target - nums[i] 是否存在此 hash table 的鍵值中，再建立 hash table。

Python Code

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        hashTable = {}

        eleLen = len(nums)

       

        # One Pass

        for i in range(eleLen):

            diff = target - nums[i]

            if diff in hashTable:

                return [i, hashTable[diff]]

           

            hashTable[nums[i]] = i # 先檢查再建立 hash table