对于算法中求 xxx 出现次数题型的解法的一个疑问

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2836 天前的主题，其中的信息可能已经有所发展或是发生改变。

算法题中有些求出现次数的题通常可以通过其中的值计算出来(而非条件成立后+=1 这样的方式),原理为何?

可能描述的不太清楚,举个例子
https://leetcode.com/problems/path-sum-iii/这道题的这一解法
https://discuss.leetcode.com/topic/64526/17-ms-o-n-java-prefix-sum-method

中的 res,通过一些运算就得到了最终的答案
以前也遇到过类似的题型,总是不太理解

算法

题型

res

次数

6 条回复 • 2017-02-17 02:26:33 +08:00

akking

2017-02-16 12:56:31 +08:00

我觉得你想问的是 backtracking 的原理吧？
凭空想的确挺难的，多做题就好了

zhy0216

2017-02-16 14:32:46 +08:00

@akking 这题没有用到 backtracking 吧?

我比较喜欢这个答案 https://discuss.leetcode.com/topic/69803/easy-to-understand-python-code

yongzhong

2017-02-16 15:18:37 +08:00

@zhy0216 这个解法看上去比较清晰,但仍然不是最优解,耗时达到了 200 多 ms.而且这个解法的思路也还是通过 result.count(sum)去判断是否相等,和上面提到的那个解法不太一样

zhy0216

2017-02-17 02:12:12 +08:00

我觉得是一样, 我改了下代码, 逻辑是一致的, 就是从数组->dict:

```python
def helper(self, root, sum):
from collections import defaultdict
if not root: return None

result = defaultdict(int)
result[root.val] += 1

left, right = self.helper(root.left, sum), self.helper(root.right, sum)

if left:
for key in left:
result[key+root.val] += left[key]
if right:
for key in right:
result[key+root.val] += right[key]

self.count += result[sum]

return result
```

不过不知怎么, 速度更慢了

zhy0216

2017-02-17 02:13:52 +08:00

上面的结构不好~~
http://pastebin.com/t8iTe6WB

akking

2017-02-17 02:26:33 +08:00

@zhy0216 为什么不是？ DFS 加上返回时删除这一步的计算结果。典型的 backtrack 。