---
title: Leetcode Top In 150 1/2
autoHeadingNumber: true
---
[TOC]
<!-- 按 Ctrl+Shift+P → Markdown: Create Table of Contents-->
# Leetcode Top Interview 150 1/2
## Array / String
### 88. Merge Sorted Array
- Given two sorted integer arrays `nums1` of length `m`and `nums2` of length `n`.
- merge `nums2` into `nums1` so that `nums1` becomes a single sorted array.
- Solution：將兩個list除了0之外的地方合併，題目給的list剛好0都會在最後，利用提供的整數數量m、n寫迴圈將整數都加入到list b，最後再全部複製到nums1
```python
class Solution(object):
def merge(self, nums1, m, nums2, n):
b = []
for i in range(m):
b.append(nums1[i])
for j in range(n):
b.append(nums2[j])
b.sort()
nums1[:] = b
return nums1
'''
# 快速解法
nums1[:] = nums1[:m] + nums2[:n]
nums1.sort() # 排序
'''
```
### 27. Remove Element
- 回傳`nums`裡面不是`val`的數量`k`
- `nums`不用回傳，但會檢查`nums`裡面的前`k`項不能有`val`
- 強調使用`in-place`的技巧
```python
class Solution(object):
def removeElement(self, nums, val):
k = 0
for i in range(len(nums)):
if nums[i] != val:
nums[k] = nums[i] # 將「不等於 val」的值移動到 nums[k]
k += 1
return k
```
### 26. Remove Duplicates from Sorted Array
- 給一個遞增排序的`nums`
- 把一樣`value`的項目刪掉
- 輸出不重複的數字數量`k`，且`nums`的前`k`項不能重複
- Solution：不能連續兩個一樣 = 跟前面第一個(k-1)不一樣即可
```python
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
k = 1 # 下一個不重複數字要放的位置
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]:
nums[k] = nums[i] # in-place 覆寫
k += 1
return k
```
```cpp
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.empty()) return 0;
int k = 1; // 下個不重複數字要放的位置
for (int i = 1; i < nums.size(); i++) {
if (nums[i] != nums[i - 1]) {
nums[k] = nums[i]; // in-place 覆寫
k++;
}
}
return k;
}
};
```
### 80. Remove Duplicates from Sorted Array II
- 給一個遞增排序的`nums`
- 把連續三個以上一樣`value`的項目刪掉
- 輸出不超過連續三個以上一樣的數字數量`k`，且`nums`的前`k`項不能重複三個以上
- Solution：不能連續三個一樣 = 跟前面第二個(k-2)不一樣即可
```python
class Solution(object):
def removeDuplicates(self, nums):
if len(nums) < 2: return len(nums)
k = 2 # 下一個能放的位置
for i in range(2, len(nums)):
if nums[i] != nums[k - 2]:
nums[k] = nums[i]
k += 1
return k
```
### 169. Majority Element
- 給一個長度為`n`的`nums`
- 輸出超過`n/2`數量的元素element
```python
class Solution(object):
def majorityElement(self, nums):
nums.sort()
count = 0
max_count = 0
max_number = nums[0]
for i in range(len(nums)-1):
if nums[i]==nums[i+1]:
count += 1
if count > max_count:
max_number = nums[i]
max_count = max(max_count,count)
else:
count = 0
return max_number
```
### 189. Rotate Array
- Input: nums = [1,2,3,4,5,6,7], k = 3
- Output: [5,6,7,1,2,3,4]
- Explanation:
- rotate 1 steps to the right: [7,1,2,3,4,5,6]
- rotate 2 steps to the right: [6,7,1,2,3,4,5]
- rotate 3 steps to the right: [5,6,7,1,2,3,4]
```python
class Solution(object):
def rotate(self, nums, k):
n = len(nums)
k %= n # 處理 k > n 的情況
nums.reverse()
nums[:k] = reversed(nums[:k]) # 0~k
nums[k:] = reversed(nums[k:]) # k~最後
```
```c
void reverse(int* nums, int left, int right) {
while (left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k) {
if (numsSize <= 1 || k == numsSize) return;
k = k % numsSize; // 處理 k > n 的情況
reverse(nums, 0, numsSize - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, numsSize - 1);
}
```
### 121. Best Time to Buy and Sell Stock
- You are given an array `prices` where `prices[i]` is the price of a given stock on the ith day.
- 哪天買哪天賣可以賺最多錢，return 可以賺的最高金額
```python
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
'''
# 這個方法會超時
max_profit = 0
for i in range(len(prices) - 1, 0, -1):
for j in range(i - 1, -1, -1):
now_profit = prices[i] - prices[j]
max_profit = max(max_profit, now_profit)
'''
# O(n)，邏輯是有更低的價格再更新就好，否則一路往下更新max_profit
min_price = prices[0]
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
else:
max_profit = max(max_profit, price - min_price)
return max_profit
```
### 122. Best Time to Buy and Sell Stock II
- You are given an array `prices` where `prices[i]` is the price of a given stock on the ith day.
- 買賣不限一次，return 可以賺的最高金額
- Solution：只要明天比今天高，那就今天買明天賣
- 我原本想從右邊到左邊，有更大值才更新基準值，但這樣測資`[1,81,1,101]`只有賺100元，其實可以賺180元
```python
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
# 只要明天的價格比今天高，就今天買明天賣
# GPT說這是Greedy
max_profit = 0
for i in range(0, len(prices) - 1):
if prices[i]<prices[i+1]:
max_profit = max_profit+(prices[i+1]-prices[i])
return max_profit
print(Solution.maxProfit(Solution,[7,1,5,3,6,4]))
```
```cpp
class Solution {
public:
int maxProfit(vector<int>& prices) {
int max_profit = 0;
for (int i=0; i < prices.size()-1;i++){
if (prices[i]<prices[i+1]){
max_profit = max_profit+(prices[i+1]-prices[i]);
}
}
return max_profit;
}
};
```
### 55. Jump Game
- You are given an integer array `nums`. You are initially positioned at the array's first index,
- and each element in the array represents your maximum jump length at that position.
- Return `true` if you can reach the last index, or `false` otherwise.
```python
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
# 假如第一個數字是0就不用跳了
# 同理nums[n]如果n-1項是0且n-1前面其他項都跳不過來，那n就是死路
# GPT說這是Greedy
max_range = nums[0]
for i in range(len(nums)):
if i<=max_range:
max_range = max(max_range, i+nums[i])
else:
return False
return True
```
```cpp
class Solution {
public:
bool canJump(vector<int>& nums) {
int max_range = nums[0];
for (int i = 0; i <nums.size(); i++){
if (i<=max_range){
max_range = max(max_range, i+nums[i]);
}
else{
return false;
}
}
return true;
}
};
```
### 45. Jump Game II
- Input: nums = [2,3,1,1,4]
- Output: 2
- Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
- Solution：
- for-if-if結構，我覺得超難
- 不能無腦擴張領土就+1，因為array的值都至少有1
- 要有一個邊界max_line，那個邊界內的都是step多少以內能到的
- nums[0]是step0
- 其中step0最遠能到的區域都是step1
- 假如step0最遠能到nums[3]，那nums[1:3] = step1
- 再看step1最遠能到多少
- 假如step1最遠到nums[10]，那nums[4:10] = step2
```python
class Solution(object):
def jump(self, nums):
max_range = 0
step = 0
last_step_line = 0
max_line = len(nums) - 1
for i in range(len(nums)):
if last_step_line >= max_line:
return step
max_range = max(max_range, i + nums[i])
if i == last_step_line: # 當i = last_step_line = 0時，進入step1
step += 1
last_step_line = max_range # step1的範圍是1~0+nums[0]
```
```cpp
class Solution {
public:
int jump(vector<int>& nums) {
int max_range = 0;
int step = 0;
int last_step_line = 0;
int max_line = nums.size()-1;
for (int i = 0; i < nums.size();i++){
if (last_step_line >= max_line){
return step; // return沒有寫在函式最後，隨便return一個0就好
}
max_range = max(max_range, i + nums[i]);
if (i==last_step_line){
step++;
last_step_line = max_range;
}
}
return 0;
}
};
```
### 274. H-Index
- `citations[i]` is the number of citations a researcher received for their ith paper, return h-index.
- h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
- 最多有H篇論文至少被引用H次
- Input：citations = [3, 0, 6, 1, 5], n = 5
- Output：h = 3
- Solution：
- (最多有H篇論文)>=(至少)被引用H次
- 論文被引用的次數統整在`count[]`裡面，這是一種bucket(分類)
- index: 0 1 2 3 4 5
- count: [1, 1, 0, 1, 0, 2]
- 最多n篇論文往下找，當n-k>=被引用的次數總和時，輸出那次的次數
```python
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
# 最多有H篇論文至少被引用H次
h_score = 0
for i in range(1, len(citations) + 1): # 窮舉法，從h=1~n逐步檢查
count = 0
for j in citations:
if j >= i:
count += 1
if count >= i:
h_score = max(h_score, i)
return h_score
# print(Solution.hIndex(Solution,[1]))
def hIndex2(self, citations): # 建立count[]後從高往下推，直到>=為止
n = len(citations)
count = [0] * (n + 1)
for c in citations:
if c >= n:
count[n] += 1
else:
count[c] += 1
total = 0
for h in range(n, -1, -1):
total += count[h]
if total >= h:
return h
```
```c
int hIndex(int* citations, int citationsSize) {
int n = citationsSize;
int count[n + 1];
for (int i = 0; i <= n; i++) {
count[i] = 0;
}
for (int i = 0; i < n; i++) { // bucket分類
int c = citations[i];
if (c >= n) {
count[n]++;
} else {
count[c]++;
}
}
int total = 0;
for (int h = n; h >= 0; h--) {
total += count[h]; // 被引用 >= h 的論文數
if (total >= h) {
return h;
}
}
return 0;
}
```
### 380. Insert Delete GetRandom O(1)
- 要求三個操作都要平均 O(1)： insert(val) → 插入 O(1)， remove(val) → 刪除 O(1)， getRandom() → 隨機取值 O(1)
- 如果只有 list： 插入 O(1)， 刪除 O(n)（因為要找元素在哪個 index）， getRandom O(1)
- 如果只有 dict： 插入 O(1)， 刪除 O(1)， getRandom 沒辦法做到，因為 dict 沒有隨機取「第幾個」的功能
- 所以才要 list + dict 搭配： list 用來隨機抽取， dict 用來快速找到元素的位置
- Solutionn：
- insert / remove → 主要靠 dict，加上 list 做同步更新
- getRandom → 只用 list
- list 與 dict 雙結構同時維護，各自負責不同需求
```python
import random
class RandomizedSet(object):
def __init__(self):
self.nums = []
self.nums_dict = {}
def insert(self, val):
"""
:type val: int
:rtype: bool
"""
if val in self.nums_dict:
return False
else:
self.nums.append(val) # list
self.nums_dict[val] = len(self.nums) - 1 # dict
return True
def remove(self, val):
"""
:type val: int
:rtype: bool
"""
if val not in self.nums_dict:
return False
else:
exchange_place = self.nums_dict[val] # dict
self.nums_dict[self.nums[-1]] = exchange_place # dict
self.nums[exchange_place], self.nums[exchange_place] = self.nums[len(self.nums) - 1], self.nums[
len(self.nums) - 1] # list
self.nums.pop() # list
del self.nums_dict[val] # dict
return True
def getRandom(self):
"""
:rtype: int
"""
if len(self.nums) == 0:
return False
else:
return random.choice(self.nums)
# ===================== 測資 =====================
inputs = ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
params = [[], [1], [2], [2], [], [1], [2], []]
obj = None
output = []
for cmd, param in zip(inputs, params):
if cmd == "RandomizedSet":
obj = RandomizedSet()
output.append(None) # 對應 LeetCode 的 null
elif cmd == "insert":
output.append(obj.insert(param[0]))
elif cmd == "remove":
output.append(obj.remove(param[0]))
elif cmd == "getRandom":
output.append(obj.getRandom())
print("Input:")
print(inputs)
print(params)
print("Output:")
print(output)
# Output = [null, true, false, true, 2, true, false, 2]
'''
# dict{x, y}：x對y可以一對一、多對一，不能一對多
# 舉例刪除掉3
# list = [1, 2, 3, 4, 5]
# dict = {1:0, 2:1, 3:2, 4:3, 5:4}
# step1:
exchange_place = self.nums_dict[val]
self.nums_dict[self.nums[-1]] = exchange_place # -> dict = {1:0, 2:1, 3:2, 4:3, 5:2}
# step2:
self.nums[exchange_place], self.nums[exchange_place] = self.nums[len(self.nums) - 1], self.nums[len(self.nums) - 1]
# -> list = [1, 2, 5, 4, 3]
# step3:
self.nums.pop() # -> list = [1, 2, 5, 4]
del self.nums_dict[val] # -> dict = {1:0, 2:1, 4:3, 5:2}
所以刪除後會引響list的順序，dict的value也會同步更新位子
# 比對時間複雜度
leetcode_380_dict的學號對應list的位子
if val in dict: O(1)
if val in list: O(n)
'''
```
### 238. Product of Array Except Self
- 給一個`nums`，全部相乘是某個整數，輸出`answer`，`answer[i]`是該整數中，因數不包含`nums[i]`的積
- Input: nums = [1,2,3,4]
- Output: [24,12,8,6]
- Solution：`answer[i]`其實就是左邊跟右邊所有元素相乘
- prefix
- suffix
```python
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
n = len(nums)
answer = [1] * n
left = 1
for i in range(0, n - 1, 1):
left *= nums[i] # 因為你要累乘
answer[i + 1] *= left
right = 1
for i in range(n - 1, 0, -1):
right *= nums[i]
answer[i - 1] *= right
return answer
```
```c
int* productExceptSelf(int* nums, int n, int* returnSize){
*returnSize = n;
int* answer = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
answer[i] = 1;
}
int left = 1;
for (int i = 0; i < n - 1; i++) {
left *= nums[i];
answer[i + 1] *= left;
}
int right = 1;
for (int i = n - 1; i > 0; i--) {
right *= nums[i];
answer[i - 1] *= right;
}
return answer;
}
```
```cpp
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) { // vector不用指標
int n = nums.size();
vector<int> answer(n, 1);
int left = 1;
for (int i = 0; i < n - 1; ++i) {
left *= nums[i];
answer[i + 1] *= left;
}
int right = 1;
for (int i = n - 1; i > 0; --i) {
right *= nums[i];
answer[i - 1] *= right;
}
return answer;
}
};
```
### 134. Gas Station
- gas[i]是抵達該加油站後可以加的油
- cost[i]是從這邊離開時要扣掉的油
- return從gas多少開始可以走完整一圈
- Solution：
- 只要total_gas >= total_cost 就一定有解
- +gas-cost可以想成新的diff
- 正+負定理：
- 能走到3，那1一定是正的，同理1+2也必定正，卡在3表示3是一個超大負
- 如果1 ->2 ->3不行，那從2、3當起點也一定不行
- 直接測試從4當起點的情況
```python
class Solution(object):
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
# gas是你抵達時得到的gas
# cost是你離開時消耗的gas
# 只要total_gas >= total_cost 就一定有解
total_tank = 0
current_tank = 0
start_index = 0
for i in range(len(gas)):
total_tank += gas[i] - cost[i]
current_tank += gas[i] - cost[i]
# 若目前的油量不足，重新選擇起點
if current_tank < 0:
start_index = i + 1
current_tank = 0 # 重置當前油量 # 不用重置total
if total_tank >= 0:
return start_index
else:
return -1
```
### 135. Candy
- arrays `ratings` of length `n`, rating[i]是小孩的價值
- 每個小孩至少一個糖果
- 小孩一定要比自己鄰居ratings更低的小孩拿更多糖
- 輸出至少需要多少糖果
- Solution：
```python
class Solution(object):
def candy(self, ratings):
"""
:type ratings: List[int]
:rtype: int
"""
n = len(ratings)
candy_L2R = [1]*n
candy_R2L = [1]*n
candy_result = [1]*n
sum = 0
for i in range(1, n):
if ratings[i]>ratings[i-1]: candy_L2R[i] = candy_L2R[i-1]+1
for j in range(n-2, -1, -1):
if ratings[j]>ratings[j+1]: candy_R2L[j] = candy_R2L[j+1]+1
for k in range(n):
candy_result[k] = max(candy_L2R[k], candy_R2L[k])
sum += candy_result[k]
return sum
```
### 42. Trapping Rain Water
- arrays `height` of length `n`, `height[i]`是牆壁的高度，輸出最多可以搜集多少雨水
- Solution：
```python
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
L2R_up = 0
R2L_up = 0
L2R_line = [0]*n
R2L_line = [0]*n
result = 0
result2 = 0
for i in range(n):
L2R_up = max(L2R_up, height[i])
L2R_line[i] = L2R_up
for i in range(n-1,-1,-1):
R2L_up = max(R2L_up, height[i])
R2L_line[i] = R2L_up
result = min(R2L_line[i], L2R_line[i])
result = result - height[i]
if result > 0:
result2 += result
return result2
```
```c
int trap(int* height, int heightSize) {
int n = heightSize;
int L2R_up = 0;
int R2L_up = 0;
int L2R_line[n]; // C創建list比C++簡單
int R2L_line[n];
int result = 0;
int result2 = 0;
for (int i = 0; i < n; i++) {
L2R_up = (L2R_up > height[i]) ? L2R_up : height[i];
L2R_line[i] = L2R_up;
}
for (int i = n - 1; i >= 0; i--) {
R2L_up = (R2L_up > height[i]) ? R2L_up : height[i];
R2L_line[i] = R2L_up;
result = (R2L_line[i] < L2R_line[i]) ? R2L_line[i] : L2R_line[i];
result = result - height[i];
if (result > 0) result2 += result;
}
return result2;
}
```
### 13. Roman to Integer
|Symbol|Value|
|-|-|
|I|1|
|IV|4|
|V|5|
|VI|6|
|X|10|
|L|50|
|C|100|
|D|500|
|M|1000|
- input是string的羅馬數字，output數字
```python
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
s_dict = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
sum = s_dict[s[len(s)-1]]
for i in range(len(s)-1):
if s_dict[s[i]]< s_dict[s[i+1]]:
sum -= s_dict[s[i]]
else:
sum += s_dict[s[i]]
return sum
```
### 12. Integer to Roman
- input數字，output是string的羅馬數字
```python
class Solution(object):
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
roman_dict = {
1: 'I',
4: 'IV',
5: 'V',
9: 'IX',
10: 'X',
40: 'XL',
50: 'L',
90: 'XC',
100: 'C',
400: 'CD',
500: 'D',
900: 'CM',
1000: 'M',
}
roman_list = sorted(roman_dict.keys()) # leetcode的dict沒有照上面的順序排
roman_number = ''
for i in list(roman_list)[::-1]: # 從大到小 # 讓迴圈發生在roman_list
roman_number += roman_dict[i] * (num // i)
num -= (num // i) * i
return roman_number
```
### 58. Length of Last Word
- input一個string，每個單字會用空格隔開，輸出最後一個單字的長度
- Python Solution：
- 有可能最後一個元素是空格，所以設定一個spare，遇到空格就把result複製到spare
- 最後如果是空格，result就會是0，輸出spare
- 最後如果不是空格，就輸出result
- C++ Solution：
- 從後面往前，如果不是空格就+1
- 如果是空格且count不是0就直接輸出count
```python
class Solution(object):
def lengthOfLastWord(self, s):
"""
:type s: str
:rtype: int
"""
result = 0
spare = 0
for i in range(len(s)):
if s[i] == ' ':
if result != 0:
spare = result
result = 0
else:
result += 1
if result == 0:
return spare
else:
return result
```
### 14. Longest Common Prefix
- 找共同的前綴詞
- Input: strs = `["flower","flow","flight"]`
- Output: "fl"
- Solution：
- 每個詞的第一個單字開始比，如果不一樣就輸出答案
```python
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
ans = ""
for i, char in enumerate(strs[0]): # 以第一個flower為基準
for word in strs: # 依序比對所有字元的i=1、i=2、i=3等
# 超出字串範圍，或字串不同，直接結束返回結果
if i >= len(word) or word[i] != char:
return ans
ans += char # 整個for word迴圈都沒return就把該char加入ans
return ans # 所有字串都遍歷完後，返回完整的共同前綴
```
### 151. Reverse Words in a String
- Input: s = "a good example"
- Output: "example good a"
- Python Solution：
- 從前面開始遇到空格的話再把前面的詞放到後面
- `result[position-length+j] = s[i-length+j]`
- C Solution：
- 從後面開始統計不是空格的數量放到result
```python
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
result = [""] * (n+1) # list of string # n+1因為可能多一個空格
count = 0
position = n
for i in range(n+1):
if i == n or s[i] == " ":
length = count
if length > 0:
for j in range(length):
result[position-length+j] = s[i-length+j] # 把最前面的You放到最後面
position -= length
position -= 1
if position >= 0:
result[position] = " " # 在You的前面補一個空格
count = 0
else:
count += 1 # 沒遇到空格就一直+1
return "".join(result).strip() # 把list裡面的子string都合起來 # .strip()會刪掉頭尾空格
#solution = Solution()
#print(solution.reverseWords("You are very smart"))
```
```c
char* reverseWords(char* s) {
int n = strlen(s);
char* result = (char*)malloc(n + 1);
int pos = 0;
int i = n - 1;
while (i >= 0) {
while (i >= 0 && s[i] == ' ') i--; // 跳過空格
if (i < 0) break;
int end = i;
while (i >= 0 && s[i] != ' ') i--; // 找單字結尾
int start = i + 1;
if (pos > 0) result[pos++] = ' '; // 補空格（不是第一個單字)
for (int k = start; k <= end; k++) result[pos++] = s[k]; // 複製單字
}
result[pos] = '\0';
// C 語言中的字串結尾的標記
// char s[] = {'H','i','\0'}; 等價 char s[] = "Hi";
return result;
}
```
### 6. Zigzag Conversion
- input = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
- output = [1, 5, 9, 13, 2, 4, 6, 8, 10, 12, 14, 3, 7, 11]
- Solution
- 剛好會是numRows +numRows -2的循環
- 用找餘數的方式分類，餘數是1的是第一row，餘數是2的是第二row
- 其中5跟3同一組、6跟2同組，所以`if x >= row: x = cycle - x`
- 從小到大，把元素加入到不同string的分類裡
```python
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
row = numRows
n = len(s)
ans = [""] * row # 可以把值存到ans_[0]、ans_[1] ...
cycle = row + row - 2
if cycle == 0:
return s
for i in range(n):
x = i % cycle
if x >= row:
x = cycle - x # 以N=4為例，6跟2同組，5跟3同組
ans[x] += s[i] if 0 <= x < numRows else ""
return "".join(ans)
'''
N = 3, 1個穿插：
1 5 9 13
2 4 6 8 10 12 14
3 7 11
1 1 1
2 4 2 4 2 4
3 3 3
N = 4, 2個穿插：
1 7 13
2 6 8 12 14
3 5 9 11
4 10
1 1 1 1
2 6 2 6 2 6 2
3 5 3 5 3 5
4 4 4
'''
```
### 28. Find the Index of the First Occurrence in a String
- Input: haystack = "absadbutsad", needle = "sad"
- Output: 2
- Solution：
- 寫兩個迴圈逐一深入比對，把所有答案加入到list最後輸出最小的值
- 建立LPS表看有多少前綴詞重複，就不用重頭比對
- 
```python
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
answer = []
for i in range(0, len(haystack)):
count = 0
for j in range(i, len(haystack)):
if haystack[j] == needle[count]:
count += 1
elif haystack[j] != needle[count]:
count = 0
if count == len(needle):
x = j-count+1
answer.append(x)
count = 0
if answer != []:
return min(answer)
return -1
```
```python
class Solution(object):
def strStr(self, haystack, needle):
if needle == "":
return 0
# ---------- build lps ----------
lps = [0] * len(needle)
# 控制j的list，告訴你哪些前綴一樣
# needed = [a, b, c, a, b, c, d], lps = [0, 0, 0, 1, 2, 3, 0]
j = 0
# j是你正在跟哪個index的元素比
# j-1是哪些index的元素已經一樣了
for i in range(1, len(needle)):
while j > 0 and needle[i] != needle[j]:
j = lps[j - 1]
if needle[i] == needle[j]:
j += 1
lps[i] = j
# ---------- KMP search ----------
j = 0
for i in range(len(haystack)):
while j > 0 and haystack[i] != needle[j]:
j = lps[j - 1]
if haystack[i] == needle[j]:
j += 1
if j == len(needle):
return i - j + 1
return -1
'''
haystack = "mississippi"
needle = "issip"
lps = [0, 0, 0, 1, 0]
當比到hystack[5]、j=3不一樣時，j不會直接歸0，根據lps j會變成1，直接跟needle[1]繼續比
'''
```
### 68. Text Justification
-
- Solution：
-
```python
```
```c
```
## Two Pointers
### 125. Valid Palindrome
- 給一個字串`s`，忽略標點符號英文大小寫，看是不是回文(正讀反讀都一樣)
```python
class Solution:
def isPalindrome(self, s):
left, right = 0, len(s) - 1
while left < right:
# 如果是非英數就額外+1 # not .sialnum 是 not False = True 就會跳過(+1)
while left < right and not s[left].isalnum(): left += 1
while left < right and not s[right].isalnum(): right -= 1
if s[left].lower() != s[right].lower(): return False
left += 1
right -= 1
return True
'''
'a'.isalnum() # True
'7'.isalnum() # True
' '.isalnum() # False
','.isalnum() # False
'''
```
### 392. Is Subsequence
- 給兩個字串`s` `t`，如果s是t的 subsequence (子序列)就return True
- 子序列可以不用相連但順序要對，如s = abc，t = ....a....b....c...
```python
class Solution(object):
def isSubsequence(self, s, t):
n = len(s)
m = len(t)
if n == 0: return True
t_l = 0
s_l = 0
while t_l < m:
if s[s_l] == t[t_l]:
s_l += 1
if s_l == n: return True
t_l += 1
return False
```
### 167. Two Sum II - Input Array Is Sorted
- 給排序的數列，找兩數相加等於target
- Solution：
- 用`while`縮小範圍，我原本以為`leetcode1`就是有排序的
```python
class Solution(object):
def twoSum(self, numbers, target):
left = 0
right = len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
# LeetCode 167 題目規定：回傳的是「1-based index」
if s == target: return [left + 1, right + 1]
elif s < target: left += 1
else: right -= 1
```
### 11. Container With Most Water
- 給你一個陣列 `height`，`height[i]` = 第 i 條直線的高度
- 每兩條線可以和 x 軸圍成一個容器
- 容器能裝的水量是：寬度 × 高度 = (右 index - 左 index) × min(左高, 右高)
- 回傳最大能裝多少水？
- Solution：
- 區域：`area = width × min(height[left], height[right])`
- 雙指標：只移比較矮的那邊，如果移動高的，容量只會被矮的那端限制住
- `if height[left] < height[right]: left += 1`
- `else: right -= 1`
```python
class Solution(object):
def maxArea(self, height):
left = 0
right = len(height) - 1
ans = 0
while left < right:
area = (right - left) * min(height[left], height[right])
ans = max(ans, area)
# 只移比較矮的那邊一定是對的
# 如果移動高的，容量只會被矮的那端限制住
if height[left] < height[right]: left += 1
else: right -= 1
return ans
```
### 15. 3Sum
- 給一個list，輸出list of list，哪三個數字加起來等於0，不能重複
- Solution：
- 先排序，再用雙指標右邊的最右邊跟最左邊依序縮短距離
- 過程中只要跟下一個狀態重複就要跳過
- C的`malloc`語法補充在`python c c++.md`的`malloc`篇中
- C的`result`是2D array，`returnColumnSizes`是1D array
```python
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
n = len(nums)
ans = []
Target = 0
for i in range(n): # 以第i個數字為主角，再去看右邊的範圍有沒有可以配合的兩個數字
if i > 0 and nums[i] == nums[i-1]: # 如果跟上一個數字一樣，就跳過不重複做
continue
left = i + 1
right = n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == Target:
ans.append([nums[i], nums[left], nums[right]]) # List[List[int]]的方法
while left < right and nums[left] == nums[left+1]:
left += 1 # 避免重複算
while left < right and nums[right] == nums[right-1]:
right -= 1 # 避免重複算
left += 1
right -= 1
elif total < Target:
left += 1 # 如果太小就左邊+1，因為有sort過左邊是小的
else:
right -= 1 # 如果太大就右邊-1，因為sort過右邊是大的
return ans
solution = Solution()
print(solution.threeSum([-1,0,1,2,-1,-4]))
```
```c
// qsort 用的
int cmp(const void* a, const void* b) { // void表示不知道什麼類別
return (*(int*)a - *(int*)b);
// 一開始宣告void，類別轉型(int*)a, 假設a是int整數
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
// 指標符號 * 有兩種用途 1.解參考 2.宣告指標回傳值
// int* returnSize是指向int的指標
// Q: 為什麼這邊要int **returnColumnSizes才代表array，但void sort(int*arr)就代表array？
// 怎麼知道int*arr是指向int的指標還是array退化成指標？
// A: 一開始有宣告過arr是array就是後者，沒有宣告過的話就要用int**
*returnSize = 0;
if (numsSize < 3) return NULL;
qsort(nums, numsSize, sizeof(int), cmp);
// 最多不會超過 n^2 組
int capacity = numsSize * numsSize;
int** result = (int**)malloc(sizeof(int*) * capacity);
// int**是double pointer，宣告array of array
// int**是指向int*的指標
// sizeof(int*)是指標的長度
*returnColumnSizes = (int*)malloc(sizeof(int) * capacity);
// 因為returnColumnSizes不會被return，所以要用*A = size(int)的方式malloc
for (int i = 0; i < numsSize - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // 重複不用算
int left = i + 1;
int right = numsSize - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result[*returnSize] = (int*)malloc(sizeof(int) * 3);
result[*returnSize][0] = nums[i];
result[*returnSize][1] = nums[left];
result[*returnSize][2] = nums[right];
(*returnColumnSizes)[*returnSize] = 3;
// (*returnColumnSizes)[i] == *(*returnColumnSizes + i)
(*returnSize)++;
// 重複不用算
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
else if (sum < 0) left++;
else right--;
}
}
return result;
}
```
## Sliding Window 兩個指標維持一個連續區間，邊移動邊更新答案
### 209. Minimum Size Subarray Sum
- 給一個array跟target，找連續的子陣列（subarray），子陣列的總和 ≥ target，return子陣列最短長度
```python
class Solution(object):
def minSubArrayLen(self, target, nums):
left = 0
curr_sum = 0
res = float('inf') # 無限大
for right in range(len(nums)):
curr_sum += nums[right]
while curr_sum >= target:
res = min(res, right - left + 1)
curr_sum -= nums[left]
left += 1
return 0 if res == float('inf') else res
```
```c
int minSubArrayLen(int target, int* nums, int numsSize) {
int left = 0;
int sum = 0;
int minLen = numsSize + 1;
for (int right = 0; right < numsSize; right++) {
sum += nums[right];
while (sum >= target) {
int len = right - left + 1;
if (len < minLen) minLen = len;
sum -= nums[left];
left++;
}
}
return minLen == numsSize + 1 ? 0 : minLen;
}
```
### 3. Longest Substring Without Repeating Characters
- input一個string，output最長不重複的字母數量
- Python Solution：
- 把string的字母加到key、第i個加到value
- for迴圈一開始更新left邊界
- C Solution1：
- 類似python，建立char_last_position的list當dict用
- `list['a']++` 等價 `freq[97]++`，freq的第97個位子會++
- list每個值預設是-1，因為python一開始就沒有值，C的list的128個位子一開始都要設定值
- for迴圈一開始更新left邊界
- 如果前面有出現過這個字母，left = 第一次出現該字母+1
- 補充 `list[s[right]] >= left` 的意思是：
- list[s[right]]本來應該要沒有值或-1
- 如果有值且>=left，表示在原本left~right之間有重複的s[right]
- left = 第一次出現該字母的位子+1
- 如abcdeabc，`s[5]`出現第二次b，則left邊界從`s[2]`開始
- 
- C Solution2：
- 建立list，如果有重複的如`freq['a']=2`，就照string的順序把前面都--，直到`freq['a']=1`為止就是left的邊界
- 跟查字典char_last_postion的位子+1更新left不同
```python
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
seen = {}
start = 0
count = 0
max_len = 0
for i in range(n):
# 更新left邊界
if s[i] in seen and seen[s[i]] >= start:
start = seen[s[i]] + 1 # 如dvdf，遇到第二個d起點從v開始
count = i - start # count不見得會直接歸0，
# 例如dvdf，遇到第二個d時，count = 2-1 = 1，
# 後面馬上count += 1，count = 2，count會從v開始算
seen[s[i]] = i
# 字串的字母加到key
# 第i個加到value
# seen[s[0]] = 0 →seen = {'a': 0}
count += 1
if count > max_len:
max_len = count
results = s[start:i+1] # 字串切割範圍從start到i+1-1
return results
solution = Solution()
print(solution.lengthOfLongestSubstring("abbcdef"))
```
```c
int lengthOfLongestSubstring(char* s) {
int char_last_position[128];
for (int i = 0; i < 128; i++) char_last_position[i] = -1;
int left = 0;
int maxLen = 0;
for (int right = 0; s[right]; right++) { // 同for ( ; s[right] != '\0'; )
// 更新left邊界
if (char_last_position[s[right]] >= left) left = char_last_position[s[right]] + 1;
char_last_position[s[right]] = right;
int len = right - left + 1;
if (len > maxLen) maxLen = len;
}
return maxLen;
}
```
```c
int lengthOfLongestSubstring(char* s) {
int freq[128] = {0}; // 128是所有字元
int left = 0;
int maxLen = 0;
for (int right = 0; s[right] != '\0'; right++) {
freq[s[right]]++; // freq['a']++ 等價 freq[97]++ // freq的第97個位子會++
// 如果有重複，就縮小左邊邊界
while (freq[s[right]] > 1) {
freq[s[left]]--;
left++;
// left會一直+到當left == right為止
// 此時再freq[s[left]]-- 才會停止迴圈
// 這段同python, start = seen[s[i]] + 1
}
int currLen = right - left + 1;
if (currLen > maxLen)
maxLen = currLen;
}
return maxLen;
}
```
### 30. Substring with Concatenation of All Words
### 76. Minimum Window Substring
## Matrix
### 36. Valid Sudoku
- 看數獨是否符合邏輯，row, column, 3x3區域內不能有重複的值
- Solution：
- python建立2D array
- C 的2D array column是實際value值-1
```python
class Solution(object):
def isValidSudoku(self, board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
val = board[r][c]
if val == '.': continue # leetcode題目規定的無值
box_id = (r // 3) * 3 + (c // 3) # 把box變成9個區間：(0,3,6)+(0,1,2)
if val in rows[r] or val in cols[c] or val in boxes[box_id]: return False
rows[r].add(val)
cols[c].add(val)
boxes[box_id].add(val)
return True
```
```c
bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
bool row[9][10] = {false};
bool col[9][10] = {false};
bool box[9][10] = {false};
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
char num = board[r][c];
if (num == '.') continue;
int num2 = num - '0'; // 因為char的1是int的49，1-'0'同49-48
int box_id = (r / 3) * 3 + (c / 3);
if (row[r][num2] || col[c][num2] || box[box_id][num2]) return false;
row[r][num2] = true;
col[c][num2] = true;
box[box_id][num2] = true;
}
}
return true;
}
```
### 54. Spiral Matrix
- 給一個mn矩陣，回傳沿著邊邊往內走順序(spiral order)的list
- Solution：
- 右往左跟下往上要多寫一個if，不然走到終點後還會繼續計算重複的點
```python
class Solution(object):
def spiralOrder(self, matrix): # mn matrix
if not matrix: return []
res = []
top, bottom = 0, len(matrix) - 1 # m, row, y-axis
left, right = 0, len(matrix[0]) - 1 # n, column, x-axis
while top <= bottom and left <= right:
for c in range(left, right + 1): res.append(matrix[top][c]) # left → right
top += 1 # 縮小範圍，top起點是0、bottom起點是m-1
for r in range(top, bottom + 1): res.append(matrix[r][right]) # top → bottom
right -= 1
if top <= bottom: # right → left
for c in range(right, left - 1, -1): res.append(matrix[bottom][c])
bottom -= 1
if left <= right: # bottom → top
for r in range(bottom, top - 1, -1): res.append(matrix[r][left])
left += 1
return res
```
```c
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
if (matrixSize == 0) {
*returnSize = 0;
return NULL;
}
int m = matrixSize;
int n = matrixColSize[0];
int total = m * n;
int* res = (int*)malloc(sizeof(int) * total);
int idx = 0;
int top = 0, bottom = m - 1;
int left = 0, right = n - 1;
while (top <= bottom && left <= right) {
for (int c = left; c <= right; c++) res[idx++] = matrix[top][c];
top++;
for (int r = top; r <= bottom; r++) res[idx++] = matrix[r][right];
right--;
if (top <= bottom) {
for (int c = right; c >= left; c--) res[idx++] = matrix[bottom][c];
bottom--;
}
if (left <= right) {
for (int r = bottom; r >= top; r--) res[idx++] = matrix[r][left];
left++;
}
}
*returnSize = idx;
return res;
}
```
### 48. Rotate Image
- 給nn矩陣，順時針轉90度
- Solution：
- 順時針轉90度：ij交換+反轉row
- 逆時針轉90度：ij交換+反轉column
- 轉180度：上下反轉+左右反轉
```python
class Solution:
def rotate(self, matrix):
n = len(matrix)
for i in range(n):
for j in range(i+1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # 轉置
for i in range(n): matrix[i].reverse() # 反轉每一row
```
```c
void rotate(int** matrix, int matrixSize, int* matrixColSize){
int n = matrixSize;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n/2; j++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n-1-j];
matrix[i][n-1-j] = tmp;
}
}
}
```
### 73. Set Matrix Zeroes
- 給mn矩陣，0的同一row跟同一column都變成0
- Solution：
- 把0所在的row, column紀錄起來，再一次把所有row, column變成0，O(2mn)
- 有更快的方法，但我覺得面試不會考這題，就不研究了
```python
class Solution(object):
def setZeroes(self, matrix):
m, n = len(matrix), len(matrix[0])
row = [False] * m
col = [False] * n
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row[i] = True
col[j] = True
for i in range(m):
for j in range(n):
if row[i] or col[j]:
matrix[i][j] = 0
```
```c
void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
int m = matrixSize;
int n = matrixColSize[0];
int row[m], col[n];
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(matrix[i][j] == 0){
row[i] = 1;
col[j] = 1;
}
}
}
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(row[i] || col[j]){
matrix[i][j] = 0;
}
}
}
}
```
### 289. Game of Life
- 給一個 0/1 矩陣（死/活），同時依照規則更新成下一代
- 4條規則，對每一格，看 8 個鄰居：
- 活細胞，活鄰居 < 2 → 死
- 活細胞，活鄰居 2 或 3 → 活
- 活細胞，活鄰居 > 3 → 死
- 死細胞，活鄰居 = 3 → 活
- 全部是同時發生，不能邊更新邊看下一個，類似non-blocking的效果，但不是non-blocking的機制
- Solution：
- 讓存的值有四種狀態
- cell > 0 → 1
- cell <= 0 → 0
- 這題沒認真刻，很類似電腦視覺的作業
|原本|後來|value|
|-|-|-|
|0|0|0|
|1|1|1|
|1|0|-1|
|0|1|2|
```python
class Solution:
def gameOfLife(self, board):
m, n = len(board), len(board[0])
dirs = [(-1,-1), (-1,0), (-1,1),
(0,-1), (0,1),
(1,-1), (1,0), (1,1)]
# 第一次遍歷：標記狀態
for i in range(m):
for j in range(n):
live = 0
for dx, dy in dirs:
x, y = i + dx, j + dy
if 0 <= x < m and 0 <= y < n and abs(board[x][y]) == 1:
live += 1
if board[i][j] == 1 and (live < 2 or live > 3):
board[i][j] = -1 # 活 → 死
elif board[i][j] == 0 and live == 3:
board[i][j] = 2 # 死 → 活
# 第二次遍歷：還原成 0 / 1
for i in range(m):
for j in range(n):
if board[i][j] > 0:
board[i][j] = 1
else:
board[i][j] = 0
```
```c
void gameOfLife(int** board, int boardSize, int* boardColSize) {
int m = boardSize;
int n = boardColSize[0];
int dirs[8][2] = {
{-1,-1}, {-1,0}, {-1,1},
{0,-1}, {0,1},
{1,-1}, {1,0}, {1,1}
};
// 第一輪：標記暫態
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int live = 0;
for (int d = 0; d < 8; d++) {
int x = i + dirs[d][0];
int y = j + dirs[d][1];
if (x >= 0 && x < m && y >= 0 && y < n &&
abs(board[x][y]) == 1) {
live++;
}
}
if (board[i][j] == 1 && (live < 2 || live > 3)) {
board[i][j] = -1; // 活 → 死
} else if (board[i][j] == 0 && live == 3) {
board[i][j] = 2; // 死 → 活
}
}
}
// 第二輪：轉回 0 / 1
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = board[i][j] > 0 ? 1 : 0;
}
}
}
```
## Hashmap
### 383. Ransom Note
-
- Solution：
- 5
```python
```
```c
```
### 205. Isomorphic Strings
-
- Solution：
- 5
```python
```
```c
```
### 290. Word Pattern
-
- Solution：
- 5
```python
```
```c
```
### 242. Valid Anagram
-
- Solution：
- 5
```python
```
```c
```
### 49. Group Anagrams
- Input: strs = ["eat","tea","tan","ate","nat","bat"]
- Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
- Solution：
- 用`defaultdict` value設定list
- `sorted_str = "".join(sorted(s))` 排序詞彙
- `ans[sorted_str].append(s)` 排序一樣的詞彙放在同一個key的list裡面
```python
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
from collections import defaultdict
ans = defaultdict(list)
for s in strs:
sorted_str = "".join(sorted(s))
ans[sorted_str].append(s)
return list(ans.values())
```
### 1. Two Sum
- 給你一個整數陣列 nums 和一個目標 target
- 找出兩個不同 index，使得 nums[i] + nums[j] == target
- 回傳這兩個 index，保證一定有解，只有一組解
- Solution：
- 可以用雙迴圈O(n*2)、while雙指標縮小範圍、dict
```python
class Solution(object):
def twoSum(self, nums, target):
# dict的key放nums的value,
# key的value放nums的index
# dict[key] -> value
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen: return [seen[complement], i]
seen[num] = i
return []
```
### 202. Happy Number
-
- Solution：
- 5
```python
```
```c
```
### 219. Contains Duplicate II
-
- Solution：
- 5
```python
```
```c
```
### 128. Longest Consecutive Sequence
-
- Solution：
- 5
```python
```
```c
```
## Intervals 一堆區間 [start, end] 的演算法
### 228. Summary Ranges
- 給一個sorted num，有連續的區間用5->9表示，其他用單獨的數字表示
- Solution：
- `if i == n or nums[i] != nums[i - 1] + 1:` 到尾巴或發現不連續
- 再看是重複的還是連續的
```python
class Solution(object):
def summaryRanges(self, nums):
res = []
n = len(nums)
if n == 0: return res
start = nums[0]
for i in range(1, n + 1):
if i == n or nums[i] != nums[i - 1] + 1: # 到尾巴 或 發現不連續
if start == nums[i - 1]: res.append(str(start))
else: res.append(str(start) + "->" + str(nums[i - 1]))
if i < n: start = nums[i]
return res
```
```c
char** summaryRanges(int* nums, int numsSize, int* returnSize) {
char** res = (char**)malloc(sizeof(char*) * numsSize);
*returnSize = 0;
if (numsSize == 0) return res;
int start = nums[0];
for (int i = 1; i <= numsSize; i++) {
if (i == numsSize || nums[i] != nums[i - 1] + 1) {
char* buf = (char*)malloc(25);
if (start == nums[i - 1]) sprintf(buf, "%d", start); // 存成字串
else sprintf(buf, "%d->%d", start, nums[i - 1]);
res[(*returnSize)++] = buf;
if (i < numsSize) start = nums[i];
}
}
return res;
}
```
### 56. Merge Intervals
-
- Solution：
- 5
```python
```
```c
```
### 57. Insert Interval
-
- Solution：
- 5
```python
```
```c
```
### 452. Minimum Number of Arrows to Burst Balloons
-
- Solution：
- 5
```python
```
```c
```
## Stack
### 20. Valid Parentheses
-
- Solution：
- 5
```python
```
```c
```
### 71. Simplify Path
-
- Solution：
- 5
```python
```
```c
```
### 155. Min Stack
-
- Solution：
- 5
```python
```
```c
```
### 150. Evaluate Reverse Polish Notation
-
- Solution：
- 5
```python
```
```c
```
### 224. Basic Calculator
-
- Solution：
- 5
```python
```
```c
```
## Linked List
### 141. Linked List Cycle
- Given head, the head of a linked list, determine if the linked list has a cycle in it.
- Solution: 給一個盲Linked List判斷是否為迴圈，同時一次只走一步跟一次走兩步，如果有迴圈遲早兩個人會重疊
```python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow = head # 慢指針，每次走一步
fast = head # 快指針，每次走兩步
while fast and fast.next: # fast.next有東西的話，fast.next.next才有意義
slow = slow.next
fast = fast.next.next
if slow == fast: return True # 相遇表示有 cycle
return False
```
```c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode *slow = head; // 慢指針，一次走一步
struct ListNode *fast = head; // 快指針，一次走兩步
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true; // 相遇表示有 cycle
}
return false; // 都沒相遇
}
```
### 2. Add Two Numbers
- 給兩個linklist，return相加後的linklist，但個十百千萬都是相反的
- Input: l1 = [2,4,3], l2 = [5,6,4]
- Output: [7,0,8]
- Explanation: 342 + 465 = 807
- Solution：
- 位數相反是好事，第一個就是個位數相加，第二個是十位數相加
- carry是看有沒有進位
- `while carry` `v1 = l1.val if l1 else 0` 都是怕最後一位相加後要進位
- 每建立新的點都要在heap上配置空間
- C宣告curr的方式 `struct ListNode* curr = l3;`；對比python `curr = l3`
- C要多一個變數`node`做malloc；python會自動建立空間才不用多一個變數malloc
```python
class Solution(object):
def addTwoNumbers(self, l1, l2):
carry = 0
l3 = ListNode(0)
curr = l3 # current用來借位
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
total = v1 + v2 + carry
carry = total // 10
curr.next = ListNode(total % 10)
curr = curr.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return l3.next
```
```c
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
int carry = 0;
struct ListNode* l3 =
(struct ListNode*)malloc(sizeof(struct ListNode));
l3->val = 0;
l3->next = NULL;
struct ListNode* curr = l3; // curr借位不要影響到l3
while (l1 != NULL || l2 != NULL || carry != 0) {
int v1 = (l1 != NULL) ? l1->val : 0;
int v2 = (l2 != NULL) ? l2->val : 0;
int total = v1 + v2 + carry;
carry = total / 10;
// 每創建一個點就要多一次malloc
// C要多一個node變數做malloc
// python會自動建立空間才不用多一個變數malloc
struct ListNode* node =
(struct ListNode*)malloc(sizeof(struct ListNode));
node->val = total % 10;
node->next = NULL;
curr->next = node;
curr = curr->next;
if (l1 != NULL) l1 = l1->next;
if (l2 != NULL) l2 = l2->next;
}
return l3->next;
}
```
### 21. Merge Two Sorted Lists
- 給兩個排序的linklist，將兩個linklist合併，每個node由小到大
- Solution：
- 建立dummy當開頭，不用建立新的linklist
- C在stack建立dummy node作為開頭，後面都是更改l1, l2的排序
- python無論如何都會在heap建立空間，dummy node建立在heap
```python
class Solution(object):
def mergeTwoLists(self, l1, l2):
dummy = ListNode(0) # python不管怎樣都會在heap建立空間
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 if l1 else l2
return dummy.next
```
```c
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy; // 不用在heap配置linklist空間，所以不用malloc
struct ListNode* curr = &dummy;
dummy.next = NULL;
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
curr->next = l1;
l1 = l1->next;
}
else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
curr->next = (l1 != NULL) ? l1 : l2; // 最後會剩下l1或l2最後一個node
return dummy.next;
}
```
### 138. Copy List with Random Pointer
- 特殊的 linked list有val, next, random，random是指向其中一個點或null
- 完整複製一份新的 linked list，不能用到舊的點
- random 不是線性的，你在複製 A 時，A.random 可能指到還沒被複製的 C
- Solution：
- 在原本的linklist每個node後面都接新的node
- `new.next = cur.next `
- `cur.next = new`
- 新node的random也要接到新的node
- `cur.next.random = cur.random.next`
- 1,3,5,7是舊點；2,4,6,8是新點，最後分解成兩個linklist
- `copy_cur.next = copy`
- `cur.next = copy.next`
```python
class Solution(object):
def copyRandomList(self, head):
# 如果原本 list 為空，直接回傳 None
if not head: return None
'''
1 -> 2 -> 3 -> None
| | |
v v v
3 1 None
'''
cur = head
while cur:
new = Node(cur.val)
new.next = cur.next # 標準插入node的兩行
cur.next = new
cur = new.next
'''
1 -> 1' -> 2 -> 2' -> 3 -> 3' -> None
| | |
v v v
3 1 None
'''
cur = head
while cur:
if cur.random: cur.next.random = cur.random.next # random是舊點，再next是新點
cur = cur.next.next # 去下一個舊點
'''
1 -> 1' -> 2 -> 2' -> 3 -> 3'
| | | | |
v v v v v
3 3' 1 1' None
'''
new_head = Node(0) # 新 list 的假頭
copy_cur = new_head # 用來走訪新 list
cur = head # 重新從舊 list 的頭開始
while cur:
copy = cur.next
# cur的第一個是舊點
# cur從下一個新點開始run
copy_cur.next = copy # 接上copy的新點
copy_cur = copy # 移到剛接上的點
cur.next = copy.next # 接上copy的舊點
cur = cur.next # 移到剛接上的點
'''
1 -> 2 -> 3 -> None
| | |
v v v
3 1 None
1' -> 2' -> 3' -> None
| | |
v v v
3' 1' None
'''
return new_head.next
```
```c
struct Node* copyRandomList(struct Node* head){
if (!head) return NULL;
struct Node* cur = head;
while (cur) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->val = cur->val;
newNode->next = cur->next;
newNode->random = NULL;
cur->next = newNode;
cur = newNode->next;
}
cur = head;
while (cur) {
if (cur->random) cur->next->random = cur->random->next;
cur = cur->next->next;
}
//struct Node* dummy = (struct Node*)malloc(sizeof(struct Node));
//dummy->next = NULL;
//struct Node* copy_cur = dummy;
struct Node dummy;
dummy.next = NULL; // 只有指標的子項目用 ->
struct Node* copy_cur = &dummy;
cur = head;
while (cur) {
struct Node* copy = cur->next;
copy_cur->next = copy;
copy_cur = copy;
cur->next = copy->next;
cur = cur->next;
}
//return dummy->next;
return dummy.next;
}
```
### 92. Reverse Linked List II
- 給一個linklist，指定範圍反轉
- linklist的輸出就是一個點，每個點都有`next`所以會無限延伸
- Solution：
- 變數很多，沒有好的命名方法，設定變數就是一直在縮短範圍
- 中間反轉同單向 Linked List 反轉
```python
class Solution:
def reverseBetween(self, head, m, n):
if not head or m == n: return head
dummy = ListNode(0)
dummy.next = head
prev = dummy # 頭多一個0
for _ in range(m - 1): prev = prev.next # prev 移到 m-1
cur = prev.next
tail = cur # 第m個之後會是尾巴
rev_prev = None
# 反轉 m~n 節點 # 同單向 Linked List 反轉
for _ in range(n - m + 1):
next_node = cur.next
cur.next = rev_prev
rev_prev = cur
cur = next_node
# 接回原 list
prev.next = rev_prev # 上面prev在m-1，後面接反轉後的linklist
tail.next = cur
return dummy.next
```
```c
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
if (!head || m == n) return head;
struct ListNode dummy;
dummy.next = head;
struct ListNode* prev = &dummy; // prev 最終指向 m 前一個節點
for (int i = 1; i < m; i++) prev = prev->next; // 移動 prev 到第 m-1 個節點
struct ListNode* cur = prev->next; // m 節點
struct ListNode* next;
struct ListNode* tail = cur; // 反轉後的尾巴是 cur
struct ListNode* rev_prev = NULL;
// 反轉 m ~ n 節點
for (int i = 0; i <= n - m; i++) {
next = cur->next;
cur->next = rev_prev;
rev_prev = cur;
cur = next;
}
// 接回原鏈表
prev->next = rev_prev; // m-1 節點接反轉後的頭
tail->next = cur; // 反轉後尾巴接 n+1 節點
return dummy.next;
}
```
### 25. Reverse Nodes in k-Group
- 給定一個 單向鏈結串列 `head`，每 `k` 個節點反轉一次，並返回修改後的鏈表
- Solution：
- 用`while curr:`計算長度
- 當`while count >= k:`成立
- 執行子迴圈`for i in range(1, k):`標準單向linklist轉向
- 直到count < k
```python
class Solution:
def reverseKGroup(self, head, k):
dummy = ListNode(0)
dummy.next = head
prev = dummy
curr = head
count = 0
while curr:
count += 1
curr = curr.next
while count >= k:
curr = prev.next # 第 1 個節點
next = curr.next
# 反轉 k 個節點 # 同單向 Linked List 反轉
for i in range(1, k):
curr.next = next.next
next.next = prev.next
prev.next = next
next = curr.next
prev = curr
count -= k
return dummy.next
```
```c
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
if (!head || k == 1) return head;
struct ListNode dummy;
dummy.val = 0;
dummy.next = head;
struct ListNode *prev = &dummy, *curr, *next; // 同時宣告*prev, *curr, *next;
// 計算長度
int count = 0;
curr = head;
while (curr) {
count++;
curr = curr->next;
}
while (count >= k) {
curr = prev->next; // 第 1 個節點
next = curr->next;
for (int i = 1; i < k; i++) {
curr->next = next->next;
next->next = prev->next;
prev->next = next;
next = curr->next;
}
prev = curr;
count -= k;
}
return dummy.next;
}
```
### 19. Remove Nth Node From End of List
- 給定一個 單向鏈結串列 `head`，刪掉倒數第`n`個元素，並返回修改後的鏈表
- Solution：
-
```python
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: Optional[ListNode]
:type n: int
:rtype: Optional[ListNode]
"""
dummy = ListNode(0)
dummy.next = head
curr = dummy.next
count=0
while curr:
count+=1
curr=curr.next
curr = dummy # 一定要從dummy開始，不然linklist只有一項會錯
for _ in range(count - n): curr = curr.next
curr.next = curr.next.next
return dummy.next
```
```c
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode dummy;
dummy.val = 0;
dummy.next = head;
struct ListNode* curr = dummy.next;
int count = 0;
while (curr) {
count++;
curr = curr->next;
}
curr = &dummy;
for (int i = 0; i < count - n; i++) curr = curr->next;
struct ListNode* temp = curr->next;
curr->next = curr->next->next;
free(temp); // C要釋放記憶體
return dummy.next;
}
```
### 82. Remove Duplicates from Sorted List II
- 給一個已排序的 linked list，刪除所有出現超過一次的數字，只留下「完全沒重複過」的節點
- Solution：
- 用`dup`紀錄重複的值，用`while`將該值都刪掉
```python
class Solution(object):
def deleteDuplicates(self, head):
dummy = ListNode(0)
dummy.next = head
prev = dummy
cur = head
while cur:
if cur.next and cur.val == cur.next.val:
dup = cur.val
while cur and cur.val == dup:
cur = cur.next
prev.next = cur
else:
prev = cur
cur = cur.next
return dummy.next
```
```c
struct ListNode* deleteDuplicates(struct ListNode* head) {
struct ListNode dummy;
dummy.next = head;
struct ListNode* prev = &dummy; // record
struct ListNode* cur = head; // process
while (cur) {
if (cur->next && cur->val == cur->next->val) {
int dup = cur->val;
while (cur && cur->val == dup) { // 同一個值都要刪掉
struct ListNode* tmp = cur;
cur = cur->next;
free(tmp);
}
prev->next = cur;
} else {
prev = cur;
cur = cur->next;
}
}
return dummy.next;
}
```
### 61. Rotate List
- 給一個已排序的 linked list，跟數字`k`，把最後一個元素放到第一個元素`k`次
- Solution：
- 把linklist變成環狀，再找新的頭跟新的尾巴
- `while curr.next:` 計算linklist長度
- 從第一個元素走`長度-k-1`是新的尾巴，`.next`是新的頭
```python
class Solution(object):
def rotateRight(self, head, k):
if not head or not head.next: return head
dummy = ListNode(0)
dummy.next = head
curr = head
count = 1
while curr.next:
curr = curr.next
count += 1
k %= count
if k == 0: return head
curr.next = head # 接成環
curr = head
# 找新尾巴：走 count - k - 1 步
for _ in range(count - k - 1): curr = curr.next
dummy.next = curr.next
curr.next = None
return dummy.next
```
```c
struct ListNode* rotateRight(struct ListNode* head, int k) {
if (head == NULL || head->next == NULL) return head;
struct ListNode dummy;
dummy.next = head;
struct ListNode* curr = head;
int count = 1;
while (curr->next != NULL) {
curr = curr->next;
count++;
}
k %= count;
if (k == 0) return head;
curr->next = head;
// 找新尾巴：走 count - k - 1 步
curr = head;
for (int i = 0; i < count - k - 1; i++) {
curr = curr->next;
}
dummy.next = curr->next;
curr->next = NULL;
return dummy.next;
}
```
### 86. Partition List
- 給你一個 linked list head，還有一個整數 x，重新排列 linked list，使得：
- 所有 < x 的節點在前面
- 所有 >= x 的節點在後面
- 重點：相對順序要保持（stable）
- Solution：
- 開兩條 `list`，一條裝 `< x`，一條裝 `>= x`，最後接起來
```python
class Solution(object):
def partition(self, head, x):
small_dummy = ListNode(0)
large_dummy = ListNode(0)
small = small_dummy
large = large_dummy
curr = head
while curr:
if curr.val < x:
small.next = curr
small = small.next
else:
large.next = curr
large = large.next
curr = curr.next
large.next = None
small.next = large_dummy.next
return small_dummy.next
```
```c
struct ListNode* partition(struct ListNode* head, int x) {
struct ListNode small_dummy, large_dummy;
small_dummy.next = NULL;
large_dummy.next = NULL;
struct ListNode* small = &small_dummy;
struct ListNode* large = &large_dummy;
struct ListNode* curr = head;
while (curr != NULL) {
if (curr->val < x) {
small->next = curr;
small = small->next;
} else {
large->next = curr;
large = large->next;
}
curr = curr->next;
}
large->next = NULL;
small->next = large_dummy.next;
return small_dummy.next;
}
```
### 146. LRU Cache
- Least Recently Used
- 實作一個快取系統，支援兩個操作：
- `get(key)` → O(1)
- `put(key, value)` → O(1)，當容量滿了，要刪掉「最久沒被使用的」資料
- 正解只能是：Hash Table + Doubly Linked List
- 只用 array / list → `get(key)`無法 O(1)
- 只用 hash table → 不知道誰最久沒用
- Solution：
- Hash Map：key → node，O(1) 找到資料
- Doubly Linked List：記錄使用順序，最近用的放前面，最久沒用的在後面（尾巴）
- `get(key)`
- key 不存在 → return -1
- key 存在：把該 node 移到最前面(因為最近使用) return value
- `put(key, value)`
- key 已存在：更新 value，把 node 移到最前面
- key 不存在：如果容量滿了：刪掉尾巴（LRU），hash 也要刪，插新 node 到最前面，hash 記錄 key → node
- 把node移到最前面都是先刪掉node`_remove`，再插入最前面`_add_to_head`
```python
class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache(object):
def __init__(self, capacity):
self.capacity = capacity
self.cache = {} # key -> node
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
prev = node.prev
nxt = node.next
prev.next = nxt
nxt.prev = prev
def _add_to_head(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_head(node)
return node.value
def put(self, key, value):
if key in self.cache:
node = self.cache[key]
node.value = value
self._remove(node)
self._add_to_head(node)
else:
if len(self.cache) == self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
node = DLinkedNode(key, value)
self.cache[key] = node
self._add_to_head(node)
```
# Reference
- [Hello Algo](https://www.hello-algo.com/zh-hant/)
- [GeeksforGeeks](https://www.geeksforgeeks.org/)
- [Leetcode](https://leetcode.com/)
- [Collegiate Programming Examination](https://cpe.mcu.edu.tw/)
- [HackerRank](https://www.hackerrank.com/)
Sign in with Wallet
Connect another wallet