活字印刷_组合总数
【摘要】 组合总和组合总和import java.util.LinkedList;import java.util.List;public class Solution { public static void DFS(int[] candidates, int pos, int target,int cur, List<List<Integer>> result, List<Integer>...
组合总和
import java.util.LinkedList;
import java.util.List;
public class Solution {
public static void DFS(int[] candidates, int pos, int target,int cur, List<List<Integer>> result, List<Integer> tmp){
if(cur>=target){
//保存一组解
if(cur==target)
result.add(new ArrayList<>(tmp));//这里需要通过 new ArrayList<>(tmp);拷贝到result中,
//result.add(tmp) //error!
return;
}
for(int i = pos;i<candidates.length;i++){
//处理当前位置!
tmp.add(candidates[i]);
//深度优先!
DFS(candidates,i,target,cur+candidates[i],result,tmp);
//DFS(candidates,i+1,target,cur+candidates[i],result,tmp);
// error 这里向下遍历下次拼接还是 i,因为这里的元素可以重复!
//回退!
tmp.remove(tmp.size()-1);
}
}
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new LinkedList<>();//保存解集!
List<Integer> tmp = new LinkedList<>();//保存一组解
DFS(candidates,0,target,0,result,tmp);
return result;
}
public static void main(String[] args) {
List<List<Integer>> lists = combinationSum(new int[]{2,3,4,5},7);
}
}
一组解不能直接
add
到结果集,这里只是一个引用,如果add
引用,最终str
改变,结果集中的元素也会改变,所以要通过构造方法!
new String(str)
拷贝到结果集中!这里 的 同一个数可以无限制的使用,那么深度遍历时就还要从当前位置开始!而不是
i+1
活字印刷
class Solution {
public void DFS(String tiles, Set<String> result,StringBuilder str,boolean[] book){
for(int i = 0;i<tiles.length();i++){
if(!book[i]){//当前字符没用过!
book[i] = true;//标记!
//保存当前位置!
str.append(tiles.charAt(i));
result.add(str.toString());
//深度遍历!
DFS(tiles,result,str,book);
//回退
str.deleteCharAt(str.length()-1);
//注意! 回退时记得把标记位也回退!
//我们已经删除了i下标的字符,那么i标记位也需要改变!
book[i] = false;
}
}
}
public int numTilePossibilities(String tiles) {
Set<String> result = new HashSet<>();//结果集(set去重)
boolean[] book = new boolean[tiles.length()];//标记数组
StringBuilder str = new StringBuilder();//保存一组结果!
DFS(tiles,result,str,book);
return result.size();
}
}
我们可以通过Set集合达到去重的效果! 这里的字符序列可以往前所以
i
要从0
开始!这里不需要
pos
位置,所以要有标记数组,标记该字符是否使用过!回退时,记得将标记位也回退!
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)