题目 memorable

leetcode:46

代码与解析

这题卡我挺长时间。
借鉴了carl大佬的思路,尤其文章中的那个图,讲解的很到位,

这里借鉴一下carl大佬博客的一张图(如有冒犯请联系我,立即删除)

这道题和491题不同
491题里面used数组是用来去重的,虽说这道题也是用来去重,他的主要作用是标记在这一个树杈里面用了哪些元素。

排列和组合不一样,排列是有序的,[1,2,3]和[3,2,1]是两个不同的排列, 元素1在[1,2,3]里面已经使用过一次了,但在[3,2,1]里面还要再使用一次,所以就不用使用startIndex了。需要使用used数组来标记一个树杈中已经选择的元素

回溯三部曲:

  • 确定参数及返回值
    不需要参数和返回值

  • 确定终止条件
    path数组长度等于给定数组长度时,将path结果转移到res

if len(path)==len(nums){
    tmp := make([]int, len(path))
    copy(tmp, path)
    res = append(res, tmp)
    return 
}
    //切记这个要复位
    used[nums[i]+10] = 0

因为每个小树杈的情况是不同的,前一个树杈使用过后,后一个还要使用,不清空的话,后一个树杈会以为该元素已经使用了。

for i:=0;i<len(nums); i++{
    if used[nums[i]+10]==1{
        continue
    }

    used[nums[i]+10] = 1
    // fmt.Println(used)
    path = append(path, nums[i])
    backtracking()
    path = path[:len(path)-1]
    // 切记这个要复位
    used[nums[i]+10] = 0
}

或许这种方式更容易理解

for i:=0;i<len(nums); i++{
    if used[i]==1{
        continue
    }

    used[i] = 1
    path = append(path, nums[i])
    backtracking()
    path = path[:len(path)-1]
    used[i] = 0
}

整体代码:

func permute(nums []int) [][]int {
    res := [][]int{}
    path := []int{}
    used := make([]int, 21)
    var backtracking func()
    backtracking = func(){
        if len(path)==len(nums){
            tmp := make([]int, len(path))
            copy(tmp, path)
            res = append(res, tmp)
            return 
        }
        // used = make([]int, 21)
        for i:=0;i<len(nums); i++{
            if used[i]==1{
                continue
            }
            used[i] = 1
            // fmt.Println(used)
            path = append(path, nums[i])
            backtracking()
            path = path[:len(path)-1]
            used[i] = 0
        }
    }
    backtracking()
    return res
}
分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:975 天
  • 访问总数:73233 人次

浙公网安备33011302000604

辽ICP备20003309号