package com.demo.s54;

import java.util.ArrayList;
import java.util.List;

/**
 * 螺旋矩阵
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 *
 */
public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ret = new ArrayList();
        if(matrix == null || matrix.length ==0 || matrix[0].length ==0) {
            return ret;
        }
        //判断需要旋转的几个方向
        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        //行数
        int m = matrix.length;
        //列数
        int n = matrix[0].length;
        int[][] visited = new int[m][n];
        int i =0;
        int j =0;
        //方向
        int directions = 0;
        for(int cnt = 0; cnt < m*n; cnt++) {
            //已访问
            visited[i][j] = 1;

            ret.add(matrix[i][j]);

            //下一个节点对应的行  遍历的方向 dirs[directions][0] 控制
            int nexti = i + dirs[directions][0];
            //下一个节点对应的列  遍历的方向 dirs[directions][1] 控制
            int nextj = j + dirs[directions][1];
            //边界判断
            if(nexti < 0 || nexti > m-1 || nextj < 0 ||nextj > n-1 || visited[nexti][nextj] == 1 ) {
                directions = (directions+1) % 4;
            }
            //行数变更 + 1 或者 不变
            i = i + dirs[directions][0];
            //列数变更 + 1 或者 不变
            j = j + dirs[directions][1];


        }
        return ret;
    }
}

package com.demo.s53;

/**
 * 最大子数组和
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分。
 */
public class Solution {
    public int maxSubArray(int[] nums) {
        //假定第一个是最大子元素
        int max = nums[0];
        //设置一个和参数，默认0
        int sum = nums[0];
        for(int i =1; i< nums.length; i++) {
            //累计的和大于0，则继续累计
            if(sum > 0){
                sum += nums[i];
            } else {
                //累计和不大于0 ，重新开始累计
                sum = nums[i];
            }
            //求最大和
            max = Math.max(sum, max);

        }
        return max;
    }
}

package com.demo.s52;

import java.util.HashSet;
import java.util.Set;

/**
 * N皇后 II
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/n-queens-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int totalNQueens(int n) {
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        return backtrack(n, 0, columns, diagonals1, diagonals2);
    }

    public int backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
            return count;
        }
    }
}

package com.demo.s51;

import java.util.*;

/**
 * N 皇后
 *按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 *
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 *
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/n-queens
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }
                queens[row] = i;
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

package com.demo.s50;

/**
 * Pow(x, n)
 * 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
 */
public class Solution {
    public double myPow(double x, int n) {
        //基数
        double base = x;
        //判断n 小于0 基数特殊处理
        if(n < 0) {
            base = 1/x;
        }
        double ans = 1;
        //循环
        while(n != 0) {
            //奇数次
            if (n % 2 != 0) {
                ans = ans * base;
            }

            base = base * base;
            n = n/2;
        }
        return ans;
    }
}

package com.demo.s5;

/**
 * 最长回文子串
 */
public class Solution {
    public String longestPalindrome(String s) {
        //定义回文子串的起始
        int start = 0;
        int end = 0;
        //遍历字符串字符
        for(int i = 0; i< s.length(); i++) {
            //以当前字符为中心点扩展
            int len1 = expandAroundCenter(s, i, i);
            //以当前字符和下一个字符为中心点扩展
            int len2 = expandAroundCenter(s, i, i + 1);
            //取两种方式扩展最大长度
            int max = Math.max(len1, len2);
            if(max > end -start + 1) {
                //-1防止 当前字符和下一个字符为中心点扩展 导致的问题
                start = i - (max-1) / 2;
                end = i + max /2;
            }
        }
        return s.substring(start,  end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        //左右相等则扩展
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left --;
            right ++;
        }
        //返回扩展的子串长度
        return right - left -1;
    }
}

package com.demo.s49;

import java.util.*;

/**
 * 字母异位词分组
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 *
 * 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/group-anagrams
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

package com.demo.s48;

/**
 *  旋转图像
 *  给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
 *
 * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/rotate-image
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix.length == 0 || matrix.length != matrix[0].length) {
            return;
        }
        int nums = matrix.length;
        for (int i = 0; i < nums; ++i){
            for (int j = 0; j < nums - i; ++j){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[nums - 1 - j][nums - 1 - i];
                matrix[nums - 1 - j][nums - 1 - i] = temp;
            }
        }
        for (int i = 0; i < (nums >> 1); ++i){
            for (int j = 0; j < nums; ++j){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[nums - 1 - i][j];
                matrix[nums - 1 - i][j] = temp;
            }
        }
    }
}

package com.demo.s470;


/**
 * 给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
 *
 * 你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。
 *
 * 每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/implement-rand10-using-rand7
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class SolBase {
    public int rand7() {
        return (int)(Math.random() * 10 % 7);
    }
}
public class Solution extends SolBase {

    //随机产生01
    private int random01() {
        int i = rand7();
        //通过4分割 123 -> 0 ;567 -> 1 如果刚好是4 就重来
        if(i< 4) {
            return 0;
        } else if( i > 4){
            return 1;
        } else {
            return random01();
        }
    }

    //随机10 通过4位二进制标识
    public int rand10() {
        int x = 0;
        //
        for(int i = 0; i < 4;i++) {
            int i1 = random01();
            int i2 = i1 << i; //左移i位
            x = x + i2;
        }
        //如果超出了 [1, 10] 重新来
        if(x>=1 && x<= 10) {
            return x;
        } else {
            return rand10();
        }
    }
}

package com.demo.s47;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 全排列 II
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 */
public class Solution {
    boolean[] vis;
    public List<List<Integer>> permuteUnique(int[] nums) {
        //返回值
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        //对原数组排序
        Arrays.sort(nums);
        //从下标0开始 回溯nums 中间结果存perm， 最终结果放到ans
        backtrack(nums, ans, 0, perm);
        return ans;
    }
    //回溯法
    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            //回溯过得本地不再回溯
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            //第二次开始重置为false
            vis[i] = false;
            perm.remove(idx);
        }
    }


}