category
type
status
date
slug
summary
tags
password
Property
Feb 18, 2023 02:48 AM
icon
去重相关题目
题目1:有重复字符串的排列组合
有重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合。示例1:输入:S = "qqe" 输出:["eqq","qeq","qqe"] 示例2:输入:S = "ab" 输出:["ab", "ba"] 提示:字符都是英文字母。 字符串长度在[1, 9]之间。
- 解决思路:
只要确保,向下遍历的每一层不会取同样的值即可避免重复,从而避免重复,不过需要提前对S进行字符排序
func permutation(S string) []string { // 重复版回溯增加的处理无非就是同一个位置不能同时取同一个值 // 因为这样会导致出现重复结果 // 先对字符串进行排序,使所有相同的字符处在相同的位置 var ans []string n := len(S) s := []byte(S) sort.Slice(s,func(i,j int)bool{ return s[i]<s[j] }) var dfs func(i int) dfs = func(i int){ if i==n{ ans=append(ans,string(s)) return } vis := make(map[byte]bool) for j:=i;j<n;j++{ // 利用hash表记录当层已经取过的值,以防重复在相同层取重复值 if vis[s[j]]{ continue } // 每个i位置的字符都可以与其右边的字符进行交换 // 从而构造全排列序列 vis[s[j]]=true s[i],s[j]=s[j],s[i] dfs(i+1) s[i],s[j]=s[j],s[i] } } dfs(0) return ans }
经典题目
题目1:解出n对括号的不同组合序列
括号。设计一种算法,打印n对括号的所有合法的(例如,开闭一一对应)组合。说明:解集不能包含重复的子集。例如,给出 n = 3,生成结果为:[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
- tips:这道题之前在面试金山云的时候手撕过🤣🤣🤣
- 方法一:利用剩余未使用左右括号数
func generateParenthesis(n int) []string { // my solution:可以使用回溯,最左的左括号按照每次隔着 // n-1,n-2...0个左括号的格式进行构建,然后递归下去,递归到底后回溯 var ans []string // leftCount,rightCount 分别记录剩余的左括号和右括号数 var dfs func(lw int, leftCount int, rightCount int, path []byte) dfs = func(lw int, leftCount int, rightCount int, path []byte) { if leftCount == 0 && rightCount == 0 { ans = append(ans, string(path)) return } // 每一层,左侧括号隔着的左括号共有0-leftCount-1种 // 左写3,剩余0,右要全写 // 左写2,剩余1,右可以1,也可以直接写2 // 左写1,剩余2,右必须写1 // 然后按照上述步骤递归 for i := leftCount; i > 0; i-- { // 这一步必须肯定写入了左括号,则下一步必须写入右括号 lw += i for j := 0; j < i; j++ { path = append(path, '(') } // 右边可以写1到已经写的左括号数个右括号 // k的数必须小于等于左边写入左括号数再减去左边已经写的右括号数 // min(lw-(n-rightCount), rightCount)是为了防止最后出现右括号未使用完毕的情况 for k := min(lw-(n-rightCount), rightCount); k > 0; k-- { for l := 0; l < k; l++ { path = append(path, ')') } dfs(lw, leftCount-i, rightCount-k, path) path = path[:len(path)-k] } lw -= i path = path[:len(path)-i] } } dfs(0, n, n, []byte{}) return ans } func min(a, b int) int { if a > b { return b } return a }
- 方法二:利用已使用左右括号数
func generateParenthesis(n int) []string{ // 方法二:思路更加清晰的回溯,利用已经使用左右括号数来解 var ans []string var dfs func(leftCount,rightCount int,path []byte) dfs = func(leftCount,rightCount int,path []byte){ if len(path)==n<<1{ ans=append(ans,string(path)) return } if leftCount<n{ path=append(path,'(') dfs(leftCount+1,rightCount,path) path=path[:len(path)-1] } if rightCount<leftCount{ path=append(path,')') dfs(leftCount,rightCount+1,path) path=path[:len(path)-1] } } dfs(0,0,[]byte{}) return ans }
- 作者:axiszql
- 链接:https://notion.axiszql.cn/article/algorithm-backtrack-01
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
相关文章