Posted Updated 

Leetcode 解題記錄 ( 持續更新中 )

將在 Leetcode 上解過的題目寫在這裡做記錄用，語言是使用 python.

Array

26. Remove Duplicates from Sorted Array

在一個已經排序好的 array 中，移除重複的元素。

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]

Explanation: Your function should return length = 5, with the first five
elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn’t
matter what values are set beyond the returned length.

想法

  • 創造新的 array 把沒有出現過的 element，存到新的 array，再回傳新 array 的長度。但因為題目規定只能操作原本的 array，所以這個方法不可行。
  • 是使用 while，檢查第一個與上一個是否相同，相同就移除。最後回傳 array 的長度。
  • 使用 pointer 兩兩比較，最後返回 pointer 的 index.

程式碼

  • While 遍歷
    Runtime: 100 ms(faster than 26.82%) / Memory Usage: 15.8 MB (less than 93.99%)

在 i 小於 array 的長度時，如果 i 的值與 i的前一個值相等，就 pop 掉 i，否則 i 加一，繼續往下比較。遍歷結束後，重複的元素就已經被移除，直接返回 array 的長度就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
# while

def removeDuplicates(self, nums: List[int]) -> int:
    if len(nums) == 0:
        return 0
    i = 1
    while (i < len(nums)):
        if nums[i] == nums[i-1]:
                nums.pop(i)
        else:
            i += 1

    return len(nums)
  • Two pointer
    run time (76 ms) / memory (15.9MB)

這題的想法是，不停把不重複的元素往前排列，最後看 pointer 停在哪一個index 上即表示當下 index 開始就是重複的元素。index 從 0 開始，因此要加上 1， 才會是 array 的長度。

1
2
3
4
5
6
7
8
9
10
11
12
13
# two pointer

def removeDuplicates(self, nums: List[int]) -> int:
    if len(nums) == 0:
        return 0
        
    x = 0
    for i in range(0, len(nums)):
         if nums[x] != nums[i]:
                    x += 1
                    nums[x] = nums[i]

    return x + 1

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

想法

  • 使用迴圈一個一個相加，看哪一個數值最大，具體操作可以看下面的程式碼。但這個方法運算的時間太長，會超出限定的時間，來一個超大測值就掰掰。
  • 使用 kadane’s algorithm 是比較好的方式。
    滴滴面试手撕算法题-kadane算法

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
# Time limit exceeded 的暴力法

def maxSubArray(self, nums: List[int]) -> int:
    max_num = nums[0]
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)+1):
            sub = nums[i:j]
            total = sum(sub)
            if total > max_num:
                max_num = total

    return max_num
  • kadane’s algorithm
    runtime : 64 ms, faster than 72.73%
    memory: 14.9 MB, less than 53.55% 
1
2
3
4
5
6
7
8
9
10
11
# kadane's algorithm

def maxSubArray(nums):
    ans = nums[0] #global sum
    sum = 0 #local sum
    
    for i in range(len(nums)):
        sum = max(nums[i] + sum, nums[i])
        ans = max(sum, ans)
    
    return ans

66. Plus One

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Constraints:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

想法

  1. 將 list 內的 int 轉為 string > 將個別 string 抽取然後 join 起來 > 將 join 起來的string 轉成 int ，再加 1 > 轉回 string > 轉回 list
  2. 把最後一個數字加 1 ，會出現三種狀況
    • 不需要進位 ([1,2,4])
    • 需要進一位 ([1,2,9])
    • 99 這類會變成 100 的

程式碼

  • 想法 1
    runtime : 32 ms, faster than 63.10%
    memory : 14.3 MB, less than 11.54%
1
2
3
4
5
6
7
# 想法 1

def plusOne(self, digits: List[int]) -> List[int]:
    arr = [str(i) for i in digits]
    nums = str(int("".join(arr)) + 1)
    return list(nums)
  • 想法 2
    Runtime: 36 ms, faster than 23.87%
    Memory Usage: 14.2 MB, less than 73.03%
1
2
3
# 想法 2 : map
def plusOne(self, digits: List[int]) -> List[int]:
    return list(str(int("".join(map(str, digits)))+1))
1
2
3
4
5
6
7
8
def plusOne(self, digits: List[int]) -> List[int]:
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] + 1 <= 9 :
            digits[i] += 1
            return digits
        else:
            digits[i] = 0
    return [1] + [0] * len(digits)

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.

想法

  • 把 nums2 塞到 nums1，再 sort 一次
  • 使用三個指針分別指向兩個 list 有數字的結尾，第三個指針指向第一個list 結尾，比較兩個數字，放到第三個指針的位置。

程式碼

預設：

  • nums1 一定有足夠的長度塞得下 nums2
  • nums2 的長度會與 n 相等
1
2
3
4
5
6
7
def merge(nums1, m, nums2, n) :
    for i in range(n):
        nums1.remove(0)

    nums1.extend(nums2)
    nums1.sort()
    return nums1
  • 指針
    Runtime: 32 ms, faster than 88.41%
    Memory Usage: 14.1 MB, less than 95.51%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def merge(nums1, m, nums2, n) :
        p = m - 1
        q = n - 1
        k = m + n -1
    
        while p >= 0 and q >= 0:
            if nums1[p] > nums2[q]:
                nums1[k] = nums1[p]
                p , k = p - 1, k - 1
            else:
                nums1[k] = nums2[q]
                q , k = q - 1, k - 1

        nums1[:q + 1] = nums2[:q + 1]

        return nums1

167. Two Sum II - Input array is sorted

Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

想法

  • 兩個指針分別指向 list 的頭與尾，兩兩相加，大於 target 尾指針就往前移動，反之則頭指針往前移。

程式碼

  • 兩個指針
    Runtime: 68 ms, faster than 28.66%
    Memory Usage: 14.8 MB, less than 29.47%
1
2
3
4
5
6
7
8
9
10
11
def twoSum(self, numbers: List[int], target: int) -> List[int]:
    first = 0
    last = len(numbers)-1

    while first < last:
        if numbers[first] + numbers[last] > target:
            last -= 1
        elif numbers[first] + numbers[last] < target:
            first += 1
        else:
            return[first + 1, last + 1]

217. Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

想法

  • 兩層 for loop 找有沒有相同的
  • 創新的空 list， 不存在 list 裡的就數字就塞進去，再檢查
  • 先排序，再 for loop 第二個等於第一個的時候 return true
  • 使用內建 map 去除重複的，再檢查兩個 list 的長度是否相同，不相同 return true

程式碼

  • 創造新的 list
1
2
3
4
5
6
7
8
9
10
11
12
# time limit exceed

def containsDuplicate(self, nums: List[int]) -> bool:
    arr = []

    for i in nums:
        if i in arr:
            return True
        else:
            arr.append(i)

    return False
  • 先排序再檢查第二個
    Runtime: 124 ms, faster than 36.11%
    Memory Usage: 19.3 MB, less than 90.31%
1
2
3
4
5
6
7
8
9
10
11
12
# 先排序，再檢查

def containsDuplicate(self, nums: List[int]) -> bool:
    nums.sort()
    
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            print("true")
            return True

    print("false")
    return False
  • 算兩個的長度
    Runtime: 120 ms, faster than 58.63%
    Memory Usage: 20.3 MB, less than 66.17%
1
2
3
# 使用 set
def containsDuplicate(self, nums: List[int]) -> bool:
    return len(nums) != len(set(nums))

219. Contains Duplicate II

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

給一個 list 和 k , 找出重複的數字，這兩個數字的 index 相減要小於 k.
( 兩個重複數字的位置距離小於等於 k )

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Input: nums = [1,0,1,1], k = 1
Output: true

想法

  • 兩層 loop 找重複的，兩個 index 相減
  • 創造新的字典，遍歷 list 不存在的就把數字本身當 key, index 當value 存進去。如果存在字典裡，就用當下數字和 value 相減。

程式碼

  • 兩層 loop
1
2
3
4
5
6
7
8
9
10
# time limie exceed
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    for i in range(len(nums)):
        for j in range(i + 1 , len(nums)):
            if nums[i] == nums[j] and abs(i - j) <= k:
                return True
            else:
                continue

    return False
  • 字典
    Runtime: 92 ms, faster than 81.08%
    Memory Usage: 21.8 MB, less than 54.38%

如果有重複但距離大於 k 就更新字典裡當下元素的 index .

1
2
3
4
5
6
7
8
9
10
11
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    dic = {}

    for index, value in enumerate(nums):
        if value not in dic:
            dic[value] = index
        else:
            if abs(index - dic[value]) <= k:
                return True
            dic[value] = index
    return False

118. Pascal’s Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

每一層的最前和最末端都是 1 ，中間則是上一層的前一個 index 和當下 index 的和。

程式碼

是二維的 list， result[i-1][j-1] 的意思是去出 result[i-1] 再取 result[i-1] 的 [j-1].

1
2
3
4
5
6
7
8
9
10
11
12
13
def generate(numRows):
    result = []
    for i in range(numRows):
        result.append([])
        for j in range(i + 1):
            if j in (0, i):
                result[i].append(1)
            else:
                result[i].append(result[i-1][j-1] + result[i-1][j])
    
    print(result)

generate(5)

面試常出現題目

13. Roman to Integer

Input: s = “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

想法

  • 把條件都存再 dictionary 裡。
  • 有兩種情況：一是只要將數字都加起來，第第二是 4 或 9 之類的數字會以兩個字母代表的數字相減表示。I 後面會接 V / X ； X 會接 L/ C ；C 會接 D / M，這幾個情況屬於第二個情況。
  • 第二個情況三組的共同點是後面字母代表的數字會比前一個大，因此可以用這個來判斷是要相加還是要相減。
  • 判斷方法
    • 使用兩個指針

程式碼

Runtime: 44 ms, faster than 81.73%
Memory Usage: 14.3 MB, less than 56.57%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def romanToInt(s):
    dic = {"I" : 1, "V" : 5, "X" : 10, "L" : 50, "C" : 100, "D" : 500,"M" : 1000}
    result = 0
    i = len(s) - 1

    while i >= 0:
        current = dic[s[i]]
        next = dic[s[i - 1]]

        if current > next and (i != 0):
            result += (current - next)
            i -= 2
        else:
            result += current
            i -= 1

    return result

69. Sqrt(x)

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since the decimal part is
truncated, 2 is returned.

想法

  • 不能使用內建的方法來找，選擇使用 binary search
  • 會遇到的情況
    • 0 & 1 的平方會是自己
    • 可以被完整根號整除的：4, 9, 16…
    • 無法被整除的就去掉小數，回傳整數：8 回傳 2, 32 回傳 5

設定兩個 pointer ( left & right )，先找出 x 的中位數 (mid) ，mid 的平方如果大於 x 即表示後面的數字都會太大，因此將 right 指標移到 mid；如果小於 x 表示前面的數字太小，將 left 指標移到 mid + 1.

在這裡面不停 loop 直到找到 mid 的平方為 x 為止。遇到無法被整除的狀況最後 left 會等於 right，回傳該值的前一個，所以回傳 left - 1.

程式碼

Runtime: 36 ms, faster than 61.05%
Memory Usage: 14.3 MB, less than 6.12%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def mySqrt(x):

    if (x < 2):
        return x
    
    left = 1
    right = x

    while left < right:
        mid = left + (right - left) // 2
        if mid * mid == x:
            print(x)
            return mid

        if mid * mid > x:
            right = mid 
        elif mid * mid <= x:
            left = mid + 1
    return left - 1

70. Climbing Stairs

費氏數列：1,1,2,3,5,8,13…（下一個數字會是前面兩個數字的和）

You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

1
2
3
4
5
6
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

想法

如果把方法都寫出來會發現在爬 2 層梯子的時候總共有 2 種方法，3 層有 3 種方法， 4 層的時候有 5 種方法， 5 層 8 種方法，到這裡會發現，每一層的有的方法數量都是前面的和，這就是費氏數列。

1,1,2,3,5,8,13…（下一個數字會是前面兩個數字的和）

  • 使用 dictionary 將每一層數字的方法數量存起來，最後返回找出 n 的方法數

程式碼

Runtime: 32 ms, faster than 50.02%
Memory Usage: 14.3 MB, less than 10.71%

1
2
3
4
5
6
7
8
def climbStairs(n):
    dic = {1:1, 2:2, 3:3}

    for i in range(4, n + 1):
        dic[i] = dic[i - 1] + dic[i - 2]
    
    return(dic[n])

Runtime: 44 ms, faster than 6.40%
Memory Usage: 14.3 MB, less than 10.71% 

1
2
3
4
5
6
7
8
9
10
def climbStairs(self, n: int) -> int:
    arr = [1,1,2]

    for i in range(3, n + 1):
        arr.append(arr[i-1] + arr[i-2])

    if n == 1:
        return 1
    else:        
        return arr[-1]

28. Implement strStr()

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Input: haystack = “hello”, needle = “ll”
Output: 2

想法

  • 檢查 needle 是否在 hashstack 裡，如果在的話用 find 找出第一次出現的 index
  • 使用兩個 pointer(start,end) 框出範圍，檢查該範圍的字串是否等於 needle 如果等於就返回 start 的 index，不等於就返回 -1.
    • 會在 haystack 裡面尋找 needle，所以 forloop 範圍可以設為 len(haystack)
    • 但因為 loop 到後面幾個（剩餘的字串長度已經少於 needle長度），兩者一定不會相等，因此範圍可以設到 “剩餘的字串長度等於 needle長度” 的那個 index
    • 框出範圍的長度與 needle 的長度要相等，才能比較

程式碼

Runtime: 48 ms, faster than 17.58%
Memory Usage: 14.6 MB, less than 23.81%

  • 內建 find()
1
2
3
4
5
6
7
8
def strStr(self, haystack: str, needle: str) -> int:
    if not needle:
        return 0

    if needle in haystack:
        return haystack.find(needle)
    else:
        return -1

Runtime: 48 ms, faster than 64.30%
Memory Usage: 14.6 MB, less than 77.40 %

  • pointer
1
2
3
4
5
6
7
8
9
10
11
12
13
def strStr(self, haystack: str, needle: str) -> int:
    if not needle:
        return 0

    end = len(needle)
    for start in range(len(haystack) - len(needle) + 1):
        substring = haystack [ start: end ]
        if substring == needle:
            return start
        else:
            end += 1

    return -1

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.

Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”

想法

  • 把 list 裡的第一個 item 當成前綴(prefix)，檢查其他的 item
  • 檢查第二個 item 從 “ 0 到 prefix 的長度 “ 的字串是否相等
  • 如果相等就回傳 prefix ，不相等就把 prefix 減少一個字母
  • 反復循環最後 prefix 會減到剩下共有的字母

程式碼

Runtime: 32 ms, faster than 80.06%
Memory Usage: 14.4 MB, less than 24.46%

1
2
3
4
5
6
7
8
9
10
11
def longestCommonPrefix(strs):
    prefix = strs[0]

    if len(strs) == 0 :
        return ""

    for i in range(1, len(strs)):
        while (strs[i][:len(prefix)] != prefix):
            prefix = prefix[:len(prefix) -1]
    
    return prefix

參考資料

Leetcode cookbook
LeetCode-Go
Algo expert
总结一下面试常考的算法题
Huahua’s Tech Road

#

Comments

Follow

Categories

Recents

Archives

Tags

JavaScript3
Nuxt1
React13
Vannila JS1
Vue1
Vuex1
學習筆記24
×