|
29 | 29 | */ |
30 | 30 | publicclass_410 { |
31 | 31 |
|
32 | | -/**credit: https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java |
33 | | - * |
34 | | - * The answer is between maximum value of input array numbers and sum of those numbers. |
35 | | - Use binary search to approach the correct answer. |
36 | | - We have l = max number of array; |
37 | | - r = sum of all numbers in the array; |
38 | | - Every time we do mid = (l + r) / 2; |
| 32 | +publicstaticclassSolution1 { |
| 33 | +/** |
| 34 | + * credit: https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java |
| 35 | + * |
| 36 | + * The answer is between maximum value of input array numbers and sum of those numbers. Use |
| 37 | + * binary search to approach the correct answer. We have l = max number of array; r = sum of all |
| 38 | + * numbers in the array; Every time we do mid = (l + r) / 2; |
| 39 | + * |
| 40 | + * Use greedy to narrow down left and right boundaries in binary search. 3.1 Cut the array from |
| 41 | + * left. 3.2 Try our best to make sure that the sum of numbers between each two cuts (inclusive) |
| 42 | + * is large enough but still less than mid. 3.3 We'll end up with two results: either we can |
| 43 | + * divide the array into more than m subarrays or we cannot. If we can, it means that the mid |
| 44 | + * value we pick is too small because we've already tried our best to make sure each part holds |
| 45 | + * as many non-negative numbers as we can but we still have numbers left. So, it is impossible |
| 46 | + * to cut the array into m parts and make sure each parts is no larger than mid. We should |
| 47 | + * increase m. This leads to l = mid + 1; If we can't, it is either we successfully divide the |
| 48 | + * array into m parts and the sum of each part is less than mid, or we used up all numbers |
| 49 | + * before we reach m. Both of them mean that we should lower mid because we need to find the |
| 50 | + * minimum one. This leads to r = mid - 1; |
| 51 | + */ |
39 | 52 |
|
40 | | - Use greedy to narrow down left and right boundaries in binary search. |
41 | | - 3.1 Cut the array from left. |
42 | | - 3.2 Try our best to make sure that the sum of numbers between each two cuts (inclusive) is large enough but still less than mid. |
43 | | - 3.3 We'll end up with two results: either we can divide the array into more than m subarrays or we cannot. |
44 | | - If we can, it means that the mid value we pick is too small because we've already |
45 | | - tried our best to make sure each part holds as many non-negative numbers as we can |
46 | | - but we still have numbers left. |
47 | | - So, it is impossible to cut the array into m parts and make sure each parts is no larger than mid. |
48 | | - We should increase m. This leads to l = mid + 1; |
49 | | - If we can't, it is either we successfully divide the array into m parts and |
50 | | - the sum of each part is less than mid, |
51 | | - or we used up all numbers before we reach m. |
52 | | - Both of them mean that we should lower mid because we need to find the minimum one. This leads to r = mid - 1;*/ |
53 | | - |
54 | | -publicintsplitArray(int[]nums,intm) { |
55 | | -intmax =0; |
56 | | -longsum =0; |
57 | | -for (intnum :nums) { |
58 | | -max =Math.max(num,max); |
59 | | -sum +=num; |
60 | | - } |
61 | | -if (m ==1) { |
62 | | -return (int)sum; |
63 | | - } |
64 | | -//binary search |
65 | | -longl =max; |
66 | | -longr =sum; |
67 | | -while (l <=r) { |
68 | | -longmid = (l +r) /2; |
69 | | -if (valid(mid,nums,m)) { |
70 | | -r =mid -1; |
71 | | - }else { |
72 | | -l =mid +1; |
| 53 | +publicintsplitArray(int[]nums,intm) { |
| 54 | +intmax =0; |
| 55 | +longsum =0; |
| 56 | +for (intnum :nums) { |
| 57 | +max =Math.max(num,max); |
| 58 | +sum +=num; |
| 59 | + } |
| 60 | +if (m ==1) { |
| 61 | +return (int)sum; |
73 | 62 | } |
| 63 | +//binary search |
| 64 | +longl =max; |
| 65 | +longr =sum; |
| 66 | +while (l <=r) { |
| 67 | +longmid = (l +r) /2; |
| 68 | +if (valid(mid,nums,m)) { |
| 69 | +r =mid -1; |
| 70 | + }else { |
| 71 | +l =mid +1; |
| 72 | + } |
| 73 | + } |
| 74 | +return (int)l; |
74 | 75 | } |
75 | | -return (int)l; |
76 | | - } |
77 | 76 |
|
78 | | -publicbooleanvalid(longtarget,int[]nums,intm) { |
79 | | -intcount =1; |
80 | | -longtotal =0; |
81 | | -for (intnum :nums) { |
82 | | -total +=num; |
83 | | -if (total >target) { |
84 | | -total =num; |
85 | | -count++; |
86 | | -if (count >m) { |
87 | | -returnfalse; |
| 77 | +publicbooleanvalid(longtarget,int[]nums,intm) { |
| 78 | +intcount =1; |
| 79 | +longtotal =0; |
| 80 | +for (intnum :nums) { |
| 81 | +total +=num; |
| 82 | +if (total >target) { |
| 83 | +total =num; |
| 84 | +count++; |
| 85 | +if (count >m) { |
| 86 | +returnfalse; |
| 87 | + } |
88 | 88 | } |
89 | 89 | } |
| 90 | +returntrue; |
90 | 91 | } |
91 | | -returntrue; |
92 | 92 | } |
93 | | - |
94 | 93 | } |