leetcode上两道题的思考

zhangxiangliang 发布于2019-07-31 11:05 / 1613人阅读

摘要：求出满足这样要求的路径的数目，并返回。第二道题给定一个数，将其拆分为个平方数的和，求最小的。这道题不能用贪心算法求解。当时，如果用贪心算法，结果就是，返回。假设给出的数字为。第三轮减，得到，将放入队列中。

第一道题：
给定一棵二叉树，在二叉树的所有路径中找到路径上结点之和为题目给定值的子路径。路径不一定以根节点为开头，也不一定以叶节点为结尾。并且根据分析路径之间应该可以重叠。求出满足这样要求的路径的数目，并返回。

      10
     /  
    5   -3
   /     
  3   2   11
 /    
3  -2   1

当给出以上的二叉树，并以8为路径节点和时，5->3，5->2->1,-3->11三条路径满足条件返回三。

对于根节点来讲，满足条件的路径，包括以根节点为起点的路径，以及不以根节点为起点的路径。
我们先定义一个函数，这个函数有两个节点node和sum，它的含义是，求出从node开始的，路径上各节点之和为sum的这样的路径的个数。注意是从node开始的。

result初始化为0。如果当前node的value等于sum，则将result加1。由于可能会有负数节点，因此不能立刻返回result，应该分别再递归的去计算以node的左孩子和右孩子为起点，和为sum-node.value的路径的数目。
代码如下：

    def path_num_from(self, node, sum):
        if node is None:
            return 0

        res = 0
        if node.val == sum:
            res += 1

        res += self.path_num_from(node.left, sum - node.val)
        res += self.path_num_from(node.right, sum - node.val)

        return res

之前已经提到过，本题所求的路径不仅包含以根节点为起点的路径，还包含不以根节点为起点的路径。因此我们再定义一个函数，来算出，包含根节点的路径，和不包含根节点的路径。

    def __pathSum(self, node, sum):
        if node is None:
            return 0

        return self.find_path(node, sum) + self.__pathSum(node.left, sum) + self.__pathSum(node.right, sum)

题目得解。

第二道题：
给定一个数，将其拆分为n个平方数的和，求最小的n。
例如13 = 9 + 4 13 = 9 + 1 + 1 + 1 + 1
13是9和4两个平方数的和，也是9和4个1的和（如果用重复，按出现的次数计数，1计数4次而不是1次），因为2小于5，所以返回2。

这道题不能用贪心算法求解。
当n=12时，如果用贪心算法，结果就是9+1+1+1，返回4。但是更优的解是4+4+4，返回3。

假设给出的数字为n。先建立一个set。set中存放所有的，小于n的平方数。
比如给出数字13时，set中添加1,4,9。因为16大于13，所以不添加。
以15举例。set为 1,4,9。建立一个队列。

第一轮：
15减去9，得到6。将6放入队列中。
15减去4，得到11。将11放入队列中。
15减去1，得到14，将14放入队列中。
第一轮遍历完毕。此时队列中还有6,11,14

第二轮：
6比9小，所以不能再减9。
6减4，得到2，将2放入队列中。
6减1，得到5，将5放入队列中。
11减9，得到2，将2放入队列中。
11减4，得到7，将7放入队列中。
11减1，得到10，将10放入队列中。
第二轮遍历完毕。去掉重复的数，此时队列中还有2,5,7,10。

第三轮：
2减1，得到1，将1放入队列中。
5减4，得到1，将1放入队列中。
5减1，得到4，将4放入队列中。
7减4，得到3，将3放入队列中。
7减1，得到6，将6放入队列中。
10减4，得到6，将6放入队列中。
10减1，得到9，将9放入队列中。
第三轮遍历完毕。去掉重复元素，此时队列中还有1,3,4,6,9。

第四轮：
1减1，得到0。结束循环。直接返回此时层数。由于遍历了四轮，因此返回4。

代码如下：

 def numSquares(self, n):
        nums_to_subtract = []
        i = 1
        while i**2 <= n:
            nums_to_subtract.append(i**2)
            i += 1

        depth = 0
        current_level_nodes = {n}

        while True:
            nodes = current_level_nodes
            current_level_nodes = set()
            depth += 1
            for num_left in nodes:
                for num in nums_to_subtract:
                    if num_left < num:
                        break
                    elif num_left > num:
                        current_level_nodes.add(num_left - num)
                    else:
                        return depth

云服务器 GPU云服务器两道 asp返回上两页代码 Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44635.html

Leetcode：刷完31道链表题的一点总结

摘要：既然说到地址空间了就顺带说一下上面环形链表这道题的另一种很的解法吧。介绍完常规操作链表的一些基本知识点后，现在回到快慢指针。前几天第一次在 Segmentfault 发文—JavaScript：十大排序的算法思路和代码实现，发现大家似乎挺喜欢算法的，所以今天再分享一篇前两个星期写的 Leetcode 刷题总结，希望对大家能有所帮助。本文首发于我的blog 前言今天终于...

DevTalking 2019-08-23 17:50 评论0 收藏0
Two Sum系列 Leetcode解题记录

摘要：如果没有，就到里面复杂度分析就是，因为只扫了一遍数组。复杂度分析当然就是最坏情况了，也是标准的双指针复杂度。复杂度分析这种题应该不太需要分析复杂度吧，能实现就行。复杂度分析还是最后再说两句所以可以看出，很多题目思路一致，换汤不换药。 Two Sum 友情提示：篇幅较长，找题目的话，右边有目录，幸好我会MarkDown语法。改成了系列模式，因为类似的题不少，本质上都是换壳，所以在同一篇文...

andong777 2019-08-14 14:31 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0