安徽合肥中国建设银行网站首页,茂名仿站定制模板建站,go网站开发,dw简述网站开发流程第七章 回溯算法 93.复原IP地址78.子集90.子集II代码随想录文章详解 93.复原IP地址
ip地址有效需要满足#xff1a;遍历完s#xff0c;将其分为4段#xff0c;每段数字有效性#xff1a;范围在[0,255],且不含前导零 为避免重复取值#xff0c;需要startIndex作为下次递归… 第七章 回溯算法 93.复原IP地址78.子集90.子集II代码随想录文章详解 93.复原IP地址
ip地址有效需要满足遍历完s将其分为4段每段数字有效性范围在[0,255],且不含前导零 为避免重复取值需要startIndex作为下次递归的初始位置。当遍历结束startIndex len(s)且ip段数为4 len(path) 4加入结果否则提前回溯。 如果当前字符串满足要求递归调用下一层
func restoreIpAddresses(s string) []string {res : []string{}path : []string{}var help func(s string, startIndex int)help func(s string, startIndex int) {if len(path) 4 {if startIndex len(s) {res append(res, strings.Join(path, .))}return}for i : startIndex; i len(s); i {str : s[startIndex : i1]if isValid(str) {path append(path, str)help(s, i1)path path[:len(path)-1]} else {break}}}help(s, 0)return res
}func isValid(str string) bool {if len(str) ! 1 str[0] 0 {return false}i, _ : strconv.Atoi(str)if i 255 {return false}return true
}78.子集
子集相当于找树的节点只要遍历到一个节点就加入结果
func subsets(nums []int) [][]int {res : [][]int{}path : []int{}var help func(nums []int, startIndex int)help func(nums []int, startIndex int) {tmp : make([]int,len(path))copy(tmp,path)res append(res, tmp)for i : startIndex; i len(nums); i {path append(path, nums[i])help(nums, i1)path path[:len(path)-1]}}help(nums, 0)return res
}90.子集II
相较于上题子集问题数组有重复元素要求结果集合不能重复需要去重 先对数组进行排序然后同层去重【否则相当于当前元素要走前一个元素已经走过的路】 同层去重used[i - 1] false,说明是从前一个元素回溯回来的若used[i - 1] true说明是进入下一个递归取值
func subsetsWithDup(nums []int) [][]int {res : [][]int{}path : []int{}used : make([]bool, len(nums))sort.Ints(nums)var help func(nums []int, startIndex int)help func(nums []int, startIndex int) {tmp : make([]int, len(path))copy(tmp, path)res append(res, tmp)for i : startIndex; i len(nums); i {if i 0 nums[i] nums[i-1] used[i-1] false {continue}path append(path, nums[i])used[i] truehelp(nums, i1)used[i] falsepath path[:len(path)-1]}}help(nums, 0)return res
}代码随想录文章详解
93.复原IP地址 78.子集 90.子集II
