每日一练（力扣新手） 24-1-2

1. 一维数组的动态和

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        result = [nums[0]]
        for i in range(1, len(nums)):
            result.append(result[i-1] + nums[i])
        return result

? ? ? ? 感觉有点类似高中的数列，后一个等于前一个加n，以此类推。但是要先定义好第一个是什么，因为第一个没有前一个，从第二个开始才有这个规律。

? ? ? ? 即： a(n) = a(n -?1) + ???

? ? ? ? 以下是官方答案：

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(1, n):
            nums[i] += nums[i - 1]
        return nums

作者：力扣官方题解
链接：https://leetcode.cn/problems/running-sum-of-1d-array/solutions/962723/yi-wei-shu-zu-de-dong-tai-he-by-leetcode-flkm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

? ? ? ? 我看了一下，我的思维习惯是，怕在原数据上修改，所以喜欢自己新开一个内存取处理数据，所以跟官方的解法不一样，官方的解法是直接在原数据上修改，hh。

? ? ? ? 小知识：

? ? ? ? def runningSum(self, nums: List[int]) -> List[int]:

? ? ? ? 这是Python的类型注解（Type Hints）语法。类型注解是Python 3.5版本引入的一个新特性，它允许你为函数的参数和返回值指定预期的类型。这可以帮助开发者理解函数应该如何使用，以及函数的预期输出。

? ?nums: List[int]表示这个函数接受一个名为nums的参数，其预期类型为List[int]，即元素类型为整数的列表。-> List[int]表示这个函数的返回值预期是一个元素类型为整数的列表。

? ? ? ? Python的类型注解是可选的，并且Python解释器不会因为类型注解而改变它的行为。类型注解主要用于提高代码的可读性和可维护性，以及支持某些IDE和工具提供更好的代码补全和错误检查功能。

2. 将数字变成0的操作次数

第一脑回路想法：

class Solution:
    def numberOfSteps(self, num: int) -> int:
        times = 0
        while (num):
            times += 1
            if num % 2 == 0:
                num = num/2
            else:
                num -= 1
        return times

官方解法：

class Solution:
    def numberOfSteps(self, num: int) -> int:
        ans = 0
        while num:
            ans += num & 1
            if num > 1:
                ans += 1
            num >>= 1
        return ans

作者：力扣官方题解
链接：https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-to-zero/solutions/1237903/jiang-shu-zi-bian-cheng-0-de-cao-zuo-ci-ucaa4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

还有糕手（别人）：

class Solution:
    def numberOfSteps(self, num: int) -> int:
        steps = 0
        while num:
            steps += 1 + num % 2
            num >>= 1
        return max(0, steps - 1)

如果一个数是偶数，必定至少要经过两部才有可能变成0。

因此，如果一个数是偶数，直接加2次次数再说。

如果不是偶数，steps += 1 + 0。不用担心出问题。

num >>= 1是这个方法的精髓，假设num的二进制为10，那么num的二进制表示是1010，num >> 1的结果是101，也就是5，所以num >>= 1会将num的值改变为5。

num >>= 1是一个位运算符，它的作用是将num的二进制表示向右移动一位。

在Python中，>>是右移运算符，num >> 1等价于将num除以2并向下取整，也就是说，它将num的所有二进制位向右移动一位。=是赋值运算符，num >>= 1等价于num = num >> 1，也就是说，它将num除以2并向下取整的结果赋值给num。

假设一个数是偶数，它的二进制必然是以0结尾（0不是偶数，但也是以0结尾）

假设一个数是奇数，它的二进制必然是以1结尾

如果一个数是奇数，num >>= 1在这种算法中一共是同时做了2步，分别是：除以2 并且 减去1

如果一个数是偶数，num >>= 1在这种算法中一共是1步，是：除以2

就是这样了。

最后，返回0或者steps - 1，而不是直接返steps，这个代码的结果可能会比实际的步骤数多1。这是因为在每次执行函数最后一次迭代中，当num变为1时，steps会增加2，但实际上只需要一步就可以将num减少到0。

3. 列表求和 以及 列表最大值

class Solution:
    def maximumWealth(self, accounts: List[List[int]]) -> int:
        sums = [sum(item) for item in accounts]
        max_value = max(sums)
        # rich_man_index = sums.index(max_value)
        return max_value

我这里使用了列表生成式，

列表生成式的套路是：【赋值给谁?for 父项目 in 祖父项目 for 子项目 in 父项目】

max（列表），可得列表中最大的元素。如果是嵌套列表，则返回最大的子列表，

力扣官方解法：

class Solution:
    def maximumWealth(self, accounts: List[List[int]]) -> int:
        return max(map(sum, accounts))

作者：力扣官方题解
链接：https://leetcode.cn/problems/richest-customer-wealth/solutions/1411600/zui-fu-you-ke-hu-de-zi-chan-zong-liang-b-8p06/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

? ?map函数会对一个可迭代对象（如列表）中的每个元素应用一个函数。在这个例子中，map函数对accounts中的每个元素（也就是每个子列表）应用sum函数，计算每个子列表的和。map函数返回一个迭代器，它包含了应用函数后的结果。?

? ?max函数会返回一个可迭代对象中的最大值。在这个例子中，max函数返回了map函数返回的迭代器中的最大值，也就是所有子列表的和中的最大值。

4. 字符串

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        answer = []
        for i in range(1, n+1):
            if i % 3 == 0 and i % 5 == 0:
                answer.append("FizzBuzz")
            elif i % 3 == 0:
                answer.append("Fizz")
            elif i % 5 == 0:
                answer.append("Buzz")
            else:
                answer.append(str(i))
        return answer

这个，没想到什么妙招。

5. 链表的中间节点

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

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        dummy = ListNode(0, head)
        slow, fast = dummy, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        slow.next = slow.next.next
        return dummy.next

慢指针走一步，快指针走两步，快指针遍历完列表的时候，慢指针刚好在中间，如果是奇数长度，慢指针刚好在中间节点的第二个节点。

6. 赎金信

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for char in set(ransomNote):
            if magazine.count(char) < ransomNote.count(char):
                return False
        return True

如果如果magazine中有字符余量少于ransomNote中的字符，那么直接False，

否则，magazine的字符是富足的，溢出的，那就True。

这是我的第一想法，但是还有糕手：

那就是力扣官方解：

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False
        return not collections.Counter(ransomNote) - collections.Counter(magazine)

作者：力扣官方题解
链接：https://leetcode.cn/problems/ransom-note/solutions/1135839/shu-jin-xin-by-leetcode-solution-ji8a/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

? ?使用collections.Counter和减法操作符更高效。这是因为collections.Counter会返回一个字典，其中键是元素，值是元素在输入中出现的次数。当你从一个Counter对象中减去另一个Counter对象时，结果将包含那些在第一个Counter对象中出现次数更多的元素。

? ?collections.Counter(ransomNote) - collections.Counter(magazine)将返回一个Counter对象，其中包含的是在ransomNote中出现次数更多的元素。

? ? ? ? 如果ransomNote可以由magazine构成，那么这个Counter对象应该是空的，所以not collections.Counter(ransomNote) - collections.Counter(magazine)将返回True。

? ? ? ? 如果ransomNote不能由magazine构成，那么这个Counter对象将包含至少一个元素，所以not collections.Counter(ransomNote) - collections.Counter(magazine)将返回False。

? ? ? ? 这种方法的时间复杂度是O(n)。n =? ransomNoteLenth + magazineLenth

? ? ? ? 而我的方法需要对每一个元素都调用count方法，所以它的时间复杂度是O(n^2)。n =? ransomNoteLenth + magazineLenth