java算法- 递归回溯法

朴灿烈づ我的快乐病毒、 2022-04-24 10:44 264阅读 0赞

1、随机输入手机上的数字，使字母组成不同的组合

public class base01 {
    
        private String letterMap[][] = {
                {},    //0
                {},     //1
                {"a","b","c"},  //2
                {"d","e","f"},  //3
                {"g","h","i"},  //4
                {"j","k","l"},  //5
                {"m","n","o"},  //6
                {"p","q","r","s"}, //7
                {"t","u","v"},  //8
                {"w","x","y","z"}  //9
        };
    
        private List<String> res = new LinkedList();
        private List<String> letters = new LinkedList<>();
        private String returnStr = "";
    
        public String letterCombinations(String str){
            String[][] choseData = new String[str.length()][4];
            //选择取值范围
            int reqInt = Integer.parseInt(str);
            for(int i= 0; i< str.length();i++){
                int sit = str.charAt(i) - '0';
                choseData[i] = letterMap[sit];
            }
            //计算变化,不同长度也可以
            for(int i = 1;i<= str.length();i++){
                letterChange(choseData,i,0,"");
            }
            for(String strList : letters){
                returnStr += strList + ",";
            }
            return returnStr;
        }
    
        private void letterChange(String[][] choseData,int num,int index,String returnStr){
            if(num <= 0 || index >= choseData.length){
                if(num > 0 && num == returnStr.length()){
                    letters.add(returnStr);
                }
                return;
            }
            //当前位置不要
            letterChange(choseData,num,index + 1,returnStr);
            //当前位置选一个数
            String[] data = choseData[index];
            for(String str : data){
                if(str.length() > 0){
                    letterChange(choseData,num,index + 1, returnStr + str);
                }
            }
        }
    
        /**
         * 随机输入手机上的数字，使字母组成不同的组合
         * @param args
         */
        public static void main(String[] args) {
            System.out.println(new base01().letterCombinations("98765"));
        }
    }

**2、不重复的整数数组，有多少种不同的排列组合**

public class Solution {
    
        private ArrayList<List<Integer>> res = new ArrayList<>();
    
        private void permute(int[] nums,int index,List<Integer> list){
            int num = nums.length;
            if(num <= 0 || index >= num){
                if(num > 0 && num == list.size()){
                    res.add(list);
                }
                return;
            }
            //当前位置选一个数
            for(int i = 0;i < num;i ++){
                if(!list.contains(nums[i])){
                    List<Integer> listCopy = new ArrayList<>(list);
                    listCopy.add(nums[i]);
                    permute(nums,index + 1, listCopy);
                }
            }
        }
    
        private void printList(List<Integer> list){
            for(Integer e: list)
                System.out.print(e + " ");
            System.out.println();
        }
    
        /**
         * 不重复的整数数组，有多少种不同的排列组合
         * @param args
         */
        public static void main(String[] args) {
            int[] nums = {1, 2, 3,4};
            Solution solution = new Solution();
            solution.permute(nums,0,new ArrayList<>());
            for(List<Integer> list: solution.res)
                solution.printList(list);
        }
    }

**3、给一个集合nums和一个数字k，其中元素各不相同。（找出所有元素和为k的组合）**

public class Solution_3 {
    
        private List<List<Integer>> retData = new LinkedList<>();
    
        public void metic(int[] nums,int k,int index,List<Integer> resultArray){
            if(index >= nums.length || k<= 0){
                if(k<= 0 && resultArray.size() > 0){
                    retData.add(resultArray);
                }
                return;
            }
    
            //当前位置不选
            metic(nums,k,index + 1,new LinkedList<>(resultArray));
            //当位置选
            int value = nums[index];
            if(k >= value){
                resultArray.add(value);
                metic(nums,k - value,index + 1,resultArray);
            }
        }
    
        public static void main(String[] args) {
            int[] nums = {1,2,3,4,5,6,7,8,9,0,10,11,12};
            Solution_3 solution = new Solution_3();
            solution.metic(nums,12,0,new LinkedList<>());
            for(List<Integer> retData : solution.retData){
                System.out.println(new Gson().toJson(retData));
            }
        }
    
    }

**4、给定一个二维平面的字母表worlds，和一个单词k,看是否能在这个平面找到这个单词。找单词的方法是，由一个单词出发，上下左右，依次连接组成这个单词，同一个位置不允许使用2次：ABCCED = true,ABCB=false**

public class Solution_4 {
    
        private String[][] worlds =
                {
                        {"A","B","C","E"},
                        {"S","F","C","S"},
                        {"A","D","E","E"}
                };
    
        private boolean[][] useWords;
    
        /**
         * @param checkWorlds 需要检查的数组
         * @param world 当前位置的字母
         * @param index 当前是检查的第几个字母
         * @param xsit 当前x坐标
         * @param ysit 当前y坐标
         * @return
         */
        private boolean sitCheck(String[] checkWorlds,String world,int index,int xsit,int ysit){
            if(xsit < 0 || xsit >= worlds.length){
                return false;
            }
            if(ysit < 0 || ysit >= worlds[xsit].length){
                return false;
            }
            if(worlds[xsit][ysit].equals(world)){
                if(index == 0){
                    useWords = new boolean[worlds.length][worlds[0].length];
                }
                if(!useWords[xsit][ysit]){
                    useWords[xsit][ysit] = true;
                    boolean have = worldSearch(checkWorlds,index + 1,xsit,ysit);
                    if(have){
                        return true;
                    }
                }
            }
            return false;
        }
        /**
         * 给定一个二维平面的字母表worlds，和一个单词k,看是否能在这个平面找到这个单词。
         * 找单词的方法是，由一个单词出发，上下左右，依次连接组成这个单词，同一个位置不允许使用2次
         * ABCCED = true,ABCB=false
         * 递归回溯法
         */
        public boolean worldSearch(String[] checkWorlds,int index,int xsit,int ysit){
            if(checkWorlds.length <= 0){
                return false;
            }
            if(index >= checkWorlds.length){
                return true;
            }
    
            String value = checkWorlds[index];
            //定位第一个位置
            if(index == 0){
                for(int i =0;i< worlds.length;i++){
                    String[] world = worlds[i];
                    for(int j = 0;j < world.length;j++){
                        if(sitCheck(checkWorlds,value,index,i,j)){
                            return true;
                        }
                    }
                }
            }else { //查找非第一个位置
                if(sitCheck(checkWorlds,value,index,xsit -1,ysit) //上
                        || sitCheck(checkWorlds,value,index,xsit +1,ysit) //下
                        || sitCheck(checkWorlds,value,index,xsit,ysit -1)//左
                        || sitCheck(checkWorlds,value,index,xsit,ysit +1)){//右
                    return true;
                }
            }
            return false;
        }
    
        public static void main(String[] args) {
            Solution_4 solution = new Solution_4();
            String data = "ADFBA";
            System.out.println(new Solution_4().worldSearch(data.split(""),0,0,0));
        }
    }

**5、给定一个二维数组lands，1代表陆地，0代表水域。横向和纵向连接的陆地是岛屿，找出这个二维组中有多少岛屿**

public class Solution_5 {
    
        private int[][] lands = {
                {1, 1, 1, 1, 0},
                {1, 0, 0, 0, 1},
                {1, 1, 1, 0, 1},
                {0, 0, 1, 0, 0},
                {0, 0, 0, 1, 0}
        };
    
        private boolean[][] landsBool;
    
        /**
         * 给定一个二维数组lands，1代表陆地，0代表水域。横向和纵向连接的陆地是
         * 岛屿，找出这个二维组中有多少岛屿
         * lands = 3
         */
        public int numberLands(int[][] lands) {
            //找到一块岛屿
            int num = 0;
            for (int x = 0; x < lands.length; x++) {
                int[] landsY = lands[x];
                for (int y = 0; y < landsY.length; y++) {
                    //感染整片岛屿
                    if(infectLand(lands,x,y)){
                        num ++;
                    }
                }
            }
            return num;
        }
    
        private boolean infectLand(int[][] lands,int x,int y){
            boolean isLand = false;
            if(x < 0 || x >= lands.length){
                return isLand;
            }
            if(y < 0 || y >= lands[x].length){
                return isLand;
            }
    
            if(!landsBool[x][y] && lands[x][y] == 1){
                isLand = true;
                //感染整片岛屿
                landsBool[x][y] = true;
                //上
                infectLand(lands,x -1,y);
                //下
                infectLand(lands,x + 1,y);
                //左
                infectLand(lands,x,y -1);
                //右
                infectLand(lands,x,y + 1);
            }
            return isLand;
        }
    
        public static void main(String[] args) {
            Solution_5 solution = new Solution_5();
            solution.landsBool = new boolean[solution.lands.length][solution.lands[0].length];
            System.out.println(solution.numberLands(solution.lands));
        }
    }

6、数独问题，数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件， 利用逻辑和推理，在其他的空格上填入1-9的数字。 9个小九宫格内是1-9个数字都有，每个数字只出现一次 整体81个格子，横向和纵向都是1-9个数字，每个数字只出现一次

public class Solution3 {
    
        private int[][] suduku = {
                {5, 3, 0, 0, 7, 0, 0, 0, 0},
                {6, 0, 0, 1, 9, 5, 0, 0, 0},
                {0, 9, 8, 0, 0, 0, 0, 6, 0},
                {8, 0, 0, 0, 6, 0, 0, 0, 3},
                {4, 0, 0, 8, 0, 3, 0, 0, 1},
                {7, 0, 0, 0, 2, 0, 0, 0, 6},
                {0, 6, 0, 0, 0, 0, 2, 8, 0},
                {0, 0, 0, 4, 1, 9, 0, 0, 5},
                {0, 0, 0, 0, 8, 0, 0, 7, 9}
        };
    
        private int[][] returnSuduku;
    
        List<Integer> range;
    
        /**
         * 数独问题，数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，
         * 利用逻辑和推理，在其他的空格上填入1-9的数字。
         * 9个小九宫格内是1-9个数字都有，每个数字只出现一次
         * 整体81个格子，横向和纵向都是1-9个数字，每个数字只出现一次
         */
        public boolean sudukuSolver(int[][] suduku, int xsit, int ysit) {
            int num = suduku[xsit][ysit];
            if (num > 0) {
                //找一个空白点
                ysit += 1;
                if (ysit >= suduku[xsit].length) {
                    ysit = 0;
                    xsit += 1;
                }
                if (xsit >= suduku.length) {
                    returnSuduku = suduku;
                    return true;
                }
                return sudukuSolver(suduku, xsit, ysit);
            }
    
            //找到空白点取值范围
            List<Integer> range = getRange(suduku, xsit, ysit);
            if (range.size() > 0) {
                for (int value : range) {
                    int[][] sudukuCopy = getSudukuCopy(suduku);
                    sudukuCopy[xsit][ysit] = value;
                    boolean isHave = sudukuSolver(sudukuCopy, xsit, ysit);
                    if (isHave) {
                        return true;
                    }
                }
            }
            return false;
        }
    
        private int[][] getSudukuCopy(int[][] suduku) {
            int[][] sudukuCopy = suduku.clone();
            for (int i = 0; i < sudukuCopy.length; i++) {
                sudukuCopy[i] = suduku[i].clone();
            }
            return sudukuCopy;
        }
    
        /**
         * 找到空白点取值范围
         *
         * @return
         */
        private List<Integer> getRange(int[][] suduku, int xsit, int ysit) {
            List<Integer> range = new LinkedList<>(this.range);
            //九宫格取值范围
            int miny = (ysit / 3) * 3;
            int maxy = miny + 2;
            int minx = (xsit / 3) * 3;
            int maxx = minx + 2;
    
            for (int i = 0; i < suduku.length; i++) {
                int[] dataY = suduku[i];
                for (int j = 0; j < dataY.length; j++) {
                    int value = suduku[i][j];
                    if(value > 0){
                        if(i == xsit || j == ysit){
                            //移除横,纵向出现数字
                            range.removeIf(x -> x == value);
                        }else {
                            //移除小9宫格出现数字
                            if(i >= minx && i <= maxx && j >= miny && j <= maxy){
                                range.removeIf(x -> x == value);
                            }
                        }
                    }
                }
            }
            return range;
        }
    
        public static void main(String[] args) {
            Solution3 solution = new Solution3();
            solution.range = Stream.iterate(1, x -> x + 1).limit(9).collect(Collectors.toList());
            solution.sudukuSolver(solution.suduku, 0, 0);
            for (int[] data : solution.returnSuduku) {
                System.out.println(new Gson().toJson(data));
            }
        }
    }