记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
1/27 45. 跳跃游戏 II
题目说明一定可以跳到队末 要次数最少
找到跳到队尾的最靠前的一个点 将队尾移到这个点 跳动次数+1 pos记录当前的地址
反复寻找
begin用来记录重新开始寻找的点
如果开头是1则直接进行跳跃 次数+1 begin+1 及略过开头若干个1
def jump(nums):
"""
:type nums: List[int]
:rtype: int
"""
begin = 0
pos = 0
num = 0
l = len(nums)
if l<2:
return num
while True:
while nums[pos]==1:
pos+=1
if pos==l-1:
break
num+=1
begin = pos
while pos+nums[pos]<l-1:
pos+=1
num +=1
if pos==begin or pos==l-1:
break
l = pos+1
pos = begin
return num
1/28 119. 杨辉三角 II
按规则生成
def getRow(rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
if rowIndex==0:
return [1]
elif rowIndex==1:
return [1,1]
pre = [1,1]
ind = 1
while ind<rowIndex:
ind+=1
cur = [1]
for i in range(len(pre)-1):
cur.append(pre[i]+pre[i+1])
cur.append(1)
pre=cur[:]
return cur
1/29 219. 存在重复元素 II
滑动窗口 保持k+1长度 记录长度内出现的数字个数
如果数字个数大于1 则成立
def containsNearbyDuplicate( nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
from collections import defaultdict
win = defaultdict(int)
for i in range(min(len(nums),k+1)):
win[nums[i]]+=1
if win[nums[i]]>1:
return True
for i in range(k+1,len(nums)):
win[nums[i-k-1]]-=1
win[nums[i]]+=1
if win[nums[i]]>1:
return True
return False
1/30 350. 两个数组的交集 II
ans1: 接349 获取不重复的交集l
遍历l中的元素
找到两个集合中该元素出现最少的次数 添加进答案
ans2: 将第一个集合编成 字符-次数 的字典 遍历第二个集合
如果某一个字符在字典中并且次数不为0 则加入 字典中的次数减一
from collections import defaultdict
def intersect(nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
n1=set(nums1)
n2=set(nums2)
l = list(n1&n2)
res=[]
for x in l:
num = min(nums1.count(x),nums2.count(x))
res.extend([x]*num)
return res
def intersect2(nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
d = defaultdict(int)
res=[]
for i in nums1:
d[i]+=1
for i in nums2:
if d[i]>0:
res.append(i)
d[i]-=1
return res
1/31 541. 反转字符串 II
l,r代表需要反正的字符段左右
l需要小于s的长度 r为l+k-1和长度n-1之间的较小值
下一个l为之前r+k+1
def reverseStr(s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
n = len(s)
ls= list(s)
l = 0
while l<n:
r = min(l+k-1,n-1)
tmp = r
while l<r:
ls[l],ls[r]=ls[r],ls[l]
l+=1
r-=1
l = tmp+k+1
return ''.join(ls)
2/1 81. 搜索旋转排序数组 II
找到当前旋转的位置 nums[n-1]>=nums[0]
恢复原来顺序 再进行二分查找
def search(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
def find(nums):
l,r = 0,len(nums)-1
while l<=r:
mid = l +(r-l)//2
if nums[mid]==target:
return True
elif nums[mid]<target:
l = mid+1
else:
r = mid-1
return False
if len(nums)==1:
return nums[0]==target
if len(nums)==2:
return nums[0]==target or nums[1]==target
if nums[0]<nums[-1]:
return find(nums)
for i in range(1,len(nums)):
if nums[i]<nums[i-1]:
return find(nums[i:]+nums[:i])
return False
2/2 598. 区间加法 II
最大整数即为每次都加到的区间
遍历记录x,y的最小值
def maxCount(m, n, ops):
"""
:type m: int
:type n: int
:type ops: List[List[int]]
:rtype: int
"""
curx,cury=m,n
for x,y in ops:
curx = min(curx,x)
cury = min(cury,y)
return curx*cury