leetcode上兩道題的思考

zhangxiangliang 發布于2019-07-31 11:05 / 1698人閱讀

摘要：求出滿足這樣要求的路徑的數目，并返回。第二道題給定一個數，將其拆分為個平方數的和，求最小的。這道題不能用貪心算法求解。當時，如果用貪心算法，結果就是，返回。假設給出的數字為。第三輪減，得到，將放入隊列中。

第一道題：
給定一棵二叉樹，在二叉樹的所有路徑中找到路徑上結點之和為題目給定值的子路徑。路徑不一定以根節點為開頭，也不一定以葉節點為結尾。并且根據分析路徑之間應該可以重疊。求出滿足這樣要求的路徑的數目，并返回。

      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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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