# Leetcode
## 1. Two sum:
###### tags: array, hash table, hashmap
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
### Example:
```python=
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Input: nums = [3,2,4], target = 6
Output: [1,2]
```
### solution:
Time complexity: O(n)
```python=
nums = [2,3,4]
target=6
hashmap = {} # 創建一個dictionary
for i in range(len(nums)):
complement = target - nums[i] # 用target 去減nums裡面的值可以少一次判斷式
# complement: 2 = target: 6 - nums[i]: 4, i=2
if complement in hashmap: #用complement 去比對有無在hashmap出現
print([i, hashmap[complement]])
# 已知答案（complement）是2，所以用hashmap[complement]去找
# hashmap 是dictionary 所以打number 會得到冒號後的index
# i是因為下一行 hashmap[nums[i]] = i時 nums[i]的位置編號就是i
hashmap[nums[i]] = i
# 在迴圈之中，但不是在判斷式之後，不需要符合判斷式，只會照迴圈執行
# 目的是要創建hashmap，就算一開始就找到值也會執行完
```
variable output when getting final result:
```python=
print:
[2, 0]
hashmap:
{2: 0, 3: 1, 4: 2}
{number:index}
i:
2
complement:
2
nums[i]:
4
```
## 217. Contains Duplicate
###### tags: sorting, hash table, hashmap
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.
### Example:
```python=
Input: nums = [1,2,3,1]
Output: true
Input: nums = [1,2,3,4]
Output: false
```
### **Solution 1: hashmap**
Time complexity: O(n)
```python=
class Solution:
def containsDuplicate(nums) -> bool:
hashmap = {} # 先創建空的dictionary
for i in nums: # 直接用nums裡面題目的值當迴圈，把i丟進去hashmap比對
if i in hashmap: #如果i出現在hashamp就會return true不會跑下一行
return True
hashmap[i] = 1
#如果if不符合就會存進hashmap，因為index不重要，所以可以等於任一數
return False
```
### Solution 2:
```python=
class Solution:
def containsDuplicate(nums]) -> bool:
so = sorted(nums) # 先將list排序，讓同樣數字排在一起
output = ''
for i in range(len(so)):
if len(so) == 1: # 若list只有一個，直接回傳false
return False
elif so[i] - so[i-1] == 0:# 用i-1省一層迴圈
output = 'true' # 把true 存進output讓後面判斷式用
return True
if output != 'true':
return False
```
### Solution 3:
```python=
class Solution:
def containsDuplicate(nums) -> bool:
return len(nums) != len(set(nums))
# 直接用return 回傳後面陳述式的布林結果
# python會回傳 比較式(>,<,==)的布林值
# set()會回傳list中的唯一數字
```
## 387. First Unique Character in a String
###### tags: hash table, hashmap, string
Given a string, find the first non-repeating character in it and return its index. If it does not exist, return -1.
### Example:
```python=
Input: s = "leetcode"
Output: 0
Example 2:
Input: s = "loveleetcode"
Output: 2
Example 3:
Input: s = "aabb"
Output: -1
```
### Solution 1: Dictionary
This solution is based on the dictionary in python
here we calculate the count of every character into a dict like {'a':1} and then search for the first element having count 1
Then we will search the index of that element into the string and return it if possible otherwise return -1
```python=
Input: s = "leetcode"
class Solution:
def firstUniqChar(self, s: str) -> int:
count = Counter(s)
# Counter()是一個內建的函數，可以計算list中每個字母的出現次數，
# 並存成dictionary
for i,j in count.items():
# items()可以用來將dictionary中的值一組一組取出
if j == 1:
return s.index(i)
# index 會回傳list中第一個出現的值的位置
return -1
```
### Solution 2: Hashmap
```python=
Input: s = "leetcode"
def firstUniqChar(self, s: str) -> int:
letter_counts = {} # 先創建空的dictionary
for i in range(len(s)):
letter = s[i] # 從list選取字母進去比對
if letter in letter_counts: # 將letter 去 dictionary 比對
continue # 若符合上面判斷式 continue會讓程式跳出if判斷式
# 因為若字母已在dictionary裡面，代表已經計數過了不用再做一次
else:
letter_count = s.count(letter)
# 計算s裡面特定字母的數量
if letter_count == 1:
# 巢狀在上面else的判斷式
'''
如果letter_count符合條件式
會直接輸出不會存進dictionary
'''
return i
else:
letter_counts[letter] = letter_count
# 按照key-value存進dictionary
return -1
```
## 9. Palindrome Number
###### tags: Math
Given an integer x, return true if x is palindrome integer.
An integer is a palindrome when it reads the same backward as forward.
For example, 121 is a palindrome while 123 is not.
### example:
```python=
Input: x = 121
Output: true
Input: x = 10
Output: false
```
### Solution 1: Fastest
```python=
class Solution:
def isPalindrome(self, x: int) -> bool:
return str(x)[::-1] == str(x)
# 先用str()把數字轉字串
# 反轉字串，當[::-1]: [begin: end:step] ，如果step=-1代表反轉
# 用return特性直接回傳 True/False，負值因為已經轉成字串，'-'也是文字之一，
# 所以不會影響結果
```
### Solution 2:
```python=
x = 0
reversed_x = 0
s = x # 因為要和reversed的比較，但while 迴圈之後會被除掉，所以要先存下來
while x !=0: # 只要x不等於0，wheile迴圈會保持執行
digit = x % 10 # 用餘數存出x最後一個數字
reversed_x = reversed_x * 10 + digit
# 組合出反轉後的數字
# reversed_x 包含上一次迴圈儲存的值
x //= 10
# 除10後不保留餘數
# ex: 10/7=1餘3，//=只會取1，目的是要刪掉已倒序過的值
if reversed_x == s:
print('true')
else:
print('false')
```
## 14. Longest Common Prefix
###### tags: String
找最長共同字首
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 "".
### example:
```python=
Input: strs = ["flower","flow","flight"]
Output: "fl"
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
```
### Solution 1: Fastest
```python=
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
c=strs[0] # 先選出第一單字
for st in strs[1:]: #按順序從第二單字開始存入st
while st[:len(c)] != c and c:
# 開始將st裁成和c(選出的第一個單字)一樣長度，如裁出的字母和c一樣則
# 終止while迴圈
c=c[:len(c)-1] # 若終止條件不符合，則把c縮減一個字母
if not c:
# 如果都沒有相同字首則中斷迴圈
# if not 可以來判斷是否為空值，若成立則執行後面程式碼
break
return c
```
### Solution 2:
```python=
strs = ["flower","flow","flight"]
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
i=0 # 用i來紀錄讀第幾個字母（即第幾組list）
for s in zip(*strs): # 將第一組讀進s (a>b>c>d)
if len(set(s))!=1:
break
# 用set來取唯一值，
# 取完若不是只有一個字母代表字首己經不一樣了，則終止迴圈
i+=1 # 若大家還是一樣用i記錄往後移一個字母
return strs[0][0:i]
# i是list的end，因為上面i是紀錄第幾個字母不同，所以剛好可以設為end，
# 實際會return的是前一個字母
```
解析：
已知：
```python=
壓縮：
list(zip(la,lb))
output:
[('a', '1'), ('b', '2'), ('c', '3'), ('d', '4')]
解壓：
y = zip(la,lb)
list(zip(*y))
output:
['a', 'b', 'c', 'd']
['1', '2', '3', '4']
```
題目：
```python=
["flower","flow","flight"]
```
可以視為3組壓縮後的結果：
```python=
[('f', 'l', 'o', 'w', 'e', 'r'),('f', 'l', 'o', 'w'),('f', 'l', 'i', 'g', 'h', 't')]
```
但因為實際壓縮只會取齊長：
```python=
[('f', 'l', 'o', 'w'),('f', 'l', 'o', 'w'),('f', 'l', 'i', 'g')]
```
另外一種表示法：
```python=
字首第一字母：
(a[0], b[0], c[0], d[0], e[0], f[0]) == ('f', 'l', 'o', 'w', 'e', 'r')
字首後第二字母：
(a[1], b[1], c[1], d[1]) == ('f', 'l', 'o', 'w')
字首後第三字母：
(a[2], b[2], c[2], d[2], e[2], f[2]) == ('f', 'l', 'i', 'g', 'h', 't')
```
解壓後結果：
```python=
a = ['f', 'f', 'f']
b = ['l', 'l', 'l']
c = ['o', 'o', 'i']
d = ['w', 'w', 'g']
```
## 20. Valid Parentheses
###### tags: String, Stack
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
#### Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.
### example:
```python=
Input: s = "()"
Output: true
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
```
### Solution 1: More neat
```python=
class Solution:
def isValid(self, s: str) -> bool:
mapping = {"(":")","{":"}","[":"]"} # 建立對照的查表
open_par = ["(","[","{"] # 建立左括號的查表
stack = [] # 定義stack為一list
for i in s:
if i in open_par:
stack.append(i) # 把符合左括號的存入stack中
elif stack and i == mapping[stack[-1]]:
# elif stack是為了要先判斷stack是否為空值（在s="]"情況下會是
# 空值），此時stack.pop()會刪不到東西會出error
# 若在s="([])"情況下，讀到最中間時會開始觸發，當讀到第一個右括號時
# stack[-1]會去讀存在stack中的括號，因為符合條件的s．
# 右半邊'})'會是stack的倒序。最後再用mapping查表，找對應的右括號
# Dictionary 只能用冒號左去查右
stack.pop()
# 如果有找到就刪掉stack中最後一個左半部的括號，用迴圈查下一個
else:
return False # 上述條件都不符合則回傳False
return stack == []
# 如果只打return true 就不會檢查到 s='{'情況，如果左右括號都有對應到理論
# 最後stack會是null
```
### Solution 2: Similar than above, but easier to understand
```python=
class Solution:
def isValid(self, s: str) -> bool:
left_parentheses = ['(', '[', '{']
stack = []
for i in s:
if i in left_parentheses:
stack.append(i)
elif stack:
if i == ')' and stack[-1] == '(':
stack.pop()
elif i == ']' and stack and stack[-1] == '[':
stack.pop()
elif i == '}' and stack[-1] == '{':
stack.pop()
else:
return False
else:
return False
return len(stack) == 0 # 和return stack == []一樣用意
```
## 53. Maximum Subarray
###### tags: Array, Divided and Conquer, Dynamic Programming
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
### Example:
```python=
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Input: nums = [1]
Output: 1
Input: nums = [5,4,-1,7,8]
Output: 23
```
### Solution: O(n),Dynamic Programming, Kadane's Algorithm
Time complexity: O(n)
Space complexity: O(1)
```python=
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
current_total = max_total = nums[0]
# 起始值都設為nums第一個數字可以省去定義為-inf的指令
for num in nums[1:]: # 跳過第一個已經被拿去做定義的數字
current_total = max(num, current_total+num)
# 只要不要被加總到比單一數還小，current_total都會一直存下去試圖
# 存出最長字串
max_total = max(current_total, max_total)
# 當max_total遇到目前最大時會存進去，current_total像是測試品，
# 在上上句試更多可能，只要不要比單一數字num小，都不會被取代，
# 但如果反之，則會帶去max_total比較，max_total可能存的是
# 目前單一數最大或是組合數最大
return max_total
```
### Solution: O(n^2^)
Time complexity: O(n^2^)
Space complexity: O(1)
```python=
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_total = -float('Inf')
for i in range(len(nums)):
current_total = 0
for j in range(i, len(nums)):
current_total = current_total + nums[j]
max_total = max(current_total,max_total)
return max_total
```
### Solution: Divide and Conquer
Time complexity: O(n*log(n))
Space complexity: O(log(n))
```python=
'''
最後執行帶入的參數：
findBestSubarray(nums, 0, len(nums) - 1)
'''
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def findBestSubarray(nums, left, right):
# Base case - empty array.
# 如果
if left > right:
return -float('inf')
mid = (left + right) // 2 # 找中心點，用//取整數
curr = best_left_sum = best_right_sum = 0
# 設定起始值，和DP一樣概念
# Iterate from the middle to the beginning.
# 用DP找左半部的最大值
for i in range(mid - 1, left - 1, -1):
curr += nums[i] # curr = curr+nums[i]
best_left_sum = max(best_left_sum, curr)
# Reset curr and iterate from the middle to the end.
# 用DP找右半部的最大值
curr = 0
for i in range(mid + 1, right + 1):
curr += nums[i] # curr = curr+nums[i]
best_right_sum = max(best_right_sum, curr)
# The best_combined_sum uses the middle element and
# the best possible sum from each half.
# 計算有使用mid 的組合的最大可能
best_combined_sum = nums[mid] + best_left_sum + best_right_sum
# Find the best subarray possible from both halves.
# 用本來的函數計算純左和右的組合，此時會一直遞迴(recursion)下去，
# 將左半部又找出新的mid，在計算左右，最後存出最大值
left_half = findBestSubarray(nums, left, mid - 1)
right_half = findBestSubarray(nums, mid + 1, right)
# The largest of the 3 is the answer for any given input array.
return max(best_combined_sum, left_half, right_half)
# Our helper function is designed to solve this problem for
# any array - so just call it using the entire input!
return findBestSubarray(nums, 0, len(nums) - 1)
```
## 13. Roman to Integer
###### tags: Hash Table, Math, String
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Given a roman numeral, convert it to an integer.
| Symbol | Value |
| -------- | -------- |
|I|1|
|V|5|
|X|10|
|L|50|
|C|100|
|D|500|
|M|1000|
For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
* I can be placed before V (5) and X (10) to make 4 and 9.
* X can be placed before L (50) and C (100) to make 40 and 90.
* C can be placed before D (500) and M (1000) to make 400 and 900.
### Example
```python=
Input: s = "III"
Output: 3
Explanation: III = 3.
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
```
### Solution 1: Faster
```python=
class Solution:
def romanToInt(self, s: str) -> int:
conversion = {
'I':1,
'V':5,
'X':10,
'L':50,
'C':100,
'D':500,
'M':1000,
}
inv_s = s[::-1] # 反轉list
sum = 0
last = 0
for char in inv_s:
current = conversion[char]
if current < last: # 需要一次讀2個字母的特色是前面一位會比後面一位小
sum -= current # 讀2個字母總值剛好等於後面減前面(ex. IV = 4)
else:
sum += current
last = current # 把這個迴圈存進去去做下一次比較，確認是不是需要一次讀2字母
return sum
```
### Solution 2:
```python=
class Solution:
def romanToInt(self, s: str) -> int:
mapping = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
"IV": 4,
"IX": 9,
"XL": 40,
"XC": 90,
"CD": 400,
"CM": 900
}
i = 0
total = 0
while i < len(s):# 因為i=0，所以在s長度執行完的前一部就會把s內容讀完
if i < len(s) - 1 and s[i:i+2] in mapping:
# 前半部是為了要確保讀進去會是2位數
# (上一行會讀進s最後一個值，等於-1會讀進去最後2個值)
# 後半部是用list功能按順序讀進2個字母，並比對有無在map中
total = total + mapping[s[i:i+2]]
i = i + 2 # 因為若進這個迴圈是一次讀2個值，所以是加2
else:
total = total + mapping[s[i:i+1]]
i = i + 1
return total
```
## 680. Valid Palindrome II
###### tags: Two pointer, String, Greedy
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
### example
```python=
Input: s = "aba"
Output: true
Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.
Input: s = "abc"
Output: false
```
### Solution: fastest
```python=
def validPalindrome(s) -> bool:
if s == s[::-1]: # 先檢查本身是不是迴文
return True
i = 0 # 定位出字首
j = len(s)-1 # 定位出字尾
while i < j:
if s[i]==s[j]: # Two pointer, 從左右開始往內檢查，若左右一樣則往內一位
i+=1
j-=1
else:
excl_i = s[i+1:j+1] # 若檢查到不一樣，刪左邊一位檢查是不是迴文
# 因為list是 [start:end]所以要加一位，上面s[i]只有表示起始值所以不影響
excl_j = s[i:j]# 同時也刪右邊一位檢查
return excl_i == excl_i[::-1] or excl_j == excl_j[::-1]
# 若移一位發現是迴文就可以回傳True
return True
```
Sign in with Wallet
Connect another wallet