leetcode
标签（空格分隔）： 2020 编程
[TOC]
2. 两数相加 (中等）
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
L = ListNode(-1)
i = L
if not l1:return l2
if not l2:return l1
n = 0
while l1 and l2:
a = l1.val +l2.val + n
m = a%10
n = a//10
i.next = ListNode(m)
i = i.next
l1 = l1.next
l2 = l2.next
B = l1 if not l2 else l2
while B:
a = B.val + n
m = a%10
n = a//10
i.next = ListNode(m)
i = i.next
B = B.next
if n != 0:
i.next = ListNode(n)
return L.next
一个修正了的答案
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
L = ListNode(-1)
i = L
if not l1:return l2
if not l2:return l1
n = 0
while l1 or l2:
x = l1.val if l1 else 0
y = l2.val if l2 else 0
a = x + y + n
m = a%10
n = a//10
i.next = ListNode(m)
i = i.next
if l1:l1 = l1.next
if l2:l2 = l2.next
if n != 0:
i.next = ListNode(n)
return L.next
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
# 我的这个答案的结果很差，勉强能通过
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
dp = [1]*len(s)
for i in range(len(s)):
for j in range(i+1,len(s)):
if s[j] not in s[i:j]:
dp[i] += 1
else:
break
return max(dp)
看了一下答案，这个题目是可以学习滑动窗口的！
5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
1 | def longestPalindrome(self, s: str) -> str: |
6. Z 字形变换
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
def convert(self, s: str, numRows: int) -> str:
if not s or numRows<2:
return s
size = len(s)
Lines = [[] for _ in range(numRows)]
p = 0
d = 1
for i in s:
print(p)
Lines[p].append(i)
if p == numRows - 1:
d = -1
if p == 0:
d = 1
p += d
T = ""
for i in Lines:
T += "".join(i)
return T
7. 整数翻转
# 用字符串反转达成
# python3
class Solution:
def reverse(self, x: int) -> int:
f = True
if x < 0 :
f = False
y = str(abs(x))
y = list(y)
y = y[::-1]
z = 0
for i in y:
z = 10*z + int(i)
if z > pow(2,31)-1 or z < -pow(2,31):
return 0
else:
if not f:
z = -z
return z
8. 字符串转换整数 (atoi)
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ‘ ‘ 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
def myAtoi(self, str: str) -> int:
p = True
N = 0
str = str.strip()
if not str:
return 0
if str[0] == "+" or str[0] == "-" or ord(str[0]) >= 48 and ord(str[0]) <= 57:
if str[0] == "+":
p = True
str = str[1:]
elif str[0] == "-":
p = False
str = str[1:]
if not str:
return 0
i = 0
t = ord(str[0])
while t >= 48 and t <= 57:
N = N * 10 + (t - 48)
i += 1
if i < len(str):
t = ord(str[i])
else:
break
if not p:
N = -N
if N < -2147483648:
return -2147483648
if N > 2147483647:
return 2147483647
return N
else:
return 0
9. 回文数
# 字符串解法
# python3
class Solution:
def isPalindrome(self, x: int) -> bool:
y = str(x)
y = list(y)
l = len(y)
for i in range(l):
if y[i] != y[l-1-i]:
return False
return True
11. 盛最多水的容器
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
# 双指针法
class Solution:
def maxArea(self, height: List[int]) -> int:
l,r = 0,len(height)-1
Max = 0
while l < r:
if (r-l)*min(height[l],height[r]) > Max:
Max = (r-l)*min(height[l],height[r])
if height[l] < height[r]:
l += 1
else:
r -= 1
return Max
12. 整数转罗马数字
def intToRoman(self, num: int) -> str:
Roman_char = {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"}
L = ""
for i in Roman_char:
L += Roman_char[i]*(num // i)
num = num - (num // i)*i
return L
13. 罗马数字转整数
# 在编译器帮助下运行通过的
# python3
class Solution:
def romanToInt(self, s: str) -> int:
roman = {'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}
right = False
num = 0
if len(s) == 1:
num += roman[s]
else:
for i in range(len(s)-1):
if right:
right = False
continue
if roman[s[i]] < roman[s[i+1]]:
right = True
num += roman[s[i]+s[i+1]]
else:
num += roman[s[i]]
if not right:
num += roman[s[i+1]]
return num
14. 最长公共前缀
# python3
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
s = ''
l = len(strs)
if l==0:
return s
mi = min([len(i) for i in strs])
for i in range(mi):
a = strs[0][i]
b = True
for j in range(1,l):
if a != strs[j][i]:
b = False
break
if b:
s = s + a
else:
break
return s
1 | def longestCommonPrefix(self, strs: List[str]) -> str: |
1 | def longestCommonPrefix(self, strs: List[str]) -> str: |
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
def letterCombinations(self, digits: str) -> List[str]:
hash_table = {"2":["a","b","c"], "3":["d","e","f"], "4":["g","h","i"],
"5":["j","k","l"], "6":["m","n","o"],"7":["p","q","r","s"],
"8":["t","u","v"],"9":["w","x","y","z"]}
temp_list = []
last_list = []
for n in digits:
if not last_list:
last_list = hash_table[n]
continue
for key in hash_table[n]:
for i in range(len(last_list)):
temp_list.append(last_list[i]+key)
last_list = temp_list
temp_list = []
return last_list
def letterCombinations(self, digits: str) -> List[str]:
# 回溯法
hash_table = {"2":["a","b","c"], "3":["d","e","f"], "4":["g","h","i"],
"5":["j","k","l"], "6":["m","n","o"],"7":["p","q","r","s"],
"8":["t","u","v"],"9":["w","x","y","z"]}
L = []
length = len(digits)
print(length)
if length < 1:
return L
def helper(n,temp_s):
if n == length:
L.append(temp_s)
else:
c = digits[n]
chars = hash_table[c]
for item in chars:
helper(n+1,temp_s + item)
s = ""
helper(0,s)
return L
19. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
L = ListNode(-1)
L.next = head
p = head
i = 0
while p:
i += 1
p = p.next
print(i)
p = L
for _ in range(i-n):
p = p.next
print(p.val)
p.next = p.next.next
return L.next
20. 有效的括号
# python3
class Solution:
def isValid(self, s: str) -> bool:
bracket = {'(':1,')':2,'[':4,']':5,'{':7,'}':8}
stack = []
for i in s:
if stack:
if bracket[stack[-1]]+1 == bracket[i]:
stack.pop()
else:
stack.append(i)
else:
stack.append(i)
if stack:
return False
else:
return True
21. 合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
L = ListNode(-1)
p = L
while l1 and l2:
l3 = None
if l1.val > l2.val:
l3 = l2
l2 = l2.next
else:
l3 = l1
l1 = l1.next
p.next = l3
p = p.next
if 1:
p.next = l1
else:
p.next = l2
return L.next
23. 合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
L = ListNode(-1)
x = L
cur_min = None
while len(lists) > 1:
n = len(lists)
if lists[0] != None:
cur_min = lists[0]
else:
lists.pop(0)
continue
# print("cur_min: "+str(cur_min.val))
# 找到最小的值
t = 0
for i in range(n):
if lists[i] == None:
continue
if lists[i].val < cur_min.val:
cur_min = lists[i]
t = i
if lists[t].next != None:
lists[t] = lists[t].next
else:
lists.pop(t)
cur_min.next = None
x.next = cur_min
x = x.next
x.next = lists[0]
return L.next
25. K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head:
return head
res = ListNode(-1)
res.next = head
def revereKnode(k,L):
# 不足k个，直接返回
t = L # 用t来表示结尾
for _ in range(k):
if t.next == None:
return L.next, None
t= t.next
# 足够k个进行翻转
d = L.next # d表示正序列上的末尾节点
u = L.next
while u != t:
u = d.next
d.next = u.next
u.next = L.next
L.next = u
return L.next,d
R = res
E = res
while E:
R = E
R.next,E = revereKnode(k,R)
return res.next
26. 删除排序数组中的重复项
# python3
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if nums:
a = nums[0]
for i in nums[1:]:
if i == a:
nums.remove(i)
else:
a = i
return len(nums)
else:
return 0
28.实现strStr()
# python3
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle:
if needle not in haystack:
return -1
else:
return haystack.index(needle)
else:
return 0
# 这个题目水很深需要再多再看看KMP算法之流多翻一翻
31. 下一个排列
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)
if n == 0:
return None
for i in range(-1,-n,-1):
if nums[i-1] < nums[i]:
t = 0
j = -1
# 找到下一个值,把它与i-1位置的元素交换
while j > i-1:
if nums[j] > nums[i-1]:
nums[i-1],nums[j] = nums[j],nums[i-1]
break
j -= 1
# i-1 后面一定是逆序的
L = i
R = -1
while L<R:
nums[L], nums[R] = nums[R],nums[L]
L += 1
R -= 1
return None
nums.sort()
return None
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
def searchRange(self, nums: List[int], target: int) -> List[int]:
res = []
n = len(nums)
p = False
for i in range(n):
if not p and nums[i] == target:
res.append(i)
p = True
if p and (i+1 == n or nums[i+1] != target):
res.append(i)
p = False
if not res:
return [-1,-1]
return res
def searchRange(self, nums: List[int], target: int) -> List[int]:
res = []
n = len(nums)
for i in range(n):
if nums[i] == target:
res.append(i)
if not res:
return [-1,-1]
return [res[0],res[-1]]
def searchRange(self, nums, target):
for i in range(len(nums)):
if nums[i] == target:
left_idx = i
break
else:
return [-1, -1]
for j in range(len(nums)-1, -1, -1):
if nums[j] == target:
right_idx = j
break
return [left_idx, right_idx]
35. 搜索插入位置
# python3 自己写的
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if target not in nums:
for i in range(len(nums)):
if target <= nums[i]:
nums.insert(i,target)
return i
nums.append(target)
return len(nums)-1
else:
return nums.index(target)
36. 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
def isValidSudoku(self, board: List[List[str]]) -> bool:
# 三重判定
# 判定行
for L in board:
temp = []
for i in L:
if i != ".":
temp.append(i)
if len(temp) != len(set(temp)):
return False
print("行OK")
# 判定列
for j in range(9):
temp = []
for i in range(9):
if board[i][j] != ".":
temp.append(board[i][j])
if len(temp) != len(set(temp)):
return False
print("列OK")
# 判定方格
for x in range(0,9,3):
for y in range(0,9,3):
print((x,y))
temp = []
for i in range(3):
for j in range(3):
if board[x+i][y+j] != ".":
temp.append(board[x+i][y+j])
print(temp)
if len(temp) != len(set(temp)):
return False
return True
def isValidSudoku(self, board: List[List[str]]) -> bool:
# 只遍历一次的答案
Row = [{} for _ in range(9)]
Col = [{} for _ in range(9)]
Square = [{} for _ in range(9)]
for i in range(9):
for j in range(9):
if board[i][j] != ".":
if board[i][j] not in Row[i]:
Row[i][board[i][j]] = 1
else:
return False
if board[i][j] not in Col[j]:
Col[j][board[i][j]] = 1
else:
return False
local = (i//3)*3 + j //3
if board[i][j] not in Square[local]:
Square[local][board[i][j]] = 1
else:
return False
return True
38. 报数
# python3自己解决
class Solution:
def countAndSay(self, n: int) -> str:
s = "1"
for j in range(n-1):
a = s[0]
x = 1
re = ""
for i in s[1:]:
if i == a:
x = x + 1
else:
re = re + str(x) + str(a)
a = i
x = 1
s = re + str(x) + str(a)
return s
l3 = []
while l1 and l2:
if l1[0] >= l2[0]:
l3.append(l2.pop(0))
elif l1[0] < l2[0]:
l3.append(l1[0].pop(0))
return l3
39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
def help(candidates,target,temp_list):
print(temp_list)
if target >= candidates[0]:
i = 0
while i < len(candidates) and candidates[i] <= target:
if target == candidates[i]:
print("yeap!!")
temp = temp_list.copy()
temp.append(target)
print(temp)
res.append(temp)
temp = temp_list.copy()
temp.append(candidates[i])
help(candidates[i:],target-candidates[i],temp)
i += 1
res = []
temp = []
help(candidates,target,temp)
return res
43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0':
return "0"
n1 = len(num1)
n2 = len(num2)
digits = [0]*(n1+n2)
for i in range(n1-1, -1, -1):
for j in range(n2-1, -1, -1):
prod = (ord(num1[i])-ord('0'))*(ord(num2[j])-ord('0'))
sum_ = 0
sum_ = prod + digits[i+j+1]
digits[i+j] += sum_ //10
digits[i+j+1] = sum_ %10
# for i in range(n1 + n2 - 1, 0, -1):
# carry = digits[i] // 10
# digits[i] = digits[i] % 10
# digits[i - 1] += carry
return ''.join([str(i) for i in digits]).lstrip('0')
47. 全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
if not nums:
return res
nums.sort()
N = len(nums)
def helper(start,temp,unused):
if start == N:
print(str(start)+ " "+str(temp)+" "+str(unused))
res.append(temp[:])
i = 0
while i < len(unused):
if i > 0 and unused[i] == unused[i-1]:
i += 1
continue
temp.append(unused[i])
a = unused.pop(i)
helper(start+1,temp,unused)
temp.pop()
unused.insert(i,a)
i += 1
helper(0,[],nums)
return res
48. 旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
N = len(matrix) # 矩阵行列数
C = N //2 # 旋转层数
for t in range(C):
print(t)
for i in range(0,N-t*2-1):
a = matrix[t][t+i] # 左上角
matrix[t][t+i] = matrix[N-t-1-i][t] # 左下角
matrix[N-t-1-i][t] = matrix[N-t-1][N-t-1-i] # 右下角
matrix[N-t-1][N-t-1-i] = matrix[t+i][N-t-1] # 右上角
matrix[t+i][N-t-1] = a
# a = matrix[t+i,N-t-1] # 右上角
# matrix[t+i,N-t-1] = matrix[t][t+i] # 左上角
# b = matrix[N-t-1][N-t-1-i] # 右下角
# matrix[N-t-1][N-t-1-i] = a
# a = matrix[N-t-1-i][t] # 左下角
# matrix[N-t-1-i][t] = b
# matrix[t][t+i] = a
49. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs):
ans = collections.defaultdict(list)
for s in strs:
ans[tuple(sorted(s))].append(s)
return ans.values()
class Solution:
def groupAnagrams(self, strs):
ans = {}
for s in strs:
if tuple(sorted(s)) in ans:
ans[tuple(sorted(s))].append(s)
else:
ans[tuple(sorted(s))] = [s]
return list(ans.values())
53. 最大子序和 （在这个题中学暴力法，动态规划和分治法）
暴力法
# 这道题不会做。
# 答案中有四种解法：暴力法，动态规划，贪心法，分治法；
# 我都可以学！！！
# 2020年1月8日学会第一种暴力法！
# 这种暴力法超时了！！
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
Max = nums[0]
for i in range(len(nums)):
Sum = 0
for j in range(i,len(nums)):
Sum += nums[j]
if Sum > Max:
Max = Sum
return Max
# 一个更为先进的暴力法，好吧，说好一起暴力呢，你怎么动起了脑子
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
Sum = nums[0]
Max = nums[0]
for i in range(1,len(nums)):
if Sum + nums[i] > nums[i]:
Sum = Sum + nums[i]
else:
Sum = nums[i]
Max = max(Max,Sum)
return Max
# 20200109
动态规划
（动态规划代码在上面第二段）
通常我们遍历子串或者子序列有三种遍历方式
以某个节点为开头的所有子序列: 如 [a]，[a, b]，[ a, b, c] … 再从以 b 为开头的子序列开始遍历 [b] [b, c]。
- 根据子序列的长度为标杆，如先遍历出子序列长度为 1 的子序列，在遍历出长度为 2 的 等等。
以子序列的结束节点为基准，先遍历出以某个节点为结束的所有子序列，因为每个节点都可能会是子序列的结束节点，因此要遍历下整个序列，如: 以 b 为结束点的所有子序列: [a , b] [b] 以 c 为结束点的所有子序列: [a, b, c] [b, c] [ c ]。
而动态规划就是第三种方式，求出以某个节点结束节点的最大值。
分治法
# 分治法
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
#递归终止条件
if n == 1:
return nums[0]
else:
#递归计算左半边最大子序和
max_left = self.maxSubArray(nums[0:len(nums) // 2])
#递归计算右半边最大子序和
max_right = self.maxSubArray(nums[len(nums) // 2:len(nums)])
max_l = nums[len(nums)//2-1]
tmp = 0
for i in range(len(nums)//2-1,-1,-1):
tmp += nums[i]
max_l = max(max_l, tmp)
max_r = nums[len(nums)//2]
tmp = 0
for i in range(len(nums)//2,len(nums)):
tmp += nums[i]
max_r = max(max_r, tmp)
return max(max_left,max_right,max_l+max_r)
54. 螺旋矩阵
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
if not matrix:
return res
m = len(matrix)
n = len(matrix[0])
def next_item(i,j):
# 这里可以用另一个矩阵来表示这个是否被换过了。
# 返回一个值，如果没返回则结束
# 如果上下左右都不能走则返回None结束
if (i==0 or matrix[i-1][j] == "*") and (i == m-1 or matrix[i+1][j] == "*") and (j == 0 or matrix[i][j-1]== "*") and (j == n-1 or matrix[i][j+1]== "*"):
return None
if (i==0 or matrix[i-1][j] == "*") and (j == 0 or matrix[i][j-1]== "*") and not (j == n-1 or matrix[i][j+1]== "*"):
return (i,j+1)
if (i==0 or matrix[i-1][j] == "*") and (j == n-1 or matrix[i][j+1]== "*") and not (i == m-1 or matrix[i+1][j] == "*"):
return (i+1,j)
if (i == m-1 or matrix[i+1][j] == "*") and (j == n-1 or matrix[i][j+1]== "*") and not (j == 0 or matrix[i][j-1]== "*"):
return (i,j-1)
if (j == 0 or matrix[i][j-1]== "*") and (i == m-1 or matrix[i+1][j] == "*") and not (i==0 or matrix[i-1][j] == "*"):
return (i-1,j)
t = (0,0)
while t:
i,j = t
res.append(matrix[i][j])
matrix[i][j] = "*"
t = next_item(i,j)
return res
55. 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
def canJump(self, nums: List[int]) -> bool:
# dp
n = len(nums)
dp = [False]*n
for i in range(n-1,-1,-1):
if i == n-1:
dp[i] = True
continue
for j in range(i+1,min(i+nums[i]+1,n)):
if dp[j] == True:
dp[i] = True
break
print(dp)
return dp[0]
61. 旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head:
return head
temp = ListNode(-1)
temp.next = head
node_count = 0
point = temp
while point.next:
node_count+= 1
point = point.next
if k>node_count:
k = k%node_count
elif k == node_count:
return head
# 再走node_count - k 步
point = temp
for _ in range(node_count-k):
point = point.next
t = point
while t.next:
t = t.next
t.next = temp.next
temp.next = point.next
point.next = None
return temp.next
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
def uniquePaths(self, m: int, n: int) -> int:
N = m + n -2
c = min(m,n)-1
res = 1
for i in range(1,c+1):
res *= N
res = res//i
N = N-1
return res
63. 不同路径 II （动态规划，浅拷贝陷阱）
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
print(obstacleGrid)
m = len(obstacleGrid)
n = len(obstacleGrid[0])
print(m,n)
dp = [[0]*n for _ in range(m)] # 不要用下面这样的浅拷贝
# dp = [[0]*n]*m # 这样赋值会把整个列赋值成一样值
# 放第一行，第一列：
for i in range(m):
if obstacleGrid[i][0] == 1:
break
dp[i][0] = 1
for j in range(n):
if obstacleGrid[0][j] == 1:
break
dp[0][j] = 1
for i in range(1,m):
for j in range(1,n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
continue
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dp = [[0]*n for _ in range(m)]
for i in range(m):
if i == 0:
dp[0][0] = grid[0][0]
continue
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1,n):
dp[0][i] = dp[0][i-1] + grid[0][i]
for i in range(1,m):
for j in range(1,n):
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
print(dp)
return dp[-1][-1]
66. 加一
这个题的第一印象就是把数组转成数字，加一后再转成数组；
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
Sum = 0
for i in digits:
Sum = 10*Sum + i
Sum =Sum + 1
D_list = []
while Sum:
D_list.append(Sum%10)
Sum = Sum//10
D_list.reverse()
return D_list
这个结果速度还可以，但是内存消耗大
第二个想法就是在原数组上进行
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
Up = False # 进位符
# 给最低位加一
if digits[-1] + 1 > 9:
digits[-1] = (digits[-1] + 1)%10
Up = True
else:
digits[-1] = digits[-1] + 1
# 给整个数字进位：
for i in range(len(digits)-2,-1,-1):
if Up:
digits[i] = digits[i] + 1
if digits[i] > 9:
digits[i] = digits[i]%10
Up = True
else:
return digits
# 多进位
if Up:
digits.insert(0,1)
Up = False
return digits
67. 二进制求和
一个不用内置函数的解法
class Solution:
def addBinary(self, a: str, b: str) -> str:
Up = False
C = ""
if len(a)>len(b):
b = (len(a)-len(b))*"0" + b
else:
a = (len(b)-len(a))*"0" + a
for i in range(len(a)-1,-1,-1):
z = int(a[i])+int(b[i])
if Up:
z = z + 1
Up = False
C = str(z%2) + C
if z//2:
Up = True
if Up:
C = "1" + C
return C
题解里的一个答案：时间和空间都优于我写的
class Solution:
def addBinary(self, a: str, b: str) -> str:
r, p = '', 0
d = len(b) - len(a)
a = '0' * d + a
b = '0' * -d + b
for i, j in zip(a[::-1], b[::-1]):
s = int(i) + int(j) + p
r = str(s % 2) + r
p = s // 2
return '1' + r if p else r
用内置函数的解法
class Solution:
def addBinary(self, a: str, b: str) -> str:
return bin(int(a,2)+int(b,2))[2:]
69. x的平方根
我的答案：
class Solution:
def mySqrt(self, x: int) -> int:
start = 0
end = x
while start + 1 != end:
mid = (end-start)//2 + start
if mid mid == x:
return mid
elif mid mid > x:
if (mid-1)(mid-1) < x:
return mid-1
end = mid
elif mid mid < x:
if (mid+1)*(mid+1) > x:
return mid
start = mid
return end
71. 简化路径
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
def simplifyPath(self, path: str) -> str:
res = []
i = 0
while i<len(path):
if path[i] == "/":
i += 1
continue
j = i
while j < len(path) and path[j] != "/":
j += 1
if j-i == 2 and path[i:j] == "..":
if res:
res.pop()
elif j-i == 1 and path[i:j] == ".":
pass
else:
res.append(path[i:j])
i = j
res_S = "/"
if res:
res_S += "/".join(res)
return res_S
73. 矩阵置零
给定一个 m x n 的矩阵，如果一个元素为0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
res = []
m = len(matrix)
n = len(matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
res.append((i,j))
for i,j in res:
for t in range(n):
matrix[i][t] = 0
for t in range(m):
matrix[t][j] = 0
74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
m = len(matrix)
n = len(matrix[0])
for row in range(m):
if target >= matrix[row][0] and target <= matrix[row][-1]:
for col in range(n):
if matrix[row][col] == target:
return True
return False
return False
75. 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
l1 = 0
for i in range(n):
if nums[i] == 0:
nums.pop(i)
nums.insert(0,0)
l1 += 1
if nums[i] == 1:
nums.pop(i)
nums.insert(l1,1)
76. 最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
def minWindow(self, s: str, t: str) -> str:
t_table = defaultdict(int)
for i in t:
t_table[i] += 1
hash_table = defaultdict(list)
left , right = 0,len(s)
count = 0
flag = False
for i in range(len(s)):
if count <len(t) and s[i] in t:
if s[i] not in hash_table or len(hash_table[s[i]])<t_table[s[i]]:
count += 1
hash_table[s[i]].append(i)
else:
hash_table[s[i]].pop(0)
hash_table[s[i]].append(i)
if count == len(t):
flag = True
alp_left = min(hash_table, key = lambda k: hash_table[k][0])
alp_right = max(hash_table,key = lambda k: hash_table[k][-1])
if hash_table[alp_right][-1]-hash_table[alp_left][0] < right-left:
right, left = hash_table[alp_right][-1], hash_table[alp_left][0]
if len(hash_table[alp_left]) >1:
hash_table[alp_left].pop(0)
else:
hash_table.pop(alp_left)
count -= 1
if not flag:
return ""
return s[left:right+1]
77. 组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
def combine(self, n: int, k: int) -> List[List[int]]:
help_List = list(range(1,n+1))
def help(temp,help_List):
l = len(temp)
T = len(help_List)
if l == k:
res.append(temp)
else:
for i in range(T-k+1+l):
help(temp + [help_List[i]],help_List[i+1:])
res = []
help([],help_List)
return res
# 第二种解法很厉害的！！ 94%
def combine(self, n: int, k: int) -> List[List[int]]:
def help(temp):
l = len(temp)
T = n - temp[-1] if l != 0 else n
if l == k:
res.append(temp)
else:
for i in range(1,T-k+1+l+1):
if temp:
help(temp + [temp[-1]+i])
else:
help([i])
res = []
help([])
return res
78. 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
if not nums:
return [[]]
N = len(nums)
def help(temp,remain):
res.append(temp)
for i in range(len(remain)):
help(temp+[remain[i]],remain[i+1:])
help([],nums)
return res
79. 单词搜索 (这道题是有点东西的)
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
def exist(self, board: List[List[str]], word: str) -> bool:
m = len(board)
n = len(board[0])
# word = "SEE"
def dfs(visited,word):
l = len(visited)
if l == len(word):
return True
x,y = visited[-1]
dir_x = [-1,0,1,0]
dir_y = [0,-1,0,1]
for dx,dy in zip(dir_x,dir_y):
if x+dx>=0 and x+dx<m and y+dy>=0 and y+dy<n and (x+dx,y+dy) not in visited and board[x+dx][y+dy]==word[l] and dfs(visited+[(x+dx,y+dy)],word):
# 这里的大判断分别判断了以下几件事：
# 判断越界
# 判断是否被访问过
# 判断当下是否等于那个字母
# 判断它以后是否找得到
# 这些都满足了，把它返回True
return True
# 四个方向都不满足，就否定它
return False
# print("嘿嘿我进来了 "+str((i,j)))
# visited = [(i,j)]
# dir_x = [-1,0,1,0]
# dir_y = [0,-1,0,1]
# x,y = i,j
# for alp in range(1,len(word)):
# flag = False
# for dx,dy in zip(dir_x,dir_y):
# if x+dx>=0 and x+dx<m and y+dy>=0 and y+dy<n and(x+dx,y+dy) not in visited and board[x+dx][y+dy]==word[alp]:
# flag = True
# x,y = x+dx,y+dy
# print(x,y,word[alp])
# visited.append((x,y))
# if not flag:
# return False
# return True
for i in range(m):
for j in range(n):
if board[i][j] == word[0] and dfs([(i,j)],word):
return True
return False
81. 搜索旋转排序数组 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
def search(self, nums: List[int], target: int) -> bool:
if len(nums) <= 0:
return False
left = 0
right = len(nums) - 1
while left < right:
mid = (right - left) // 2 + left
if nums[mid] == target:
return True
if nums[left] == nums[mid]:
left += 1
continue
if nums[left] < nums[mid]:
if nums[left] <= target <= nums[mid]:
right = mid
else:
# 这里 +1，因为上面是 <= 符号
left = mid + 1
else:
# 注意：这里必须是 mid+1，因为根据我们的比较方式，mid属于左边的序列
if nums[mid+1] <= target <= nums[right]:
left = mid + 1
else:
right = mid
return True if nums[left] == target else False
82. 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现 的数字。
def deleteDuplicates(self, head: ListNode) -> ListNode:
Temp = ListNode(-1)
Temp.next = head
t = Temp
while t:
if t.next and t.next.next:
if t.next.val == t.next.next.val:
R = t.next.next
while R.next:
if R.next.val == R.val:
R = R.next
else:
break
t.next = R.next
else:
t = t.next
else:
t = t.next
return Temp.next
83. 删除排序链表中的重复元素
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
cur = head
if not cur:
return head
V = cur.val
while cur.next:
if cur.next.val != V:
V = cur.next.val
cur = cur.next
else:
cur.next = cur.next.next
return head
84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25def largestRectangleArea(self, heights: List[int]) -> int:
hash_table = {}
area = 0
for i in range(len(heights)):
delete = []
for item in hash_table:
if heights[i] < item:
if item * hash_table[item] > area:
area = item * hash_table[item]
delete.append(item)
else:
hash_table[item] += 1
if heights[i] not in hash_table:
m = 0
for item in delete:
if hash_table[item] > m:
m = hash_table[item]
hash_table[heights[i]] = m + 1
for item in delete:
hash_table.pop(item)
for item in hash_table:
if item * hash_table[item] > area:
area = item * hash_table[item]
return area
86. 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62def partition(self, head: ListNode, x: int) -> ListNode:
temp = ListNode(-1)
temp.next = head
t = temp
p1 = temp
pass_flag = False
while t and p1:
R = None
if t.next:
if pass_flag and t.next.val < x:
R = t.next
t.next = R.next
R.next = None
if t.next and t.next.val >= x:
pass_flag = True
t = t.next
if not pass_flag:
t = t.next
else:
break
while p1.next:
if p1.next.val < x:
p1 = p1.next
else:
if R:
R.next = p1.next
p1.next = R
p1 = p1.next
break
return temp.next
def partition(self, head: ListNode, x: int) -> ListNode:
temp = ListNode(-1)
temp.next = head
t = temp
p1 = temp
pass_flag = False
while p1.next:
if p1.next.val < x:
p1 = p1.next
else:
break
while t:
R = None
if t.next:
if pass_flag and t.next.val < x:
R = t.next
t.next = R.next
R.next = None
if t.next and t.next.val >= x:
pass_flag = True
t = t.next
if not pass_flag:
t = t.next
else:
break
if R:
R.next = p1.next
p1.next = R
p1 = p1.next
return temp.next
89. 格雷编码
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
格雷编码序列必须以 0 开头。
1 | def grayCode(self, n: int) -> List[int]: |
下面这是一个完全理解了格雷码产生方式的写法：
1 | def grayCode(self, n: int) -> List[int]: |
90. 子集 II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
1 | def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: |
92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
1 | def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: |
100. 相同的树
# 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: TreeNode, q: TreeNode) -> bool:
if p and q:
if p.val != q.val:
return False
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
elif not p and not q:
return True
else:
return False
101. 对称二叉树
# 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: TreeNode) -> bool:
if not root:
return True
if not root.left and not root.right:
return True
elif root.left and root.right:
return self.isSameTree(root.left,root.right)
else:
return False
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p and q:
if p.val != q.val:
return False
return self.isSameTree(p.left,q.right) and self.isSameTree(p.right,q.left)
elif not p and not q:
return True
else:
return False
104. 二叉树的最大深度
# 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: TreeNode) -> int:
if root:
MD = 1
return MD + max(self.maxDepth(root.left),self.maxDepth(root.right))
else:
return 0
105. 从前序与中序遍历序列构造二叉树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
head = TreeNode(preorder[0])
ind_inorder = inorder.index(preorder[0])
head.left = self.buildTree(preorder[1:1+ind_inorder],inorder[0:ind_inorder])
head.right = self.buildTree(preorder[1+ind_inorder:], inorder[ind_inorder+1:])
return head
107. 二叉树的层次遍历
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
A = []
B = []
if root.left:
B.append(root.left)
if root.right:
B.append(root.right)
nextL = [root.val]
while nextL:
A.insert(0,nextL)
nextL = []
nextNodes = []
while B:
c = B.pop(0)
nextL.append(c.val)
if c.left:
nextNodes.append(c.left)
if c.right:
nextNodes.append(c.right)
B = nextNodes
return A
108.将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
首先答案是不一致的，则需要将他做成符合一定规则的结果。
emmmm最后的答案还是非常简单的。首先应该抓住他是一个生成平衡树的题目。其他的要求都是细节。有的细节需要技巧得出。有的细节自然而然就可以得出来结果。
# 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: List[int]) -> TreeNode:
def helper(left, right):
if left > right:
return None
p = (left + right)//2
root = TreeNode(nums[p])
root.left = helper(left, p-1)
root.right = helper(p+1, right)
return root
return helper(0,len(nums)-1)
110.平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
首先它是一个判断题。针对每个节点都有可能进行对比。
# 这是一个暴力解法，从上到下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
def helper(root):
if not root:
return 0
return 1+ max(helper(root.left),helper(root.right))
if abs(helper(root.left)-helper(root.right)) > 1:
return False
else:
return self.isBalanced(root.left) and self.isBalanced(root.right)
这里是从底到顶的解法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def helper(root):
if not root:
return 0
left = helper(root.left)
if left == -1:
return -1
right = helper(root.right)
if right == -1:
return -1
return max(left,right)+1 if abs(left-right) < 2 else -1
return helper(root)!= -1
111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
mLeft = self.minDepth(root.left)
mRight = self.minDepth(root.right)
if mLeft > 0 and mRight > 0:
return 1 + min(mLeft,mRight)
elif mRight == 0:
return 1+ mLeft
elif mLeft == 0:
return 1+ mRight
112.路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
def helper(root,temp):
temp += root.val
if not root.left and not root.right: # 叶子节点
return temp == sum
elif root.left and not root.right: # 有左节点没有右节点
return helper(root.left, temp)
elif not root.left and root.right: # 有右节点没有左节点
return helper(root.right, temp)
else:
return helper(root.left, temp) or helper(root.right, temp)
if not root:
return False
return helper(root,0)
118.杨辉三角
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
L = []
for i in range(numRows):
temp = (i+1)*[1]
if i>1:
for j in range(i-1):
temp[j+1] = L[i-1][j] +L[i-1][j+1]
L.append(temp)
return L
# 优秀解法
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows == 0: return []
res = [[1]]
while len(res) < numRows:
newRow = [a+b for a, b in zip([0]+res[-1], res[-1]+[0])]
res.append(newRow)
return res
119.杨辉三角II
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
res = [1]
while len(res) <= rowIndex:
res = [a+b for a, b in zip([0]+res, res+[0])]
return re
121.买股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
暴力法：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
m = 0
for i in range(1,len(prices)):
a = min(prices[0:i])
if m < prices[i]-a:
m = prices[i]-a
return m
改进：x5i
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
minprice = prices[0]
maxprofit = 0
for i in range(1,len(prices)):
if minprice > prices[i]:
minprice = prices[i]
elif prices[i]-minprice > maxprofit:
maxprofit = prices[i]-minprice
return maxprofit
125.验证回文串
class Solution:
def isPalindrome(self, s: str) -> bool:
if not s:
return True
# 1.字符串格式转换
s = s.lower()
t = ""
for i in s:
if (i>="0" and i<="9") or (i>="a" and i<="z"):
t = t+i
# 2.对字符串进行翻转
S = t[::-1]
return S == t
# 3.判断两字符串是否相等
136.只出现一次的数字
哈希表是最快的！！！
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 暴力一点，
only = 0
l = len(nums)
for i in range(0,l):
only = nums[i]
if only not in nums[0:i] and only not in nums[i+1:l]:
return only
class Solution(object):
def singleNumber(self, nums):
# 列表操作
tale = []
for i in nums:
if i not in tale:
tale.append(i)
else:
tale.remove(i)
return tale[0]
class Solution(object):
def singleNumber(self, nums):
# 哈希操作
hash_table = {}
for i in nums:
try:
hash_table.pop(i)
except:
hash_table[i] = 1
return hash_table.popitem()[0]
class Solution(object):
def singleNumber(self, nums):
# 位操作
“””
:type nums: List[int]
:rtype: int
“””
a = 0
for i in nums:
a ^= i
return a
141.环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
# 列表法
hash_table = []
t = head
while t:
if t in hash_table:
return True
else:
hash_table.append(t)
t = t.next
return False
class Solution:
def hasCycle(self, head: ListNode) -> bool:
# 哈希法
hash_table = {}
t = head
while t:
try:
hash_table.pop(t)
return True
except:
hash_table[t] = 1
t = t.next
return False
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if head == None or head.next == None:
return False
# 双指针法
fast = head.next
slow = head
while slow != fast:
if fast ==None or fast.next == None:
return False
slow = slow.next
fast = fast.next.next
return True
151.翻转字符串里的单词
class Solution:
def reverseWords(self, s: str) -> str:
if not s:
return s
s = s.strip()
L = []
P = False
j = 0
for i in range(len(s)):
if s[i]!=" ":
if not P:
j = i
P = True
else:
if P:
P = False
L.append(s[j:i])
L.append(s[j:])
return " ".join(L[::-1])
152. 乘积最大子数组
给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
def maxProduct(self, nums: List[int]) -> int:
hash_table = {}
hash_table[-1] = 1
posi = [-1]
nega = []
Max = nums[0]
for i in range(len(nums)):
t = nums[i] * hash_table[i-1]
if t > 0:
if Max < t/hash_table[posi[0]]:
Max = t//hash_table[posi[0]]
hash_table[i] = t
elif t < 0:
if nega:
if Max < t/hash_table[nega[0]]:
Max = t//hash_table[nega[0]]
else:
nega.append(i)
hash_table[i] = t
else:
posi = [i]
nega = []
hash_table[i] = 1
if Max < 0:
Max = 0
return Max
153. 寻找旋转排序数组中的最小值(二分查找)
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
def findMin(self, nums: List[int]) -> int:
# nums = [4,5,6,7,0,1,2]
# 二分查找走一波
left = 0
right = len(nums)-1
while left < right:
mid = left + (right-left)//2
print(left,mid,right)
if nums[mid] < nums[mid-1]:
return nums[mid]
if nums[left] <= nums[right]:
return nums[left]
if nums[mid] >= nums[left]:
left = mid+1
else:
right = mid
return nums[left]
160.相交链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# 第一个想法，简单法：弄两个列表然后得到答案
if not headA or not headB:
return None
listA = []
listB = []
A = headA
B = headB
while A:
listA.append(A)
A = A.next
while B :
listB.append(B)
B = B.next
if listA[-1] != listB[-1]:
return None
t = listA[-1]
for i in range(1,min(len(listB),len(listA))+1):
if listA[-i] != listB[-i]:
return t
else:
t = listA[-i]
return t
162. 寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
def findPeakElement(self, nums: List[int]) -> int:
left = 0
right = len(nums) -1
while left < right:
mid = left + (right - left)//2
if nums[mid] > nums[mid+1]:
right = mid
else:
left = mid + 1
return left
167.相交链表
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
m=0;n = 0
for i in range(len(numbers)):
T = target-numbers[i]
if T in numbers[i+1:]:
m = i+1
n = numbers[m:].index(T)+m+1
break
return [m,n]
168. Excel表列名称
class Solution:
def convertToTitle(self, n: int) -> str:
L = ""
while n != 0:
j = n % 26
if j == 0:
j = 26
n -= 1
L = chr(ord("A") + j -1) + L
n = n//26
return L
169. 多数元素
class Solution:
def majorityElement(self, nums: List[int]) -> int:
hashtable = {}
for i in nums:
if i in hashtable:
hashtable[i] += 1
else:
hashtable[i] = 1
M = 0
N = 0
for i in list(hashtable):
if hashtable[i]>M:
N = i
M = hashtable[i]
return N
171. Excel表列序号
class Solution:
def titleToNumber(self, s: str) -> int:
N = 0
for i in s:
w = ord(i)-ord("A")+1
N = N*26 +w
return N
172. 阶乘后的零
class Solution:
def trailingZeroes(self, n: int) -> int:
count = 0
while n >= 5:
n = n//5
count += n
return count
189. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
190. 颠倒二进制位
颠倒给定的 32 位无符号整数的二进制位。
示例 1：
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
class Solution:
def reverseBits(self, n: int) -> int:
a = bin(n)[2:]
if len(a) < 32:
a = "0"*(32-len(a))+a
return int(a[::-1],2)
191. 位1的个数
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
class Solution:
def hammingWeight(self, n: int) -> int:
return bin(n)[2:].count("1")
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
我开始想把奇数与偶数分开算，但发现了例外测试。就是第一个和第四个加起来是最大的。所以我采用了动态规划的方法。
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) <2:
return nums[0]
table = [0]*len(nums)
table[0] = nums[0]
table[1] = nums[1]
for i in range(2,len(nums)):
table[i] = nums[i] + max(table[0:i-1])
return max(table)
我要看看答案里有没有更好的结果。
200. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
R = len(grid)
C = len(grid[0])
def modify_grid(i,j):
x = [-1,1,0,0]
y = [0,0,-1,1]
if i >= 0 and i < R and j >= 0 and j < C:
if grid[i][j] == "1":
grid[i][j] = "0"
for p,q in zip(x,y):
modify_grid(i+p,j+q)
I_num = 0
for i in range(R):
for j in range(C):
# print(i)
# print(j)
if grid[i][j] == "1":
I_num += 1
modify_grid(i,j)
return I_num
202. 快乐数
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
class Solution:
def isHappy(self, n: int) -> bool:
while True:
n = sum([int(i)**2 for i in str(n)])
if n == 4:
return False
if n == 1:
return True
203. 移除链表元素
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
L = ListNode(-1)
L.next = head
head = L
while L.next:
if L.next.val == val:
L.next = L.next.next
else:
L = L.next
return head.next
204. 计数质数
关于质数的计算还是很有讲究的。
class Solution:
def countPrimes(self, n: int) -> int:
if n < 3:
return 0
results = [1]*n
results[0],results[1] = 0, 1
for i in range(2,int(n**0.5)+1):
if results[i] == 1:
results[i*2:n:i] = [0]*len(results[i*2:n:i])
return sum(results)-1
205. 同构字符串
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
示例 1:
输入: s = “egg”, t = “add”
输出: true
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
hashtable1 = {}
hashtable2 = {}
x = 0
for i in s:
if i not in hashtable1:
hashtable1[i] = x
x = x + 1
x = 0
for i in t:
if i not in hashtable2:
hashtable2[i] = x
x = x + 1
for i,j in zip(s,t):
if hashtable1[i] != hashtable2[j]:
return False
return True
206. 反转链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur:
n = cur.next
cur.next = pre
pre = cur
cur = n
return pre
210. 课程表 II
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
# 广度优先和深度优先方法的解法
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# 存储有向图
edges = collections.defaultdict(list)
# 存储每个节点的入度
indeg = [0] * numCourses
# 存储答案
result = list()
for info in prerequisites:
edges[info[1]].append(info[0])
indeg[info[0]] += 1
q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])
while q:
# 从队首取出一个节点
u = q.popleft()
# 放入答案中
result.append(u)
for v in edges[u]:
indeg[v] -= 1
# 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
if indeg[v] == 0:
q.append(v)
if len(result) != numCourses:
result = list()
return result
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# 存储有向图
edges = collections.defaultdict(list)
# 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
visited = [0] * numCourses
# 用数组来模拟栈，下标 0 为栈底，n-1 为栈顶
result = list()
# 判断有向图中是否有环
invalid = False
for info in prerequisites:
edges[info[1]].append(info[0])
def dfs(u: int):
nonlocal invalid
# 将节点标记为「搜索中」
visited[u] = 1
# 搜索其相邻节点
# 只要发现有环，立刻停止搜索
for v in edges[u]:
if visited[v] == 0:
dfs(v)
if invalid:
return
# 如果「搜索中」说明找到了环
elif visited[v] == 1:
invalid = True
return
# 将节点标记为「已完成」
visited[u] = 2
# 将节点入栈
result.append(u)
# 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
for i in range(numCourses):
if not invalid and not visited[i]:
dfs(i)
if invalid:
return list()
# 如果没有环，那么就有拓扑排序
# 注意下标 0 为栈底，因此需要将数组反序输出
return result[::-1]
217. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
hashtable = {}
for i in nums:
if i in hashtable:
return True
else:
hashtable[i] = 1
return False
219. 存在重复元素 II
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
n = len(nums)
table = n * [0]
hashtable = {}
for i in range(n):
if nums[i] not in hashtable:
hashtable[nums[i]] = i
table[i] = 0
else:
table[i] = i - hashtable[nums[i]]
hashtable[nums[i]] = i
print(table)
for i in table:
if i>0 and i<=k:
return True
return False
221. 最大正方形
在一个由 0 和 1 组成的二维矩阵内，找到只包含1的最大正方形，并返回其面积。
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
if not matrix[0]:
return 0
Row = len(matrix)
Col = len(matrix[0])
Max = 0
for i in range(Row):
for j in range(Col):
if matrix[i][j] == "1":
print(i,j)
temp = self.getArea(matrix,Row,Col,i,j)
print(temp)
if temp > Max:
Max = temp
return Max
# 判定以该节点为左上角所能得到的最大正方形面积
def getArea(self, matrix,Row, Col, i, j):
x,y = i,j
t = 1
R = t
flag = True
while x+t < Row and y+t < Col:
t += 1
for p in range(t):
if matrix[x+p][y+t-1] == "0":
flag = False
break
if not flag:
break
for q in range(t-1):
if matrix[x+t-1][y+q]== "0":
flag = False
break
if not flag:
break
R = t
return R*R
225. 用队列实现栈
使用队列实现栈的下列操作：
push(x) — 元素 x 入栈
pop() — 移除栈顶元素
top() — 获取栈顶元素
empty() — 返回栈是否为空
注意:
你只能使用队列的基本操作— 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）
226. 翻转二叉树
翻转一棵二叉树。
# 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: TreeNode) -> TreeNode:
if not root:
return root
a = self.invertTree(root.right)
root.right = self.invertTree(root.left)
root.left = a
return root
231. 2的幂
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
i = 0
while i == 0 and n >= 2:
i = n%2
n = n//2
if i == 0 and n > 0:
return True
else:
return False
234. 回文链表（解答明天看一下）
请判断一个链表是否为回文链表。
我的简单解法
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
L = []
t = head
while t:
L.append(t.val)
t = t.next
return True if L == L[::-1] else False
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return None
b = p if p.val >= q.val else q
s = p if p.val < q.val else q
if root.val > b.val:
return self.lowestCommonAncestor(root.left,p,q)
elif root.val >=s.val:
return root
else:
return self.lowestCommonAncestor(root.right,p,q)
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 两个节点在路径中的最后一个相同的节点
L1 = self.search(root,p)
L2 = self.search(root,q)
i,j = 0,0
while i<len(L1) and i <len(L2):
if L1[i] == L2[i]:
i += 1
else:
break
return L1[i-1]
def search(self, root, p):
# p在root中的路径
if not root:
return []
if root == p:
return [root]
left = self.search(root.left,p)
right = self.search(root.right,p)
if not left and not right:
return []
if not right:
return [root] + left
if not left:
return [root] + right
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root == p or root == q: return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if not left: return right
if not right: return left
return root
238. 除自身以外数组的乘积
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
1 | class Solution: |
一个我写的更好的答案1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
pre_Sum = 1
rear_Sum = 1
n = len(nums)
help_table = [[0,0] for _ in range(n)]
for i in range(n):
help_table[i][0] = pre_Sum
help_table[n-i-1][1] = rear_Sum
pre_Sum *= nums[i]
rear_Sum *= nums[n-i-1]
res = []
for i in range(n):
res.append(help_table[i][0]*help_table[i][1])
return res
1 | class Solution: |
1 | class Solution { |
242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
hash_table1 = {}
hash_table2 = {}
for i in s:
if i in hash_table1:
hash_table1[i] += 1
else:
hash_table1[i] = 1
for j in t:
if j in hash_table2:
hash_table2[j] += 1
else:
hash_table2[j] = 1
if len(hash_table2) != len(hash_table1):
return False
else:
for i in hash_table1:
if i not in hash_table2:
return False
elif hash_table2[i] != hash_table1[i]:
return False
return True
257. 二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
258. 各位相加
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
class Solution:
def addDigits(self, num: int) -> int:
x = 0
while num != 0:
x += num % 10
num =num // 10
return self.addDigits(x) if x >= 10 else x
263. 丑数
编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
class Solution:
def isUgly(self, num: int) -> bool:
if num == 0:
return False
if num == 1:
return True
while True:
if num % 2 == 0:
num = num /2
else: break
while True:
if num % 3 == 0:
num = num /3
else: break
while True:
if num % 5 == 0:
num = num /5
else: break
return True if num == 1 else False
268. 缺失数字
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
class Solution:
def missingNumber(self, nums: List[int]) -> int:
M = len(nums) + 1
for i in range(M+1):
if i not in nums:
return i
return M+1
278. 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
二分排序
"""
i = 1
j = n
while i<j:
x = (i+j)//2
if isBadVersion(x):
j = x
else:
i = x+1
return i
290. 单词规律
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
class Solution:
def wordPattern(self, pattern: str, str: str) -> bool:
a = str.strip().split()
b = list(pattern)
hash_tabel = {}
if len(a) != len(b):
return False
for i,j in zip(a,b):
if j in hash_tabel:
if hash_tabel[j] != i:
return False
else:
hash_tabel[j] = i
# 判断不同key值不同
S = []
for i in hash_tabel:
if hash_tabel[i] not in S:
S.append(hash_tabel[i])
else:
return False
return True
292. Nim 游戏
你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
class Solution:
def canWinNim(self, n: int) -> bool:
if n%4==0:
return False
else:
return True
300.最长上升子序列
动态规划
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
我第一时间想到的也是动态规划，可是没有抓住重点就没写出来。还好。这个代码也是一看就懂的。动态规划的基本要素，一个表来记录已有的最好记录。一步一步推到想要的那一步。表是用来记录最好的结果的。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
dp = len(nums)*[1]
for i in range(len(nums)):
t = dp[i]
for j in range(0,i):
if nums[j] < nums[i]:
if dp[i] < dp[j] + t:
dp[i] = dp[j] + t
return max(dp)
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
# 递归解法
def decodeString(self, s: str) -> str:
res = ""
i = 0
while i < len(s) :
if ord(s[i]) >= ord("0") and ord(s[i]) <= ord("9"):
k = int(s[i])
i += 1
while ord(s[i]) >= ord("0") and ord(s[i]) <= ord("9"):
k = k*10 + int(s[i])
i += 1
j = i+1
stack = ["["]
while j<len(s) and len(stack)>0:
if s[j] == "[":
stack.append("[")
elif s[j] == "]":
stack.pop()
j += 1
temp = self.decodeString(s[i+1:j-1])
res += k*temp
i = j
else:
res += s[i]
i += 1
return res
# 栈解法
def decodeString(self, s: str) -> str:
res = ""
i = 0
stack = []
while i < len(s) :
if ord(s[i]) >= ord("0") and ord(s[i]) <= ord("9"):
k = int(s[i])
i += 1
while ord(s[i]) >= ord("0") and ord(s[i]) <= ord("9"):
k = k*10 + int(s[i])
i += 1
stack.append(k)
elif s[i] == "]":
temp = ""
t = stack.pop()
while t != "[":
temp = t + temp
t = stack.pop()
k = stack.pop()
stack.append(k*temp)
i += 1
else:
stack.append(s[i])
i += 1
return "".join(stack)
466. 统计重复个数
由 n 个连接的字符串 s 组成字符串 S，记作 S = [s,n]。例如，[“abc”,3]=“abcabcabc”。
如果我们可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。例如，根据定义，”abc” 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。
现在给你两个非空字符串 s1 和 s2（每个最多 100 个字符长）和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。
请你找出一个可以满足使[S2,M] 从 S1 获得的最大整数 M 。
def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
if n1 == 0:
return 0
s1cnt, index, s2cnt = 0, 0, 0
# recall 是我们用来找循环节的变量，它是一个哈希映射
# 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符
# 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了
# 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果
# 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组
# 循环节就是；
# - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
# - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
# 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配
# 注意 s2 要从第 index 个字符开始匹配
recall = dict()
while True:
# 我们多遍历一个 s1，看看能不能找到循环节
s1cnt += 1
for ch in s1:
if ch == s2[index]:
index += 1
if index == len(s2):
s2cnt, index = s2cnt + 1, 0
# 还没有找到循环节，所有的 s1 就用完了
if s1cnt == n1:
return s2cnt // n2
# 出现了之前的 index，表示找到了循环节
if index in recall:
s1cnt_prime, s2cnt_prime = recall[index]
# 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
pre_loop = (s1cnt_prime, s2cnt_prime)
# 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)
break
else:
recall[index] = (s1cnt, s2cnt)
# ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop
ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]
# S1 的末尾还剩下一些 s1，我们暴力进行匹配
rest = (n1 - pre_loop[0]) % in_loop[0]
for i in range(rest):
for ch in s1:
if ch == s2[index]:
index += 1
if index == len(s2):
ans, index = ans + 1, 0
# S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2
return ans // n2
560. 和为K的子数组 (##)
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
# 数组还可能有小于0的情况
res = 0
s = 0
n = len(nums)
hash_table = {}
hash_table[s] = 1
for i in range(n):
pre += nums[i]
if pre-k in hash_table:
res += hash_table[s-k]
if pre in hash_table:
hash_table[pre] += 1
else:
hash_table[pre] = 1
return res
695.岛屿的最大面积
用深度优先遍历：
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m = len(grid)
if m == 0: return 0
n = len(grid[0])
ans = 0
def dfs(i,j):
if i<0 or i>=m or j<0 or j>=n: return 0
if grid[i][j] == 0: return 0
grid[i][j] = 0
top = dfs(i+1, j)
bottom = dfs(i-1,j)
left = dfs(i,j-1)
right = dfs(i,j+1)
return 1 + sum([top,bottom,left,right])
for i in range(m):
for j in range(n):
ans = max(ans,dfs(i,j))
return ans
739. 每日温度
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
1 | def dailyTemperatures(self, T: List[int]) -> List[int]: |
837. 新21点 (回溯法超时了，经提示还是用动态规划）
1 | def new21Game(self, N: int, K: int, W: int) -> float: |
动态规划1
2
3
4
5
6
7
8
9
10def new21Game(self, N: int, K: int, W: int) -> float:
dp = [0]*(K+W)
if K+W-1 <= N:
return 1
for i in range(K,N+1):
dp[i] = 1
for i in range(K-1,-1,-1):
for j in range(i+1,i+1+W):
dp[i] += dp[j]/W
return dp[0]1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public double new21Game(int N, int K, int W) {
double[] dp = new double[N+1];
for (int i = K; i<N+1;i++)
dp[i] = 1.0;
for (int i = K-1;i>-1;i--){
for (int j = i+1; j<N+1 && j<i+1+W;j++){
dp[i] += dp[j]/W;
}
}
return dp[0];
}
}1
2
3
4
5
6
7
8
9
10
11
12class Solution:
# 最终通过的答案！！把相加的步骤优化一下
def new21Game(self, N: int, K: int, W: int) -> float:
dp=[None]*(K+W)
s=0
for i in range(K,K+W): # 填蓝色的格子
dp[i] = 1 if i<=N else 0
s+=dp[i]
for i in range(K-1,-1,-1): # 填橘黄色格子
dp[i]=s/W
s=s-dp[i+W]+dp[i]
return dp[0]
876. 链表的中间结点
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
L = head
N = 0
while L:
N += 1
L = L.next
L = head
for _ in range(N//2):
L = L.next
return L
887. 鸡蛋掉落
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
memo = {}
def dp(k, n):
if (k, n) not in memo:
if n == 0:
ans = 0
elif k == 1:
ans = n
else:
lo, hi = 1, n
# keep a gap of 2 X values to manually check later
while lo + 1 < hi:
x = (lo + hi) // 2
t1 = dp(k-1, x-1)
t2 = dp(k, n-x)
if t1 < t2:
lo = x
elif t1 > t2:
hi = x
else:
lo = hi = x
ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x))
for x in (lo, hi))
memo[k, n] = ans
return memo[k, n]
return dp(K, N)
914. 卡牌分组
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
每组都有 X 张牌。
组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
hashtable = {}
for i in deck:
if i in hashtable:
hashtable[i] += 1
else:
hashtable[i] = 1
a = set(hashtable.values())
if len(a) == 1:
return True if list(a)[0]>1 else False
else:
b = min(a)
for j in range(b,1,-1):
print(j)
p = False
for i in a:
if i%j != 0:
p = True
break
if p:
continue
return True
return False
974. 和可被 K 整除的子数组
给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
def subarraysDivByK(self, A: List[int], K: int) -> int:
hash_table = defaultdict(list)
hash_table[0] = [-1]
count = 0
S = 0
for i in range(len(A)):
S += A[i]
count += len(hash_table[S%K])
hash_table[S%K].append(i)
return count
990. 等式方程的可满足性 (并查集)
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
1 | def equationsPossible(self, equations: List[str]) -> bool: |
1 | from collections import defaultdict |
999. 车的可用捕获量
在一个 8 x 8 的棋盘上，有一个白色车（rook）。也可能有空方块，白色的象（bishop）和黑色的卒（pawn）。它们分别以字符 “R”，“.”，“B” 和 “p” 给出。大写字符表示白棋，小写字符表示黑棋。
车按国际象棋中的规则移动：它选择四个基本方向中的一个（北，东，西和南），然后朝那个方向移动，直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外，车不能与其他友方（白色）象进入同一个方格。
返回车能够在一次移动中捕获到的卒的数量。
class Solution:
def numRookCaptures(self, board: List[List[str]]) -> int:
[(x,y)] = [(i,j) for i in range(8) for j in range(8) if board[i][j]=="R"]
N = 0
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
for i,j in zip(dx,dy):
d = 1
while True:
if x + i*d <0 or x + i*d >=8 or y + j*d < 0 or y + j*d >= 8:
break
if board[x + i*d][y + j*d] == "B":
break
elif board[x + i*d][y + j*d] == "p":
N += 1
break
d += 1
return N
1014. 最佳观光组合
给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。
1 | # 超时答案 |
1 | def maxScoreSightseeingPair(self, A: List[int]) -> int: |
1028. 从先序遍历还原二叉树
我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
如果节点只有一个子节点，那么保证该子节点为左子节点。
给出遍历输出 S，还原树并返回其根节点 root。
1 | # Definition for a binary tree node. |
1095. 山脉数组中查找目标值
（这是一个 交互式问题 ）
给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
如果不存在这样的下标 index，就请返回 -1。
何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：
首先，A.length >= 3
其次，在 0 < i < A.length - 1 条件下，存在 i 使得：
A[0] < A[1] < … A[i-1] < A[i]
A[i] > A[i+1] > … > A[A.length - 1]
你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：
MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）
MountainArray.length() - 会返回该数组的长度
# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
# def get(self, index: int) -> int:
# def length(self) -> int:
class Solution:
def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
length = mountain_arr.length()
left = 0
right = length -1
return self.helper(target,mountain_arr,left,right)
def helper(self, target,mountain_arr, left, right):
if left >= right:
if mountain_arr.get(left) == target:
# 这里可以做一个实验，删掉这个判断和有这个有什么区别
return left
return -1
mid = left + (right - left)//2
x = mountain_arr.get(index = mid)
print(“left: “ + str(left) + “ mid: “ + str(mid) + “ right: “ + str(right))
print(“x: “ +str(x))
if x > target:
# 先找前面，如果有就return，没有就再找后面
# 也可以判断坡
t = self.helper(target,mountain_arr, left, mid)
return t if t != -1 else self.helper(target,mountain_arr, mid+1, right)
else:
# 中间值小于目标值先判断在前坡还是后坡
if mid == 0 or x > mountain_arr.get(mid-1):
# 如果在前坡，就舍弃0~mid,查找mid+1到后面
# 在前坡与目标值相等，直接返回
if x == target:
return mid
return self.helper(target,mountain_arr, mid+1, right)
else:
# 如果在后坡，就舍弃mid:,查找前面
t = self.helper(target,mountain_arr, left, mid)
if t != -1:
return t
else:
if x == target:
return mid
return self.helper(target,mountain_arr, mid+1, right)
面试题 17.16. 按摩师
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
class Solution:
def massage(self, nums: List[int]) -> int:
if not nums:
return 0
curMax = 0
preMax = 0
for x in nums:
temp = curMax
curMax = max(preMax+x, curMax)
preMax = temp
return curMax
面试题40. 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
1 | # 我的方法就比较暴力，在原来的数组中把最大的几个给删了，剩下k个最小的留下 |
面试题46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
1 | # 回溯法 |
面试题51. 数组中的逆序对(用分治法和归并排序的经典使用模式）
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
class Solution:
def reversePairs(self, nums: List[int]) -> int:
L = len(nums)
if L < 2:
return 0
def reversePairs(nums, left, right):
if left == right:
return 0
mid = left + (right - left)//2
leftpairs = reversePairs(nums, left, mid)
rightpairs = reversePairs(nums, mid+1, right)
crosspairs = self.crosspairs(nums, left, mid, right)
return leftpairs + rightpairs + crosspairs
return reversePairs(nums, 0, L-1)
def crosspairs(self, nums, left, mid, right):
temp = nums[left:right+1]
m = mid - left
r = right - left
i,j = 0, m+1
count = 0
for k in range(left, right+1):
if i == m+1:
nums[k] = temp[j]
j += 1
elif j == r + 1:
nums[k] = temp[i]
i += 1
elif temp[i] <= temp[j]:
nums[k] = temp[i]
i += 1
else:
nums[k] = temp[j]
j += 1
count += m - i + 1
return count
面试题62. 圆圈中最后剩下的数字
[TOC]