活字印刷_组合总数

举报
bug郭 发表于 2022/08/27 00:26:42 2022/08/27
【摘要】 组合总和组合总和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>...

组合总和

组合总和

image-20220507151217709

image-20220507151056333

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

活字印刷

活字印刷

image-20220507160144973

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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。