早起刷题（Day 13）

LeetCode366. 寻找二叉树的叶子节点

#二叉树 #DFS

题目描述

给你一棵二叉树，请按以下要求的顺序收集它的全部节点：

1. 依次从左到右，每次收集并删除所有的叶子节点
2. 重复如上过程直到整棵树为空

示例:

输入: [1,2,3,4,5]
  
          1
         / \
        2   3
       / \     
      4   5    

输出: [[4,5,3],[2],[1]]
 

解释:

1. 删除叶子节点 [4,5,3] ，得到如下树结构：

          1
         / 
        2          
 

2. 现在删去叶子节点 [2] ，得到如下树结构：

          1          
 

3. 现在删去叶子节点 [1] ，得到空树：

          []         

解题思路

(1). 将叶子结点收集的过程相当于是收集树高相同的节点，所以只需要统计每个节点的高度并且将相同高度的节点加入同一索引的数组中；
(2). 创建一个二维数组 ret [][]int 来保存所有叶子结点，当节点的高度小于 len(ret) 时，可以直接在对应的高度索引数组中插入节点的值；否则就要 append ret 的长度。

解题代码

/**
* Definition for a binary tree node.
* type TreeNode struct {
* 	Val int
* 	Left *TreeNode
* 	Right *TreeNode
* }
*/

func findLeaves(root *TreeNode) [][]int {

	ret := [][]int{}
	if root == nil {
		return ret
	}
	
	var backTracking func(*TreeNode) int
	backTracking = func(p *TreeNode) int {
		if p == nil {
			return -1
		}

		height := 1+max(backTracking(p.Left), backTracking(p.Right))
		if height < len(ret) {
			ret[height] = append(ret[height], p.Val)
		} else {
			ret = append(ret, []int{p.Val})
		}
		
		return height
	}

	backTracking(root)

	return ret
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

LeetCode474. 一和零

#动态规划

题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
 

提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

解题思路

(1). 这道题可以看作是背包问题，但是和经典的背包问题只有一种容量不同，这道题有两种容量，即选取的字符串子集中的 0 和 1 的数量上限；
(2). 经典的背包问题可以使用二维动态规划求解，两个维度分别是物品和容量。这道题有两种容量，因此需要使用三维动态规划求解，三个维度分别是字符串、0 的容量和 1 的容量；
(3). 定义三维数组 dp，其中 dp[i][j][k] 表示在前 i 个字符串中，使用 j 个 0 和 k 个 1 的情况下最多可以得到的字符串数量。假设数组 strs 的长度为 l，则最终答案为 dp[l][m][n]。
(4). 当 0 和 1 的容量分别是 j 和 k 时，考虑以下两种情况：

• 如果 j<zeros 或 k<ones，则不能选第 i 个字符串，此时有 dp[i][j][k]=dp[i−1][j][k]；
• 如果j≥zeros 且 k≥ones，则如果不选第 i 个字符串，有 dp[i][j][k]=dp[i−1][j][k]，如果选第 i 个字符串，有 dp[i][j][k]=dp[i−1][j−zeros][k−ones]+1，dp[i][j][k] 的值应取上面两项中的最大值。
  因此状态转移方程如下：
  $d p[i][j][k]= \begin{cases}d p[i-1][j][k], & j<\text { zeros } \mid k<\text { ones } \ \max (d p[i-1][j][k], d p[i-1][j-\text { zeros }][k-\text { ones }]+1), & j \geq \text { zeros } & k \geq \text { ones }\end{cases}$

时间复杂度

O(L*M*N)

解题代码

func findMaxForm(strs []string, m int, n int) int {

	dp := make([][][]int, len(strs)+1)
	
	var numCount func(string) (int, int)
	numCount = func(s string) (int, int) {
		zeros, ones := 0, 0
		for i:=0; i<len(s); i++ {
			if s[i] == '0' {
				zeros++
			} else {
				ones++
			}
		}

		return zeros, ones
	}

	for i:=0; i<=len(strs); i++ {
		dp[i] = make([][]int, m+1)

		for j:=0; j<=m; j++ {
			dp[i][j] = make([]int, n+1)

			for k:=0; k<=n; k++ {

				if i == 0 {
					dp[i][j][k] = 0
					continue
				}

				zeros, ones := numCount(strs[i-1])
				if j<zeros || k<ones {
					dp[i][j][k] = dp[i-1][j][k]
				} else {
					dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones]+1)
				}
			}
		}
	}

	return dp[len(strs)][m][n]
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}