当前位置：首页 > article >正文

LeetCode 每日一题 2025/1/27-2025/2/2

article 2025/2/7 13:34:24

记录了初步解题思路以及本地实现代码；并不一定为最优也希望大家能一起探讨一起进步

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