子寒的博客
0%

leetcode1354 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
2
3
4
5
6
7
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

分析

    这道题很巧妙的运用了逆向思维的方法，从target开始，一步步推导前面的一个数组会是什么。比如例子里给的[9,3,5] 它的前一个数组必然是 [1,3,5]，因为前一个数组的和所变的数一定是最大的那个数，这样问题就变成了能不能从target变回1数组。     推导过程： [9,3,5] => [9 – (3+5), 3, 5] => [1, 3, 5] => [1, 3, 5 – (1+3)] => [1, 3, 1] => [1, 3 – (1+1), 1] => [1,1,1] done     参考了花花酱的做法，可以看这里

python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isPossible(self, target: List[int]) -> bool:
        if len(target) == 1 and target[0] != 1:
            return False
        
        heapq._heapify_max(target)
        
        while True:
            maximum = target[0]
            if maximum == 1:
                return True
            rest = sum(target[1:])
            if len(target) == 2 and rest == 1:
                return True
            if rest > maximum or maximum % rest == 0:
                return False
            formernum = maximum % rest
            heapq._heapreplace_max(target, formernum)

用到了heapq，这里要注意python的heapq可以写成最大堆，但是最大堆没法push，我这里用的是heapreplace直接改，想要push的话最好还是用最小堆，然后取负值，用的时候在反过来就可以了。