Leetcode question brushing (10) - sequential question brushing 46 to 50

46. Full Permutation

Given a No duplicate numbers Array of nums , Back to its All possible permutations . You can In any order Return to the answer .
Example 1：

 Input ：nums = [1,2,3]
 Output ：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2：

 Input ：nums = [0,1]
 Output ：[[0,1],[1,0]]

Example 3：

 Input ：nums = [1]
 Output ：[[1]]

Tips ：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums  All integers in   Different from each other 

analysis ： This question is very simple dfs problem , And the elements in the array are different , We can choose to put different numbers in each position to form a tree structure to achieve full arrangement .
Code ：

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)
    {
    
    	// It means that the positions are full , You can put the answer in res It's in 
        if( u == nums.size())
        {
    
            res.push_back(path);
            return;
        }
        for(int i=0; i<nums.size(); i++)
        {
    
            if(!st[i])// If this number has not been used 
            {
    
                st[i]=true;
                path.push_back(nums[i]);
                dfs(nums,u+1);
                // Restore the scene 
                path.pop_back();
                st[i]=false;    
            }
        }
    }
};

---

47. Full Permutation I I

Given a Can contain duplicate numbers Sequence nums , In any order Returns all non repeating permutations .
Example 1：

 Input ：nums = [1,1,2]
 Output ：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2：

 Input ：nums = [1,2,3]
 Output ：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Tips ：

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

analysis ： This question is related to 46 The difference between questions is that they contain the same elements , If and 46 Using the same method will produce many repeated results , This is wrong , Since the same elements are included, we can specify the order of use of the same elements （ For example, the order to be arranged is 1 1 1 2, You can see that there are three "1", We can stipulate that there is only the first "1" Run out of , the second "1" Just can use , Empathy , Only when the second "1" Used up the third "1" Just can use ）, In this way, we can avoid the repetition of tone .
Code ：

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++)
        {
    
            // If nums[i] Not yet used 
            if(!st[i])
            {
    
            	// Realize the operation of sequential use 
                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. Rotated image

Given a n × n Two dimensional matrix of matrix Represents an image . Please rotate the image clockwise 90 degree .
You must be there. In situ Rotated image , This means that you need to modify the input two-dimensional matrix directly . Please do not Use another matrix to rotate the image .
Example 1：

 Input ：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 Output ：[[7,4,1],[8,5,2],[9,6,3]]

Example 2：

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

Tips ：

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

analysis ： This question is difficult to say, but it is also difficult , But if I happen to think of it, I will actually do it （ It's kind of like a brain teaser ）, Spin to the right 90° Can be broken down into Exchange positions symmetrically along the diagonal on the right + Right and left symmetry

Code ：

class Solution {
    
public:
    void rotate(vector<vector<int>>& matrix) {
    
        int n = matrix.size();
        // Right diagonal swap 
        for(int i = 0; i < n; i++)
        {
    
            for(int j = 0; j < i; j++)
            {
    
                swap(matrix[i][j],matrix[j][i]);
            }
        }
		// Left-right exchange 
        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. Letter heterotopic word grouping

Here's an array of strings , Would you please Letter heterotopic word Put together . You can return a list of results in any order .
Letter heterotopic word Is a new word obtained by rearranging the letters of the source word , Letters in all source words are usually used just once .
Example 1:

 Input : strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 Output : [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

 Input : strs = [""]
 Output : [[""]]

Example 3:

 Input : strs = ["a"]
 Output : [["a"]]

Tips ：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i]  Only lowercase letters 

analysis ： Find the common ground of the same group , That is, the composition of letters is the same , We can str Every... In the array string Sort them all （ Of course , We have to put the original str The elements in the array are saved ）, Then we can judge whether it is in In the same group , Can pass hash Store and classify , Finally, output the answer .
Code ：

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());// Sort 
            mmap[item].push_back(strTmp); // utilize hash To classify , Take the sorted elements as key
        }
		// Output the answer 
        vector<vector<string>>res;
        for(auto & item : mmap){
    
            res.push_back(item.second);
        }

        return res;
    }
};

---

50. Pow(x, n)

Realization pow(x, n) , Computation x The integer of n Power function （ namely ,x^n ）.
Example 1：

 Input ：x = 2.00000, n = 10
 Output ：1024.00000

Example 2：

 Input ：x = 2.10000, n = 3
 Output ：9.26100

Example 3：

 Input ：x = 2.00000, n = -2
 Output ：0.25000
 explain ：2^-2 = 1/2^2 = 1/4 = 0.25

Tips ：

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

analysis ： This problem is a typical fast power problem , Here's the picture

Code ：

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)// Bitwise AND 
            {
    
                res *= x;
            }
            x *=x;
        }
        
        if(is_minus) return 1/res;
        return res;
    }
};