|
3 | 3 | importjava.util.Collections; |
4 | 4 | importjava.util.PriorityQueue; |
5 | 5 |
|
6 | | -/** |
7 | | - * 1354. Construct Target Array With Multiple Sums |
8 | | - * |
9 | | - * Given an array of integers target. From a starting array, A consisting of all 1's, you may perform the following procedure : |
10 | | - * let x be the sum of all elements currently in your array. |
11 | | - * choose index i, such that 0 <= i < target.size and set the value of A at index i to x. |
12 | | - * You may repeat this procedure as many times as needed. |
13 | | - * Return True if it is possible to construct the target array from A otherwise return False. |
14 | | - * |
15 | | - * Example 1: |
16 | | - * Input: target = [9,3,5] |
17 | | - * Output: true |
18 | | - * Explanation: Start with [1, 1, 1] |
19 | | - * [1, 1, 1], sum = 3 choose index 1 |
20 | | - * [1, 3, 1], sum = 5 choose index 2 |
21 | | - * [1, 3, 5], sum = 9 choose index 0 |
22 | | - * [9, 3, 5] Done |
23 | | - * |
24 | | - * Example 2: |
25 | | - * Input: target = [1,1,1,2] |
26 | | - * Output: false |
27 | | - * Explanation: Impossible to create target array from [1,1,1,1]. |
28 | | - * |
29 | | - * Example 3: |
30 | | - * Input: target = [8,5] |
31 | | - * Output: true |
32 | | - * |
33 | | - * Constraints: |
34 | | - * N == target.length |
35 | | - * 1 <= target.length <= 5 * 10^4 |
36 | | - * 1 <= target[i] <= 10^9 |
37 | | - * */ |
38 | 6 | publicclass_1354 { |
39 | 7 | publicstaticclassSolution1 { |
40 | 8 | /** |
41 | 9 | * 1. A good idea/trick to calculate the previous value of the largest number max: (2 * max - total). |
42 | 10 | * 2. Use a PriorityQueue to store the elements in reverse order to help us get the largest element in O(1) time |
43 | 11 | * 3. Also keep a variable of total sum |
44 | | - * |
| 12 | + * <p> |
45 | 13 | * reference: https://leetcode.com/problems/construct-target-array-with-multiple-sums/discuss/510214/C%2B%2B-Reaching-Points-Work-Backwards |
46 | 14 | */ |
47 | 15 | publicbooleanisPossible(int[]target) { |
|