HW手撕汇总

Leecode56. 合并区间

题目链接：https://leetcode.cn/problems/merge-intervals/
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])

        merged=[]

        for interval in intervals:
            #如果列表为空或当前区间与上一区间不重合，直接添加
            if not merged or merged[-1][1]<interval[0]:
                merged.append(interval)
            else:
                merged[-1][1]=max(merged[-1][1],interval[1])

        return merged

Leecode168. Excel表列名称

题目链接：https://leetcode.cn/problems/excel-sheet-column-title/submissions/
给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        result=''
        while columnNumber:
            curr=columnNumber%26
            result+=(chr(curr+64) if curr >0 else 'Z')
            columnNumber=columnNumber//26
            if curr==0:
                columnNumber-=1
        return ''.join(result[::-1])

Leecode171. 表列序号

题目链接：https://leetcode.cn/problems/excel-sheet-column-number/description/
给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回该列名称对应的列序号。

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        result=0
        count=0
        for column in reversed(columnTitle):
            result+=(ord(column)-ord('A')+1)*26**count
            count+=1
        return result

Leecode5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

解题思路：
枚举每个点作为回文串的中心点，左右扩散，如果左边等于右边则继续扩散。
注意要考虑回文串长度为奇偶的情况

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        res=''

        for i in range(n):
        #如果最长回文子串的长度为奇数
            l,r=i-1,i+1
            while l>=0 and r<n and s[l]==s[r]:
                l,r=l-1,r+1
            if (r-l-1>len(res)):
                res=s[l+1:r]

            #如果最长回文子串的长度为偶数
            l,r=i,i+1
            while l>=0 and r<n and s[l]==s[r]:
                l,r=l-1,r+1
            if (r-l-1>len(res)):
                res=s[l+1:r]
        return res

Leecode678. 有效的括号字符串

给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。

有效字符串符合如下规则：

任何左括号 '(' 必须有相应的右括号 ')'。
任何右括号 ')' 必须有相应的左括号 '(' 。
左括号 '(' 必须在对应的右括号之前 ')'。
'*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串。
一个空字符串也被视为有效字符串。

class Solution:
    def checkValidString(self, s: str) -> bool:

        # 正向遍历按照优先级使用"("和"*"消除")"
        stack = []
        for w in s:
            if w != ")":
                stack.append(w)
            else:
                if not stack:
                    return False
                m = len(stack)
                i = -1
                for j in range(m - 1, -1, -1):
                    if stack[j] == "(":
                        i = j
                        break
                if i != -1:
                    stack.pop(i)
                else:
                    stack.pop()

        # 反向遍历使用"*"消除"("
        stack.reverse()
        ans = []
        for w in stack:
            if w != "(":
                ans.append(w)
            else:
                if not ans:
                    return False
                ans.pop()
        return True

Leecode20. 有效括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

class Solution:
    def isValid(self, s: str) -> bool:
      dic = {')':'(',']':'[','}':'{'}

      stack=[]

      for w in s:
        if stack and w in dic.keys():
          if stack[-1]==dic[w]:
            stack.pop()
          else:
            return False
        else:
          stack.append(w)
      return not stack

Leecode735. 行星碰撞

题目链接：https://leetcode.cn/problems/asteroid-collision/description/

给定一个整数数组 asteroids，表示在同一行的行星。

对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack=[]

        for t in asteroids:
            ok=True
            while ok and stack and stack[-1]>0 and t<0:
                a,b=stack[-1],-t

                if a<=b:
                    stack.pop()
                if a>=b:
                    ok=False
            if ok:
                stack.append(t)
        return stack

Offer54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        result=[]
        def dfs(root):
            if not root:
                return 
            dfs(root.left)
            result.append(root.val)
            dfs(root.right)

        dfs(root)
        return result[-k]

LCR 060. 前k个高频元素

题目链接：https://leetcode.cn/problems/g5c51o/description/

给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按任意顺序返回答案。

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic={}

        for i in nums:
            if i not in dic:
                dic[i]=1
            else:
                dic[i]+=1

        dic=sorted(dic.items(),key=lambda x:x[1],reverse=True)
        return [num[0] for num in dic][:k]

Leecode.994 腐烂的橘子

题目链接：https://leetcode.cn/problems/rotting-oranges/description/

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        direction=[(1,0),(-1,0),(0,1),(0,-1)]
        row=len(grid)
        col=len(grid[0])
        time=0

        rotten={(i,j) for i in range(row) for j in range(col) if grid[i][j]==2}
        fresh={(i,j) for i in range(row) for j in range(col) if grid[i][j]==1}
        #当存在新鲜橘子时，继续迭代
        while fresh:
        #如果腐烂集合为空，则结束迭代
            if not rotten:
                return -1
            rotten={(i+di,j+dj) for i,j in rotten for di,dj in direction if (i+di,j+dj) in fresh}
            fresh-=rotten
            time+=1
        return time

01背包

f=[[0]*(m+1) for _ in range(n+1)]
def find_max():
    #有多少物品可选择
    for i in range(1,n+1):
        #背包的容量是多少
        for j in range(1,m+1):
            #如果背包容量小于物品质量
            if j<v[i-1]:
                #不拿这个物品
                f[i][j]=f[i-1][j]
                else:
                    #选择最好的一种方式，去价值的较大值
                    f[i][j]=max(f[i-1][j],f[i-1][j-v[i-1]]+w[i-1])

剑指Offer25. 合并两个排序的链表

题目链接：https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/description/
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy=ListNode(0)
        tmp=dummy
        while l1 and l2:
            if l1.val<=l2.val:
                tmp.next=l1
                l1=l1.next
                tmp=tmp.next
            else:
                tmp.next=l2
                l2=l2.next
                tmp=tmp.next

        while l1:
            tmp.next=l1
            l1=l1.next
            tmp=tmp.next

        while l2:
            tmp.next=l2
            l2=l2.next
            tmp=tmp.next

        return dummy.next

面试题16.26 计算器

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格。整数除法仅保留整数部分。

具体来说，遍历字符串 s，并用变量 preSign 记录每个数字之前的运算符，对于第一个数字，其之前的运算符视为加号。每次遍历到数字末尾时，根据 preSign 来决定计算方式：

加号：将数字压入栈；
减号：将数字的相反数压入栈；
乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。


class Solution:
    def calculate(self, s: str) -> int:
        n=len(s)
        num=0
        stack=[]
        presign='+'

        for i in range(n):
            if s[i]!=' ' and s[i].isdigit():
                num=num*10+ord(s[i])-ord('0')
            if i==n-1 or s[i] in '+-*/':
                if presign=='+':
                    stack.append(num)
                elif presign=='-':
                    stack.append(-num)
                elif presign=='*':
                    stack.append(stack.pop()*num)
                else:
                    stack.append(int(stack.pop()/num))
                presign=s[i]
                num=0
        return sum(stack)

Leecode55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        #初始化当前能达到最远的位置
        max_i=0
        #i为当前位置，jump是当前位置的跳数
        for i,jump in enumerate(nums):
            # 如果当前位置能达到，并且当前位置+跳数>最远位置
            if max_i>=i and i+jump>max_i:
                #更新最远能够到达的位置
                max_i=i+jump
        return max_i>=i

面试题 08.01. 三步问题

题目链接：https://leetcode.cn/problems/three-steps-problem-lcci/
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

class Solution:
    def waysToStep(self, n: int) -> int:
        dp=[1,1,2,4]

        if n<=3:
            return dp[n]

        for i in range(4,n+1):
            dp.append((dp[-1]+dp[-2]+dp[-3])%1000000007)

        return dp[n]