1. Two Sum （Easy）
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = dict()
for i, n in enumerate(nums):
if target - n in dic:
return [i, dic[target-n]]
dic[n] = i
笨方法，double loop， 找到加和是target。O（N**2）
实际解法，用map存位置，如果target-n 剩余的在之前存过的map里，说明 target-n 和 n 就是要求的结果。
2. Add Two Numbers （Medium）
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
result = ListNode('NULL')
head = result
carry = 0
while l1 or l2:
l1val = 0
l2val = 0
if l1:
l1val = l1.val
l1 = l1.next
if l2:
l2val = l2.val
l2 = l2.next
val = (l1val+l2val+carry)%10
carry = (l1val+l2val+carry)//10
head.next = ListNode(val=val)
head = head.next
if carry:
head.next = ListNode(val=carry)
return result.next
已经是reverse ordered linked list，所以可以直接对l1,l2的val加和， 但是需要注意carry 以及 l1 or l2 可能在loop到下一位时提前空了， 所以预先定义l1val=0 和l2val=0 有value就overwrite，最后检查是否还有carry， 有就新建个ListNode存carry。返回结果。
3. Longest Substring Without Repeating Characters （Medium）
Given a string s, find the length of the longest substring without repeating characters.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
#when meet the overlapping char, start = overlapping char pos end =current char pos -1
#when not meet overlapping char, start stil old start end = current char pos
if s == ' ': return 1
if not s: return 0
result = 0
dic = dict()
start = 0
for i,char in enumerate(s):
if (char in dic) and (dic[char]>=start):
#find a overlapping char
start = dic[char]
tmp_result = i-start
result = max(result,tmp_result)
start = start + 1
else:
# no overlapping
# 0 1 2
tmp_result = i-start+1
result = max(result,tmp_result)
dic[char] = i
return result
花了些时间还是写出答案了，但是时间较长，解题思路：
如果存在已经见过的char，更新结果result = max（result， i-dic[char]），老的已经见过char的下一位是新的起始点， 如果没见过char，则同样更新结果 result = max（result， i-start+1）,
但注意 start 这个位置一直应该是单增的， 所以 有这行判断 if (char in dic) and (dic[char]>=start) 例子： abba，如果没这行判断， start 在遇到第二个a时候会重置回0，明显错误。 根据leetcode 这种解法属于sliding window。
精简写法
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
dic = dict()
res = 0
start = 0
for i,char in enumerate(s):
if char in dic:
start = max(start,dic[char]+1) # a b ..... a # start=b pos
res = max(res, i-start+1)
dic[char] = i
return res
4. Median of Two Sorted Arrays (Hard)
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
粗暴解法直接重新排序求中位数，但不满足 O(log (m+n))， 说明用了二分法。
中位数定义是一半的数， 则假设有个分界线 | 同时分开nums1，nums2.
nums1[0] nums1[1] ... nums1[i-1] | nums1[i] ... nums1[m-1]
nums2[0] nums2[1] ... nums2[j-1] | nums2[j] ... nums2[n-1]
median nums1[i-1] 小于 nums2[j]
nums2[j-1] 小于 nums1[i]
i+j = (m+n +1)//2
i: 0~m j = (m+n+1)//2 - i m小于n
在 0~m中 二分查找
确定 i
确定 j
知道 | 边界情况来决定是左移还是右移动搜索边界
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# nums1[0] nums1[1] ... nums1[i-1] | nums1[i] ... nums1[m-1]
# nums2[0] nums2[1] ... nums2[j-1] | nums2[j] ... nums2[n-1]
# median nums1[i-1]<nums2[j]
# nums2[j-1]<nums1[i]
# i+j = (m+n +1)//2
# i: 0~m j = (m+n+1)//2 - i m<n
#edge cases
if nums1 and not nums2:
if len(nums1)%2==1:
return nums1[len(nums1)//2]
else:
return (nums1[len(nums1)//2] + nums1[len(nums1)//2-1])/2.0
if nums2 and not nums1:
if len(nums2)%2==1:
return nums2[len(nums2)//2]
else:
return (nums2[len(nums2)//2] + nums2[len(nums2)//2-1])/2.0
m = len(nums1)
n = len(nums2)
if m>n:
m,n= n,m
nums1,nums2=nums2,nums1
left = 0
right = m
while left <= right:
i = (left+right)//2
j = (m+n+1)//2 - i
if i-1>=0 and nums1[i-1] > nums2[j]:
# i is too large
right = i-1
elif i<m and nums2[j-1] > nums1[i]:
#i is too small
left = i+1
else:
if i==0:
larget_left=nums2[j-1]
elif j==0:
larget_left = nums1[i-1]
else:
larget_left = max(nums2[j-1],nums1[i-1])
if (m+n)%2==1: return larget_left
if i==m:
smaller_right = nums2[j]
elif j==n:
smaller_right = nums1[i]
else:
smaller_right = min(nums1[i],nums2[j])
return (larget_left+smaller_right)/2.0
直接copy了答案。。。
5. Longest Palindromic Substring （Medium）
Given a string s, return the longest palindromic substring in s.
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
#Best Answer
class Solution:
def longestPalindrome(self, s: str) -> str:
res = ""
resLen = 0
for i in range(len(s)):
#odd length
l,r = i,i
while l>=0 and r<len(s) and s[l]==s[r]:
if (r-l+1)>resLen:
res = s[l:r+1]
resLen = r-l+1
l-=1
r+=1
#enven length
l,r = i,i+1
while l>=0 and r<len(s) and s[l]==s[r]:
if (r-l+1)>resLen:
res = s[l:r+1]
resLen = r-l+1
l-=1
r+=1
return res
class Solution:
def longestPalindrome(self, s: str) -> str:
# ith pos, s[i-length]~ s[i] is palindrome
# ith
# 0 1 2
# b a b
# or s[i-length-1]~s[i] is palindrome
if not s: return s
if len(s)==1: return s
length = 1
string = s[0]
for i in range(len(s)):
if (i-length>=0) and (s[i-length:i+1] == s[i-length:i+1][::-1]):
l = len(s[i-length:i+1])
if l > length:
string = s[i-length:i+1]
length = l
if (i-length-1>=0) and s[i-length-1:i+1] == s[i-length-1:i+1][::-1]:
l = len( s[i-length-1:i+1])
if l > length:
string = s[i-length-1:i+1]
length = l
6. Zigzag Conversion （Medium）
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1: return s
#init rows
res = [[] for _ in range(numRows)]
#
direction_down = True
#y_pos is the next y_pos char sitting at
y_pos = 0
#
for char in s:
res[y_pos].append(char)
if direction_down:
y_pos += 1
if y_pos == numRows:
#revert pos
direction_down = not direction_down
y_pos = numRows-1-1
else:
y_pos -= 1
if y_pos == -1:
#revert pos
direction_down = not direction_down
y_pos = 1
return ''.join([''.join(row) for row in res])
注意numRows==1 edge case
7. Reverse Integer （Medium）
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
class Solution:
def reverse(self, x: int) -> int:
sign = 1 if x>=0 else -1
x = abs(x)
res = 0
while x:
last_dig = x%10
res = res*10 + last_dig
x = x//10
return res*sign if (res*sign>=-2**31 and res*sign<=2**31-1) else 0
8. String to Integer (atoi) （Medium）
class Solution:
def myAtoi(self, s: str) -> int:
sign = 1
#1)remove leading white space
while s and s[0] == ' ':
s = s[1:]
#2) check +/-
if len(s)>1 and s[0] in {'-','+'}:
s0 = s[0]
s = s[1:]
if s0 == '-':
sign = -1
#3) read next until next none-dig/end
i = 0
while (i<len(s)) and (s[i] in '0123456789') :
i+=1
string = s[:i]
#4) conver to int
res = int(string) if string else 0
#5) clamp res
res = res*sign
if res<-2**31:
res = -2**31
if res> 2**31-1:
res = 2**31-1
return res
按照题目要求写每个判断，很easy。
9. Palindrome Number （easy）
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 palindrome while 123 is not.
class Solution:
def isPalindrome(self, x: int) -> bool:
x_backup = x
if x<0: return False
res = 0
while x:
last_dig = x%10
res = res*10 + last_dig
x = x//10
return res == x_backup
10. Regular Expression Matching (Hard)
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
class Solution:
@lru_cache(None)
def isMatch(self, s: str, p: str) -> bool:
# .match one
# p[0] is . isMatch[s[1:],p[1:]]
# *match 0/more p[0]
# p[1] is * if * match 0 p[0]
# isMatch(s, p[2:])
# if * match more p[0]
# s[0]==p[0] and isMatch(s[1:],p)
if not p:
return not s
firstmatch = p[0] in {s[0],'.'} if s else False
if len(p)>1 and p[1]=='*':
#start matching
return (firstmatch and self.isMatch(s[1:],p)) or self.isMatch(s,p[2:])
else:
#normal matching
return firstmatch and self.isMatch(s[1:],p[1:])
注意判断 p[0] in {s[0],'.'} if s else False 这里的if s不为空。差一点写出来。。。