class Solution {
    static String[][] dir = {{"a", "b", "c"}, {"d", "e", "f"}, {"g", "h", "i"},
            {"j", "k", "l"}, {"m", "n", "o"}, {"p", "q", "r", "s"}, {"t", "u", "v"},
            {"w", "x", "y", "z"}};
    static List<String> result;

    /**
     * dfs + 回溯
     *
     * @param digits
     * @return
     */
    public static List<String> letterCombinations(String digits) {
        result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        StringBuilder builder = new StringBuilder();
        //传入初始参数
        dfs(digits, 0, builder);
        return result;
    }

    /**
     * dfs 回溯时，先判断结束条件，即 判断是否满足条件，将临时数据保存到结果集合中
     * 递归前，先修改，再递归， 最后恢复
     *
     * @param digits
     * @param index
     * @param builder
     */
    private static void dfs(String digits, int index, StringBuilder builder) {
        if (builder.length() == digits.length()) {
            result.add(builder.toString());
            return;
        }
        int i = (digits.charAt(index) - '0') - 2;
        String[] temp = dir[i];
        for (int j = 0; j < temp.length; j++) {
            builder.append(temp[j]);
            dfs(digits, index + 1, builder);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}

class Solution {
    List<List<Integer>> result;

    public List<List<Integer>> findSubsequences(int[] nums) {
        // 定义全局变量保存结果
        result = new ArrayList<List<Integer>>();
        LinkedList<Integer> list = new LinkedList<>();
        // idx 初始化为 -1，开始 dfs 搜索。
        dfs(nums, -1, list);
        return result;
    }

    private void dfs(int[] nums, int index, LinkedList<Integer> list) {
        // 只要当前的递增序列长度大于 1，就加入到结果 res 中，然后继续搜索递增序列的下一个值。
        if (list.size() > 1) {
            result.add(new LinkedList(list));
        }
        // 在 [idx + 1, nums.length - 1] 范围内遍历搜索递增序列的下一个值。
        // 借助 set 对 [idx + 1, nums.length - 1] 范围内的数去重。
        // 注： 表明在当前搜索的范围内，寻找一位符合条件的值，若当前值已经搜索过，则直接continue,否则加入set中，注意哦，set不是dfs的参数
        // 仅仅保存当前搜索范围内的 已搜索情况
        HashSet<Integer> set = new HashSet<>();
        for (int i = index + 1; i < nums.length; i++) {
            int temp = nums[i];
            // 1. 如果 set 中已经有与 nums[i] 相同的值了，说明加上 nums[i] 后的所有可能的递增序列之前已经被搜过一遍了，因此停止继续搜索。
            if (set.contains(temp)) {
                continue;
            }
            set.add(temp);
            // 2. 如果 nums[i] >= list.getLast() 的话，说明出现了新的递增序列，因此继续 dfs 搜索
            // （因为 list 在这里是复用的，因此别忘了 remove 哦）
            if (list.isEmpty() || list.getLast() <= temp) {
                list.addLast(temp);
                dfs(nums, i, list);
                list.removeLast();
            }
        }
    }
}

/**
 * * 第一步，求最大公共前后缀的长度
 * * 根据原始字符串新建一个等长的辅助数组 prefix，存储从第 0 位 开始 到 第 i 位的 parten 的最大公共前后缀 的长度
 * * <p>
 * * 0 --  AB
 * * 0 --  ABC
 * * 0 --  ABCD
 * * 1 --  ABCDA
 * * 2 -- ABCDAB
 * * 3 -- ABCDABC
 * * 1 -- ABCDABCA
 * * 最终 prefix数组为 [0, 0, 0, 0, 1, 2, 3, 1]
 * * <p>
 * * 第二步：开始匹配
 * * 当text[i] == parten[j]相等时，i++，j++,两个指针都右移
 * * 不相等时；j = prefix[j]; 若j==-1，说明已经到头，i++,j++
 *
 * @param text
 * @param parten
 * @return
 */
public boolean kmpSearch(char[] text, char[] parten) {
    int partenLength = parten.length;
    int textLength = text.length;
    int[] prefix = new int[partenLength];
    //第一步：填充prefixs数组
    prefixTable(parten, prefix);
    //第二步：移动prefixs数组
    move_prefix_table(prefix);
    //双指针 ； i 指向 text的下标 -- j指向 parten的下标
    int i = 0;
    int j = 0;
    boolean flag = false;
    while (i < textLength) {
        // 当模式串的前partenLength - 1 都匹配，且 text当前位 等于 模式串的最后一位时，匹配成功
        if (j == partenLength - 1 && text[i] == parten[j]) {
            flag = true;
            result = i - partenLength + 1;
            break;
        }
        // 当text[i] == parten[j]相等时，i++，j++,两个指针都右移
        if (text[i] == parten[j]) {
            i++;
            j++;
        } else {
            j = prefix[j];
            //已经到头了，也都不相等, i++
            if (j == -1) {
                i++;
                j++;
            }
        }
    }
    return flag;
}

/**
 * 整体往右移动prefix数组，在第0位补为 -1；
 *
 * @param prefix
 */
public void move_prefix_table(int[] prefix) {
    for (int i = prefix.length - 1; i > 0; i--) {
        prefix[i] = prefix[i - 1];
    }
    prefix[0] = -1;
}


/**
 * 使用双指针 j 和 i,初始化 j = 0 , i =1;
 * 遍历 i 到最后一位，i指明的是 当前处理的是 parten 的 第 i 位，且需要求出当前 公共前后缀数组的 第 i 位的值；
 * prefix[i]表示的意思是: 从第 0 位 开始 到 第 i 位的 parten 的最大公共前后缀 的长度
 * 初始默认 prefix[0] = 0;
 *
 * @param parten
 */
public void prefixTable(char[] parten, int[] prefix) {
    int length = parten.length;
    prefix[0] = 0;
    int j = 0;
    int i = 1;
    while (i < length) {
        // 当 parten[i] == parten[j] 时，则 prefix[i] = j + 1;
        if (parten[i] == parten[j]) {
            prefix[i] = j + 1;
            i++;
            j++;
        } else {
            //如果 j == 0 ,则表明 已经到达头部节点 且 与 i 位置的数不相等，则可以直接将 prefix[i] 置为 0;
            if (j == 0) {
                prefix[i] = 0;
                i++;
            } else {
                j = prefix[j - 1];
            }
        }
    }

}

class Solution {
/**
     * 当 s 没有循环节时：
     * 如果 s 中没有循环节，那么 ss 中必然有且只有两个 s，此时从 ss[1] 处开始寻找 s ，必然只能找到第二个，所以此时返回值为 s.size()。
     * ----------------
     * 当 s 有循环节时：
     * 当 s 中有循环节时，设循环节为 r，其长度为 l，那么 ss 中必然可以找出 s.size()/l + 1 个 s 。
     * 因为去掉了第一个 S 的第一个字符 (代码中，(s+s).find(s, 1)， 是从 ss[1] 处开始 find )
     * 所以此时必回找到第二个 s 的起点。
     *
     * @param s
     * @return
     */
    public static boolean repeatedSubstringPattern(String s) {
        String substring = (s + s).substring(1, (s + s).length());
        return substring.indexOf(s) != (s.length() - 1);
    }

    /**
     * 模拟
     * 如果匹配，则至少循环两次，所以模板子串的最长长度为 length / 2;
     * 从 length / 2 遍历到 1；如果不能被 length 整除，则直接continue，否则遍历N的次数，stringbuilder append 去判断是否相等
     *
     * @param s
     * @return
     */
    public static boolean repeatedSubstringPattern2(String s) {
        int length = s.length();
        int count = length / 2;
        boolean flag = false;
        for (int i = count; i >= 1; i--) {
            if (length % i == 0) {
                if (deal(s, i)) {
                    flag = true;
                    break;
                }
            }
        }
        return flag;
    }

    public static boolean deal(String s, int length) {
        StringBuilder sb = new StringBuilder();
        int count = s.length() / length;
        String temp = s.substring(0, length);
        for (int i = 0; i < count; i++) {
            sb.append(temp);
        }
        return temp.toString().equals(s);
    }
}

public class 查找大小为M的最新分组_5497 {

    int[] parent;
    int[] nums;

    /**
     * 并查集 -- 使用两个数组，一个保存当前节点的父节点，另一个用来保存集合父节点所在集合的总的个数
     * 之后就是遍历数组，每个节点都要判断 左右节点的情况，一共四种
     * 使用int count 计数，符合 m 的个数的集合 一种的个数，处理当前节点时，判断count 是否为0
     * 不为0，则表明当前步骤有有效步骤，赋值给 result;否则，当前步骤无效，不做记录
     * @param arr
     * @param m
     * @return
     */
    public int findLatestStep(int[] arr, int m) {
        int result = -1;
        int length = arr.length;
        int count = 0;
        //数组的范围 取值为 0-1--n-n+1,为了防止数组越界，其中0 和 n+1 防止数组越界
        parent = new int[length + 2];
        nums = new int[length + 2];
        for (int i = 1; i <= length; i++) {
            int index = arr[i - 1];
            //如果，当前位置的左右两个数都为0 (不会对当前的数字情况造成任何影响)
            if (parent[index - 1] == 0 && parent[index + 1] == 0) {
                parent[index] = index;
                nums[index] = 1;
                if (nums[index] == m) {
                    count++;
                }
            }
            //当前位置的 左边不为 0 ，右边为 0
            else if (parent[index - 1] != 0 && parent[index + 1] == 0) {
                //注意合并集的时候，往右合并（较大值）--这样 左边的数 就无需递归寻找父节点
                parent[index - 1] = index;
                parent[index] = index;
                nums[index] = 1 + nums[index - 1];
                //
                if (nums[index - 1] == m) {
                    count--;
                }
                if (nums[index] == m) {
                    count++;
                }
            }
            //当前位置的 左边为 0 ，右边不为 0
            else if (parent[index - 1] == 0 && parent[index + 1] != 0) {
                int parentNode = findParent(index + 1);
                parent[index] = parentNode;
                if (nums[parentNode] == m) {
                    count--;
                }
                nums[parentNode] = 1 + nums[parentNode];
                //
                if (nums[parentNode] == m) {
                    count++;
                }
            }
            //当前位置的 左边 和 右边 都不为 0
            else {
                int parentNode = findParent(index + 1);
                parent[index] = parentNode;
                parent[index - 1] = parentNode;
                if (nums[parentNode] == m) {
                    count--;
                }
                if (nums[index - 1] == m) {
                    count--;
                }
                nums[parentNode] = 1 + nums[parentNode] + nums[index - 1];
                if (nums[parentNode] == m) {
                    count++;
                }
            }

            // 当前节点处理完毕，判断count，不为0，则表明当前步骤有有效步骤，赋值给 result;
            if (count != 0) {
                result = i;
            }
        }
        return result;
    }

    /**
     * 递归寻找父节点
     * @param index
     * @return
     */
    private int findParent(int index) {
        if (parent[index] != index) {
            return findParent(parent[index]);
        }
        return index;
    }

import java.util.Arrays;

public class 你可以获得的最大硬币数目_5496 {
    /**
     * 贪心算法
     * 先排序，再将当前最小的和最大的分给其他两人，自己保留次大的数，排除当前三个数后再依次执行
     *
     * @param piles
     * @return
     */
    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int result = 0;
        int begin = piles.length / 3;
        //简化版： 先将最小的 N/3 个分出去，再从0开始第(N/3)个遍历累加，每次index+=2;
        for (; begin < piles.length; begin += 2) {
            result += piles[begin];
        }
        return result;
    }
}

class Solution {
/**
     * 1、使用N的数组保存，模拟计数
     * 2、简化问题：
     * （1）当数组的第一位 和 最后一位是相同的，则表明，中间跑了完整的 M 圈，
     * 由于是起始位置，那么就会相对于其他分段 就会多跑一次，所以返回起始阶段
     * （2）如果，起始点和结束点不一致，则分为两种情况，结束点 大于 起始点，则直接保存即可
     * 结束点 小于 起始点，表明跨越了最大分段，需要再从1加到结束点
     *
     * @param n
     * @param rounds
     * @return
     */
    public List<Integer> mostVisited(int n, int[] rounds) {
        List<Integer> result = new ArrayList<>();
        int begin = rounds[0];
        int end = rounds[rounds.length - 1];
        if (begin == end) {
            result.add(begin);
        } else {
            while (begin != end) {
                result.add(begin);
                begin++;
                if (begin > n) {
                    begin -= n;
                }
            }
            result.add(end);
        }
        Collections.sort(result);
        return result;
    }
}