LeetCode 算法题练习笔记。
做了一段时间的 LeetCode，以下记录的我的题解，主要使用 Python3 实现，部分也用了 C 语言实现。
1 Two Sum
思路：
首先，对于每个数值，将与其相加等于 target 的数值，称为该元素的「匹配值」。
然后，建立一个哈希表，依次扫描序列中的元素，将每个元素以「匹配值」为索引，存储到哈希表。
当被扫描到的元素是哈希表中的一个索引时，那么则说明该元素是之前某个元素的「匹配值」，则这两个值即是本题的解。
# Python 实现
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
num_to_add = {}
for i, num in enumerate(nums):
if num in num_to_add:
return [num_to_add[num],i]
else:
num_to_add[target - num] = i
return []2 Add Two Numbers
# Python 实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
carryover = 0
node = l3 = ListNode(0)
while l1 or l2 or carryover:
if l1:
carryover += l1.val
l1 = l1.next
if l2:
carryover += l2.val
l2 = l2.next
node.next = ListNode(carryover % 10)
node = node.next
carryover = 0 if carryover<10 else 1
return l3.next// C 实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
struct ListNode *l3 = malloc(sizeof(struct ListNode));
struct ListNode *n3 = l3;
int sum = 0;
do {
if (l1) {
sum += l1->val;
l1 = l1->next;
}
if (l2) {
sum += l2->val;
l2 = l2->next;
}
n3->val = sum % 10;
sum = sum / 10;
if (l1 || l2 || sum) {
n3->next = malloc(sizeof(struct ListNode));
n3 = n3->next;
}
} while (l1 || l2 || sum);
n3->next = NULL;
return l3;
}3 Longest Substring Without Repeating Characters
# Python 实现
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
hashset = set()
offset = 0
length = 0
for i in range(0,len(s)):
# remove all elements which are added before the last s[i]
while s[i] in hashset:
hashset.remove(s[offset])
offset += 1
hashset.add(s[i])
length = max(len(hashset),length)
return length4 Median of Two Sorted Arrays
思路：归并排序的 Merge 程序。
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
# 归并排序的 Merge 子程序，但只需 Merge 数组的前半部分
full_len = len(nums1) + len(nums2)
mid_left = (full_len-1)//2
mid_right = full_len//2
pos1 = pos2 = pos3 = 0
nums3 = []
# 尚未 Merge 完成数组的前半部分
while pos3<=mid_right:
# nums1 还有剩余
if pos1<len(nums1):
# 【1】都有剩余，nums2 更小
if pos2<len(nums2) and nums1[pos1]>nums2[pos2]:
nums3.append(nums2[pos2])
pos2 += 1
# 【2】都有剩余，nums1 更小
# 【3】nums1 有剩余，nums2 无
else:
nums3.append(nums1[pos1])
pos1 += 1
# 【4】nums2 有剩余，nums2 无
elif pos2<len(nums2):
nums3.append(nums2[pos2])
pos2 += 1
pos3 += 1
return (nums3[mid_left]+nums3[mid_right])/25 Longest Palindromic Substring
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) == 0:
return ''
maxlen = 0
for i in range(len(s)):
left = i - maxlen
if left>0 and s[left-1:i+1] == s[left-1:i+1][::-1]:
start = left -1
maxlen += 2
elif s[left:i+1] == s[left:i+1][::-1]:
start = left
maxlen += 1
return s[start:start+maxlen]6 ZigZag Conversion
class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows==1 or numRows>=len(s):
return s
ans = [[] for _ in range(numRows)]
index = 0
step = -1
for ch in s:
ans[index].append(ch)
if index==0:
step=1
if index==numRows-1:
step=-1
index += step
return ''.join(''.join(row) for row in ans)7 Reverse Integer
class Solution:
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
m = 1 if x>0 else -1
r = int(str(m*x)[::-1])
return m*r*(r<2**31)int reverse(int x) {
if(x==INT_MIN) return 0;
int submax = INT_MAX / 10;
int maxmod = INT_MAX % 10;
int sign = (x>=0?1:-1);
x *= sign;
int a[32], i, j;
for(i=0; x>0; i++){
a[i] = x % 10;
x = x/10;
}
for(j=0; j<i; j++){
if(x>submax || (x==submax && a[j]>maxmod)){
return 0;
}
x *= 10;
x += a[j];
}
printf("%d\n",INT_MIN);
return sign*x;
}8 String to Integer (atoi)
class Solution:
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
import re
INT_MAX = 2147483647
INT_MIN = -2147483648
ans = 0
num_table = {'0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}
group = re.match(r'\s*([+-]?)(\d*)\s*', str).groups()
for i in group[1]:
ans = ans*10 + num_table[i]
ans = -ans if group[0] is '-' else ans
if ans>INT_MAX:
return INT_MAX
if ans<INT_MIN:
return INT_MIN
return ans9 Palindrome Number
class Solution:
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x<0:
return False
r = 1
while x//r >= 10:
r *= 10
while r:
left = x // r
right = x % 10
if left != right:
return False
x %= r
x //= 10
r //= 100
return True11 Container With Most Water
class Solution:
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
max_area = 0
i = 0
j = len(height)-1
# 从两端往中间逼近，每次都只走矮边（若高边向内走，面积只会减少），每次都检查一下面积是否有增加
while i<j:
max_area = max((j-i)*min(height[i],height[j]), max_area)
if height[i]<height[j]:
i+=1
else:
j-=1
return max_area12 Integer to Roman
class Solution:
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
M = ['','M','MM','MMM']
C = ['','C','CC','CCC','CD','D','DC','DCC','DCCC','CM']
X = ['','X','XX','XXX','XL','L','LX','LXX','LXXX','XC']
I = ['','I','II','III','IV','V','VI','VII','VIII','IX']
return M[num//1000] + C[(num%1000)//100] + X[(num%100)//10] + I[num%10]13 Roman to Integer
class Solution:
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
M = ['M','MM','MMM']
C = ['','C','CC','CCC','CD','D','DC','DCC','DCCC','CM']
X = ['','X','XX','XXX','XL','L','LX','LXX','LXXX','XC']
I = ['','I','II','III','IV','V','VI','VII','VIII','IX']
ret = 0
roman = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}
for i in range(len(s)-1):
if roman[s[i]]<roman[s[i+1]]:
ret -= roman[s[i]]
else:
ret += roman[s[i]]
return ret + roman[s[-1]]14 Longest Common Prefix
class Solution:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs or not strs[0]:
return ''
# 假设第一个字符串即为公共前缀
ans = strs[0]
for string in strs:
while not string.startswith(ans):
# 若不是前缀，就删掉末位再试
ans = ans[:-1]
return ans15 3Sum
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
if len(nums)<=3 or nums[-1]<0:
return [nums] if len(nums)==3 and sum(nums)==0 else []
ans = []
for i in range(len(nums)-2):
# num[i] 为三数中最小值，必须<=0
if nums[i]>0:break
# 过滤掉重复的 i
if i>0 and nums[i] == nums[i-1]:
continue
j = i+1
k = len(nums)-1
while j<k:
if nums[k]<0:
break
sij = nums[i] + nums[j]
# 若 nums[i]+nums[j]>0 了就不用继续了
if sij>0: break
s = sij + nums[k]
if s<0:
j += 1
elif s>0:
k -= 1
else:
ans.append((nums[i],nums[j],nums[k]))
# 过滤掉重复的j、k
while j<k and nums[j]==nums[j+1]:
j += 1
while j<k and nums[k]==nums[k-1]:
k -= 1
j += 1
k -= 1
return ans16 3Sum Closest
class Solution:
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums)<3:
return 0
if len(nums)==3:
return sum(nums)
nums.sort()
ans = nums[0]+nums[1]+nums[-1]
diff = abs(target-ans)
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
j = i+1
k = len(nums)-1
while j<k:
s = nums[i] + nums[j] + nums[k]
cur_diff = abs(s-target)
if cur_diff<diff:
diff = cur_diff
ans = s
if s<target:
j += 1
elif s>target:
k -= 1
else:
return target
return ans17 Letter Combinations of a Phone Number
class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
ret = []
if not digits:
return []
dic = {
'2':'abc',
'3':'def',
'4':'ghi',
'5':'jkl',
'6':'mno',
'7':'pqrs',
'8':'tuv',
'9':'wxyz'
}
if len(digits)==1:
return [x for x in dic.get(digits[0])]
return [''.join((x,y)) for x in dic.get(digits[0]) for y in self.letterCombinations(digits[1:])]18 4Sum
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
ans = []
if len(nums)<=4:
return [nums] if len(nums)==4 and sum(nums)==target else ans
nums.sort()
if nums[-1]*4<target:
return ans
for i in range(len(nums)-3):
if nums[i]*4>target:
break
if i>0 and nums[i]==nums[i-1]:
continue
for j in range(i+1,len(nums)-2):
if j>i+1 and nums[j]==nums[j-1]:
continue
k = j+1
l = len(nums)-1
while k<l:
if nums[l]*4<target:
break
s = nums[i] + nums[j] + nums[k] + nums[l]
if s<target:
k += 1
elif s>target:
l -= 1
else:
ans.append([nums[i],nums[j],nums[k],nums[l]])
while k<l and nums[k]==nums[k+1]:
k += 1
while k<l and nums[l]==nums[l-1]:
l -= 1
k += 1
l -= 1
return ans19 Remove Nth Node From End of List
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
new_head = ListNode(0)
new_head.next = head
cur = end = new_head # 便于删除头结点
# 使得 end 比 cur 提前 n+1 个结点
for i in range(n + 1):
end = end.next
# 当 end 越过最后一个结点，成为 None 时，cur 将指向倒数第 n+1 个结点，其 next 结点即为要删除的结点
while end:
cur = cur.next
end = end.next
cur.next = cur.next.next
return new_head.next20 Valid Parentheses
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
dic = {
']':'[',
'}':'{',
')':'('
}
stack = []
for ch in s:
# 若栈非空，且闭口括号与栈中最后一个开口括号匹配，则出栈（用get()不用[]是为了处理非闭口括号）
if stack and dic.get(ch) == stack[-1]:
stack.pop()
# 开口括号直接入栈
else:
stack.append(ch)
return not stack21 Merge Two Sorted Lists
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
l = l3 = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
l3.next = l1
l1 = l1.next
else:
l3.next = l2
l2 = l2.next
l3 = l3.next
l3.next = l1 or l2
return l.next22 Generate Parentheses
class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
ans = []
if n < 2:
ans.append('' if n==0 else '()')
return ans
maxlen = 2*n
def dfs(left=0, right=0, s=''):
if len(s) == maxlen:
ans.append(s)
return
if left<n:
dfs(left+1, right, s+'(')
if right<left:
dfs(left, right+1, s+')')
dfs()
return ans23 Merge k Sorted Lists
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if len(lists)<2:
return lists if len(lists)==0 else lists[0]
if len(lists)==2:
left, right = lists
else:
center = len(lists)//2
left = self.mergeKLists(lists[:center])
right = self.mergeKLists(lists[center:])
cur = header = ListNode(0)
while left and right:
if left.val<=right.val:
cur.next = left
left = left.next
else:
cur.next = right
right = right.next
cur = cur.next
cur.next = left or right
return header.next24 Swap Nodes in Pairs
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
cur = head
head = head.next
while cur and cur.next:
temp = cur.next.next
cur.next.next = cur
cur.next = temp.next if temp and temp.next else temp
cur = temp
return head25 Reverse Nodes in k-Group
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head or k<2:
return head
last = first = head
for _ in range(k-1):
last = last.next
if not last: return head
head = last
x = first
y = x.next
while last:
z = y.next
while y is not last:
y.next = x
x,y,z = y,z,z.next
y.next = x
# 上一段的第一个结点现在是末尾结点，指向下一段
first.next = z
# 至此上一段完成，开始下一段
if not z: return head
# 初始化下一段的 x 和 last
x = last = z
for _ in range(k-1):
last = last.next
if not last: return head
# 若下一段可以继续循环，那么上一段的第一个结点应改为指向
first.next = last
first = z
y = z.next26 Remove Duplicates from Sorted Array
class Solution:
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums)-1,0,-1):
if nums[i]==nums[i-1]:
del nums[i]
return len(nums)27 Remove Element
class Solution:
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
for i in range(len(nums)-1,-1,-1):
if val == nums[i]:
# 或者直接 del(nums[i])
for j in range(i,len(nums)-1):
nums[j] = nums[j+1]
nums.pop()
return len(nums)28 Implement strStr()
class Solution:
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
for i in range(len(haystack)-len(needle)+1):
if haystack[i:i+len(needle)] == needle:
return i
return -129 Divide Two Integers
class Solution:
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
if dividend==0: return 0
if divisor==0: return MAX_INT
positive = (dividend>0)==(divisor>0)
dividend, divisor = abs(dividend), abs(divisor)
ret = 0
while divisor<=dividend:
i, temp_divisor = 1, divisor
while temp_divisor<=dividend:
dividend -= temp_divisor
ret += i
temp_divisor <<= 1
i <<= 1
if not positive:
return max(-ret, -2147483648)
return min(ret, 2147483647)33 Search in Rotated Sorted Array
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums:
return -1
self.nums, self.target = nums, target
self.ret = -1
self.binary(0, len(nums)-1)
return self.ret
def binary(self, left, right):
left_num, right_num = self.nums[left], self.nums[right]
if self.target == left_num:
self.ret = left
elif self.target == right_num:
self.ret = right
elif left!=right and left_num>=right_num or left_num<self.target<right_num:
mid = (left + right)//2
self.binary(left, mid)
if mid<right:
self.binary(mid+1, right)
return34 Search for a Range
class Solution:
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
self.left = self.right = -1
if nums:
self.target = target
self.nums = nums
self.length = len(nums)-1
self.binarySearch(0, self.length)
return [self.left, self.right]
def binarySearch(self, left, right):
if self.left!=-1 and self.right!=-1:
return
for index in (left,right):
if self.left == -1 and (index == 0 or self.nums[index-1]<self.target) and self.target == self.nums[index]:
self.left = index
if self.right == -1 and (index == self.length or self.nums[index+1]>self.target) and self.target==self.nums[index]:
self.right = index
mid = (left+right)//2
if left<mid and self.nums[left]<=self.target<=self.nums[mid]:
self.binarySearch(left, mid)
if mid+1<right and self.nums[mid+1]<=self.target<=self.nums[right]:
self.binarySearch(mid+1, right)35 Search Insert Position
class Solution:
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
for row in board:
if not self.isValidRow(row):
return False
for row in zip(*board):
if not self.isValidRow(row):
return False
for i in (slice(0,3),slice(3,6),slice(6,9)):
for j in (slice(0,3),slice(3,6),slice(6,9)):
if not self.isValidRow([x for row in board[i] for x in row[j]]):
return False
return True
def isValidRow(self, row):
base = '123456789'
cur = set()
for i in row:
if i is '.':
continue
elif i not in base or i in cur:
return False
else:
cur.add(i)
return True36 Valid Sudoku
class Solution:
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
for row in board:
if not self.isValidRow(row):
return False
for row in zip(*board):
if not self.isValidRow(row):
return False
for i in (slice(0,3),slice(3,6),slice(6,9)):
for j in (slice(0,3),slice(3,6),slice(6,9)):
if not self.isValidRow([x for row in board[i] for x in row[j]]):
return False
return True
def isValidRow(self, row):
base = '123456789'
cur = set()
for i in row:
if i is '.':
continue
elif i not in base or i in cur:
return False
else:
cur.add(i)
return True38 Count and Say
class Solution:
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
if n==1:
return '1'
else:
x = []
count = 0
laststr = self.countAndSay(n-1) + 'x'
for i in range(0,len(laststr)-1):
count += 1
if laststr[i] != laststr[i+1]:
x.append(str(count))
x.append(laststr[i])
count = 0
return ''.join(x)39 Combination Sum
class Solution:
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
candidates.sort()
def dfs(temp, index=0, subtarget=target):
if subtarget<0:
return
if subtarget == 0:
res.append(temp)
return
for i in range(index,len(candidates)):
dfs(temp+[candidates[i]],i,subtarget-candidates[i])
dfs([])
return res46 Permutations
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.length = len(nums)
self.nums = nums
self.set = set()
self.ret = []
self.temp = [0]*self.length
self.dfs(0)
return self.ret
def dfs(self, step):
if step == self.length:
self.ret.append(self.temp[:])
return
for num in self.nums:
if num not in self.set:
self.temp[step] = num
self.set.add(num)
self.dfs(step + 1)
self.set.remove(num)48 Rotate Image
class Solution:
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
side = len(matrix)
for i in range(side//2):
matrix[i],matrix[-i-1] = matrix[-i-1],matrix[i]
for i in range(side):
for j in range(i+1,side):
matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]49 Group Anagrams
class Solution:
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
index = 0
str_dict = {}
ret = []
for str in strs:
sorted_str = ''.join(sorted(str))
if sorted_str not in str_dict:
ret.append([str])
str_dict[sorted_str] = index
index += 1
else:
ret[str_dict[sorted_str]].append(str)
return ret50 Pow(x, n)
class Solution:
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n==0:
return 1
if n==1:
return x
if n<0:
return 1/self.myPow(x,-n)
if n%2==0:
return self.myPow(x*x,n//2)
return x*self.myPow(x,n-1)53 Maximum Subarray
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
maxSum = curSum = nums[0]
for num in nums[1:]:
curSum = curSum + num if curSum >0 else num
maxSum = max(maxSum, curSum)
return maxSum54 Spiral Matrix
class Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
from collections import deque
ret = []
mdeque = [deque(x) for x in matrix]
while mdeque:
if mdeque:
ret.extend(mdeque.pop(0))
if mdeque and mdeque[0]:
for row in mdeque:
ret.append(row.pop())
if mdeque:
ret.extend(reversed(mdeque.pop()))
if mdeque and mdeque[0]:
for row in reversed(mdeque):
ret.append(row.popleft())
return ret55 Jump Game
class Solution:
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
last = 0
for i in range(len(nums)):
if i>last:
return False
last = max(last, i + nums[i])
if last>=len(nums)-1:
return True56 Merge Intervals
# Definition for an interval.
# class Interval:
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution:
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
if len(intervals) == 0:
return []
intervals.sort(key = lambda x: x.start)
ret = [intervals[0]]
for i,interval in enumerate(intervals[1:]):
if ret[-1].end>=interval.start:
ret[-1].end = max(ret[-1].end,interval.end)
else:
ret.append(interval)
return ret58 Length of Last Word
class Solution:
def lengthOfLastWord(self, s):
"""
:type s: str
:rtype: int
"""
return len(s.rstrip(' ').split(' ')[-1])66 Plus One
class Solution:
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
return [int(num) for num in str(int(''.join(map(str,digits))) + 1)]67 Add Binary
class Solution:
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
return bin(int(a,2)+int(b,2))[2:]69 Sqrt(x)
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x==0:
return 0
self.x = x
lenX = len(str(x))
left = 10**((lenX-1)//2)
right = 10**((lenX+1)//2)
return self.find(left, right)
def find(self, left, right):
if left==right:
return left
mid = (left + right)//2
midSquare = mid**2
if left==mid or self.x==midSquare:
return mid
if self.x<midSquare:
return self.find(left, mid)
if self.x>midSquare:
return self.find(mid, right)70 Climbing Stairs
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
a = b = 1
for i in range(n):
a, b = b, a+b
return a73 Set Matrix Zeroes
class Solution:
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
setx=set()
sety=set()
for row in matrix:
zero = False
for k,v in enumerate(row):
if v==0:
setx.add(k)
zero = True
if zero:
row[:]=[0]*len(row)
for row in matrix:
for k in setx:
row[k] = 078 Subsets
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.nums = nums
self.res = []
self.dfs(0,[])
return self.res
def dfs(self, index, path):
self.res.append(path)
for i in range(index,len(self.nums)):
self.dfs(i+1,path+[self.nums[i]])100 Same Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return p == q101 Symmetric Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.isMirror(root, root)
def isMirror(self, tree1, tree2):
if tree1 and tree2:
return tree1.val == tree2.val and self.isMirror(tree1.left, tree2.right) and self.isMirror(tree1.right, tree2.left)
elif tree1 or tree2:
return False
else:
return True104 Maximum Depth of Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1 if root else 0108 Convert Sorted Array to Binary Search Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
m = len(nums)//2
root = TreeNode(nums[m])
root.left = self.sortedArrayToBST(nums[0:m])
root.right = self.sortedArrayToBST(nums[m+1:])
return root118 Pascal’s Triangle
class Solution:
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
if not numRows:
return []
triangle = [[1]]
for i in range(1, numRows):
triangle.append([a+b for a,b in zip(triangle[-1]+[0], [0]+triangle[-1])])
return triangle119 Pascal’s Triangle II
class Solution:
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
row = [1]
for _ in range(rowIndex):
row = [x+y for x,y in zip(row+[0],[0]+row)]
return row121 Best Time to Buy and Sell Stock
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
min_price = prices[0] if prices else None
max_profit = 0
for price in prices:
min_price = min(min_price, price)
profit = price - min_price
max_profit = max(max_profit, profit)
return max_profit122 Best Time to Buy and Sell Stock II
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
days = len(prices)
if days <2:
return 0
max_profit = 0
for i in range(1, days):
profit = prices[i] - prices[i-1]
if profit > 0:
max_profit += profit
return max_profit125 Valid Palindrome
class Solution:
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
str = [x.lower() for x in filter(lambda ch: ch.isalnum(), s)]
return str==str[::-1]136 Single Number
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
from functools import reduce
return reduce(lambda x,y: x^y, nums)141 Linked List Cycle
# 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
"""
p1 = p2 = head
while p1 and p2 and p2.next:
p1 = p1.next
p2 = p2.next.next
if p1 == p2:
return True
return False155 Min Stack
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.stack.append(x)
self.min.append(x if not self.min else min(self.min[-1], x))
def pop(self):
"""
:rtype: void
"""
self.min.pop()
return self.stack.pop()
def top(self):
"""
:rtype: int
"""
return self.stack[-1]
def getMin(self):
"""
:rtype: int
"""
return self.min[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()160 Intersection of Two Linked Lists
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
node_set = set()
head1 = headA
head2 = headB
while True:
if head1:
if head1 in node_set:
return head1
node_set.add(head1)
head1 = head1.next
elif head2:
if head2 in node_set:
return head2
node_set.add(head2)
head2 = head2.next
else:
return None169 Majority Element
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return sorted(nums)[len(nums)//2]171 Excel Sheet Column Number
class Solution(object):
def titleToNumber(self, s):
"""
:type s: str
:rtype: int
"""
num = 0
ch0 = ord('A') - 1
for ch in s:
num = 26 * num + ord(ch) - ch0
return num172 Factorial Trailing Zeroes
class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
count = 0
while n:
n //= 5
count += n
return count189 Rotate Array
class Solution:
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
for i in range(k):
nums.insert(0, nums.pop())190 Reverse Bits
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
return int(bin(n)[2:].zfill(32)[::-1], 2)191 Number of 1 Bits
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
return len(filter(lambda x:x=='1', bin(n)[2:]))202 Happy Number
class Solution:
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
scanned = set()
while n not in scanned:
scanned.add(n)
left, n = n, 0
while left:
n += (left % 10)**2
left //= 10
return n==1226 Invert Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root == None:
return None
self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root