Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (27) 另一个树的子树 全排列II 圆圈中最后剩下的数字 组合总和II

发表于 更新于 分类于

另一个树的子树

另一个树的子树

解题思路

在root的每一个节点上，判断以这个节点为根的树是否与subRoot相同。

判断两个树是否相等的三个条件是与的关系，即：

  1. 当前两个树的根节点值相等；
  2. 并且，root1的左子树和root2的左子树相等；
  3. 并且，root1的右子树和root2的右子树相等。

而判断 一棵树是否是另一棵树的子树的三个条件是或的关系，即：

  1. 当前两棵树相等；
  2. 或者，subRoot在root的左子树中；
  3. 或者，subRoot在root的右子树中。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil && subRoot == nil {
        // 两棵树都为空
        return true
    } else if root == nil || subRoot == nil {
        // 二叉树和子树一个为空，一个不为空
        return false
    } else {
        // 二叉树和子树都不为空
        return isSame(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
    }
}

// 判断两棵树是否是结构和值相同的树
func isSame(root1 *TreeNode, root2 *TreeNode) bool {
    if root1 == nil && root2 == nil {
        // 都为空树
        return true
    } else if root1 == nil || root2 == nil {
        // 一棵树为空，另一棵树不为空
        return false
    } else {
        // 两棵树都不为空
        return root1.Val == root2.Val && isSame(root1.Left, root2.Left) && isSame(root1.Right, root2.Right)
    }
}

全排列 II

全排列 II

解题代码

利用回溯算法，关键在于如何去重：对于两个相同的数字，可以有三种处理的方法，两个都选、两个都不选、如果选择一个那么选哪个都一样，最后一种情况需要考虑去重。

  • 首先将数组排序

  • 有效结果：当选择的数字个数等于数组长度时，得到一个有效的结果

  • 剪枝条件：

    • 若当前数字已经被选择，则剪枝
    • 若当前数字与前一个数字相同，且前一个数字没有被选择，则剪枝

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func permuteUnique(nums []int) [][]int {
    n := len(nums)
    path := make([]int, 0)          // 记录已经选择的数字 
    res := make([][]int, 0)           // 记录返回的结果
    chosen := make([]bool, n)       // 记录对各个数字的选择情况
    var backtrack func()
    backtrack = func() {
        if len(path) == n {
            // 选择了足够的数字，将选择的数字加入结果
            tmp := make([]int, n)
            copy(tmp, path)
            res = append(res, tmp)
            return
        }

        for i := 0; i < n; i++ {
            // 当前元素选了，剪枝
            if chosen[i] {
                continue
            }
            // 若与前一个元素相同，且前一个没有选，则剪枝
            if i > 0 && nums[i-1]==nums[i] && !chosen[i-1] {
                continue
            }
            // 选择nums[i]
            chosen[i] = true
            path = append(path, nums[i])
            backtrack()
            // 恢复状态
            chosen[i] = false
            path = path[:len(path)-1]
        }
    }

    // 先对数组进行排序
    sort.Ints(nums)
    // 再进行回溯算法
    backtrack()

    return res
}

圆圈中最后剩下的数字

圆圈中最后剩下的数字

解题思路

  1. 构建循环链表，模拟删除过程（超时）
  2. 数学推导：最后只剩下一个元素，假设这个最后存活的元素为num，这个元素最终的的下标一定是0（因为最后只剩这一个元素），所以如果我们可以推出上一轮次中这个num的下标，然后根据上一轮num的下标推断出上上一轮num的下标，直到推断出元素个数为n的那一轮num的下标，那我们就可以根据这个下标获取到最终的元素了：
    • 首先最后一轮中num的下标一定是0， 这个是已知的。
    • 那上一轮应该是有2个元素，此轮次中num的下标为(0 + m)%2
    • 再上一轮应该是有3个元素，此轮次中num的下标为(上一轮次下标 + m)%3
    • ……
    • 总结一下推导公式(此轮过后的num下标 + m) % 上轮元素个数 = 上轮num的下标

解题代码

  1. 构建循环链表，模拟删除过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 循环链表节点
type LinkList struct {
    val int
    next *LinkList
}

func lastRemaining(n int, m int) int {
    head, rear := buildLinkList(n)    // 构建一个循环链表
    // 下面开始模拟删除过程，删除n-1个元素
    cur := head         // 当前遍历元素
    pre := rear         // 当前遍历元素的前驱
    for n > 1 {
        // 找到第m个节点
        for i := 1; i < m; i++ {
            pre = cur
            cur = cur.next
        }
        // 删除第m个节点
        pre.next = cur.next
        // 下一次从删除后的下一个数字开始计数
        cur = pre.next
        n--
    }

    return cur.val
}

// 根据0, 1, 2, ..., n-1构造一个循环链表，返回链表头和链表尾
func buildLinkList(n int) (*LinkList, *LinkList) {
    head := &LinkList{ val: 0 }     // 指向循环链表头
    rear := head                    // 指向循环链表的最后一个节点
    for i := 1; i < n; i++ {
        newNode := &LinkList{ val: i }
        rear.next = newNode
        rear = newNode
    }
    // 最后一个节点连接到第一个节点，构成循环特性
    rear.next = head

    return head, rear
}
  1. 数学推导
1
2
3
4
5
6
7
8
9
func lastRemaining(n int, m int) int {
    ans := 0        // 最后一轮剩下的元素下标必然是0
    // 从倒数第2轮开始反推
    for i := 2; i <= n; i++ {
        ans = (ans + m) % i
    }

    return ans
}

组合总和 II

组合总和 II

解题思路

利用回溯算法，与前面的一样，关键是在于如何去重。

  • 首先将数组排序

  • 有效的结果：若当前选择的数字之和为target，则加入结果集

  • 剪枝条件：

    • 同一层中，与前面的数字相同，剪枝
    • 加上当前元素已经大于目标值，剪枝

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func combinationSum2(candidates []int, target int) [][]int {
    path := make([]int, 0)      // 记录已经选择的数字
    res := make([][]int, 0)     // 记录返回结果
    var backtrack func(begin int, curSum int)
    backtrack = func(begin int, curSum int) {      // begin为下一个待判断的数字下标，curSum为当前已经选择的数字之和
        if curSum == target {
            // 数字之和为目标值，加入结果之中
            tmp := make([]int, len(path))
            copy(tmp, path)
            res = append(res, tmp)
        }

        for i := begin; i < len(candidates); i++ {
            // 若与前一个元素相同，则剪枝
            if i > begin && candidates[i] == candidates[i-1] {
                continue
            }
            // 加上当前元素已经大于目标值，中止循环，剪枝（因为后面的数字大于等于当前数字，后边的不用判断了）
            if curSum+candidates[i] > target {
                break
            }
            // 选择candidates[i]
            path = append(path, candidates[i])
            backtrack(i+1, curSum+candidates[i])
            // 恢复状态
            path = path[:len(path)-1]
        }
    }

    // 首先进行排序
    sort.Ints(candidates)
    // 再进行回溯算法
    backtrack(0, 0)

    return res
}