算法问题——（二维平面的DFS和动态规划的问题）

题目描述（DFS）

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

/**
 * Copyright (C), 2018-2020
 * FileName: Permutation
 * Author:   xjl
 * Date:     2020/7/15 15:51
 * Description: 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 */
package DFS_BFS;

import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeSet;

public class Permutation {

    public static void main(String[] args) {
        //数据的输入
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        //函数的调用
        ArrayList list = permutationtest(str);
        //结果的打印
        for (String s : list) {
            System.out.print(s + " ");
        }

    }

    private static ArrayList permutationtest(String str) {
        if (str == null || str.length() < 1) {
            return new ArrayList();
        }
        //存放所有的元素
        ArrayList chars = new ArrayList();
        //定义一个去重的
        TreeSet result = new TreeSet();
        for (char c : str.toCharArray()) {
            chars.add(c);
        }
        Compose(chars, 0, new StringBuffer(), str.length(), result);
        return new ArrayList(result);
    }

    private static void Compose(ArrayList chars, int index, StringBuffer buffer, int length, TreeSet result) {
        //递归结束的条件
        if (index == length) {
            result.add(buffer.toString());
            return;
        }
        for (int i = 0; i < chars.size(); i++) {
            char c = chars.get(i);
            buffer.append(c);
            chars.remove(i);
            //递归
            Compose(chars, index + 1, buffer, length, result);
            //回溯
            chars.add(i, c);
            buffer.deleteCharAt(buffer.length() - 1);
        }
    }
}

面试题 08.07. 无重复字符串的排列组合

class Solution {
    public String[] permutation(String S) {
        Set set = new HashSet();
        char[] chars = S.toCharArray();
        boolean[] visit = new boolean[S.length()];
        slove(chars, 0, "", set, visit);
        String[] result = new String[set.size()];
        int index = 0;
        for (String s : set) {
            result[index++] = s;
        }
        return result;
    }

     private  void slove(char[] chars, int index, String str, Set set, boolean[] visit) {
        if (index == chars.length) {
            set.add(str);
        } else {
            for (int i = 0; i < chars.length; i++) {
                if (!visit[i]) {
                    visit[i] = true;
                    str += chars[i];
                    slove(chars, index + 1, str, set, visit);
                    //回溯
                    str = str.substring(0,str.length() - 1);
                    visit[i] = false;
                }
            }
        }
    }
}

题目：输入若干个证书 求解这些数字能够最大的或者最小的数组的数字的字符串：

/**
 * Copyright (C), 2018-2020
 * FileName: DFS
 * Author:   xjl
 * Date:     2020/7/15 20:46
 * Description: ces
 */
package DFS_BFS;

import java.util.ArrayList;
import java.util.Scanner;

public class DFS {

    public static void main(String[] args) {
        //数据的输入
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        sc.nextLine();
        String[] nums = sc.nextLine().split(",");
        //函数的调用
        String maxnumbers = test(nums);
        //结果
        System.out.println(maxnumbers);
    }

    private static String test(String[] nums) {
        //存放所有数据的结果
        ArrayList result = new ArrayList();
        //每次
        ArrayList list = new ArrayList();
        boolean[] visit = new boolean[nums.length];
        slove(nums, 0, result, list, visit);
        //获取最大值
        int max = Integer.valueOf(result.get(0));
        for(String s:result){
            max=max> Integer.valueOf(s)?max:Integer.valueOf(s);
        }
        return String.valueOf(max);
    }

    private static void slove(String[] nums, int index, ArrayList result, ArrayList list, boolean[] visit) {
        //终止条件
        if (index == nums.length) {
            result.add(change(list));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (!visit[i]) {
                    visit[i] = true;
                    list.add(nums[i]);
                    slove(nums, index + 1, result, list, visit);
                    //回溯算法
                    visit[i] = false;
                    list.remove(list.size() - 1);
                }
            }
        }

    }

    private static String change(ArrayList list) {
        String res = "";
        for (String s : list) {
            res += s;
        }
        return res;
    }
}

79. 单词搜索 /剑指 Offer 12. 矩阵中的路径

class Solution {
     //四个方向
    int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int m, n;
    boolean[][] visit;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        //赋值没有访问过
        visit=new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                visit[i][j] = false;
            }
        }
        //开始遍历
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (searchword(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean searchword(char[][] board, String word, int index, int startx, int starty) {
        //递归的终止条件
        if (index == word.length() - 1) {
            return board[startx][starty] == word.charAt(index);
        }
        //递归的流程
        if (board[startx][starty] == word.charAt(index)) {
            visit[startx][starty] = true;
            //从四个方向开始往下寻找
            for (int i = 0; i < 4; i++) {
                int newx = startx + d[i][0];
                int newy = starty + d[i][1];
                if (inArea(newx, newy) && !visit[newx][newy]) {
                    if (searchword(board, word, index + 1, newx, newy)) {
                        return true;
                    }
                }
            }
            visit[startx][starty] = false;
        }
        return false;
    }

    //判断是否在矩阵中
    private boolean inArea(int newx, int newy) {
        return newx >= 0 && newx < m && newy >= 0 && newy