当前位置: 首页> 汽车> 车展 > 字体设计图片_徐州做网站的公司有哪些_人民网 疫情_广东深圳疫情最新

字体设计图片_徐州做网站的公司有哪些_人民网 疫情_广东深圳疫情最新

时间:2025/7/12 2:14:37来源:https://blog.csdn.net/shaui058/article/details/143595477 浏览次数: 0次
字体设计图片_徐州做网站的公司有哪些_人民网 疫情_广东深圳疫情最新

22. 括号生成
该算法题使用回溯来进行求解为最优,回溯重点为进如递归函数前改一下状态,出来后进行状态还原。复杂回溯可以结合备忘录模式来求解更为复杂的场景。回溯思考过程一般结合树来进行思考。以下是该题的思考过程。

思路一:错误思路
首先我想到的一个非回溯思路1如下:

// 创建一个空的list,用于存储所有满足条件的括号组合Set<String> sets = new HashSet();if (n <= 0)return new ArrayList(sets);sets.add("()");for(int i = 1; i < n; i++){String[] strs = sets.toArray(new String[sets.size()]);sets.clear();// 对于每一个上一次括号组合,根据在每一个元素左边、右边、左右进行添加for (String str:strs){sets.add("()" + str);sets.add(str + "()");sets.add("(" + str + ")");}}return new ArrayList(sets);

以上算法逻辑,1、把"()“加入一个集合sets中。2、复制该集合,并进行遍历,再每一个元素的前面加上”()“,后面加上”()“,元素前加”(“后加”)“。加入sets中进行去重。
该思路有一个明显的错误,会造成缺少某些组合,比如”(())(())"。因为以上策略,无法产生某些对称的组合。

思路二:非最优思路
思路二采用回溯来进行求解,回溯算法擅长于给定一个状态变量,每一次都来对该状态进行改变。

// 方法一:利用左右括号差集来减少回溯 回溯方法求解 n代表单个括号的数量、str代表回溯的位置字符串、diff代表左括号个数 - 右括号个数
public void generateParenthesisByBackTracking(int n, StringBuilder str, int diff){  if(str.length() == n ){if(diff != 0)  // 当两个括号相等时,才会加入lists集合return;lists.add(new String(str.toString()));return;}if (diff < n / 2){  // 添加左括号的条件str.append("("); generateParenthesisByBackTracking(n, str, diff + 1);str.deleteCharAt(str.length() - 1);}if(diff > 0){str.append(")");generateParenthesisByBackTracking(n, str, diff - 1);str.deleteCharAt(str.length() - 1);}}

以上思路是没有问题的,但是并非最优,因为在str.length() == n出口判断中,要判断左右括号是否相等,就说明存在部分枝干没有减掉(减枝),导致无效的递归。主要是在diff < n / 2判断处,因为diff代表左右括号数量的差,diff < n / 2减枝不彻底。因此,改进该算法,如下思路三。

加粗样式
该思路不使用diff而是换成left和right来实现。

   // 方法二:方法一中,在加入集合前依然要判断左右括号是否相等,说明在回溯过程中减枝不彻底,所以引入方法二 left right机制public void generateParenthesisByBackTracking(int n, StringBuilder str, int left, int right){  if(str.length() == n){lists.add(new String(str.toString()));return;}// 是否加入左括号if(left < n / 2){str.append("("); generateParenthesisByBackTracking(n, str, left + 1, right);str.deleteCharAt(str.length() - 1);}// 是否加入右括号if(left > right){str.append(")"); generateParenthesisByBackTracking(n, str, left, right + 1);str.deleteCharAt(str.length() - 1);}}

此处,在判断left < n / 2时,并非差,而是左括号,因此,将不正确的枝干减掉,没有一次是多余的递归。

关键字:字体设计图片_徐州做网站的公司有哪些_人民网 疫情_广东深圳疫情最新

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: