11. Container With Most Water (Medium)
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
class Solution:
def maxArea(self, height: List[int]) -> int:
res = 0
l = 0
r = len(height)-1
while l<r:
res = max(res, (r-l)*min([height[r],height[l]]))
if height[l]<height[r]:
l+=1
else:
r-=1
return res
two pointer 方法， 计算 left到right之间的water，如果left小于right，得寻找更大的left所以left右移动，反之right左移动。 假如 l --- r 移动中错过了最优解，比如在 l 前，比l 还高， 那这个解已经扫过了，因为r只可能在现在的位置或者更右的位置，所有two pointer可以扫出最优解。
12. Integer to Roman （Medium）
class Solution:
def intToRoman(self, num: int) -> str:
#finding highest possible symbol, extract the val then loop until 0
dic = {1000:'M',900:'CM',500:'D',400:'CD',
100:'C',90:'XC' ,50:'L',40:'XL',10:'X',
9:'IX',5:'V',4:'IV',1:'I'}
res = ''
while num:
for k,v in dic.items():
if num-k >=0:
num = num-k
res+=v
break
return res
13. Roman to Integer (easy)
class Solution:
def romanToInt(self, s: str) -> int:
# I before V is 4
# X is 9
# X before L is 40
# C is 90
# C before D is 400
# M is 900
dic1 = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,}
dic2={
'IV':4,
'IX':9,
'XL':40,
'XC':90,
'CD':400,
'CM':900
}
res = 0
while s:
if len(s)>1 and s[:2] in dic2:
res += dic2[s[:2]]
s=s[2:]
elif s[0] in dic1:
res += dic1[s[0]]
s=s[1:]
return res
14. Longest Common Prefix (Easy)
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 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
max_len = min([len(s) for s in strs])
i=0
res = ''
common_char = None
while i<max_len:
for s in strs:
char = s[i]
if common_char is None:
common_char = char
else:
if common_char!=char:
return res
res+= common_char
i+=1
common_char = None
return res
15. 3Sum (Medium)
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
#backtracking
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
#-4 -1 -1 0 1 2
res = []
def bt(nums,tmp,start):
if len(tmp)==3 and sum(tmp)==0:
res.append(tmp[:])
for i in range(start,len(nums)):
if i > start and nums[i] == nums[i-1]: continue
n = nums[i]
tmp.append(n)
bt(nums,tmp,i+1)
tmp.pop()
nums.sort()
bt(nums,[],0)
return res
#two pointer
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res=[]
for i in range(len(nums)-2):
cur = nums[i]
if i-1>=0 and nums[i]==nums[i-1]: continue
l = i+1
r = len(nums)-1
while l<r:
if nums[l]+nums[r]+cur<0:
l+=1
elif nums[l]+nums[r]+cur>0:
r-=1
else:
res.append([cur,nums[l],nums[r]])
while l+1<len(nums) and nums[l]==nums[l+1]:
l+=1
while r-1>=0 and nums[r]==nums[r-1]:
r-=1
l+=1
r-=1
return res
backtracking在去重复时候卡住了（但正确结果也会TIME LIMIT EXCEED），two pointer？忘记了算法。。。 选定一个target 然后 移动left 和right 注意去重。
16. 3Sum Closest (Medium)
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
abs_diff = float('inf')
res = float('inf')
for i in range(len(nums)-2):
cur = nums[i]
left= i+1
right = len(nums)-1
while left< right:
val = cur+nums[left]+nums[right]
if abs(val-target)< abs_diff:
abs_diff = abs(val-target)
res = val
if val>target:
right -= 1
elif val<target:
left+=1
else:
left+=1
right -=1
return res
17. Letter Combinations of a Phone Number (Medium)
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
Example :
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
m = {
'2':'abc',
'3':'def',
'4':'ghi',
'5':'jkl',
'6':'mno',
'7':'pqrs',
'8':'tuv',
'9':'wxyz'
}
res = []
def bt(dig,tmp):
if not dig:
if tmp:
res.append(tmp)
return
cur = dig[0]
for ch in m[cur]:
bt(dig[1:],tmp+ch)
bt(digits,'')
return res
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
dic= {
2:'abc',
3:'def',
4:'ghi',
5:'jkl',
6:'mno',
7:'pqrs',
8:'tuv',
9:'wxyz'
}
res = []
l = len(digits)
def bt(digits,tmp,start):
if len(tmp)==l:
res.append(tmp[:])
for i in range(start,len(digits)):
key = int(digits[i])
row = dic[key]
for char in row:
tmp.append(char)
bt(digits,tmp,i+1)
tmp.pop()
bt(digits,[],0)
return [''.join(r) for r in res] if len(res)>0 else []
标准的backtracking应用
18. 4Sum （Medium）
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums)-3):
if i-1>=0 and nums[i-1] == nums[i]: continue
for j in range(i+1,len(nums)-2):
if j-1>i and nums[j-1]==nums[j]:continue
l=j+1
r=len(nums)-1
while l<r:
if nums[i]+nums[j]+nums[l]+nums[r]<target:
l+=1
elif nums[i]+nums[j]+nums[l]+nums[r]>target:
r-=1
else:
res.append([nums[i],nums[j],nums[l],nums[r]])
while l+1<len(nums) and nums[l+1]==nums[l]:
l+=1
while r-1>=0 and nums[r-1]==nums[r]:
r-=1
l+=1
r-=1
return res
注意去重判断 if i-1>=0 and nums[i-1] == nums[i]: continue， if j-1>i and nums[j]==nums[j-1]: continue， while l+1小于len(nums) and nums[l+1]==nums[l]: l+=1， while r-1>=0 and nums[r-1]==nums[r]: r-=1
19. Remove Nth Node From End of List （Medium）
Given the head of a linked list, remove the nth node from the end of the list and return its head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummyhead = ListNode(val='NULL')
dummyhead.next = head
heada = dummyhead
headb = dummyhead
for i in range(n):
headb = headb.next
while headb and headb.next:
heada = heada.next
headb = headb.next
heada.next = heada.next.next
return dummyhead.next
20. Valid Parentheses (Easy)
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.
class Solution:
def isValid(self, s: str) -> bool:
# meet （ push in stack
# meet ）pop outof stack
dic={')':'(',']':'[','}':'{'}
stack = []
for char in s:
if char in {'(','[','{'}:
stack.append(char)
else:
#pop
if not stack:
return False
top_stack = stack.pop()
if top_stack!= dic[char]:
return False
return not stack
#simply way of writing code
class Solution:
def isValid(self, s: str) -> bool:
dic = {')':'(',']':'[','}':'{'}
stack = []
for e in s:
if e in dic:
#pop
if not stack or stack[-1]!=dic[e]:
return False
stack.pop()
else:
stack.append(e)
return not stack