leetcode 8.31-9.06

2020-09-04

1551 使数组中所有元素相等的最小操作数
257 二叉树的所有路径

1551. 使数组中所有元素相等的最小操作数

存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。

一次操作中，你可以选出两个下标，记作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 减去 1 、arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。最终的目标是使数组中的所有元素都相等。题目测试用例将会保证：在执行若干步操作后，数组中的所有元素最终可以全部相等。

给你一个整数 n，即数组的长度。请你返回使数组 arr 中所有元素相等所需的最小操作数。

示例 1：

输入：n = 3
输出：2
解释：arr = [1, 3, 5]
第一次操作选出 x = 2 和 y = 0，使数组变为 [2, 3, 4]
第二次操作继续选出 x = 2 和 y = 0，数组将会变成 [3, 3, 3]

提示：

1 <= n <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-operations-to-make-array-equal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：数组实际上是个奇数序列。每次操作，数组的数值总和不变，所以最后所有元素的值是这个数组的平均数n，那么操作数实际就是数组前半部分数字与n的差值的和，数学计算一下$\Sigma_{i=0}^{\frac{n}{2}}(n-(2i + 1))$

这题不值得中等难度。

class Solution(object):
    def minOperations(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n % 2 == 0:
            return n * n / 4
        else:
            return (n+1)*(n-1)/4

257. 二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

1
/ \
2 3
\
5

输出: [“1->2->5”, “1->3”]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：深度优先搜索，递归构造字符串

AC代码：

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        if root == None:
            return []
        if root.left == None and root.right == None:
            return [str(root.val)]
        
        rootstr = str(root.val)
        ret = []

        def paths(node, cur_str):
            cur_str = cur_str+"->"+str(node.val)
            if  node.left == None and node.right == None:
                ret.append(cur_str)
            if node.left:
                paths(node.left, cur_str)
            if node.right:
                paths(node.right, cur_str)

        if root.left:
            paths(root.left, rootstr)
        if root.right:
            paths(root.right, rootstr)
        return ret