leetcode 经验
1 一维数组查重要使用hash表
python的 Python 的 dict 和 set 都是使用 hash 表实现的，查找操作复杂度为O(1)
而in list的复杂度为O(n)
def findRepeatNumber(self, nums: List[int]) -> int:
table = set()
for i in nums:
if i in table:
return i
else:
table.add(i)
2 递增二维数组查重
数组横向递增纵向递增，所以删除第一个数大的行和最后一个数小的列
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
i = len(matrix) - 1
j = 0
while i >= 0 and j < len(matrix[0]):
if matrix[i][j] > target: i -= 1
elif matrix[i][j] < target: j += 1
else: return True
return False
3 list头插
list.insert(0,xx)，list.insert有一个可选参数是插入位置
但是速度很慢。只击败了54%。。但空间消耗很少，击败100%。。发现到现在还都是速度不到100%。。空间都是100%。。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
list1 =[]
while head!=None:
list1.insert(0,head.val)
head = head.next
return list1
4 给前序中序，得二叉树
前序为 中左右，中序为 左中右，后序为 左右中
耗时又多了，空间还是击败100%。。
# 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 len(preorder)<1:
return None
root = TreeNode(preorder[0])
root.left = self.buildTree(preorder[1:1+inorder.index(preorder[0])],inorder[0:inorder.index(preorder[0])])
root.right = self.buildTree(preorder[1+inorder.index(preorder[0]):],inorder[1+inorder.index(preorder[0]):])
return root
5 斐波那契数列
青蛙跳台阶问题
class Solution:
def fib(self, n: int) -> int:
if (n<2):
return n
n1=0
n2=1
for i in range(1,n):
ret = n1+n2
n1=n2
n2=ret
return ret%1000000007
6 旋转数组的最小数字
第一次双100% ！！
就是代码写的有点丑
class Solution:
def minArray(self, numbers: List[int]) -> int:
left = 0
right = len(numbers)-1
mid =1
while numbers[left]>=numbers[right]:
mid = int((left+right)/2)
if left==mid:
return numbers[right]
if (numbers[left]<numbers[mid]):
left=mid
elif numbers[left]==numbers[mid]:
left+=1
if (numbers[right]>numbers[mid]):
right = mid
elif numbers[right]==numbers[mid]:
right-=1
return numbers[left]
7 二进制中1的个数
处理二进制就应该用位运算
class Solution:
def hammingWeight(self, n: int) -> int:
res=0;
while n>0:
res += n & 1
n >>= 1
return res
8 剪绳子问题
怎么剪绳子各段之积最大
从2到n找最大，知道乘积减小了，证明找到了最大值
class Solution:
def cuttingRope(self, n: int) -> int:
pres= 0
res= 1
i=1
while res>pres:
pres = res
i+=1
res = self.mnum(n,i)
return pres
def mnum(self,n,m):
c = n//m
d = n%m
res = 1
for i in range(m):
if d>0:
res*=(c+1)
d-=1
else:
res*=c
return res
9 实现幂运算
二进制表示n，为1 的就乘上
class Solution:
def myPow(self, x: float, n: int) -> float:
res= 1.0
if n < 0:
x = 1/x
n = -n
while n > 0:
if n & 1:
res *=x
x *= x
n >>= 1
return res
10 正则匹配
我一开始用递归写的。。改了无数次。。结果时间只击败了5%，空间还是100%
class Solution:
def isMatch(self, s: str, p: str) -> bool:
s1=0
p1=0
while p1<len(p)-1:
if p[p1]=='.' and p[p1+1]=='*':
while s1<=len(s):
res = self.isMatch(s[s1:],p[p1+2:])
if res==True:
return True
s1+=1
return False
elif p[p1]=='.':
if s1>=len(s):
return False
return self.isMatch(s[s1+1:],p[p1+1:])
elif p[p1+1]=='*':
res = False
while s1<=len(s):
res = self.isMatch(s[s1:],p[p1+2:])
if res==True:
return True
if s1>=len(s):
break;
elif s[s1]!=p[p1]:
break;
s1+=1
return False
elif s1<len(s) and s[s1]==p[p1]:
s1+=1
p1+=1
else:
break
if len(p)==p1 and len(s)==s1:
return True
elif len(p)==p1 or len(s)==s1:
return False
if p[p1]==s[s1] and s1== len(s)-1:
return True
elif p[p1]=='.' and s1== len(s)-1:
return True
else:
return False
看大家的题解都是动态规划，也学着写了写
动态规划，将问题转化为数学问题的递推
用dp[i][j]表示s的前i项和p的前j项是否匹配，
然后找每个dp和之前的dp的关系
class Solution:
def isMatch(self, s: str, p: str) -> bool:
s, p = '#'+s, '#'+p
m, n = len(s), len(p)
[[False for _ in range(n)] for _ in range(m)]
dp[0][0] = True
for i in range(m):
for j in range(1, n):
if i == 0:
dp[i][j] = j > 1 and p[j] == '*' and dp[i][j-2]
elif p[j] ==s[i] or p[j]=='.':
dp[i][j] = dp[i-1][j-1]
elif p[j] == '*':
dp[i][j] = j > 1 and dp[i][j-2]
if p[j-1] ==s[i] or p[j-1]=='.':
dp[i][j] |= dp[i-1][j]
else:
dp[i][j] = False
return dp[m-1][n-1]
烂橘子问题
网格里有橘子，每分钟烂橘子会将周围橘子变烂，问多少分钟后，橘子会烂完？或者橘子烂不完
这里首先将网络往外扩了一圈，用于减少之后的判断
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
ydo = 1
turn =-1
list22 =[]
listnull =[]
for j in range(len(grid[0])+2):
listnull.append(0)
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j]==2:
list22.append((i+1,j+1))
grid[i].insert(0,0)
grid[i].append(0)
grid.append(listnull)
grid.insert(0,listnull)
while ydo:
ydo=0
turn+=1
len2= len(list22)
for _ in range(len2):
i,j = list22[0][0],list22[0][1]
if grid[i][j-1]==1:
grid[i][j-1]=2
list22.append((i,j-1))
ydo=1
if grid[i-1][j]==1:
grid[i-1][j]=2
list22.append((i-1,j))
ydo=1
if grid[i+1][j]==1:
grid[i+1][j]=2
list22.append((i+1,j))
ydo=1
if grid[i][j+1]==1:
grid[i][j+1]=2
list22.append((i,j+1))
ydo=1
del list22[0]
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j]==1:
return -1
return turn
和为s的连续正数序列
又一次双百，用数列求和来算，对偶数2n，为target%2n==n时是能够得到序列，target%(2n+1)==0时为能够得到，还要注意序列不能为0开始
class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
res = []
n=1
while (1+2*n)*n <= target:
if target%(2*n)==n:
left = target//(2*n)-n+1
res1 = [ _ for _ in range(left,left+2*n)]
res.insert(0,res1)
if target%(2*n+1)==0:
left = target//(2*n+1)-n
if left>0:
res1 = [_ for _ in range(left,left+2*n+1)]
res.insert(0,res1)
n+=1
return res
字符串最大公因子
此处给出的是官网的，不是我写的，因为其非常直白的表现了python在字符串处理上的优点。
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
for i in range(min(len(str1), len(str2)), 0, -1):
if (len(str1) % i) == 0 and (len(str2) % i) == 0:
if str1[: i] * (len(str1) // i) == str1 and str1[: i] * (len(str2) // i) == str2:
return str1[: i]
return ''
数组中不连续上升子序列
数组中不连续的最长上升子序列，要求复杂度O(nlogn0)，考虑用辅助数组。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
dp = [1 for _ in len(nums)]
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
拼写单词
用给的字符串里的字符拼单词，返回能拼的单词的总长度
官网题解是给的Counter，比我的慢一倍多。。
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
chlist = [0 for _ in range(26)]
wolist = [0 for _ in range(26)]
res = 0
for c in chars:
chlist[ord(c)-ord('a')]+=1
for word in words:
for i in range(26):
wolist[i]=0
flag=1
for w in word:
r = ord(w)-ord('a')
wolist[r]+=1
if wolist[r]>chlist[r]:
flag=0
break;
if flag==1:
res+=len(word)
return res