每日一题(4月)

1-10

1006.笨阶乘

把求阶乘中的 * 运算变成 * / + - 的循环

#数学观察，N⋅(N−1)/(N−2)=N+1（N>4时）
class Solution:
    def clumsy(self, n: int) -> int:
        if n==1: return 1
        elif n==2: return 2
        elif n==3: return 6
        elif n==4: return 7

        if n%4==0: return n+1
        elif n%4<=2: return n+2
        else: return n-1

#学不来，找规律

面试题 17.21. 直方图的水量

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
如图，能接住6的水

#方法一：找规律当成数组做
class Solution:
    def trap(self, height: List[int]) -> int:
        pre=0
        ans=0
        for h in height:
            pre=max(pre,h)
            ans+=(pre-h)
        
        r_pre=0
        for h in height[::-1]:    #减去右边多出的水
            r_pre=max(r_pre,h)
            if r_pre==pre: break
            ans-=(pre-r_pre)
        return ans

#方法二：双指针
class Solution:
    def trap(self, height: List[int]) -> int:
        ans=0
        l,r=0,len(height)-1
        lm,rm=0,0
        while l<r:
            lm=max(lm,height[l])
            rm=max(rm,height[r])
            if height[l]<height[r]:
                ans+=lm-height[l]
                l+=1
            else:
                ans+=rm-height[r]
                r-=1
        return ans

1143.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在公共子序列，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

#经典二维动态规划
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m,n=len(text1),len(text2)
        dp=[[0]*(n+1) for _ in range(m+1)]  #写成*(m+1)会出错，？？
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
                #print(dp)
        return dp[m][n]

781.森林中的兔子

森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        c=Counter(answers)
        ans=0
        for num,cnt in c.items():
            if num==0: ans+=cnt
            else: ans+=(num+1)*((cnt-1)//(num+1)+1)
        return ans

88.合并两个有序数组

合并两个有序的数组，nums1 不需要补充空间，长为 m+n

#双指针普通做法
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        ans=[]
        p1,p2=0,0
        while p1<m or p2<n:
            if p1==m:
                ans.append(nums2[p2])
                p2+=1
            elif p2==n:
                ans.append(nums1[p1])
                p1+=1
            elif nums1[p1]<nums2[p2]:
                ans.append(nums1[p1])
                p1+=1
            else:
                ans.append(nums2[p2])
                p2+=1
        nums1[:]=ans

# nums[:]=ans 和 nums=ans.copy(),第二个高效些

"""
Do not return anything, modify nums1 in-place instead.
"""
#逆向双指针，避免使用额外数组空间
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1, p2 = m-1, n-1
        tail = m+n-1
        while p1>=0 or p2>=0:
            if p1==-1:
                nums1[tail] = nums2[p2]
                p2-=1
            elif p2==-1:
                nums1[tail] = nums1[p1]
                p1-=1
            elif nums1[p1]<=nums2[p2]:
                nums1[tail] = nums2[p2]
                p2-=1
            else:
                nums1[tail] = nums1[p1]
                p1-=1
            tail-=1

80.删除有序数组中的重复项II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        if n<=2: return n
        slow, fast = 2, 2   #slow:放入值的指针，fast:读取值的指针
        while fast < n:
            if nums[slow-2] != nums[fast]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

81.搜索旋转排序数组II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false

#二分查找，对情况分类
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if not nums: return False
        n = len(nums)
        if n==1: return nums[0]==target

        l,r=0,n-1
        while l<=r:    #=
            mid = (l + r)//2
            if target == nums[mid]: return True
            if nums[l]==nums[mid] and nums[mid]==nums[r]:  #额外
                r-=1
                l+=1
            elif nums[l]<=nums[mid]:
                if nums[l]<=target<nums[mid]:
                    r = mid - 1
                else: 
                    l = mid + 1
            else:
                if nums[mid]<target<=nums[n-1]:
                    l = mid + 1
                else:
                    r = mid - 1
        return False

#嗯，这也能正常二分

153.寻找旋转排序数组中的最小值

class Solution:
    def findMin(self, nums: List[int]) -> int: 
        l, r = 0, len(nums)-1
        while l < r:
            mid = (l+r)//2
            if nums[mid]<nums[r]:
                r = mid
            else:
                l = mid + 1
        return nums[l]
#二分

旋转排序数组总是两段上升的数组，且右边处于低位

154.寻找旋转排序数组中的最小值 II

相较上题，可能存在重复元素。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums)-1
        while l < r:
            mid = (l+r)//2
            if nums[mid] < nums[r]:
                r = mid
            elif nums[mid] == nums[r]:  #无法确定最小值位于mid左侧，或右侧
                r -= 1
            else:
                l = mid + 1
        return nums[l]

263.丑数

判断一个数是否是只含质因数2, 3, 5 的正整数。

class Solution:
    def isUgly(self, n: int) -> bool:
        if not n: return False  # 0
        while n!=1:
            if n%2==0:
                n//=2
            elif n%3==0:
                n//=3
            elif n%5==0:
                n//=5
            else:
                return False
        return True

11-20

264.丑数II

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 或 5 的正整数。

#三指针，有些东西啊
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0]*(n+1)
        dp[1] = 1
        p2 = p3 = p5 = 1  
        for i in range(2, n+1):
            num2, num3, num5 = dp[p2]*2, dp[p3]*3, dp[p5]*5
            dp[i] = min(num2, num3, num5)
            if dp[i] == num2: p2+=1
            if dp[i] == num3: p3+=1
            if dp[i] == num5: p5+=1
        return dp[n]

179.最大数

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums_str = [str(num) for num in nums]
        compare = lambda x, y: 1 if x + y < y + x else -1
        nums_str.sort(key = functools.cmp_to_key(compare)) #指定比较函数为compare
        res = "".join(nums_str)
        if res[0] == "0":
            res = "0"
        return res

783.二叉搜索树节点最小距离

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
        self.ans=float('inf')
        self.pre=float('-inf') #pre是整个中序遍历中的pre
        def dfs(root):
            if root:
                dfs(root.left)
                self.ans=min(self.ans,root.val-self.pre)
                self.pre = root.val
                dfs(root.right)
                
        dfs(root)        
        return self.ans

# 94.二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        return [i for i in inorder(root)]

208.实现Trie前缀树⭐

Trie 或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。

通常应用场景：自动补全和拼写检查。

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self._children = [None] * 26
        self._is_ending_char = False


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        root = self
        for i in map(lambda x : ord(x) - ord('a'), word):
            if not root._children[i]:
                root._children[i] = Trie()
            root = root._children[i]
        root._is_ending_char = True


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        root = self
        for i in map(lambda x: ord(x) - ord('a'), word):
            if not root._children[i]:
                return False
            root = root._children[i]
        return root._is_ending_char


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        root = self
        for i in map(lambda x: ord(x) - ord('a'), prefix):
            if not root._children[i]:
                return False
            root = root._children[i]
        return True



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

213.打家劫舍II

相邻房间报警，首尾相邻

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n<=3: return max(nums)

        def rob(l, r):
            first, second = nums[l], max(nums[l], nums[l+1])
            for i in range(l+2,r+1):
                first, second = second, max(second, first + nums[i])
            return second

        return max(rob(0,n-2),rob(1,n-1))

87.扰乱字符串

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        @cache
        def dfs(i1: int, i2: int, length: int) -> bool:
            """
            第一个字符串从 i1 开始，第二个字符串从 i2 开始，子串的长度为 length，是否和谐
            """

            # 判断两个子串是否相等
            if s1[i1:i1+length] == s2[i2:i2+length]:
                return True
            
            # 判断是否存在字符 c 在两个子串中出现的次数不同
            if Counter(s1[i1:i1+length]) != Counter(s2[i2:i2+length]):
                return False
            
            # 枚举分割位置
            for i in range(1, length):
                # 不交换的情况
                if dfs(i1, i2, i) and dfs(i1 + i, i2 + i, length - i):
                    return True
                # 交换的情况
                if dfs(i1, i2 + length - i, i) and dfs(i1 + i, i2, length - i):
                    return True
        
            return False

        ans = dfs(0, 0, len(s1))
        dfs.cache_clear()
        return ans

#copy

220.存在重复元素III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if t<0 or k<0: return False
        buckets = {}           #桶与数字的字典
        size = t+1             #桶中只有一个数字
        for i in range(len(nums)):
            idx = nums[i]//size
            if idx in buckets: return True
            buckets[idx] = nums[i]
            if (idx-1) in buckets and nums[i]-buckets[idx-1]<=t: return True
            if (idx+1) in buckets and buckets[idx+1]-nums[i]<=t: return True
            if i>=k: buckets.pop(nums[i-k]//size)
        return False

26. 删除有序数组中的重复项

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        left = 0
        for right in nums:
            if not left:
                left += 1
            elif nums[left-1] != right:
                nums[left] = right
                left += 1
        return left

27. 移除元素

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left = 0
        for right in nums:
            if right != val:
                nums[left] = right
                left += 1
        return left

28.实现 strStr()

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1

needle 为空串时返回 0

#　一、暴力匹配
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle: return 0
        if haystack == needle: return 0
        m, n = len(haystack), len(needle)
        for i in range(m-n+1):
            if haystack[i:i+n] == needle:
                return i
        return -1

# 二、KMP
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle: return 0
        m, n = len(haystack), len(needle)
        tmp, k = [0], 0     #计算相同前后缀，不是回文
        for i in range(1,n):
            while k>0 and needle[i]!=needle[k]:
                k = tmp[k-1]      #前后缀指针回退
            if needle[i] == needle[k]:
                k += 1
            tmp.append(k)
        #print(tmp)
        k = 0
        for i in range(m):
            while k>0 and haystack[i]!=needle[k]:
                k = tmp[k-1]
            if haystack[i] == needle[k]:
                k +=1
            if k == n: return i-k+1
        return -1

#子串长度较小时，或子串相同前后缀较少时，收益不大

# 三、用index
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:return 0
        if needle in haystack:
            position = haystack.index(needle)
            return position
        else :
            return -1

21-30

91. 解码方法

363. 矩形区域不超过 K 的最大数值和

368. 最大整除子集

377.组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [1] + [0]*target
        for i in range(1, target+1):
            for num in nums:
                if num <= i:
                    dp[i] += dp[i-num]
        return dp[target]

897. 递增顺序搜索树

给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

#方法一
# 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 increasingBST(self, root: TreeNode) -> TreeNode:
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)

        vals = [i for i in inorder(root)]

        new_root = TreeNode(vals[0])
        p = new_root
        for val in vals[1:]:
            p.left = None
            p.right = TreeNode(val)
            p = p.right
        
        return new_root

#方法二：推荐做法
class Solution:
    def __init__(self):
        self.head = TreeNode(-1)
        self.p = self.head

    def increasingBST(self, root: TreeNode) -> TreeNode:
        def traverse(node):
            if node:
                traverse(node.left)
                self.p.right = TreeNode(node.val)
                self.p = self.p.right
                traverse(node.right)
        traverse(root)
        return self.head.right

# 过程类似中序遍历，p指针负责建树即可

938.二叉搜索树的范围和

#中序遍历
# 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 rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        self.ans = 0
        def inorder(node):
            if node:
                inorder(node.left)
                if node.val>high:
                    return 
                if node.val>=low:
                    self.ans += node.val
                inorder(node.right)
        
        inorder(root)
        return self.ans

633.平方数之和

#双指针
from math import *
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        l, r = 0, int(sqrt(c))
        while l <= r:
            if l*l+r*r > c: r-=1
            elif l*l+r*r < c: l+=1
            else: return True
        return False

coding for fun

剑指 Offer 03. 数组中重复的数字

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        tmp = set()
        for num in nums:
            if num not in tmp:
                tmp.add(num)
            else: return num

#使用集合或字典提高效率

剑指 Offer 04. 二维数组中的查找

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix: return False
        rows, cols = len(matrix), len(matrix[0])
        x, y = 0, cols-1
        while x < rows and 0 <= y:
            if target > matrix[x][y]: 
                x += 1
                continue
            elif target < matrix[x][y]:
                y -= 1
                continue
            else: return True
        return False

#从矩阵的右上角开始查找

剑指 Offer 05. 替换空格

class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(" ","%20")

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

#普通做法
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        ans = []
        p = head
        while p:
            ans.append(p.val)
            p = p.next
        return ans[::-1]

#递归
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        return self.reversePrint(head.next) + [head.val] if head else []

#耗时好像更多

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

#递归
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder: return None
        root = TreeNode(preorder[0])
        idx = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:1+idx],inorder[:idx])
        root.right = self.buildTree(preorder[1+idx:],inorder[idx+1:])
        return root

官方答案：

# 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

"""
思路：前序遍历：根节点->左子树->右子树 中序遍历：左子树->根节点->右子树
框架：（1）先把根节点建立起来 （2）递归地构造左子树并连接到根节点 （3）递归地构造右子树并连接到根节点
"""
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def myBulidTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
            if preorder_left > preorder_right:
                return None
            # 前序遍历中的第一个节点就是根节点
            preorder_root_index = preorder_left
            # 在中序遍历中定位根节点,获得索引值
            inorder_root_index = index[preorder[preorder_root_index]]

            # 先构建根节点
            root = TreeNode(preorder[preorder_root_index])
            # 得到左子树中节点的数目
            size_left_subtree = inorder_root_index - inorder_left
            # 构建左子树，并跟根节点相关联
            # 前序遍历中[从左边界+1 开始的 size_left_subtree]个元素就对应了中序遍历中[从 左边界 开始到 根节点定位-1]的元素
            root.left = myBulidTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root_index - 1)
            # 构建右子树，并跟根节点相关联
            # 前序遍历中[从根节点+size_left_subtree+1 开始到 右边界]个元素就对应了中序遍历中[从根节点+1 到 右边界]的元素
            root.right = myBulidTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root_index + 1, inorder_right)
            return root

        n = len(preorder)
        # 构建哈希映射，帮助快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        return myBulidTree(0, n-1, 0, n-1)

剑指 Offer 49. 丑数

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0]*(n+1)
        dp[1] = 1
        p2 = p3 = p5 =1
        for i in range(2, n+1):
            num2, num3, num5 = dp[p2]*2, dp[p3]*3, dp[p5]*5
            dp[i] = min(num2, num3, num5)
            if dp[i] == num2: p2+=1
            if dp[i] == num3: p3+=1
            if dp[i] == num5: p5+=1
        return dp[n]