A 牛牛的分配

解题思路
这道题贪心的来想，如果想让尽可能多的瓶子满足要求，则应该让所有瓶子的初始容量尽可能的大，所以做法就是我们对所有的瓶子按照初始的容量从小到大排序，然后从后往前看，累加所有瓶子的容积，然后除以它们的个数，直到当前所有瓶子的容积的平均值小于,就跳出循环。
参考代码

import java.util.*;


public class Solution {
    /**
     * 返回重新分配后，满足牛牛要求的水量的瓶子最多的数量
     * @param n int整型 瓶子的数量
     * @param x int整型 牛牛的对瓶中的水量要求
     * @param a int整型一维数组 每个瓶子中的含水量
     * @return int整型
     */
    public int solve (int n, int x, int[] a) {
        // write code here
        Arrays.sort(a, 0, n);

        // 如果当前容量最多的瓶子的容积都小于x，则该序列绝对不满足要求
        if(a[n - 1] < x) return 0;

        long sum = 0;
        int res = 1;
        for(int i=n-1; i>=0; i--){
            sum += a[i];
            int cur = n - 1 - i + 1; // 获得当前的瓶子个数
            if(sum >= (long)x * cur){ // 以防出现精度问题
                res = Math.max(res, cur);
            }else break;
        }

        return res;
    }
}


B playfair

解题思路
这道题就是一个模拟题，按照题目的意思来就行，需要注意的是加密过程中的j都由i来代替, 在替换明文的时候需要注意
参考代码

import java.util.*;


public class Solution {
    /**
     * playfair加密算法
     * @param key string字符串 密钥
     * @param str string字符串 明文
     * @return string字符串
     */
    public String Encode (String key, String str) {
        // write code here
        char[][] g = new char[5][5]; // 设计密码表
        List<Character> s = new ArrayList<Character>();
        for(int i=0; i<key.length(); i++) {
            char c = key.charAt(i);
            if(s.contains(c)) continue;

            if(c == 'j') c = 'i';
            if(!s.contains(c)) s.add(c);
        }

        // 先将已有的字符填入密码表
        int x = 0;
        int y = 0;
        for(Character c : s) {
            g[x][y ++] = c;

            if(y == 5) {
                x += 1;
                y = 0;
            }
        }

        // 补全没有的字符
        while(x != 5 || y != 0) {
            for(char c ='a'; c<='z'; c++) {
                if(!s.contains(c) && c != 'j') {
                    g[x][y] = c;
                    s.add(g[x][y]);
                    break;
                }
            }

            y ++;
            if(y == 5) {
                x += 1;
                y = 0;
            }
        }

        // 使用StringBuilder使得字符串拼接效率更高
        StringBuilder res = new StringBuilder();

        for(int i=0; i<str.length(); i+=2) {
            // 截取字符串str
            String cur = str.substring(i, Math.min(i+2, str.length()));

            if(cur.length() < 2) {
                res.append(cur);
            }else {
                char a = cur.charAt(0);
                char b = cur.charAt(1);

                // 如果明文中含有j，则将其替换为i
                if(a == 'j') a = 'i';
                if(b == 'j') b = 'i';

                // 获取a和b两个字符在矩阵中的位置
                int x1 = -1; int y1 = -1;
                int x2 = -1; int y2 = -1;
                for(int u=0; u<5; u++) {
                    for(int v=0; v<5; v++) {
                        if(g[u][v] == a) {
                            x1 = u;
                            y1 = v;
                        }
                        if(g[u][v] == b) {
                            x2 = u;
                            y2 = v;
                        }
                    }
                }

                if(x1 == x2 && y2 == y1){
                    String c = a + "";
                    res.append(c + c);
                }else if(x1 == x2) {
                    String c = g[x1][(y1+1)%5] + "";
                    String d = g[x2][(y2+1)%5] + "";
                    res.append(c + d);
                }else if(y1 == y2) {
                    String c = g[(x1+1)%5][y1] + "";
                    String d = g[(x2+1)%5][y2] + "";
                    res.append(c + d + "");
                }else if(x1 != x2 && y1 != y2){
                    String c = g[x1][y2] + "";
                    String d = g[x2][y1] + "";
                    res.append(c + d + "");
                }
            }
        }

        return res.toString();
    }
}


C 牛牛摇骰子

解题思路
首先这道题贪心的来想，对于所有大于11的数字，当然优先用11来将它们变得更小，但是这里要考虑一个特殊的数字，也算是打表找出的规律吧，就是例如13，它实际上只需要3步，也就是0 - > 3 - > 10 - > 13, 对于24，
0 - > 7 - > 14 > 21 - > 24，只需要4步，但是如果按照贪心的想法来做的话，对于13就需要5步，对于24就需要6步，故我们可以发现，所有模11余2的数字都比按贪心直接做的要少2步，而对于剩下的数字都是可以正确计算的，因此最终我的做法就是预先处理出来[0, 22]的所有数字需要的最小步数，然后对于每一个新的数字，优先让它们被11削减，然后与剩下数字所需的最小步数相加就ok了。
参考代码

import java.util.*;


public class Solution {
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型一维数组 要查询坐标的数组
     * @return int整型一维数组
     */
    public int[] MinimumTimes (int[] arr) {
        // write code here
        // BFS出22以内的数字的最小步数使用(0, 3, 7, 11)来构造

        int[] a = {0, 3, 7, 11};
        int[] d = new int[23];
        boolean[] st = new boolean[23];
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(0);
        d[0] = 0;
        st[0] = true;

        while(!q.isEmpty()){

            int cur = q.poll();

            for(int i=0; i<a.length; i++){
                int u = cur + a[i];
                int v = cur - a[i];
                if((u <= 22 && u >= 0) && !st[u]){
                    st[u] = true;
                    d[u] = d[cur] + 1;
                    q.add(u);
                }

                if((v <= 22 && v >= 0) && !st[v]){
                    st[v] = true;
                    d[v] = d[cur] + 1;
                    q.add(v);
                }
            }
        }

        int[] res = new int[arr.length];
        for(int i=0; i<arr.length; i++) {
            int cur = arr[i];
            if(cur <= 11) {
                res[i] = d[cur % 11];
            }else {
                int u = cur / 11 - 1;
                int v = d[cur % 11 + 11];
                res[i] = u + v;
            }
        }

        return res;
    }
}