class Solution {
   /**
     * 优化方法 -- check 同一列、主对角线、副对角线的状态检查
     * 主对角线 -- 横坐标 - 纵坐标 （在同一主对角线上的点，两坐标相减总相等 ，为了保证数组不越界，加上偏移量）
     * 副对角线 -- 横坐标 + 纵坐标 （在同一副对角线上的点，两坐标相加总相等）
     */

    /**
     * 回溯算法（按行存放 皇后 ，backTracing(help, 0);）
     * backTracing(String[][] help, int index) 当index大于等于n时，结束递归，加入结果集
     * <p>
     * 当准备向 第 index 行 选择第 j 列，进行存放 Q 时，先进行竖向检查、左上检查、以及右上检查，都符合条件时，再修改数组，进行递归，
     * 最后 修改回 原先临时数组状态
     *
     * @param n
     * @return
     */

    static List<List<String>> result;

    static boolean[] shuXiangHelp;//j为坐标  size = length  i - j 的取值范围为：[-(length-1) , length -1]
    static boolean[] zhuDuiJiaoHelp;// i -j + length -1为坐标  size = 2*length-1;
    static boolean[] fuDuiJiaoHelp;// i -j + length -1为坐标  size = 2*length-1;


    public static List<List<String>> solveNQueens(int n) {
        char[][] help = new char[n][n];
        shuXiangHelp = new boolean[n];
        zhuDuiJiaoHelp = new boolean[2 * n - 1];
        fuDuiJiaoHelp = new boolean[2 * n - 1];
        result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Arrays.fill(help[i], '.');
        }
        backTracing(help, 0);
        return result;
    }

    private static void backTracing(char[][] help, int index) {
        //backTracing(String[][] help, int index) 当index大于等于n时，结束递归，加入结果集
        if (index >= help.length) {
            ArrayList<String> list = new ArrayList<>();
            for (int i = 0; i < help.length; i++) {
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < help[i].length; j++) {
                    builder.append(help[i][j]);
                }
                list.add(builder.toString());
            }
            result.add(list);
            return;
        }
        // 当准备向 第 index 行 选择第 j 列，进行存放 Q 时，先进行竖向检查、左上检查、以及右上检查，都符合条件时，再修改数组，进行递归，
        // 最后 修改回 原先临时数组状态
        for (int j = 0; j < help.length; j++) {
            if (!checkZhuDuiJiao(index, j, help.length)) {
                continue;
            }
            if (!checkFuDuiJiao(index, j, help.length)) {
                continue;
            }
            if (!checkShuxiang(j)) {
                continue;
            }
            zhuDuiJiaoHelp[index - j + help.length - 1] = true;
            fuDuiJiaoHelp[index + j] = true;
            shuXiangHelp[j] = true;
            help[index][j] = 'Q';
            backTracing(help, index + 1);
            help[index][j] = '.';
            zhuDuiJiaoHelp[index - j + help.length - 1] = false;
            fuDuiJiaoHelp[index + j] = false;
            shuXiangHelp[j] = false;
        }
    }

    /**
     * 主对角线 -- 横坐标 - 纵坐标 （在同一主对角线上的点，两坐标相减总相等 ，为了保证数组不越界，加上偏移量）
     *
     * @param index
     * @param j
     * @param length
     * @return
     */
    private static boolean checkZhuDuiJiao(int index, int j, int length) {
        return !zhuDuiJiaoHelp[index - j + length - 1];
    }

    /**
     * 副对角线 -- 横坐标 + 纵坐标 （在同一副对角线上的点，两坐标相加总相等）
     *
     * @param index
     * @param j
     * @param length
     * @return
     */
    private static boolean checkFuDuiJiao(int index, int j, int length) {
        return !fuDuiJiaoHelp[index + j];
    }

    private static boolean checkShuxiang(int j) {
        return !shuXiangHelp[j];
    }


    private static boolean checkXiexiang1(char[][] help, int index, int j) {
        while (index - 1 >= 0 && j - 1 >= 0) {
            if (help[index - 1][j - 1] == 'Q') {
                return false;
            }
            index--;
            j--;
        }
        return true;
    }

    private static boolean checkXiexiang2(char[][] help, int index, int j) {
        while (index - 1 >= 0 && j + 1 < help.length) {
            if (help[index - 1][j + 1] == 'Q') {
                return false;
            }
            index--;
            j++;
        }
        return true;
    }

    private static boolean checkShuxiang2(char[][] help, int index, int j) {
        for (int i = 0; i <= index; i++) {
            if (help[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

class Solution {
/**
     * 递归版本 2
     *
     * @param nums
     * @return
     */
    public static boolean PredictTheWinner(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int n = dfs(nums, 0, nums.length - 1);
        return n >= (sum - n);
    }

    //表示，先手时，在begin - end 范围内能取的最大值
    private static int dfs(int[] nums, int begin, int end) {
        if (begin == end) {
            return nums[begin];
        }
        if (begin + 1 == end) {
            return Math.max(nums[begin], nums[end]);
        }
        // 当前选择begin位置上的数时，则下次选择的范围只能是[begin+1,end-1](后手选择了end)、或者是[bengin+2,end](后手选择了begin+1)
        // Math.min(dfs(nums, begin + 1, end - 1), dfs(nums, begin + 2, end));后手一定会留最小的取值范围
        int beginValue = nums[begin] + Math.min(dfs(nums, begin + 1, end - 1), dfs(nums, begin + 2, end));
        int endValue = nums[end] + Math.min(dfs(nums, begin + 1, end - 1), dfs(nums, begin, end - 2));
        return Math.max(beginValue, endValue);
    }


    /**
     * 递归版本一
     *
     * @param nums
     * @return
     */
    public static boolean PredictTheWinner4(int[] nums) {
        return dfs2(nums, 0, nums.length - 1, 1) >= 0;
    }

    private static int dfs2(int[] nums, int begin, int end, int flag) {
        if (begin == end) {
            return nums[begin] * flag;
        }
        int socreBegin = nums[begin] * flag + dfs2(nums, begin + 1, end, -flag);
        int socreEnd = nums[end] * flag + dfs2(nums, begin, end - 1, -flag);
        if (flag == 1) {
            return Math.max(socreBegin, socreEnd);
        } else {
            return Math.min(socreBegin, socreEnd);
        }
    }


    /**
     * 优化的 DP  -- dp[i][j] 与 另一方法的 表意不同
     * 定义二维数组 dp，其行数和列数都等于数组的长度，dp[i][j] 表示当数组剩下的部分为下标 i 到下标 j时，当前玩家领先数值大小
     * 当前玩家与另一个玩家的分数之差的最大值，注意当前玩家不一定是先手。
     * <p>
     * 只有当 i≤j 时，数组剩下的部分才有意义，因此当 i>j 时，dp[i][j]=0。
     *
     * @param nums
     * @return
     */
    public static boolean PredictTheWinner2(int[] nums) {
        int length = nums.length;
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = nums[i];
        }
        for (int end = 1; end < length; end++) {
            for (int begin = end - 1; begin >= 0; begin--) {
                //begin -end 范围内，player1先手，取begin位置上的数， nums[begin] - dp[begin + 1][end]
                //dp[begin + 1][end] 表示 此时 player2 的领先数值大小
                dp[begin][end] = Math.max(nums[begin] - dp[begin + 1][end], nums[end] - dp[begin][end - 1]);
            }
        }
        return dp[0][length - 1] >= 0;
    }

    static int[] temp;

    /**
     * dp 动态规划  int[][] dp = new int[length][length];
     * dp[begin][end] 表示: 在nums数组中的begin - end 范围内，先手 所能获取到的最大值
     * 就是计算出player1可能得到的最大分数，然后用数组总和减去player1的得分就是player2的得分，然后两者比较一下就可以了。
     *
     * @param nums
     * @return
     */
    public static boolean PredictTheWinner3(int[] nums) {
        int length = nums.length;
        int[][] dp = new int[length][length];
        temp = new int[length];
        int pre = 0;
        for (int i = 0; i < length; i++) {
            temp[i] = pre + nums[i];
            pre = temp[i];
        }
        for (int end = 0; end < length; end++) {
            for (int begin = end; begin >= 0; begin--) {
                if (begin == end) {
                    // 如果当前 begin 和 end 相等，则dp[begin][end] = nums[end];
                    dp[begin][end] = nums[end];
                } else {
                    //当前先手取 begin位置上的值，则 num1 = nums[begin] + （begin-1,end）范围内的最小值
                    //（begin-1,end）范围内的最小值 的获取： sum(begin + 1, end, nums) - dp[begin + 1][end];
                    //（begin-1,end）所有数据之和  减去 （begin-1,end）范围内先手的最大值
                    int num1 = nums[begin] + sum(begin + 1, end, nums) - dp[begin + 1][end];
                    //当前先手取 end 位置上的值
                    int num2 = nums[end] + sum(begin, end - 1, nums) - dp[begin][end - 1];
                    dp[begin][end] = Math.max(num1, num2);
                }
            }
        }
        int sum = sum(0, length - 1, nums);
        int leftNum = sum - dp[0][length - 1];
        return dp[0][length - 1] >= leftNum;
    }

    //求取begin - end 之间的和
    private static int sum(int begin, int end, int[] nums) {
        return temp[end] - temp[begin] + nums[begin];
    }
}

/**
 * tags: 欧拉路径  dfs 回溯  图
 * <p>
 * <p>
 * 什么是欧拉路径？欧拉路径就是一条能够不重不漏地经过图上的每一条边的路径，即小学奥数中的一笔画问题。而若这条路径的起点和终点相同，则将这条路径称为欧拉回路。
 * <p>
 * 如何判断一个图是否有欧拉路径呢？显然，与一笔画问题相同，一个图有欧拉路径需要以下几个条件：
 * <p>
 * 首先，这是一个连通图
 * 若是无向图，则这个图的度数为奇数的点的个数必须是0或2；若是有向图，则要么所有点的入度和出度相等，要么有且只有两个点的入度分别比出度大1和少1
 * 上面这两个条件很好证明。查找欧拉路径前，必须先保证该图满足以上两个条件，否则直接判误即可。
 * <p>
 * 查找欧拉路径的算法有Fluery算法和Hierholzer算法。下面介绍一下Hierholzer算法。
 *
 * @author l00511002
 * @since 2020-08-27
 */
class Solution {
    /**
     * 测试代码
     * 特殊用例--[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
     * String[][] array = {{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}};
     * String[][] array = {{"JFK", "KUL"}, {"JFK", "NRT"}, {"NRT", "JFK"}};
     * String[][] array = {{"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"}, {"ATL", "SFO"}};
     * List<List<String>> tickets = new ArrayList<>();
     * for (int i = 0; i < array.length; i++) {
     * String[] strs = array[i];
     * List<String> strings = Arrays.asList(strs);
     * tickets.add(strings);
     * }
     *
     * @param args
     */
    public static void main(String[] args) {
        String[][] array = {{"JFK", "KUL"}, {"JFK", "NRT"}, {"NRT", "JFK"}};
        List<List<String>> tickets = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            String[] strs = array[i];
            List<String> strings = Arrays.asList(strs);
            tickets.add(strings);
        }
        System.out.println(findItinerary(tickets));
    }

    /**
     * 新建一个 HashMap<String, ArrayList<String>> map , key 表示 from , value 表示 to 的 list
     * map 填充完毕后，对 list 进行排序，目的在于保证找到result-size长度的第一个集合就是按字符自然排序的
     * （result的size一定等于tickets.length+1）
     * 接着 DFS + 回溯 ，这里注意，从list中获取一个to时，先判断是否为空串，若不是，加入到tempList中，继续调用dfs方法
     * 若是空串，表明，该 to 已经访问过，直接continue！！！
     * -- 注意，dfs处理完当前string后，一定要将其从空串复原， 且 复原 tempResult ！！！
     * --- 定义全局 Boolean变量，剪枝 的同时，保证全局变量result 只会赋值一次 !!
     *
     * @param tickets
     * @return
     */
    static List<String> result;

    static boolean hasFind;

    public static List<String> findItinerary2(List<List<String>> tickets) {
        result = new ArrayList<>();
        hasFind = false;
        HashMap<String, ArrayList<String>> map = new HashMap<>();
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            if (map.containsKey(from)) {
                map.get(from).add(to);
            } else {
                ArrayList<String> list = new ArrayList<>();
                list.add(to);
                map.put(from, list);
            }
        }
        //对list进行排序
        for (Map.Entry<String, ArrayList<String>> entry : map.entrySet()) {
            ArrayList<String> value = entry.getValue();
            value.sort((x, y) -> x.compareTo(y));
        }
        String from = "JFK";
        int targetLength = tickets.size() + 1;
        ArrayList<String> tempResult = new ArrayList<>();
        tempResult.add(from);
        dfs2(tempResult, map, from, targetLength);
        return result;
    }

    private static void dfs2(ArrayList<String> tempResult, HashMap<String, ArrayList<String>> map, String
            from, int targetLength) {
        // 定义全局变量，剪枝 的同时，保证全局变量result 只会赋值一次
        if (hasFind) {
            return;
        }
        if (tempResult.size() == targetLength) {
            result = new ArrayList<>(tempResult);
            hasFind = true;
            return;
        }
        if (!map.containsKey(from)) {
            return;
        }
        ArrayList<String> list = map.get(from);
        for (int i = 0; i < list.size(); i++) {
            String to = list.get(i);
            if (to.length() == 0) {
                continue;
            }
            // 修改为空串，表明 改 string 已经访问过了
            list.set(i, "");
            tempResult.add(to);
            dfs2(tempResult, map, to, targetLength);
            // 复原 tempResult
            tempResult.remove(tempResult.size() - 1);
            //注意，dfs处理完当前string后，一定要将其从空串复原！！！
            list.set(i, to);
        }
    }

    /******************* 代码优化  *****************************************/
    /**
     * Hierholzer 算法用于在连通图中寻找欧拉路径，其流程如下：
     * 1、从起点出发，进行深度优先搜索。
     * 2、每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。
     * 3、如果没有可移动的路径，则将所在节点加入到栈中，并返回。
     * <p>
     * 当我们顺序地考虑该问题时，我们也许很难解决该问题，因为我们无法判断当前节点的哪一个分支是「死胡同」分支。
     * 不妨倒过来思考。我们注意到只有那个入度与出度差为 11 的节点会导致死胡同。而该节点必然是最后一个遍历到的节点。
     * 我们可以改变入栈的规则，当我们遍历完一个节点所连的所有节点后，我们才将该节点入栈（即逆序入栈）。
     * 对于当前节点而言，从它的每一个非「死胡同」分支出发进行深度优先搜索，都将会搜回到当前节点。
     * 而从它的「死胡同」分支出发进行深度优先搜索将不会搜回到当前节点。
     * 也就是说当前节点的死胡同分支将会优先于其他非「死胡同」分支入栈。
     * 这样就能保证我们可以「一笔画」地走完所有边，最终的栈中逆序地保存了「一笔画」的结果。我们只要将栈中的内容反转，即可得到答案。
     */
    static List<String> list;
    //定义一个优先级队列，用来存放to集合
    static HashMap<String, PriorityQueue<String>> map;

    public static List<String> findItinerary(List<List<String>> tickets) {
        list = new ArrayList<>();
        map = new HashMap<>();
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            if (!map.containsKey(from)) {
                map.put(from, new PriorityQueue<>());
            }
            map.get(from).offer(to);
        }
        dfs("JFK");
        return list;
    }

    private static void dfs(String from) {
        while (map.containsKey(from) && !map.get(from).isEmpty()) {
            dfs(map.get(from).poll());
        }
        //头插法
        list.add(0, from);
    }
}