乐趣区

关于golang:golangleetcode中级括号生成全排列

jiezi

第一题 括号生成

题目

动静布局解法

咱们能够将括号的生成看作
一直的在括号对中退出新的括号
这样对于 n 对括号的生成 咱们便能在 n - 1 对括号中进行操作


参考
https://leetcode-cn.com/probl…
https://leetcode-cn.com/probl…

java 版本

递归实现

// 9ms
public List<String> generateParenthesis(int n) {List<String> res = new LinkedList<>();
    if (n == 0) {res.add("");
        return res;
    }
    for (int i = 0; i < n; i++) {
        int j = n - i - 1;
        List<String> iRes = generateParenthesis(i);
        List<String> jRes = generateParenthesis(j);
        for (String s1 : iRes) {for (String s2 : jRes) {res.add(s1 + "(" + s2 + ")");
            }
        }
    }
    return res;
}

作者：fan-lu-5
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/java-0ms-cong-zhao-gui-lu-dao-xuan-ding-2qm9t/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

将小于 n 的计算结果存储起来供后续计算应用，缩小反复计算

// 8ms
public List<String> generateParenthesis(int n) {Map<Integer, List<String>> mem = new HashMap<>();
    return dp(n, mem);
}

private List<String> dp(int n, Map<Integer, List<String>> mem) {if (mem.containsKey(n))
        return mem.get(n);
    List<String> res = new LinkedList<>();
    if (n == 0) {res.add("");
        return res;
    }
    for (int i = 0; i < n; i++) {
        int j = n - i - 1;
        List<String> iRes = dp(i, mem);
        List<String> jRes = dp(j, mem);
        for (String s1 : iRes) {for (String s2 : jRes) {res.add(s1 + "(" + s2 + ")");
            }
        }
    }
    mem.put(n, res);
    return res;
}

作者：fan-lu-5
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/java-0ms-cong-zhao-gui-lu-dao-xuan-ding-2qm9t/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

go 版本

递归实现

func generateParenthesis(n int) []string {var res []string
    if n == 0 {res=append(res,"")
        return res
    }
    // i 从 0 到 n -1 j 从 n - 1 到 0
    for i := 0; i < n; i++ {
        j := n - i - 1
        // 生成 i 和 j 的括号序列
        iRes := generateParenthesis(i)
        jRes := generateParenthesis(j)
        for _,s1:=range iRes {
            for _,s2:=range jRes {res=append(res,s1 + "(" + s2 + ")")
                }
            }
        }
    return res
}

成果

退出存储

func generateParenthesis(n int) []string {var mem map[int][]string
    // 如果没有对 mem 进行初始化，只进行申明 那么 mem 默认为 nil
    // 在对 mem 进行赋值操作时会抛出一个 panic 异样
    mem = make(map[int][]string)
    return dp(n, mem)
}
func dp(n int, mem map[int][]string) []string {if value, ok := mem[n];ok{return value}
    var res []string
    if n == 0 {res=append(res,"")
        return res
    }
    for i := 0; i < n; i++ {
        j := n - i - 1
        iRes := dp(i, mem)
        jRes := dp(j, mem)
        for _,s1:=range iRes {
            for _,s2:=range jRes {res=append(res,s1 + "(" + s2 + ")")
            }
        }
    }
    mem[n]=res
    return res
}

成果

官解 从暴力到回溯

暴力解法


go 版本

func generateParenthesis(n int) []string {var combinations []string
    num := make([]byte, 2*n)
    generateAll(&num, 0,&combinations)
    return combinations
}
func generateAll(current *[]byte, pos int, result *[]string) {if pos == len(*current) {if valid(*current) {*result = append(*result, string(*current))
        }
    } else {(*current)[pos] = '('
        generateAll(current, pos+1, result)
        (*current)[pos] = ')'
        generateAll(current, pos+1, result)
    }
}
func valid(current []byte) bool {
    balance := 0
    for _,c := range current {
        if c == '(' {balance++} else {balance--}
        if balance < 0 {return false}
    }
    return balance == 0
}

func generateParenthesis(n int) []string {res = []string{}
    run([]byte{}, 2 * n)
    return res
}

var res []string

func run(cur []byte, n int) {
    if n == 0 {if isValid(cur) {res = append(res, string(cur))
        }
        return
    }
    tpl := []byte{'(', ')'}
    for i := 0; i < len(tpl); i++ {cur = append(cur, tpl[i])
        run(cur, n - 1)
        cur = cur[:len(cur)-1]
    }
}

func isValid(cur []byte) bool {var st []byte
    for i := 0; i < len(cur); i++ {if cur[i] == '(' {st = append(st, cur[i])
            continue
        }
        if len(st) == 0 {return false}
        st = st[:len(st)-1]
    }
    return len(st) == 0
}

作者：dfzhou6
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/jian-dan-yi-dong-go-by-dfzhou6-frkl/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

第二题 全排列

题目

递归

每次在 nums 中挑出一个数作为第一个数，剩下的数进行排列之后放在第一个数前面

剩下的数又能够调用该函数持续实现全排列

反复 n 次，就实现了所有可能性的组合

代码

func permute(nums []int) [][]int {var res [][]int
    if len(nums) == 0 {return res}
    var n []int
    if len(nums) == 1 {n = append(n, nums[0])
        res = append(res, n)
    }
    for i := 0; i < len(nums); i++ {n = append(n, nums[i])
        co :=make([]int,len(nums))
        copy(co, nums)
        co[0], co[i] = co[i], co[0]
        pers := permute(co[1:])
        for _, per := range pers {nn := append(n, per...)
            res = append(res, nn)
        }
        n = nil
    }
    return res
}

后果

尽管递归的工夫复杂度比拟快，但在数量级比拟高的时候递归调用栈应用的空间会比拟大

回溯法

https://leetcode-cn.com/probl…

var res [][]int
func permute(nums []int) [][]int {res = [][]int{}
    backTrack(nums,len(nums),[]int{})
    return res
}
func backTrack(nums []int,numsLen int,path []int)  {if len(nums)==0{p:=make([]int,len(path))
        copy(p,path)
        res = append(res,p)
    }
    for i:=0;i<numsLen;i++{cur:=nums[i]
        path = append(path,cur)
        nums = append(nums[:i],nums[i+1:]...)// 间接应用切片
        backTrack(nums,len(nums),path)
        nums = append(nums[:i],append([]int{cur},nums[i:]...)...)// 回溯的时候切片也要还原，元素地位不能变
        path = path[:len(path)-1]

    }
}


作者：carlsun-2
链接：https://leetcode-cn.com/problems/permutations/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-hui-s-mfrp/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

成果

退出移动版