No.1 重新格式化字符串

★解题思路

该题目比较简单, 统计字符和数字的数量即可, 只要差距不超过 1 就可以交叉着构造出答案. 代码展示

class Solution {
   public String reformat(String s) {
       LinkedList<Character> digits = new LinkedList<>();
       LinkedList<Character> letters = new LinkedList<>();
       for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);
           if (Character.isDigit(c)) {
               digits.add(c);
           } else {
               letters.add(c);
           }
       }
       if (Math.abs(digits.size() - letters.size()) > 1) {
           return "";
       }
       StringBuilder sb = new StringBuilder(); 
       while (letters.size() > 0 && digits.size() > 0) {
           sb.append(letters.poll());
           sb.append(digits.poll());
       }
       // 若字母有剩余, 应该添加到末尾; 若数字有剩余, 应该添加到开头
       if (letters.size() > 0) {
           sb.append(letters.poll());
       }
       if (digits.size() > 0) {
           sb.insert(0, digits.poll());
       }
       return sb.toString();
   }
}

No.2 点菜展示表

★解题思路 该题目比较简单, 逻辑正确即可. 详见代码注释. 代码展示 ```

class Solution {    public List<List> displayTable(List<List> orders) {        // 1. 获取所有的菜名和桌号的列表 (排序后的)        Set tableIDSet = new HashSet<>();        Set foodNameSet = new HashSet<>();        for (var order : orders) {            tableIDSet.add(order.get(1));            foodNameSet.add(order.get(2));        }        List tableIDs = new ArrayList<>(tableIDSet);        tableIDs.sort(Comparator.comparingInt(Integer::parseInt));        List foodNames = new ArrayList<>(foodNameSet);        Collections.sort(foodNames);        // 2. 菜名对应的列表序号        Map<String, Integer> nameToIndex = new HashMap<>();        for (int i = 0; i < foodNames.size(); i++) {            nameToIndex.put(foodNames.get(i), i);        }        // 3. 每个桌号对应的点餐列表        Map<String, List> tableToOrder = new HashMap<>();        for (var order : orders) {            String id = order.get(1);            String food = order.get(2);            if (!tableToOrder.containsKey(id)) {                List list = new ArrayList<>();                for (int i = 0; i < foodNames.size(); i++) {                    list.add(0);                }                tableToOrder.put(id, list);            }            int idx = nameToIndex.get(food);            List orderList = tableToOrder.get(id);            orderList.set(idx, orderList.get(idx) + 1);        }        // 4. 构造出最终答案        List<List> res = new ArrayList<>();        // 列名        List columns = new ArrayList<>();        columns.add("Table");        columns.addAll(foodNames);        res.add(columns);        // 每一行数据        for (String id : tableIDs) {            List row = new ArrayList<>();                 row.add(id);            for (int count : tableToOrder.get(id)) {                row.add(String.valueOf(count));            }            res.add(row);        }        return res;    } }

<figure class="image">![](upload/attach/202004/2020_04_19_13_08_21_33119)</figure>

**No.3 数青蛙**

★**解题思路**

遍历给定的字符串, 每当遇到字符 c 就说明有一只青蛙开始蛙鸣. 遇到其他字符则要求当前正在蛙鸣的青蛙中存在即将蛙鸣到该字符的青蛙, 否则直接返回 -1.

维护当前正在蛙鸣的青蛙蛙鸣到了哪些字符即可, 注意最后所有青蛙必须完成了蛙鸣.
**代码展示**

class Solution {    final Map<Character,Integer> index = new HashMap<>() {{        put('c', 0);        put('r', 1);        put('o', 2);        put('a', 3);        put('k', 4);    }};    public int minNumberOfFrogs(String croakOfFrogs) {        char[] str = croakOfFrogs.toCharArray();        int n = str.length;        int res = 0;        int cnt = 0; // 当前正在蛙鸣的青蛙数量        int[] nums = new int[5];  // nums[i] 表示蛙鸣到了第 i 个字符的青蛙数量        for (char c : str) {            int idx = index.get(c);            cnt += idx == 0 ? 1 : 0; // 一只青蛙开始蛙鸣            cnt -= idx == 4 ? 1 : 0; // 一只青蛙结束蛙鸣            if (idx != 0) { // 非开始蛙鸣, 那么要求有青蛙刚好蛙鸣到 idx                if (nums[idx - 1] == 0) {                    return -1;                }                nums[idx - 1]--;            }                 nums[idx]++;            res = Math.max(res, cnt);        }        for (int i = 0; i < 4; i++) {            if (nums[i] > 0) {                return -1;            }        }        return res;    } }

**No.4 生成数组**
★**解题思路**
动态规划问题.

- 定义状态: dp[i][j][k] 表示已经生成了 i 个数字, 其中最大的为 j, 并且最大值已经更新了 k 次时的方案数.

- 状态转移: 枚举下一个数字生成谁即可, 与 j 比较来判断是否需要给 k  加 1.
**代码展示**
**```**

class Solution {
   final long MOD = 1000000007;
   int N, M, K;
   long[][][] f;
   public int numOfArrays(int n, int m, int k) {
       N = n; M = m; K = k;
       f = new long[n + 1][m + 1][k + 1];
       // 初始化 -1 表示没计算过
       for (int i = 0; i <= n; i++) {
           for (int j = 0; j <= m; j++) {
               Arrays.fill(f[i][j], -1);
           }
       }
       return (int)dp(0, 0, 0);
   }

   private long dp(int i, int j, int k) {
       // 边界状态, 已经生成了 N 个数字时, 必须被更新 K 次才可以
       if (i == N) {
           return k == K ? 1 : 0;
       }
       if (f[i][j][k] >= 0) {
           return f[i][j][k];
       }
       f[i][j][k] = 0;
       // 下一个数字不超过 j, 就不会触发更新
       for (int nj = 1; nj <= j; nj++) {
           f[i][j][k] = (f[i][j][k] + dp(i + 1, j, k)) % MOD;
       }
       // 下一个数字超过 j, 触发一次更新
       if (k < K) {
           for (int nj = j + 1; nj <= M; nj++) {
               f[i][j][k] = (f[i][j][k] + dp(i + 1, nj, k + 1)) % MOD;
           }
       }
       return f[i][j][k];
   }
}