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]]

C++ Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        map<int, int> hashTable;

        for(int i = 0; i < nums.size(); i++)
            hashTable[nums[i]] = i;

        for(int i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if( hashTable.find(diff) != hashTable.end() && hashTable[diff] != i )  {
                ret.push_back(i);
                ret.push_back(hashTable[diff]);
                return ret;
            }
        }
        return ret;
    }
};

解法三:一階段查表法 ( 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


C++ Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        map<int, int> hashTable;

        for(int i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if( hashTable.find(diff) != hashTable.end() )  {
                ret.push_back(i);
                ret.push_back(hashTable[diff]);
                return ret;
            }
            hashTable[nums[i]] = i; // 先檢查再建立 hash table
        }
        return ret;
    }
};