128. 最長連續序列

給定一個未排序的整數數組 nums ，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。

請你設計並實現時間複雜度為 O(n) 的算法解決此問題。

 

示例 1：

輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長數字連續序列是 [1, 2, 3, 4]。它的長度為 4。

示例 2：

輸入：nums = [0,3,7,2,5,8,4,6,0,1]
輸出：9

示例 3：

輸入：nums = [1,0,1,2]
輸出：3

 

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109


class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Arrays.sort(nums);
        int j=1;
        int max=1;
        for (int i = 0; i < nums.length-1; i++) {
            if(nums[i]+1 == nums[i+1]){
                ++j;
            }
            else if(nums[i] == nums[i+1])
            {
               continue;
            }
            else 
            {
                max=Math.max(max,j);
                j=1;
            }
        }
        max=Math.max(max,j);
        return max;
    }
}

129. 求根節點到葉節點數字之和

給你一個二叉樹的根節點 root ，樹中每個節點都存放有一個 0 到 9 之間的數字。

每條從根節點到葉節點的路徑都代表一個數字：

  • 例如，從根節點到葉節點的路徑 1 -> 2 -> 3 表示數字 123 。

計算從根節點到葉節點生成的 所有數字之和 。

葉節點 是指沒有子節點的節點。

 

示例 1：

128. 最長連續序列，129. 求根節點到葉節點數字之和_數組

1->2
12
1->3
13
25

示例 2：

128. 最長連續序列，129. 求根節點到葉節點數字之和_數組_02

4->9->5
4->9->1
4->0
1026

 

提示：

  • 樹中節點的數目在範圍 [1, 1000] 內
  • 0 <= Node.val <= 9
  • 樹的深度不超過 10
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    
    private int dfs(TreeNode node, int sum){
        if(node == null) return 0; //dfs 出口
        sum = sum * 10 + node.val;

        if(node.left == null && node.right == null){ //node.left == node.right == null 這麼寫是錯誤的
            return sum;
        }
        //向左右子樹繼續 dfs，左子樹返回的路徑數字 + 右子樹返回的路徑數字
        return dfs(node.left, sum) + dfs(node.right, sum);
    }
}