【leetcode】1354. Construct Target Array With Multiple Sums

题目如下：

Given an array of integers target. From a starting array, A consisting of all 1‘s, you may perform the following procedure :

• let x be the sum of all elements currently in your array.
• choose index i, such that 0 <= i < target.size and set the value of A at index i to x.
• You may repeat this procedure as many times as needed.

Return True if it is possible to construct the target array from A otherwise return False.

Example 1:

Input: target = [9,3,5]
Output: true
Explanation: Start with [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

Example 2:

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].

Example 3:

Input: target = [8,5]
Output: true

Constraints:

• N == target.length
• 1 <= target.length <= 5 * 10^4
• 1 <= target[i] <= 10^9

解题思路：本题我用的是贪心算法，每次取target最大的元素 max，逆向计算还原成 max- (sum(target)- max)，循环计算直到target中最大值小于等于1为止，判断最终的target是否全为1。

代码如下：

class Solution(object):
    def isPossible(self, target):
        """
        :type target: List[int]
        :rtype: bool
        """
        import bisect
        total = sum(target)
        target.sort()
        inx = len(target) - 1
        while True:
            largest = target.pop(-1)
            if largest <= 1:
                break
            val = largest - (total - largest)
            total -= (largest - val)
            if val < 1:
                return False
            bisect.insort_left(target,val)
        return target == [1] * len(target)

【leetcode】1354. Construct Target Array With Multiple Sums

原文：https://www.cnblogs.com/seyjs/p/12349885.html