LeetCode刷题(十)——顺序刷题46至50

46.全排列

给定一个不含重复数字的数组 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：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

分析：这一题就是很简单的dfs问题，而且数组中的元素都不相同，我们可以选择在每个位置放不同的数形成一种树形结构来实现全排列。
代码：

class Solution {
    
public:
    vector<vector<int>>res;
    vector<int>path;
    bool st[7];
    vector<vector<int>> permute(vector<int>& nums) {
    
        dfs(nums,0);
        return res;
    }
    void dfs(vector<int>nums,int u)
    {
    
    	//说明位置都已经满了，就可以将答案放到res中了
        if( u == nums.size())
        {
    
            res.push_back(path);
            return;
        }
        for(int i=0; i<nums.size(); i++)
        {
    
            if(!st[i])//如果这个数还没用过
            {
    
                st[i]=true;
                path.push_back(nums[i]);
                dfs(nums,u+1);
                //恢复现场
                path.pop_back();
                st[i]=false;    
            }
        }
    }
};

---

47.全排列 I I

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

分析：这一题与46题的区别在于包含了相同元素，如果和46题采用同样方法的话会产生很多重复的结果，这样是错误的，既然包含了同样的元素我们可以规定相同元素的使用顺序（比如要排列的顺序是1 1 1 2，可以看到存在着三个"1"，我们可以规定只有第一个"1"用完了，第二个"1"才可以用，同理，只有当第二个"1"用完了第三个"1"才可以用），这样就可以规避调重复的情况了。
代码：

class Solution {
    
public:
    vector<int>path;
    vector<vector<int>>res;
    vector<bool>st;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    
        sort(nums.begin(),nums.end());
        st = vector<bool>(nums.size());
        dfs(nums,0);
        return res;
    }
    void dfs(vector<int>& nums,int u)
    {
    
        if( u == nums.size())
        {
    
            res.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); i++)
        {
    
            //如果nums[i]还未使用
            if(!st[i])
            {
    
            	//实现顺序使用的操作
                if(i&&nums[i]==nums[i-1]&&!st[i-1])continue;
                path.push_back(nums[i]);
                st[i]=true;
                dfs( nums, u+1);
                st[i]=false;
                path.pop_back();

            }
        }
    }
};

---

48.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：

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

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

分析：这题要说难其实也难，但是如果刚好想到了那其实是会做的出来的（有点像脑筋急转弯），向右旋转90°可以分解成沿着斜右对角线对称交换位置+左右对称

代码：

class Solution {
    
public:
    void rotate(vector<vector<int>>& matrix) {
    
        int n = matrix.size();
        //右斜对角线交换
        for(int i = 0; i < n; i++)
        {
    
            for(int j = 0; j < i; j++)
            {
    
                swap(matrix[i][j],matrix[j][i]);
            }
        }
		//左右交换
        for(int i = 0; i < n; i++)
        {
    
            for(int j = 0 , k = n - 1; j < k; j++,k--)
            {
    
                swap(matrix[i][j],matrix[i][k]);
            }
        }
    }
};

---

49.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

分析：找出同一分组的共同点，即字母组成相同，我们可以将str数组中的每个string都进行排序（当然，我们得把原str数组中的元素给保存下来），然后进行比较就可以判断是否是在同一个组中，可以通过hash进行存储和分类，最后输出答案就可以了。
代码：

class Solution {
    
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
    
        unordered_map<string,vector<string>>mmap;
        for(auto & item : strs){
    
            string strTmp = item;
            sort(item.begin(),item.end());//进行排序
            mmap[item].push_back(strTmp); //利用hash进行分类，将排序完的元素作为key
        }
		//输出答案
        vector<vector<string>>res;
        for(auto & item : mmap){
    
            res.push_back(item.second);
        }

        return res;
    }
};

---

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。
示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2^-2 = 1/2^2 = 1/4 = 0.25

提示：

-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= x^n <= 10^4

分析：这一题就是很典型的快速幂问题，如下图

代码：

class Solution {
    
public:
    double myPow(double x, int n) {
    
        bool is_minus = n < 0;
        double res = 1;
        for(long long k = abs(n); k > 0; k>>=1)
        {
    
            if(k & 1)//按位与
            {
    
                res *= x;
            }
            x *=x;
        }
        
        if(is_minus) return 1/res;
        return res;
    }
};