1、 生成不重复验证码

题目描述

根据指定的种子（不含重复字符），生成指定验证码个数的字符串数组，要求验证码不能有重复字符。返回值需要生成所有可能的排列，并按照字典顺序升序返回。

分析设计

一道DFS基础题，由于题目中说不含重复字符，所以不需要排序种子，直接遍历即可。同时，需要设置有一个vis标志用于判断该字符是否在本轮遍历中访问过。

代码实现

class Solution{
    ArrayList<String> list = new ArrayList<>();
    public String[] getVerificationCode(char[] seed, int size){
        int n = seed.length;
        boolean[] vis = new boolean[n];
        dfs(seed, n, vis, size, "");
        Collections.sort(list);
        String[] ans = new String[list.size()];
        for(int i = 0; i < list.size(); ++i){
            ans[i] = list.get(i);
        }
        return ans;
    }
    public void dfs(char[] seed, int n, boolean[] vis, int size, String s){
        if(s.length() == size){
            list.add(s);
            return;
        }
        for(int i = 0; i < n; ++i){
            if(vis[i]){
                continue;
            }
            vis[i] = true;
            dfs(seed, n, vis, size, s + seed[i]);
            vis[i] = false;
        }
    }
}

2、数猴王

题目描述

一群猴子需要选出猴***举规则是：给定一个数字，所有猴子排成一排按照顺序编号从1开始，然后猴子从队头按照顺序1、2、3...数数，数到给定的数字的猴子淘汰，每淘汰一个猴子，给定的数字加1，下一个猴子接着从1开始数，数到那个给定的数字就淘汰，到队尾后循环从队头接着数字数，直到剩下最后一只猴子就是猴王。

分析设计

很典型的一道“约瑟夫环”问题，主要考察的是循环的判断和处理。往常类似的题目是给定的数字不变，这道题目稍微进行了变形，但基本套路不变。
对于一个环来说，变化的下标是需要对环长做取余操作的，避免越界。
对于这类“约瑟夫环”问题，有很多大佬都有详细的解答，也探讨了数学公式的解答，我这里主要是模拟实现过程，不去考虑数学公式问题。
假设5个猴子，从1开始数数，假设第一轮中，数到3的猴子淘汰，则1->2->3->4->5变成了1->2->4->5；第二轮中，给定的数字由3变成4，则数到4的猴子淘汰，则1->2->4->5变成了1->4->5；第三轮中，给定的数字由4变成5，则数到5的猴子淘汰，则1->4->5变成了1->4；第四轮中，给定的数字由5变成6，则数到6的猴子淘汰，则1->4变成了1，返回结果。
每轮去掉的下标=(前一下标+当前轮次中给定的数字+环长)%环长

代码实现

class Solution{
    public int doPermute(int M, int N){
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 1; i <= N; ++i){
            list.add(i);
        }
        int index = 0;
        while(list.size() > 1){
            index = (index + list.size() + M - 1) % list.size();
            list.remove(index);
            M++;
        }
        return list.get(0);
    }
}