客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()" 1 public static List<string> GenerateParenthesesDPOpt(int n) 2 { 3 List<HashSet<string>> ret = new List<HashSet<string>>(); 4 ret.Add(new HashSet<string>(){""}); 5 6 for (int i = 1; i <= n; i++) 7 { 8 ret.Add(new HashSet<string>()); 9 foreach (var s in ret[i - 1]) 10 { 11 string temp = "()" + s; 12 ret[i].Add(temp); 13 14 temp = s + "()"; 15 ret[i].Add(temp); 16 17 temp = "(" + s + ")"; 18 ret[i].Add(temp); 19 20 for (int j = 0; j < s.Length; j++) //Credit to ffengfrank, Thank you! 21 { 22 if (s[j] == '(') 23 { 24 temp = s.Insert(j + 1, "()"); 25 ret[i].Add(temp); 26 } 27 } 28 } 29 } 30 31 return ret[n].ToList(); 32 }
代码分析： DP n = 1 : () n = 2 : ()(), ()()重复, (()) n = 3 : ()()(), ()()()重复, (()()), ()(()), (())(), ((())) ...... 利用HASHSET<string>减少时间复杂度。 每次比较的时间从O(n)到O(1) 感谢ffengfrank找到的bug，添加了20 ~ 27代码。
1 public static List<string> GenerateParenthesesRecursive(int n) 2 { 3 string result = ""; 4 List<string> ret = new List<string>(); 5 GenerateParenthesesRecursive(n, n, result, ret); 6 return ret; 7 } 8 9 public static void GenerateParenthesesRecursive(int left, int right, string result, List<string> ret) 10 { 11 if (left == 0 && right == 0) 12 { 13 ret.Add(result); 14 } 15 else 16 { 17 if (left > 0) 18 { 19 result += "("; 20 GenerateParenthesesRecursive(left - 1, right, result, ret); 21 result = result.Remove(result.Length - 1); 22 } 23 if (right > left) 24 { 25 result += ")"; 26 GenerateParenthesesRecursive(left, right - 1, result, ret); 27 result = result.Remove(result.Length - 1); 28 } 29 } 30 }
代码分析： 递归做法。
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期
今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知
今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道
今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要
我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多
今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不
电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很
我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法
今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win
今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎
请发表评论