1.两数之和(easy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
c=[]
for i in range(len(nums)-1):
for j in range(i+1,len(nums)):
if nums[i]+nums[j]==target:
c.append(i)
c.append(j)
return c2.两数相加(medium)
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# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
c1=[]
c2=[]
while l1:
c1.append(l1.val)
l1=l1.next
while l2:
c2.append(l2.val)
l2=l2.next
j1=-1
j2=-1
sum1=0
sum2=0
for i in range(len(c1)):
sum1=sum1*10+c1[j1]
j1=j1-1
for i in range(len(c2)):
sum2=sum2*10+c2[j2]
j2=j2-1
res=sum1+sum2
p=head=node=ListNode(None)
l=len(str(res))
while l:
node=ListNode(res%10)
p.next=node
p=node
res/=10
l-=1
return head.next3.无重复字符的最长子串(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if len(s)==0:
return 0
maxl=0
i=0
for j in range(len(s)):
if s[j] in s[i:j]:
i = s[i:j].find(s[j])+i+1
if j-i+1>maxl:
maxl=j-i+1
return maxl4.寻找两个正序数组的中位数(hard)
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
for i in nums2:
nums1.append(i)
nums1 = sorted(nums1)
if len(nums1)%2 !=0:
return nums1[len(nums1)/2]
else:
return (nums1[len(nums1)/2]+nums1[len(nums1)/2-1])/2.011.盛最多水的容器(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
i=0
j=len(height)-1
res=0
while i<j:
h=min(height[i],height[j])
res=max(res,h*(j-i))
if height[i]>height[j]:
j-=1
else:
i+=1
return res15.三数之和(medium)
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
62
63
64class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
#第一种方法，可行但超时
# if len(nums)==0 or len(nums)==1 or len(nums)==2:
# return []
# sum_two=[]
# d={}
# res=[]
# count=0
# for i in range(len(nums)-1):
# for j in range(i+1,len(nums)):
# d[count]=[i,j]
# sum_two.append(nums[i]+nums[j])
# count+=1
# # print(d)
# # print(sum_two)
# for i in range(len(nums)):
# for j in range(len(sum_two)):
# if i not in d[j] and nums[i]+sum_two[j]==0:
# temp = [nums[d[j][0]]] + [nums[i]] + [nums[d[j][1]]]
# temp.sort()
# if temp not in res:
# res.append(temp)
# # res = list(set([tuple(t) for t in res]))
# # res = list([list(l) for l in res])
# return res
#第二种方法，还是超时....
# d = {}
# res = []
# count=0
# for i in range(len(nums)-1):
# for j in range(i+1,len(nums)):
# d[count] = [i,j]
# count+=1
# for k in range(len(nums)):
# for v in d.values():
# if k not in v and nums[v[0]]+nums[v[1]]+nums[k]==0:
# temp = [nums[v[0]],nums[v[1]],nums[k]]
# temp.sort()
# if temp not in res:
# res.append(temp)
# return res
#参考别人的方法
d = {}
res = []
for i in range(len(nums)):
d = {}
for j in range(i + 1, len(nums)):
key = nums[j]
if key in d:
value = d[key] + [key]
value.sort()
if value not in res:
res.append(value)
key = -nums[i] - nums[j]
if key not in d:
d[key] = [nums[i], nums[j]]
return res17.电话号码的字母组合(medium)
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
29class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
res=[]
d={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"]}
if len(digits)==0:
return []
if len(digits)==1:
return d[int(digits)]
l = len(digits)
if l==2:
for i in d[int(digits[0])]:
for j in d[int(digits[1])]:
res.append(i+j)
if l==3:
for i in d[int(digits[0])]:
for j in d[int(digits[1])]:
for k in d[int(digits[2])]:
res.append(i+j+k)
if l==4:
for i in d[int(digits[0])]:
for j in d[int(digits[1])]:
for k in d[int(digits[2])]:
for m in d[int(digits[3])]:
res.append(i+j+k+m)
return res19.删除链表的倒数第N个节点(medium)
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# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
if head.next==None and n==1:
return None
"""
nhead:找到需要删除的节点
pre_nhead:找到需要删除的节点的前一个节点
temp:通过从temp向后遍历找到倒数第n个节点
"""
nhead = pre_nhead = temp = head
flag = 1 #如果flag没变，说明没进while循环，说明要删除的是头节点
while n-1>0:
temp =temp.next
n-=1
# print(temp.val)
while temp.next!=None:
flag = 0
temp = temp.next
pre_nhead = nhead
nhead = nhead.next
if flag:
head = head.next
return head
pre_nhead.next = nhead.next
return head20.有效的括号(easy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
c=[]
j=0
if s=='':
return True
if s[0]==')' or s[0]==']' or s[0]=='}':
return False
for i in range(len(s)):
if len(c)==0:
c.append(s[i])
else:
if (c[-1]=='(' and s[i]==')') or (c[-1]=='[' and s[i]==']') or (c[-1]=='{' and s[i]=='}'):
c.pop(-1)
else:
c.append(s[i])
if len(c)==0:
return True
else:
return False21.合并两个有序链表(medium)
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# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
res=ListNode(None) #合并之后的新数组
p=res #保持头节点不动
if l1==None:
res.next=l2
return res.next
if l2==None:
res.next=l1
return res.next
while l1 and l2:
if l1.val < l2.val:
p.next=l1
l1=l1.next
else:
p.next=l2
l2=l2.next
p=p.next
if l1: #如果l1还没循环结束
p.next=l1
else: #如果l2还没循环结束
p.next=l2
return res.next39.组合总和(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def trace(path,result,index):
if result < 0:
return
if result == 0:
res.append(path)
return
for i in range(index,len(candidates)):
if result >= candidates[i]:
trace(path+[candidates[i]],result-candidates[i],i)
else:
break
res = []
candidates.sort()
trace([],target,0)
return res42.接雨水(hard)
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
48class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if len(height) <= 1:
return 0
#两层循环时间复杂度太大了。不过思路没问题
# ans=0
# start=0
# end=0
# max_h = max(height)
# for i in range(1,max_h+1):
# for j in range(len(height)):
# if height[j]>=i:
# start=j
# break
# for k in range(len(height)):
# if height[len(height)-k-1]>=i:
# end=len(height)-k-1
# break
# for j in range(start+1,end):
# if height[j]<i:
# ans+=1
# return ans
#找到最大值
max_h = max(height)
#找到最大值的下标(第一个最大值)
index = height.index(max_h)
ans=0
temp=0
#从左到最大值遍历
for i in range(index):
if height[i]<height[temp]:
ans=ans+(height[temp]-height[i])
else:
temp=i
height=list(reversed(height[index:]))
temp2=0
for i in range(len(height)):
if height[i]<height[temp2]:
ans=ans+(height[temp2]-height[i])
else:
temp2=i
return ans46.全排列(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# res=[]
# def backtrack(nums,tmp):
# if not nums:
# res.append(tmp)
# return
# for i in range(len(nums)):
# backtrack(nums[:i]+nums[i+1:],tmp+[nums[i]])
# backtrack(nums,[])
# return res
if not nums:
return []
if len(nums) == 1:
return [nums]
ans = []
for i, n in enumerate(nums):
ans.extend([[n] + p for p in self.permute(nums[:i] + nums[i + 1:])])
return ans48.旋转图像(medium)
1
2
3
4
5
6
7class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
matrix[::] = map(list,zip(*reversed(matrix)))49.字母异位词分组(medium)
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
35class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
#方法一
# res=[]
# c=[]
# result=[]
# for i in range(len(strs)):
# res.append((strs[i],Counter(strs[i])))
# while len(res)!=0:
# temp=res[0][1]
# num=[]
# count=[]
# for i in range(len(res)):
# if temp==res[i][1]:
# num.append(res[i][0])
# count.append(i)
# result.append(num)
# for i in reversed(count):
# res.pop(i)
# return result
#其他解法
res = []
dic = {}
for s in strs:
keys = "".join(sorted(s))
if keys not in dic:
dic[keys] = [s]
else:
dic[keys].append(s)
return list(dic.values())62.不同路径(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
res=[[1]*n]*m
# print(res)
for i in range(1,m):
for j in range(1,n):
res[i][j]=res[i][j-1]+res[i-1][j]
return res[-1][-1]64.最小路径和(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
for i in range(len(grid)):
for j in range(len(grid[0])):
if i == j == 0: continue
elif i == 0: grid[i][j] = grid[i][j - 1] + grid[i][j]
elif j == 0: grid[i][j] = grid[i - 1][j] + grid[i][j]
else: grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
return grid[-1][-1]70.爬楼梯(easy)
1
2
3
4
5
6
7
8
9
10class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
res=[1,2,3]
for i in range(n-3):
res.append(res[-1]+res[-2])
return res[n-1]75.颜色分类(medium)
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
27class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
def quicksort(i,j,res):
if i>=j:
return res
p = res[i]
low = i
high = j
while i<j:
while i<j and res[j]>=p:
j-=1
res[i]=res[j]
while i<j and res[i]<=p:
i+=1
res[j]=res[i]
res[j]=p
quicksort(low,i-1,res)
quicksort(i+1,high,res)
return res
quicksort(0,len(nums)-1,nums)
# return nums.sort()78.子集(medium)
1
2
3
4
5
6
7
8
9
10class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res=[[]]
for i in nums:
res+=[j+[i] for j in res]
return res94.二叉树的中序遍历(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root==None:
return []
return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right)98.验证二叉搜索树(medium)
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# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
res = []
def inorder(node):
if node == None:
return False
inorder(node.left)
res.append(node.val)
inorder(node.right)
inorder(root)
# print(res)
if sorted(list(set(res))) == res:
return True
else:
return False101.对称二叉树(easy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.ismirror(root,root)
def ismirror(self,p,q):
if p == None and q == None:
return True
if p == None or q == None:
return False
if p.val == q.val:
return self.ismirror(p.left,q.right) and self.ismirror(p.right,q.left)102.二叉树的层序遍历(medium)
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# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root==None:
return []
queue = []
queue.append(root)
res = []
num=[]
temp=[]
while len(queue)>0:
while len(queue)>0:
node = queue.pop(0)
# print(type(node))
num.append(node.val)
if node.left:
temp.append(node.left)
if node.right:
temp.append(node.right)
# print(type(temp[0]))
res.append(num)
num=[]
for i in range(len(temp)):
queue.append(temp[i])
temp=[]
# for i in temp:
# queue.append(temp)
# temp=[]
return res104.二叉树的最大深度(easy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
return max(self.maxDepth(root.left),self.maxDepth(root.right))+1105.从前序与中序遍历序列构造二叉树(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if not preorder:
return None
x = preorder[0]
node = TreeNode(x)
i = inorder.index(x)
node.left = self.buildTree(preorder[1:i+1],inorder[:i])
node.right = self.buildTree(preorder[i+1:],inorder[i+1:])
return node
114.二叉树展开为链表(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: None Do not return anything, modify root in-place instead.
"""
if root == None:
return []
self.flatten(root.left)
self.flatten(root.right)
tmp = root.right
root.right = root.left
root.left = None
while(root.right != None):
root = root.right
root.right = tmp121.买卖股票的最佳时机(easy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
# max_num=0
# if len(prices)==0:
# return 0
# for i in range(1,len(prices)):
# if prices[i]-min(prices[:i])>max_num:
# max_num = prices[i]-min(prices[:i])
# return max_num
max_num=0
if len(prices)==0:
return 0
min_num=prices[0]
for i in range(1,len(prices)):
min_num = min(min_num,prices[i-1])
if prices[i]-min_num>max_num:
max_num = prices[i]-min_num
return max_num128.最长连续序列(hard)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return 0
nums = list(set(nums))
nums = sorted(nums)
# print(nums)
res=[1]
count=1
for i in range(1,len(nums)):
if nums[i]-nums[i-1]==1:
count+=1
else:
res.append(count)
count=1
res.append(count)
return max(res)136.只出现一次的数字(easy)
1
2
3
4
5
6
7
8
9
10class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a = 0
for num in nums:
a = a ^ num
return a141.环型链表(easy)
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# 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
"""
if head==None or head.next==None:
return False
p=head
q=head.next
while p:
if q.next==p:
return True
else:
if q.next==None:
return False
if q.next.next==None:
return False
p=p.next
q=q.next.next
return False142.环形链表II(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
res=[]
node=head
while node!=None:
if node.next not in res:
res.append(node)
node=node.next
else:
return node.next
return None148.排序链表(medium)
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# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
h_head = ListNode(None) #申请头节点
res = [] #将节点保存在列表中
while head is not None:
next_h = head.next
head.next = None
res.append(head)
head = next_h
# head = head.next
res = sorted(res,key = lambda x:x.val)
# print(res)
n = len(res)
if n == 0:
return None
h_head.next = res[0]
for i in range(n-1):
res[i].next = res[i+1]
# print(res)
return h_head.next152.乘积最大子数组(medium)
1
2
3
4
5
6
7
8
9
10
11class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
rev_nums = nums[::-1]
for i in range(1,len(nums)):
nums[i] *= nums[i-1] or 1
rev_nums[i] *= rev_nums[i-1] or 1
return max(max(nums),max(rev_nums))155.最小栈(easy)
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
47class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.l = []
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.l.append(x)
self.minnum = min(self.l)
def pop(self):
"""
:rtype: None
"""
self.l.pop()
self.minnum =not self.l or min(self.l)
def top(self):
"""
:rtype: int
"""
return self.l[-1]
def getMin(self):
"""
:rtype: int
"""
return self.minnum
# 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.相交链表(easy)
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# 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
"""
l1=0
l2=0
node1=headA
node2=headB
while headA: #求第一个链表长度
l1+=1
headA=headA.next
while headB: #求第二个链表长度
l2+=1
headB=headB.next
s=l1-l2
while s>0: #对齐两个链表长度
node1=node1.next
s-=1
while s<0:
node2=node2.next
s+=1
while node1 and node2:
if node1==node2:
return node1
node1=node1.next
node2=node2.next
return None
# while node1!=node2: #从头开始判断地址是否相同
# node1=node1.next
# node2=node2.next
# return node1169.多数元素(easy)
1
2
3
4
5
6
7
8class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = sorted(nums)
return res[(len(nums)//2)]206.反转链表(easy)
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# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# if head:
# pre=head
# q=head.next
# while pre.next:
# pre.next=q.next
# q.next=head
# head=q
# q=pre.next
# return head
if head==None or head.next==None:
return head
pre=head
q=head.next
while pre.next:
pre.next=q.next
q.next=head
head=q
q=pre.next
return head215.数组中的第K个最大元素(medium)
1
2
3
4
5
6
7
8
9class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
s = sorted(nums,reverse=True)
return s[k-1]226.翻转二叉树(easy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root == None:
return root
temp = root.left
root.left = root.right
root.right = temp
root.left = self.invertTree(root.left)
root.right = self.invertTree(root.right)
return root234.回文链表(easy)
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# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
#第一种思路
#再创建一个链表与head相反，然后逐个对比
#超时 失败
#第二种思路
#用list存下链表所有值，逐个对比
#超时 失败
if head==None or head.next==None:
return True
if head!=None and head.next!=None and head.next.next==None:
if head.val==head.next.val:
return True
else:
return False
c=[]
pre=head
while pre:
c.append(pre.val)
pre=pre.next
i=0
j=-1
for i in range(len(c)/2):
if c[i]!=c[j]:
return False
j-=1
return True
# if head==None or head.next==None:
# return True
# if head!=None and head.next!=None and head.next.next==None:
# if head.val==head.next.val:
# return True
# else:
# return False
# pre=head
# node=None
# node_head=None
# while pre:
# node_head=ListNode(pre.val)
# node_head.next=node
# node=node_head
# pre=pre.next
# while node_head and head:
# if node_head.val!=head.val:
# return False
# return True238.除自身以外数组的乘积(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
res=[]
res1=[1 for i in range(len(nums))]
res2 = [1 for i in range(len(nums))]
for i in range(1,len(nums)):
res1[i]=nums[i-1]*res1[i-1]
for j in range(len(nums)-2,-1,-1):
res2[j]=nums[j+1]*res2[j+1]
for i in range(len(res1)):
res.append(res1[i]*res2[i])
return res
# print(res)
# for i in range(len(nums)):
# for j in range(i):
# res[i]*=nums[j]
# for k in range(i+1,len(nums)):
# res[i]*=nums[k]
# return res279.完全平方数(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
#n = (4^a)*(8b+7) return 4
while n%4==0:
n/=4
if n%8==7:
return 4
a=0
#n=a**2 + b**2 return 1 or 2
while a**2 <=n:
b= int((n-a**2)**0.5)
if a**2 + b**2 == n:
if a>0:
a=1
if b>0:
b=1
return a+b
a+=1
return 3283.移动零(easy)
1
2
3
4
5
6
7
8
9
10
11class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
for i in nums:
if i==0:
nums.insert(len(nums),0)
nums.remove(i)
return nums287.寻找重复数(medium)
1
2
3
4
5
6class Solution:
def findDuplicate(self, nums: List[int]) -> int:
s= sorted(nums)
for i in range(len(s)-1):
if not s[i]^s[i+1]:
return s[i+1]297.二叉树的序列化与反序列化(hard)
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# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def dfs(root):
if not root:
return 'null '
left = dfs(root.left)
right = dfs(root.right)
return str(root.val)+' '+left+right
return dfs(root)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
def dfs(data):
val = data.pop(0)
if val == 'null':
return None
node = TreeNode(val)
node.left = dfs(data)
node.right = dfs(data)
return node
# print(data)
dataList = data.split(' ')
# print(dataList)
return dfs(dataList)
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))347.前K个高频元素(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
res = []
for i in Counter(nums).most_common(k):
res.append(i[0])
return res
# res = Counter(nums)
# result = []
# for i in res.most_common(k):
# result.append(i[0])
# return result394.字符串解码(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution(object):
def decodeString(self, s):
"""
:type s: str
:rtype: str
"""
stack = []
num = 0
res = ""
for c in s :
if c.isdigit():
num = num*10+int(c)
elif c == "[":
stack.append((res,num))
res = ""
num = 0
elif c == "]":
top = stack.pop()
res = top[0]+res*top[1]
else:
res += c
return res448.找到所有数组中消失的数字(easy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
# if len(nums)==0:
# return []
# max_n = len(nums)
# s = set([i for i in range(1, max_n+1)])
# s = s.difference(set(nums))
# return list(s)
# c=[]
c=set(nums)
d=set()
for i in range(1,len(nums)+1):
d.add(i)
result = d.difference(c)
return list(result)461.汉明距离(easy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
count = 0
a=bin(x)[2:]
b=bin(y)[2:]
if len(a)>len(b):
for i in range(len(a)-len(b)):
b = "0"+b
elif len(a)<len(b):
for i in range(len(b)-len(a)):
a = "0"+a
for i in range(len(a)):
if a[i]!=b[i]:
count+=1
return count560.和为K的子数组(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
m={0:1}
sumN=0
count=0
for i in range(len(nums)):
sumN+=nums[i]
count+=m.get(sumN-k,0)
m[sumN]=m.get(sumN,0)+1
return count617.合并二叉树(easy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def mergeTrees(self, t1, t2):
"""
:type t1: TreeNode
:type t2: TreeNode
:rtype: TreeNode
"""
if t1 and t2:
t1.val +=t2.val
t1.left = self.mergeTrees(t1.left,t2.left)
t1.right = self.mergeTrees(t1.right,t2.right)
return t1
return t1 or t2647.回文子串(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
# int count = len(s)
count = 0
for j in range(1,len(s)+1):
i=0
k=j
while k<=len(s):
t=s[i:k]
if t==t[::-1]:
count+=1
i+=1
k+=1
return count739.每日温度(medium)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution(object):
def dailyTemperatures(self, T):
"""
:type T: List[int]
:rtype: List[int]
"""
res=[0 for _ in range(len(T))]
stack=[]
# print(s)
for k,v in enumerate(T):
if stack:
while stack and T[stack[-1]] < v:
res[stack[-1]] = k - stack[-1]
stack.pop()
stack.append(k)
return res