分类 算法 下的文章

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,
并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 
对于给定的输入,保证和为 target 的不同组合数少于 150 个。

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

解析

    涉及到排列组合问题,或者说求多个解的问题,都优先考虑DFS。套用DFS公式:

  • 找到递归边界:组合之和大于等于target,或者最新加入组合的元素大于等于target-sum(当前组合)
  • 再找到状态遍历:for range candidates,搜索树的每个节点都可以选取所有元素
  • 然后看如何递归进行状态转移,在这里由于每次搜索都增加一个元素,只要递归调用中更新当前组合就行,递归调用里基于入参往组合里添加元素
  • 最后考虑回溯,即当达到递归边界时,递归调用返回,当前分支搜索结束,进行下一个分支搜索,需要将调用递归前往当前组合中添加进来的元素剔除掉

实现


//用于获取所有组合
var targetFrom = make([][]int, 0)
//用于去重
var alreadyMap = make(map[string]struct{})

func getTargetBy(candidates []int, childSet []int, target int) bool {
    sum := intSum(childSet)
    //终止条件
    if sum >= target {
        if sum == target {
            return true
        }
        return false
    }

    length := len(candidates)
    for i := 0; i < length; i ++ {
        childSet = append(childSet, candidates[i])
        if getTargetBy(candidates, childSet, target) {
            tmpSet := make([]int, len(childSet))
            copy(tmpSet, childSet)
            key := getKey(tmpSet)
            if _, ok := alreadyMap[key]; !ok {
                targetFrom = append(targetFrom, tmpSet)
                alreadyMap[key] = struct{}{}
            }
        }
        //回溯
        childSet = childSet[:len(childSet)-1]
    }
    return false
}

func intSum(arr []int) int {
    sum := 0
    for _,v := range arr {
        sum += v
    }
    return sum
}

func getKey(arr []int) string {
    sort.Slice(arr, func(i, j int) bool {
        return arr[i] < arr[j]
    })
    key := ""
    for i,v := range arr {
        subKey := fmt.Sprintf("%v", v)
        if i == 0 {
            key = subKey
        } else {
            key += fmt.Sprintf("-%s", subKey)
        }
    }
    return key
}

题目

已有函数 rand13() ⽣成从 1 到 13 均匀分布的随机整数。请使⽤这⼀函数实现 rand5() ⽣成
⼀个从 1 到 5 均匀分布的随机整数。反之,如已有 rand5(),请据此实现 rand13()

解答

rand13 生成1~13的随机数,每个随机数出现的概率相等,即1~5出现的概率相等,即只获取1~5的随机数等同于rand5

for {
    v := rand13()
    if v <= 5 {
    break
    }
}

rand5 生成1~5的随机数,也可生成[5,10,15,20,25] 的随机数,即5*rand5,[1-5]与[5,10,15,20,25]的组合为[1,2,3,4,5,6,7,8,9,10,10,11,12,13,14,15,15,16,17,18,19,10,20,21,22,23,24,25,25,26,27,28,29,30],其中重复了[10,15,20,25],考虑将[10,15,20,25]转为[9,14,19,24],去除了重复值,随机数范围为[129],获取其中[113]部分

//[1,2,3,4,5] + [4,9,14,19,24]
for {
    v := rand5() + 5 * (rand5()-1)
    if v <= 13 {
        break
    }
}

题目:

请根据以下框架代码,编写函数 perm() ,打印输⼊字符串的所有排列。即对于字符串
ABC ,打印输出以下内容,不需要按照特定顺序。
ABC
ACB
BAC
BCA
CBA
CAB

框架代码:

package main
import "fmt"
// Perm() 对 a 形成的每⼀排列调⽤ f().
func Perm(a []rune, f func([]rune)) {
perm(a, f, 0) }
// 对索引 i 从 0 到 len(a) - 1,实现递归函数 perm().
func perm(a []rune, f func([]rune), i int) {
// TODO
}
func main() {
Perm([]rune("ABC"), func(a []rune) {
 fmt.Println(string(a)) }) }

实现:

package main

import "fmt"

// Perm() 对 a 形成的每⼀排列调⽤ f().
func Perm(a []rune, f func([]rune)) {
    perm(a, f, 0)
}

// 对索引 i 从 0 到 len(a) - 1,实现递归函数 perm().
func perm(a []rune, f func([]rune), i int) {
    alen := len(a)
    if i == alen {
        f(a)
        return
    }
    aMap := make(map[rune]struct{})
    for index := i; index < alen; index++ {
        //去重
        if _, ok := aMap[a[index]]; ok {
            continue
        }
        aMap[a[index]] = struct{}{}
        swap(a, index, i)
        //求i+1 从 len(a) - 1的全排列
        perm(a, f, i+1)
        swap(a, index, i)
    }
}

func swap(b []rune, i int, j int) {
    if i == j || b[j] == b[i] {
        return
    }
    tmp := b[j]
    b[j] = b[i]
    b[i] = tmp
}

func main() {
    Perm([]rune("ABC"), func(a []rune) {
        fmt.Println(string(a))
    })
}

  1. https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
  2. https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
  3. https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
  4. https://leetcode-cn.com/problems/longest-increasing-subsequence/
  5. https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
  6. https://leetcode-cn.com/problems/reorder-list/
  7. https://leetcode-cn.com/problems/reverse-linked-list-ii/
  8. https://leetcode-cn.com/problems/reverse-linked-list/
  9. https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
  10. https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
  11. https://leetcode-cn.com/problems/lru-cache/
  12. https://leetcode-cn.com/problems/OrIXps/
  13. https://leetcode-cn.com/problems/lru-cache-lcci/
  14. https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
  15. https://leetcode-cn.com/problems/binary-tree-right-side-view/
  16. https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
  17. https://leetcode-cn.com/problems/merge-k-sorted-lists/
  18. https://leetcode-cn.com/problems/min-stack/
  19. https://leetcode-cn.com/problems/spiral-matrix/
  20. https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
  21. https://leetcode-cn.com/problems/sqrtx/
  22. https://leetcode-cn.com/problems/3sum/
  23. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
  24. https://leetcode-cn.com/problems/palindrome-linked-list/
  25. https://leetcode-cn.com/problems/trapping-rain-water/
  26. https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
  27. https://leetcode-cn.com/problems/qiu-12n-lcof/
  28. https://leetcode-cn.com/problems/shopping-offers/
  29. https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
  30. https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
  31. https://leetcode-cn.com/problemset/all/?search=31&page=1
  32. https://leetcode-cn.com/problems/validate-binary-search-tree/