leetcode刷题（不邻接植花、电话号码的字母组合、统计共同度过的日子数、节点与其祖先之间的最大差值、分隔数组以得到最大和、二进制求和、x的平方根、最小偶倍数）

目录

1、不邻接植花

2、电话号码的字母组合

3、统计共同度过的日子数

4、节点与其祖先之间的最大差值

5、分隔数组以得到最大和

6、 二进制求和

7、 x的平方根

8、最小偶倍数

1、不邻接植花

2、电话号码的字母组合

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:    #啥都不输入
            return []
        phone = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]  #模拟键
        queue = ['']    #初始化队列
        for digit in digits:    #遍历数字
            for i in range(len(queue)):
                tmp = queue.pop(0)   #把队列里面的第一个字母搞出来
                for letter in phone[ord(digit) - 50]:    #ord()函数是返回字符ASCLL码的，2的ASCLL码是50
                    queue.append(tmp + letter)    #相加组合
        return queue

3、统计共同度过的日子数

dayPerMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
class Solution:
    def stringToInt(self, s: str) -> int:    #转换天数很关键
        m, d = map(int, s.split('-'))
        ans = 0
        for i in range(1, m):
            ans += dayPerMounth[i - 1]
        ans += d
        return ans   #把输入的日期的天数算出来

    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        aa = self.stringToInt(arriveAlice)
        la = self.stringToInt(leaveAlice)
        ab = self.stringToInt(arriveBob)
        lb = self.stringToInt(leaveBob)
        if aa > ab:          #将两者统一一下,统一成aa<=ab，方便计算
            aa, ab = ab, aa
            la, lb = lb, la
        if ab > la:   #b还没到，a就走了
            return 0
        return min(la, lb) - ab + 1

4、节点与其祖先之间的最大差值

# 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 maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def dfs(root, mi, mx):
            if root is None:
                return   #没有这个节点就拉倒
            nonlocal ans
            ans = max(ans, abs(mi - root.val), abs(mx - root.val))
            mi = min(mi, root.val)
            mx = max(mx, root.val)
            dfs(root.left, mi, mx)
            dfs(root.right, mi, mx)
        ans = 0
        dfs(root, root.val, root.val)
        return ans

5、分隔数组以得到最大和

#copy来的
class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        d = [0] * (n + 1)
        for i in range(1, n + 1):
            maxValue = arr[i - 1]
            for j in range(i - 1, max(-1, i - k - 1), -1):
                d[i] = max(d[i], d[j] + maxValue * (i - j))
                if j > 0:
                    maxValue = max(maxValue, arr[j - 1])
        return d[n]

6、 二进制求和

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a,2)+int(b,2))[2:]       
#先使用二进制int(a,2)转换成十进制，再利用bin()转换成二进制，注意最后[2:]的目的是使用bin()的得到的最后前缀会加上0b，这样方便去除

7、 x的平方根

class Solution(object):
    def mySqrt(self, x):
        if x == 0 or x == 1:
            return x

        low, high, res = 1, x, -1

        while low <= high:
            mid = (low + high) // 2   #二分查找
            if mid * mid <= x:
                res = mid
                low = mid + 1
            else:
                high = mid - 1

        return res

8、最小偶倍数

class Solution:
    def smallestEvenMultiple(self, n: int) -> int:
        if n % 2 == 0:
            return n
        else:
            return 2 * n