玛雅人的密码

解析

1. 将所有可能的字符串列举出来，然后判断是否有包含“2012”的
2. 又要求输出最少的移位次数，所以应该以图的形式列举出来，然后按照广度优先搜索的方式进行遍历（因为要求的是最少的移位次数）
3. 建立这张图的方式：将源字符串作为第一个节点, 然后将它的移位字符串作为邻接点即可.

列举方式类似如下：

所以本题的关键点有两个：

1. 将所有可能的结果生成图
2. 广度优先搜索

代码

package t56;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 玛雅人的密码：https://www.nowcoder.com/practice/761fc1e2f03742c2aa929c19ba96dbb0?tpId=40&tqId=21343&tPage=7&rp=7&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking
 */

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            String code = sc.next();
            int moveTime = getMoveTime(code, n);
            System.out.println(moveTime);
        }
        sc.close();
    }

    private static int getMoveTime(String code, int n) {
        if (n < 4) {
            return -1;
        }
        ArrayList<String> record = new ArrayList<>();
        Queue<StringNum> que = new LinkedList<>();
        StringNum stringNum = new StringNum(code, 0);
        que.offer(stringNum);
        record.add(code);
        while (!que.isEmpty()) {
            stringNum = que.remove();
            if (stringNum.str.contains("2012")) {
                return stringNum.num;
            }
            for (int i = 0; i < n - 1; ++i) {
                char[] temp = stringNum.str.toCharArray();
                swap(temp, i, i + 1);
                String tempStr = new String(temp);
                if (!record.contains(tempStr)) {
                    record.add(tempStr);
                    que.offer(new StringNum(tempStr, stringNum.num + 1));
                }
            }
        }
        return -1;
    }

    private static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

class StringNum {
    String str;
    int num;

    public StringNum(String str, int num) {
        this.str = str;
        this.num = num;
    }
}