代码随想录day24 || 93 复原IP地址，78 子集， 90 子集2

93 复原ip地址

func restoreIpAddresses(s string) []string {
	// 字符串分割问题，考虑回溯算法
	var path, res []string
	if len(s) < 4 {
		return res
	}

	backtracking(s, &path, &res)
	return res
}
func backtracking(s string, path *[]string, res *[]string) {
	if len(s) == 0 && len(*path) == 4{
		//var copypath = make([]string, len(*path))
		//copy(copypath, *path)
		r := strings.Join(*path, ".")  // join操作将*path底层数组转换为字符串变量，所以不需要重新赋值
		*res = append(*res, r)
		return
	}

	// 剪枝
	if len(*path) > 4 {
		return
	}

	for i := 0; i < len(s); i++{
		if vaildIp(s[0 : i+1]) {
			*path = append(*path, s[0 : i+1])
			backtracking(s[i+1 : ], path, res)
			*path = (*path)[0 : len(*path) - 1]
		}
	}
	return
}

func vaildIp (s string) bool {
	// 处理0开头的两位或者三位ip
	if len(s) > 1 && s[0] == '0' {
		return false
	}
	ip, _ := strconv.Atoi(s)
	if ip > 255 {
		return false
	}
	return true
}

78 无重复元素子集

func subsets(nums []int) [][]int {
	// 子集问题，同样考虑回溯算法，但是这次要树的所有节点包括首位的空节点都要收集
	var path = []int{}
	var res = [][]int{}
	res = append(res, path) // 收集首位空节点
	backtracking(nums, &path, &res)
	return res
}

func backtracking(nums []int, path *[]int, res *[][]int) {
	if len(nums) == 0 {
		return
	}

	for i:=0; i<len(nums); i++{
		*path = append(*path, nums[i])

		// 对于path每次变动，res都要收录
		var copypath = make([]int, len(*path))
		copy(copypath, *path)
		*res = append(*res, copypath)

		backtracking(nums[i+1 : ], path, res)
		*path = (*path)[0 : len(*path) - 1]
	}
	return
}

90 有重复元素子集

func subsetsWithDup(nums []int) [][]int {
// 子集问题，同样考虑回溯算法，但是这次要树的所有节点包括首位的空节点都要收集，重复问题只需要先排序然后相邻元素判断相等跳过即可
var path = []int{}
var res = [][]int{}
res = append(res, path) // 收集首位空节点

nums = quicksort(nums)
backtracking(nums, &path, &res)
return res

}

func backtracking(nums []int, path *[]int, res *[][]int) {
if len(nums) == 0 {
return
}

for i:=0; i<len(nums); i++{
	// 去重
	if i > 0 && nums[i] == nums[i-1] {
		continue
	}
	*path = append(*path, nums[i])

	// 对于path每次变动，res都要收录
	var copypath = make([]int, len(*path))
	copy(copypath, *path)
	*res = append(*res, copypath)

	backtracking(nums[i+1 : ], path, res)
	*path = (*path)[0 : len(*path) - 1]
}
return

}

func quicksort(nums []int) []int{
if len(nums) == 0 {
return nil
}

// 每次根据nums长度随机选取一个值作为基准变量，避免都选取首位，出现【9，8，7，6，5，4，3，2，1】这种极端情况
r := rand.New(rand.NewSource(time.Now().Unix())) // 创建rand实例
povid := nums[r.Intn(len(nums))]

var left, right, equal []int
for _, num := range nums {
	if num > povid {
		right = append(right, num)
	}else if num < povid {
		left = append(left, num)
	}else {
		equal = append(equal, num)
	}
}

// 递归排序左右子数组并拼接结果
left = quicksort(left)
right = quicksort(right)
return append(left, append(equal, right...)...)

}