30网站首页 技术教程

LeetCode 每日一题 2023/4/24-2023/4/30

alphaTao 2023-06-26 12:00:02

简介LeetCode 每日一题 2023/4/24-2023/4/30

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

4/24 1163. 按字典序排在最后的子串

只需要考虑后缀子串因为一个非后缀子串s1 加上s1后的字符串必定排在s1后
记录i为当前最大子串的起始位置
j为当前比较的子串起始位置
k为当前正在比较的第k个字符
比较s[i+k],s[j+k]
如果相等则比较下一个 k=k+1
如果s[i+k]<s[j+k] 说明s[j]~s[j+k]更大
跳过i~i+k 因为其中i后的第m个为起始 m<=k i+m_必定有j+m比它更大
所以更新i=i+k+1开始比较如果此时i>j则从i后一个开始 j=i+1
如果s[i+k]>s[j+k] 说明s[i]~s[i+k]更大
跳过j~j+k 因为对于其中j后的第m个为起始 m<=k j+m~ 必定有i+m~比他更大
更新j=j+k+1

def lastSubstring(s):
    """
    :type s: str
    :rtype: str
    """
    n=len(s)
    i,j=0,1
    k=0
    while j+k<n:
        while j+k<n and s[i+k]==s[j+k]:
            k+=1
        if j+k<n and s[i+k]<s[j+k]:
            i = i+k+1
            k=0
            if i>=j:
                j = i+1
        else:
            j=j+k+1
            k=0
    return s[i:]

4/25 2418. 按身高排序

名字和身高组合按身高排序输出姓名

def sortPeople(names, heights):
    """
    :type names: List[str]
    :type heights: List[int]
    :rtype: List[str]
    """
    n=len(names)
    s = [(heights[i],names[i]) for i in range(n)]
    s.sort(key=lambda x:x[0],reverse=True)
    return [s[i][1]for i in range(n)]

4/26 1031. 两个非重叠子数组的最大和

考虑 firstlen的子数组在secondlen子数组前
使用dp[i]记录在i位置前firstlen长度子数组的最大和
我们考虑secondlen长度nums[i~i+secondlen-1]和
再加上dp[i]就是两个子数组和的最大值
同样考虑secondlen的子数组在firstlen子数组前

def maxSumTwoNoOverlap(nums, firstLen, secondLen):
    """
    :type nums: List[int]
    :type firstLen: int
    :type secondLen: int
    :rtype: int
    """
    n = len(nums)
    def check(l1,l2):
        dp = [0]*(n+1)
        cur = sum(nums[:l1])
        dp[l1] = cur
        for i in range(l1,n):
            cur = cur+nums[i]-nums[i-l1]
            dp[i+1] = max(cur,dp[i])
            
        cur = sum(nums[l1:l1+l2])
        ans = dp[l1]+cur
        for j in range(l1+l2,n):
            cur = cur+nums[j]-nums[j-l2]
            ans = max(ans,cur+dp[j-l2+1])
        return ans
    return max(check(firstLen,secondLen),check(secondLen,firstLen))

4/27 1048. 最长字符串链

按长度排序
对于某个词word 判断其所有可能的前身是否出现过

def longestStrChain(words):
    """
    :type words: List[str]
    :rtype: int
    """
    from collections import defaultdict
    words.sort(key=len)
    ans = 0
    m = defaultdict(int)
    for word in words:
        m[word]=1
        for i in range(len(word)):
            pre = word[:i]+word[i+1:]
            if pre in m:
                m[word] = max(m[word],m[pre]+1)
        ans = max(ans,m[word])
    return ans

4/28 1172. 餐盘栈

cap为每个栈容量 stacks依次存放所有的栈 notfull存放未放满的栈的序号
push:
如果notfull内没有有空位的栈则在最后新添一个栈
如果cap>1 说明新添的栈没有满加入到notfull
如果notfull内存在有空位的栈找到最靠前的位置ind
将盘子放入ind栈中判断此时该栈是否满了如果满了从nutfull中移除
popAtStack:
判断index位置是否满足条件在stacks内或者stacks[ind]为空
移除stacks[ind]栈顶的盘子
如果index为最后一个栈且最后的栈为空则将栈移除
pop:
即为popAtStack最后一个栈

from sortedcontainers import SortedSet
class DinnerPlates(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cap = capacity
        self.stacks = []
        self.notfull = SortedSet()


    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        if not self.notfull:
            self.stacks.append([val])
            if self.cap>1:
                self.notfull.add(len(self.stacks)-1)
        else:
            ind = self.notfull[0]
            self.stacks[ind].append(val)
            if len(self.stacks[ind])==self.cap:
                self.notfull.discard(ind)


    def pop(self):
        """
        :rtype: int
        """
        return self.popAtStack(len(self.stacks)-1)


    def popAtStack(self, index):
        """
        :type index: int
        :rtype: int
        """
        if index<0 or index>=len(self.stacks) or not self.stacks[index]:
            return -1
        v = self.stacks[index].pop()
        if index == len(self.stacks)-1 and not self.stacks[-1]:
            while self.stacks and not self.stacks[-1]:
                self.notfull.discard(len(self.stacks)-1)
                self.stacks.pop()
        else:
            self.notfull.add(index)
        return v