数组有序

例题:https://blog.devilwst.top/2021/12/31/子集-回溯/
去重方法可以用

if i>start&&nums[i]==nums[i-1]{
    continue
}

数组无序

树层去重

例题:https://blog.devilwst.top/2022/01/01
去重方法可以用

// 模板
used := make([]int, 201)
for xx;xx;xx{
    // 本层去重
    if used[nums[i]] == 1{
        continue
    }
    used[nums[i]] = 1
}
// 具体应用
used := make([]int, 201)
for i:=start;i<len(nums); i++{
    // 之前的去重逻辑不行, 因为这次数组不是有序的
    // if i>start&&nums[i]==nums[i-1]{
    //     continue
    // }

    // 本层去重
    if used[nums[i]+100] == 1{
        continue
    }
    used[nums[i]+100] = 1
    // path = append(path, nums[i])
    // backtracking(i+1)
    // path = path[:len(path)-1]
}

树杈去重

例题:https://blog.devilwst.top/2022/01/01
可以用:

// 模板
for i:=0;i<len(nums); i++{
    if used[i]==1{
        continue
    }
    used[i] = 1
    // backtracking()
    // 在递归完归位, 当前树杈搜索完了,要复原
    used[i] = 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
}
分类: 算法

站点统计

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

浙公网安备33011302000604

辽ICP备20003309号