11.3打卡

1. 字母异位词分组（49）

将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
        for (String str : strs) {
             char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key,list);
        }
        return new ArrayList<>(map.values());
    }
}

2. pow(x, n)（50）

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数

思想：二分+位运算，需要考虑Java int溢出

class Solution {
    public double myPow(double x, int n) {
        long b  = n;
        if(x==0.0)return 0.0;
        if(b<0){
            x = 1/x;
            b =-b;
        }
        double res = 1.0;
        while (b>0){
            if((b&1)==1) res *=x;
            x *=x;
            b>>=1;
        }
        return res;
    }
}

3.N皇后（51）

思想：回溯，用数字代表所在斜对角

class Solution {
    public List<List<String>> solveNQueens(int n) {
 List<List<String>> res = new ArrayList<>();
        Set<Integer> columns= new HashSet<>(n);
        Set<Integer> diag1= new HashSet<>(n);
        Set<Integer> diag2= new HashSet<>(n);
        int[] queens =new int[n];
        for (int i = 0; i <n ; i++) {
            queens[i]=-1;
        }
        bpdfs(res,0,n,queens,columns,diag1,diag2);
        return res;
     }

    private void bpdfs(List<List<String>> res, int row, int n, int[] queens, Set<Integer> columns, Set<Integer> diag1, Set<Integer> diag2) {
        if(row==n){
            List<String> list = show(queens,n);
            res.add(list);
            return;
        }
        for (int i = 0; i < n; i++) {
            if(columns.contains(i))
                continue;
            int pos1 = row - i;
            if(diag1.contains(pos1))
                continue;
            int pos2= row+i;
            if(diag2.contains(pos2))
                continue;
            queens[row]=i;
            columns.add(i);
            diag1.add(pos1);
            diag2.add(pos2);
            bpdfs(res,row+1,n,queens,columns,diag1,diag2);
            queens[row]=-1;
            columns.remove(i);
            diag1.remove(pos1);
            diag2.remove(pos2);
        }
    }
         private List<String> show(int[] queens, int n) {
        List<String> res =new ArrayList<>();
        for (int i = 0; i <n ; i++) {
            char[] temp = new char[n];
            Arrays.fill(temp,'.');
            temp[queens[i]] = 'Q';
            res.add(new String(temp));
        }
        return res;
    }
    
}