JAVA实现字符串之间的组合方式-(使用回溯加双端算法)

Java技术教程 收藏
0 70

前奏
回溯特点:就是方法调用本身自己实现一个回溯效果,注意调用之后的回溯方法中一定要有结束条件否则会出现栈溢出错误
栈特点:  就是中数据结构其存入顺序是先进后出
双端队列:就是结合了普通队列和栈的特点的数据结构

注意事项和问题思路
实现:用到了,回溯(用于循环多少次),双端队列(存储各个回溯中对应的循环索引值)
 注意:各个回溯循环对应的字符串索引都是不一样的
 思路:
  1 将对应的各个回溯层的循环索引保存起来
  2 判断当前索引与之前的索引队列是否不包含
  3 判断当前回溯层是否是最后一层
  4 不管是在那一层上的循环一次循环结束都要刷新当前层对应的索引信息

代码实现
public class StringGroupDemo {
    public static void main(String[] args) {
        String [] list={"刘","梓","江"};
        List<List> lists = StringGroup.StringGroupWay(list);
        for(List arr:lists){
            System.out.println(arr.toString());
        }
    }
}

//创建一个字符串使用类
class StringGroup{

    //一个字符串组合方法
    public static List<List> StringGroupWay(String [] content){

        //创建组合结果集的集合
        List<List> resultList=new ArrayList<>();
        //创建一个双端队列存储每层回溯对应的方法
        Deque layerIndexs=new ConcurrentLinkedDeque<>();

        StringGroupWay(content,resultList,layerIndexs);
        return resultList;

    }
    private static void StringGroupWay(String [] content, List<List> results, Deque layerIndexs){

        //循环当前索引层对于的content内容
        for(int index=0;index<content.length;index++){

            //判断当前索引值是否在layerIndexs中包含
            if (!layerIndexs.contains(index)){
                //将当前层对于的索引添加到layerIndexs中
                layerIndexs.addLast(index);

                //判断是否是content.length层
                if(layerIndexs.size()>=content.length){

                    //创建一个当前组合集合
                    List currGroupList=new ArrayList<>();
                    //创建一个数组用于封装每一层的不同的索引
                    Integer[] eachLayerIndex=new Integer[layerIndexs.size()];
                    eachLayerIndex= Arrays.copyOfRange(layerIndexs.toArray(),0,layerIndexs.size(),Integer[].class);
                    for(int currIndex=0;currIndex<eachLayerIndex.length;currIndex++){
                        currGroupList.add(content[eachLayerIndex[currIndex]]);
                    }
                    //将当前组合集合存储到results
                    results.add(currGroupList);
                }else{
                    //由于当前层不是最后一层继续回溯
                    StringGroupWay(content,results,layerIndexs);
                }
                //将当前层对于的索引移除
                layerIndexs.removeLast();
            }
        }

    }
}


结果

20200325212616871
提示:有什么写的不对的地方你可以说,相互交流,不懂的也可以评论, 代码很简短但是思路一定要清晰,主要用到了回溯和栈的概念






版权声明:本文为「丿旧城以西」的原创文章,遵循 CC 4.0 BY-SA 版权协议
原文链接:https://blog.csdn.net/weixin_44698882/article/details/103557639



    暂时没有人评论
0