关于算法:每日一道算法题-20200826-回溯法解决递归问题

35次阅读

共计 737 个字符,预计需要花费 2 分钟才能阅读完成。

两道题放到一起说

首先是力扣的题 本质上是能转化成树的经典递归题 因为程序肯定 所以思路是先组成 HashMap 汇合 而后把依据输出的字母寻找到门路 在每次搜寻后须要删除这次的搜寻 所以是回溯 外围是

combination.append(str);                recursion(map,list,digits,index+1,combination);
combination.deleteCharAt(index);

同样
这道题一样能够用回溯法解决 惟一的区别是输出的形式不同,我的思路是遍历一次字母就删掉该字母

String letter = String.valueOf(str.charAt(i));
StringBuffer stringBuffer = new StringBuffer(str);
stringBuffer.deleteCharAt(i);
stringbuffer.append(letter);

这个中央还被好兄弟揭示了

stringbuffer.append(String.valueOf(str.charAt(i)))

这样写更简洁也更好了解


最初用回溯解决

recursion(list,index+1,stringBuffer.toString(),stringbuffer);
stringbuffer.deleteCharAt(index);

惟一的问题是 如果传入 ”AA” 字符串则可能会有反复输入,所以在最初进行了一次去重,题目上要求了依据字典输入所以用了 LinkedHashSet

 Set<String> set = new LinkedHashSet<String>();
 set.addAll(list);
 ArrayList<String> list1 = new ArrayList<String>(set);

正文完
 0