1. 求字符串排列组合

获取字符串无重复排列组合数量。

输入：

baac

输出：

12

分析：

• 要考虑到字符串有重复的字母
• 字符数量阶乘 / 每一个字母数量阶乘
• 使用 map 记录每一个字符的 count。

代码：

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class StringPermutations {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            StringPermutations sp = new StringPermutations();
            sp.str = scanner.next();
            int res = sp.permutation();
            System.out.println(res);
        }
    }
    public  String str;

    public int permutation() {
        if(str.isEmpty()) return 0;
        int len = str.length();
        char[] arr = str.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        int count = getFactorial(len);
        for(int i = 0; i < len; i++) {
            int c = map.containsKey(arr[i]) ? map.get(arr[i]) + 1 : 1;
            map.put(arr[i], c);
        }
        int div = 1;
        for(Character c : map.keySet()) {
            div *= getFactorial(map.get(c));
        }
        return count/div;
    }

    public int getFactorial(int num) {
        int res = 1;
        for(int i = 1; i <= num; i++) {
            res *= i;
        }
        return res;
    }
}

2. 删除字母求字典序最小的字符串

删除字母求字典序最小的字符串。输入 第一行代表字符串，第二行 k 代表要删除字母的个数，k 小于字符串长度。输出字典序最小的字符串。

输入：

abacc

1

输出：

aacc

分析：

• 贪心算法，每一次都从前往后删除，当遇到第一个比后面字符大的字符，删掉当前的字符。停止

• 循环删除 k 次

代码：

import java.util.Scanner;

public class MinDictionary {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            MinDictionary md = new MinDictionary();
            md.str = scanner.next();
            md.k = scanner.nextInt();
            String res = md.getAnswer();
            System.out.println(res);
        }
    }
    private String str;
    private int k;
    public String getAnswer() {
        String res = str;
        for(int i = 0; i < k; i++) {
            res = core(res);
        }
        return res;
    }

    public String core(String str) {
        char[] arr = str.toCharArray();
        StringBuilder sb = new StringBuilder();
        boolean flag = true;
        for(int i = 1; i < arr.length; i++) {
            if(!flag) {
                sb.append(arr[i]);
            } else {
                if(arr[i] < arr[i-1]) {
                    flag = false;
                    sb.append(arr[i]);
                } else {
                    sb.append(arr[i-1]);
                }
            }
        }
        return sb.toString();
    }
}

3. 约会城市最短路径 + 有限路费

题目大意：

k : 硬币数量

n：城市数量

r：城市道路数量

接下来输入 r 行，每一行有四个元素，第一个表示源城市 S，第二个表示目标城市 D , 第三个表示路径长度 L，第四个表示路费 C

求从 1 ~ n 的最短路径，并且能保证硬币足够。如果没有这样的路径那么输出 -1；

分析：

• 遍历所有道路，如果源城市与当前城市相同，那么就进行一次判定。

• 减去路费，目标城市变为源城市，路径长度变长。

• 递归下去

输入：

5
6
7
1 2 2 4
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

输出：

11

代码：

import java.util.Scanner;

public class MinDistanceWithLimitedCoins {
    public static void main(String[] args) {
//        test();
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            MinDistanceWithLimitedCoins md = new MinDistanceWithLimitedCoins();
            md.K = scanner.nextInt();
            md.N = scanner.nextInt();
            md.R = scanner.nextInt();
            road = new int[md.R][4];
            for(int i = 0; i < md.R; i++) {
                for(int j = 0; j < 4; j++) {
                    road[i][j] = scanner.nextInt();
                }
            }
            int res = md.getAnswer(0, 1, md.K);
            System.out.println(res);
        }
    }
    private int K = 5;
    private int N = 6;
    private int R = 7;
    private static int[][] road;

    public int getAnswer(int L, int curCity, int K) {
        int min = Integer.MAX_VALUE;
        if(curCity == N) {
            return L;
        } else {
            for(int i = 0; i < R; i++) {
                if(road[i][0] == curCity && road[i][3] <= K) {
                    int tmp = getAnswer(L + road[i][2], road[i][1], K - road[i][3]);
                    min = tmp == -1 ? min : Math.min(tmp, min);
                }
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    public static void test() {
        MinDistanceWithLimitedCoins md = new MinDistanceWithLimitedCoins();
        road = new int[][]{{1, 2, 2, 4}, {2, 4, 3, 3}, {3, 4, 2, 4}, {1, 3, 4, 1}, {4, 6, 2, 1}, {3, 5, 2, 0}, {5, 4, 3, 2}};
        int res = md.getAnswer(0, 1, md.K);
        System.out.println(res);
    }
}