? LeetCode 热题 HOT 100: 46 && 48

“Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。”

46. 全排列

一、题目描述：

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]

输出：[[0,1],[1,0]]

二、思路分析：

• 回溯， 遍历所有的可能， 主要考虑3点

1. 结束的条件（path 的 size 等于数组的大小）
2. 可以做出的选择(num 不在已经做出的选择之中 ）
3. 记录已经做出的选择（path）

三、AC 代码：

class Solution {

    List<List<Integer>> ans;
    public List<List<Integer>> permute(int[] nums) {
        this.ans = new ArrayList<>();
        dfs(nums, new ArrayList<>());

        return ans;
    }

    void dfs(int[] nums, List<Integer> path){
        if(path.size() == nums.length){
            ans.add(new ArrayList<>(path));
            return;
        }

        for(int num : nums){
            if(path.contains(num)){
                continue;
            }
            path.add(num);
            dfs(nums, path);
            path.remove(path.size() - 1);
        }
    }
}
复制代码

48. 旋转图像

一、题目描述：

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

输入： matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出： [[7,4,1],[8,5,2],[9,6,3]]
复制代码

二、思路分析：

自外向内，对每一层进行旋转即可

三、AC 代码：

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        int lr = 0, lc = 0, rr = n - 1, rc = n - 1;
        while(lr < rr){
            rate(matrix, lr, lc, rr, rc);
            lr++;
            lc++;
            rr--;
            rc--;
        }
    }

    void rate(int[][] matrix, int lr, int lc, int rr, int rc){
        int count = rr - lr;
        int index = 0;
        while(index < count){
            int temp = matrix[lr][lc + index];
            matrix[lr][lc + index] = matrix[rr - index][lc];
            matrix[rr - index][lc] = matrix[rr][rc - index];
            matrix[rr][rc - index] = matrix[lr + index][rc];
            matrix[lr + index][rc] = temp;
            index++;
        }
    }
}
复制代码