共计 4214 个字符，预计需要花费 11 分钟才能阅读完成。
第一题 括号生成
题目
动静布局解法
咱们能够将括号的生成看作
一直的在括号对中退出新的括号
这样对于 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）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。成果
正文完
