l***e
发帖数: 480 | 1 array: [3,1,2,4]
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,
1,2,4]
min * sum: 3*3,1*1,2*2,4*4,1*4,1*2,2*6,1*6,1*&,1*10
sum 9+1+4+16+4+2+12+6+10
搜leetcode,没搜到。只有907有点像(Sum of Subarray Minimums).但它的方法好像不
能用。
哪位有思路？ | n******g
发帖数: 2201 | 2 先理解题好不好 1,2,4 这个子集 min x sum =
1 x 7 你怎么没有写
3,
【在 l***e 的大作中提到】
: array: [3,1,2,4]
: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,
: 1,2,4]
: min * sum: 3*3,1*1,2*2,4*4,1*4,1*2,2*6,1*6,1*&,1*10
: sum 9+1+4+16+4+2+12+6+10
: 搜leetcode,没搜到。只有907有点像(Sum of Subarray Minimums).但它的方法好像不
: 能用。
: 哪位有思路？
| l***e
发帖数: 480 | 3 不是没写， 是写错了： 1*& == 1*7
sum里漏掉了。
感谢 指出。 | g****y
发帖数: 2810 | 4 没明白意思，没个数组的最小值乘以数组的和？然后把这些结果加在一起？
那不就遍历一遍就行了吗
3,
【在 l***e 的大作中提到】
: array: [3,1,2,4]
: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,
: 1,2,4]
: min * sum: 3*3,1*1,2*2,4*4,1*4,1*2,2*6,1*6,1*&,1*10
: sum 9+1+4+16+4+2+12+6+10
: 搜leetcode,没搜到。只有907有点像(Sum of Subarray Minimums).但它的方法好像不
: 能用。
: 哪位有思路？
| n******g
发帖数: 2201 | 5 哦谢谢 那我理解没错
暴力解 加memo 先排序 top down dp 具体怎么解我也没见过
尼码你们看看这些题太难了 我几年前刷过LC 一年不刷这样的题我是肯定做不出来的
但是这不合理 我的coding. 这些年明显提高了
【在 l***e 的大作中提到】
: 不是没写， 是写错了： 1*& == 1*7
: sum里漏掉了。
: 感谢 指出。
| l******r
发帖数: 1 | 6 https://leetcode.com/problems/sum-of-total-strength-of-wizards/
这题是难题。
竞赛的时候只有5%的accept rate。
不怎么暴力解 O(N^2)
神人才能给出O(N)的解法。
这里的大厂马公多，来挑战下。
🙈解答，先做做。
3,
【在 l***e 的大作中提到】
: array: [3,1,2,4]
: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,
: 1,2,4]
: min * sum: 3*3,1*1,2*2,4*4,1*4,1*2,2*6,1*6,1*&,1*10
: sum 9+1+4+16+4+2+12+6+10
: 搜leetcode,没搜到。只有907有点像(Sum of Subarray Minimums).但它的方法好像不
: 能用。
: 哪位有思路？
| l******r
发帖数: 1 | 7 他的方法不是不能用，是我等不会用。
那个大神就是用的这个方法，不过generalize了prefix sum这个东西。
【在 l******r 的大作中提到】
: https://leetcode.com/problems/sum-of-total-strength-of-wizards/
: 这题是难题。
: 竞赛的时候只有5%的accept rate。
: 不怎么暴力解 O(N^2)
: 神人才能给出O(N)的解法。
: 这里的大厂马公多，来挑战下。
: 🙈解答，先做做。
:
: 3,
| f*******t
发帖数: 7549 | 8 不要钻牛角尖，写个比暴力解好一点的应该就行了。如果哪个公司面试官傻逼到非要你
45分钟内给O（n）解，不去也罢。 | l***e
发帖数: 480 | 9 刚发现，这是 leetcode 2281. 真新啊！
leetcode要是能把每题的发布时间标出来，就好了！
油管上看了几个视频讲解 leetcode 907.感觉它的思路可以用，把求子数组的最小值转
成求每个值的最小区间，把o(n^3)转成o(n).
但是，求子数组的和，有什么好办法吗？
能想到的o(n^2) ? | l***e
发帖数: 480 | 10 leetcode现在真popular。
油管上都已经有讲解了！
🙏 多谢了，各位。 | g*****g
发帖数: 390 | 11 瞎说哈，先排序 O(nlogn) (does sorting change result?)
然后O(n^2)如下：
assume array [a, b, c, d] sorted
1) one element array: a^2 + b^2 + c^2 + d^2
2) two-element array: a(a+b) + b(b+c) + c(c+d)
= a^2 + ab + b^2 + bc + c^2 +cd
3) 3 element array: a(a+b+c) + b(b+c+d)
= a^2 + ab + ac + b^2 + bc + bd
4) 4 element array = a(a + b + c + d)
= a^2 + ab + ac + ad
the summary becomes:
4a^2 + 3b^2 + 2c^2 + d^2 each element itself, step = 0
+ 3ab + 2bc + cd continuous 2 element, step = 1
+ 2ac + bd every other 2 element, step = 2
+ ad step = 3
----
thinking really hard here, seems the result possibly could mathematically
relate to (but I don't now how to prove it):
（n-1）！ * sum^2 | n******g
发帖数: 2201 | 12 支持
排序使得min 就是 A[0]
少了一个复杂度 sum 还是要做的不偷懒
然后subset 还是要遍历
【在 g*****g 的大作中提到】
: 瞎说哈，先排序 O(nlogn) (does sorting change result?)
: 然后O(n^2)如下：
: assume array [a, b, c, d] sorted
: 1) one element array: a^2 + b^2 + c^2 + d^2
: 2) two-element array: a(a+b) + b(b+c) + c(c+d)
: = a^2 + ab + b^2 + bc + c^2 +cd
: 3) 3 element array: a(a+b+c) + b(b+c+d)
: = a^2 + ab + ac + b^2 + bc + bd
: 4) 4 element array = a(a + b + c + d)
: = a^2 + ab + ac + ad
|
|
