|
3 | 3 | import java.util.Collections;
|
4 | 4 | import java.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 | public class _1354 {
|
39 | 7 | public static class Solution1 {
|
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 | public boolean isPossible(int[] target) {
|
|
0 commit comments