每日5题Day10 - LeetCode 46 - 50

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：46. 全排列 - 力扣（LeetCode）

class Solution {
    //这道题就是一个dfs
    //把所有结果遍历，到叶子节点就可以添加结果了
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        //要给一个flag数组来判断是否被选过
        //以此来成为排列、不是组合
        int[] flag = new int[nums.length];
        traversal(0, nums, flag);
        return res;
    }
 
    private void traversal(int startindex, int[] nums, int[] flag){
        if(startindex == nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(flag[i] == 0){
                flag[i] = 1;
                path.add(nums[i]);
                traversal(startindex + 1, nums, flag);
                path.removeLast();
                flag[i] = 0;
            }
        }
    }
}

---

第二题：47. 全排列 II - 力扣（LeetCode）

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int[] flag = new int[nums.length];
        traversal(0, res, path, nums, flag);
        return res;
    }
    private void traversal(int start, List<List<Integer>> res, List<Integer> path, int[] nums, int[] flag){
        if(start == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            //和上一题一样，但是数组会有重复的，
            //所以我们要剪枝去重
            if(flag[i] == 1 || (i > 0 && nums[i] == nums[i - 1] && flag[i - 1] == 0)){
                continue;
            }
            flag[i] = 1;
            path.add(nums[i]);
            traversal(start + 1, res ,path, nums, flag);
            path.removeLast();
            flag[i] = 0;
        }
    }
}

---

第三题：48. 旋转图像 - 力扣（LeetCode）

class Solution {
    public void rotate(int[][] matrix) {
        //题目要求不能复制来实现，要原地调转，
        //所以不能笨笨地复制粘贴，那样会用很多额外空间
        int n = matrix.length;
        // 先沿对角线翻转
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // 再沿中线左右翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}
 

---

第四题：49. 字母异位词分组 - 力扣（LeetCode）

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 朴素的做法，时间长但是空间非常小
        // 使用 flag 数组标记已经处理过的字符串
        int[] flag = new int[strs.length];
        // 结果列表
        List<List<String>> res = new ArrayList<>();
        // 遍历每个字符串
        for(int i = 0; i < strs.length; i++){
            // 如果当前字符串已经处理过，直接跳过
            if(flag[i] == 1){
                continue;
            }
            // 临时列表，用于存放同一组异位词
            List<String> tmp = new ArrayList<>();
            // 统计当前字符串的字符频率
            int[] fre = new int[26];
            for(int j = 0; j < strs[i].length(); j++){
                fre[strs[i].charAt(j) - 'a']++;
            }
            // 遍历剩余字符串，寻找异位词
            for(int k = i; k < strs.length; k++){
                int flagg = 0;
                // 如果当前字符串已经处理过，直接跳过
                if(flag[k] == 1){
                    continue;
                }
                // 统计当前遍历到的字符串的字符频率
                int[] free = new int[26];
                for(int j = 0; j < strs[k].length(); j++){
                    free[strs[k].charAt(j) - 'a']++;
                }
                // 检查是否为异位词
                for(int x = 0; x < 26; x++){
                    if(fre[x] != free[x]){
                        flagg = 1;
                        break;
                    }
                }
                // 如果是异位词，则加入临时列表，并标记已处理
                if(flagg == 0){
                    tmp.add(strs[k]);
                    flag[k] = 1;
                }
            }
            // 将当前异位词组加入结果列表
            res.add(tmp);
        }
        return res;
    }
}

---

 第五题：50. Pow(x, n) - 力扣（LeetCode）

class Solution {
    public double myPow(double x, int n) {
        // 这道题最适合就是使用递归来实现
        // 如果指数为0，则结果为1
        if(n == 0) {
            return 1.0;
        }
        // 如果指数为负数，则将底数取倒数，指数取绝对值
        if(n < 0) {
            return 1 / (x * myPow(x, -(n + 1)));
        }
        // 如果指数为正数，则使用递归计算幂
        double temp = myPow(x, n / 2);
        // 如果指数为偶数，则结果为 temp 的平方
        if(n % 2 == 0) {
            return temp * temp;
        } else { // 如果指数为奇数，则结果为 temp 的平方乘以底数
            return temp * temp * x;
        }
    }
}

---