(给算法爱好者加星标,修炼编程内功)
来源: 五分钟学算法-P.yh
平时我们在解题的时候,如果遇到 TEL 的情况,往往我们的第一想法就是使用 动态规划,不过今天这道题使用 动态规划 貌似不太好使,而需要借助数学里面的一种思路:正难则反。
给你一个整数数组 target 。一开始,你有一个数组 A ,它的所有元素均为 1 ,你可以执行以下操作:
令 x 为你数组里所有元素的和
选择满足 0 <= i < target.size 的任意下标 i ,并让 A 数组里下标为 i 处的值为 x 。
你可以重复该过程任意次
如果能从 A 开始构造出目标数组 target ,请你返回 True ,否则返回 False 。
示例 1:
输入:target = [9,3,5]
输出:true
解释:从 [1, 1, 1] 开始
[1, 1, 1], 和为 3 ,选择下标 1
[1, 3, 1], 和为 5, 选择下标 2
[1, 3, 5], 和为 9, 选择下标 0
[9, 3, 5] 完成
示例 2:
输入:target = [1,1,1,2]
输出:false
解释:不可能从 [1,1,1,1] 出发构造目标数组。
示例 3:
输入:target = [8,5]
输出:true
提示:
N == target.length
1 <= target.length <= 5 * 10^4
1 <= target[i] <= 10^9
题目让你用一个元素全为 1 的数组构造一个 target 数组,规则是每一次操作可以将数组中所有元素的和赋值给其中一个元素,然后反复迭代进行,问你能否构建 target 数组。
这道题如果顺着题目想很难得到可行解,你可能会尝试使用暴力的深度优先搜索。
举个例子,你要构建 [9,3,5],起始数组是 [1,1,1],第一次迭代你得到了数组和为 3,那么这个 3 放在数组下标 0,1,2 三个位置都是可行的,你需要每个位置都尝试放一下,这么做是一种解法,但是时间复杂度是指数级别的,对这道题目的输入数据大小来说,不适用。
暴力搜索走不通,你或许会想当然的往动态规划的方向思考,但是这个方向也很难走通,原因在于你很难拆解问题,定义状态。因此这里我们应该换一种思考方式了。
既然从前往后思考问题得不出答案,那我们就倒着想。
我们从我们最后想要构建的数组出发(结果),往前推,看能不能推得出全为 1 的初始数组。
怎么推?在回答这个问题之前,我们首先要知道的是,数组元素之间的联系,根据题目描述,我们可以得知数组当前的所有元素和 sum 与最大的元素存在着一定的关系,sum 是下一次迭代的最大值,那么之前迭代的最大值是否可以根据这个计算出来呢?
答案是肯定的,我们来根据例子看看:
[a_max,a_2,a_3,...]
为了简便,我们令 a_other = a_2 + a_3 + ...
sum_prev = a_max // 之前的 sum 就是当前所有元素的最大值
sum_cur = a_max + a_other // 当前的 sum 就是当前所有元素之和
// 因为数组中的元素是在不断改变的,每次只变一个元素
// 如果要知道之前所有元素的最大值,我们必须还原当前改变的元素
// 当前改变的元素就是 a_max
sum_prev = a_prev + a_other = a_max
a_prev = sum_prev - a_other
= a_max - (sum_cur - a_max)
= 2 * a_max - sum_cur
通过上面的一系列推导,我们可以通过当前改变的值(最大值)推得出这个元素在改变之前的值,然后不断地反向推导,就能得出数组里面元素最原始的状态,我们再看是否能得到全为 1 的最原始的数组。
那么这里又存在一个问题,如何动态找出所有元素中的最大值?
这个简单,我们可以借助 最大堆 这个数据结构,它可以帮助我们在 logn 的时间维护一个排序好的序列。
有了这些,这道题基本上就可以解决了。
以上就是最为基本的解题思路,当然这道题目会存在一些比较极端的 case,比如 [1, 100000000] ,因此我们要对之前的解法进行优化。我们之前说过,我们需要考虑 sum 还有就是 max,但是当 max 相对于其他元素过于大的时候,我们需要对这一个元素反复做同样的事情很多次,这个过程能否简化呢?这里我们可以用一个取余的方法做到:
[2, 100]
sum = 102, max = 100, other = 2
sum = 100, max = 98, other = 2
sum = 98, max = 96, other = 2
...
// 如果 max 与 other 差距过大,每次迭代我们其实都在更新 max
// 因为 other 没有变,每次 max 减去的都是相同的值
// 这里,我们可以利用取余的方式来使得 max 一次性更新到刚好比 other 小的值
// end_max = max % other
参考代码
//author:P.yh
public boolean isPossible(int[] target) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
long sum = 0;
for (int i : target) {
pq.offer(i);
sum += i;
}
while (pq.peek() != 1) {
int max = pq.poll();
// 获得 other
sum -= max;
// other = 1,不管 max 是多少,都可以通过 1 不断迭代而成
if (sum == 1) {
return true;
}
// 由于是反向推,只减不加
// other 小于 1,说明无法构建
// other 必须小于 max 来保证 max 的正常迭代递减,不然 max 无法递减到 1
if (sum <= 0 || max <= sum) {
return false;
}
// 通过取余操作将 max 迭代到比 other 小的地方
max %= sum;
// other + prev_max = prev_sum
sum += max;
// prev_max 放入队列,继续迭代
pq.offer(max);
}
return true;
取余其实是一个很常用的数学技巧,能够很好地帮助我们节省时间。这道题目有点偏数学了,它的思想其实有点贪心的意思在里面,也就是把局部解衍生到全局。
通过这道题,其实告诉我们以后思考问题正着想不通,我们完全可以从结果出发,倒着想,说不定有奇效。
联系客服