leetcode 6.01-6.07

2020-06-01

1431 拥有最多糖果的孩子
238 除自身以外数组的乘积

1431. 拥有最多糖果的孩子

给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有最多的糖果。注意，允许有多个孩子同时拥有最多的糖果数目。

示例 1：

输入：candies = [2,3,5,1,3], extraCandies = 3
输出：[true,true,true,false,true]
解释：
孩子 1 有 2 个糖果，如果他得到所有额外的糖果（3个），那么他总共有 5 个糖果，他将成为拥有最多糖果的孩子。
孩子 2 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。
孩子 3 有 5 个糖果，他已经是拥有最多糖果的孩子。
孩子 4 有 1 个糖果，即使他得到所有额外的糖果，他也只有 4 个糖果，无法成为拥有糖果最多的孩子。
孩子 5 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。

提示：

2 <= candies.length <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

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

先扫一遍数组，得到孩子拥有的最大糖果数目maxc，再扫一遍数组，当前数字加上extraCandies大于等于maxc为true，否则false

AC代码：

class Solution(object):
    def kidsWithCandies(self, candies, extraCandies):
        """
        :type candies: List[int]
        :type extraCandies: int
        :rtype: List[bool]
        """
        max_candy = max(candies)
        res = []
        for num in candies:
            res.append(num + extraCandies >= max_candy)
            # if num + extraCandies >= max_candy:
            #     res.append(true)
            # else:
            #     res.append(false)
        return res

238. 除自身以外数组的乘积

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：
你可以在常数空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

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

不许用除法做，题目又提到了前缀、后缀，疯狂暗示，思路是$result[i]$ = 第$i$个元素的前缀元素积 * 第$i$个元素的后缀元素积。先从前到后扫一遍数组，记录下各个位置的前缀元素积；再从后往前扫一遍数组，记录下各个位置的后缀元素积，两个数组对应位置相乘就是最后的结果。复杂度$O(n)$，符合要求

题目进阶要求常数空间复杂度，那么前缀元素积数组可以用结果数组代替，后缀元素积数组可以只用一个数字来计算，边算suffix边算结果（AC代码的思路）。

AC代码：

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ret = [1]
        for i in range(1, len(nums)):
            ret.append(ret[i-1]*nums[i-1])
        suffix = 1
        nums.reverse()
        for i in range(1, len(nums)):
            ret[-i] *= suffix
            suffix *= nums[i-1]
        ret[0] *= suffix
        return ret

但是不明白为什么我的空间复杂度才打败了12.5%的人。