2024.5.7 —— LeetCode 高频题复盘

136. 只出现一次的数字

题目链接

Python

方法一

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans=nums[0]
        for i in range(1,len(nums)):
            ans=nums[i]^ans
        return ans

核心思想：一个数被另一个数异或两次，该数本身不变。

方法二

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return sum(set(nums))*2-sum(nums)

LCR 155. 将二叉搜索树转化为排序的双向链表

题目链接

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        # 1.二叉搜索树——>排序的双向链表(中序遍历)
        def dfs(cur):
            if not cur:
                return
            dfs(cur.left)
            
        # 2. 双向链表（相邻节点）
            if self.pre:
                self.pre.right=cur
                cur.left=self.pre
            else:
                self.head=cur
            self.pre=cur

            dfs(cur.right)

        if not root:
            return
        self.pre=None
        dfs(root)
        # 3. 循环链表（首尾节点）
        self.head.left=self.pre
        self.pre.right=self.head
        return self.head

11. 盛最多水的容器

题目链接

Python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        res = 0
        i = 0
        j = len(height) - 1
        while i < j:
            area = (j - i) * min(height[i], height[j])
            res = max(res, area)
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return res

498. 对角线遍历

题目链接

Python

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m,n,ans=len(mat),len(mat[0]),[]
        for k in range(m+n-1):
            # 偶对角线（左下到右上）
            if k%2==0:
                ans+=[mat[x][k-x] for x in range(min(k,m-1),max(0,k-n+1)-1,-1)]
            # 奇对角线（右上到左下）
            else:
                ans+=[mat[x][k-x] for x in range(max(0,k-n+1),min(k,m-1)+1)]
        return ans

对角线上横纵坐标和为定值 k 。

402. 移掉 K 位数字

题目链接

Python

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack=[]
        remain=len(num)-k # 不可少，例如输入为"9",1或者"112",1
        for n in num:
            while k and stack and stack[-1]>n:
                stack.pop()
                k-=1
            stack.append(n)
        return "".join(stack[:remain]).lstrip("0") or "0"

归并排序

Python

class Solution:
    # 合并两个有序数组
    def merge(self,left,right):
        merged=[]
        i=j=0
        while i<len(left) and j<len(right):
            if left[i]<=right[j]:
                merged.append(left[i])
                i+=1
            else:
                merged.append(right[j])
                j+=1
        while i<len(left):
            merged.append(left[i])
            i+=1
        while j<len(right):
            merged.append(right[j])
            j+=1
        return merged
    # 划分左右数组
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums)<=1:
            return nums
        mid=len(nums)//2
        left=self.sortArray(nums[:mid])
        right=self.sortArray(nums[mid:])
        return self.merge(left,right)

958. 二叉树的完全性检验

题目链接

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        # 设根节点编号为1，树中所有节点的编号按照广度优先搜索顺序正好是升序，
        # 我们检测编号序列是否为无间隔的 1, 2, 3, …，事实上，我们只需要检查最后一个编号是否正确，因为最后一个编号的值最大。
        nodes=[[root,1]]
        i=0
        while i<len(nodes):
            node,v=nodes[i]
            i+=1
            if node:
                nodes.append([node.left,2*v])
                nodes.append([node.right,2*v+1])
        return nodes[-1][1]==len(nodes)

123. 买卖股票的最佳时机 III

题目链接

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp[i][0]不操作
        # dp[i][1]第一次持有股票的最大金额 
        # dp[i][2]第一次不持有股票的最大金额
        # dp[i][3]第二次持有股票的最大金额 
        # dp[i][4]第二次不持有股票的最大金额
        dp=[[0]*5 for _ in range(len(prices))]
        dp[0][1]=-prices[0]
        dp[0][3]=-prices[0]
        for i in range(1,len(prices)):
            dp[i][0]=dp[i-1][0]
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
            dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i])
            dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i])
            dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i])
        return dp[-1][-1]

79. 单词搜索

题目链接

Python

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i,j,k):
            # 不满足条件的进行剪枝
            if not 0<=i<m or not 0<=j<n or visited[i][j]==True or board[i][j]!=word[k]:
                return False
            # 匹配到单词最后一个字符
            if k==len(word)-1:
                return True
            visited[i][j]=True
            for d in directions:
                ni,nj=i+d[0],j+d[1]
                if dfs(ni,nj,k+1):
                    return True
            visited[i][j]=False

        m,n=len(board),len(board[0])
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        visited=[[False for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if dfs(i,j,0):
                    return True
        return False

排序奇升偶降链表

题目链接

在做该题之前建议先做 206. 反转链表、21. 合并两个有序链表、328. 奇偶链表这三题。

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:    
    def sortOddEvenList(self,head):     
        if not head or not head.next:      
            return head        
        oddList,evenList = self.partition(head)        
        evenList = self.reverse(evenList)        
        return self.merge(oddList,evenList)    
    def partition(self, head):        
        evenHead = head.next        
        odd, even = head, evenHead        
        while even and even.next:            
            odd.next = even.next            
            odd = odd.next            
            even.next = odd.next            
            even = even.next        
        odd.next = None        
        return [head,evenHead] 
    def reverse(self, head):
        pre=None
        cur=head
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre
	def merge(self, list1, list2):
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val<list2.val:
            list1.next=self.merge(list1.next,list2)
            return list1
        else:
            list2.next=self.merge(list2.next,list1)
            return list2