0100-0149

Solutions to LeetCode Problems 0100-0149.

1: 0128.最长连续序列
2: 0129.求根节点到叶节点数字之和
3: 0132.分割回文串 II

1 - 0128.最长连续序列

https://leetcode.cn/problems/longest-consecutive-sequence/

方法一：HashSet

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

impl Solution {
    pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
        let mut set = std::collections::HashSet::new();
        for (_, &num) in nums.iter().enumerate() {
            set.insert(num);
        }
        let mut longest = 0;
        for num in nums {
            if !set.contains(&(num - 1)) {
                let mut current = num;
                let mut current_longest = 1;
                while set.contains(&(current + 1)) {
                    current += 1;
                    current_longest += 1;
                }
                longest = std::cmp::max(longest, current_longest);
            }
        }
        longest
    }
}

2 - 0129.求根节点到叶节点数字之和

https://leetcode.cn/problems/sum-root-to-leaf-numbers/

方法一：前序遍历

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
	var dfs func(root *TreeNode, value int) int
	dfs = func(root *TreeNode, value int) int {
		if root == nil {
			return 0
		}
		preSum := value*10 + root.Val
		if root.Left == nil && root.Right == nil {
			return preSum
		}
		return dfs(root.Left, preSum) + dfs(root.Right, preSum)
	}
	return dfs(root, 0)
}

3 - 0132.分割回文串 II

https://leetcode.cn/problems/palindrome-partitioning-ii/

方法一：动态规划

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

class Solution {
 public:
  int minCut(string s) {
    int n = s.size();
    vector<vector<bool>> g(n, vector<bool>(n, false));
    // construct palindrome map
    for (int end = 0; end < n; end++) {
      for (int start = 0; start <= end; start++) {
        if (s[start] == s[end] && (end - start < 2 || g[start + 1][end - 1])) {
          g[start][end] = true;
        }
      }
    }
    // define dp[n], dp[x] means min Cut
    vector<int> dp(n);
    iota(dp.begin(), dp.end(), 0);
    for (int end = 1; end < n; end++) {
      for (int start = 0; start <= end; start++) {
        if (g[start][end]) {
          dp[end] = min(dp[end], start ? dp[start - 1] + 1 : 0);
        }
      }
    }
    return dp[n - 1];
  }
};