LeetCode开心刷题二十五天——47. Permutations II48. Rotate Image

古城微笑少年丶 2023-08-17 15:14 65阅读 0赞

47. Permutations II

Medium

109246FavoriteShare

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
    Output:
    [
      [1,1,2],
      [1,2,1],
      [2,1,1]
    ]

Accepted

257,204

Submissions

622,317

C++ Method:

Because this is too similar to the last one 46,so just let "set" to delete duplicate in vector

we use this method

Use this method to change to former code can pass.But this is poor performance

#include<set>
    #include<vector>
    #include<iostream>
    using namespace std;
    
    
    int main()
    {
    vector<int> vec;
    vec = { 1, 2, 3, 4, 8, 9, 3, 2, 1, 0, 4, 8 };
    //for loop just let vec begin to end give set,then evaluate set to vector again
    set<int> st(vec.begin(), vec.end());
    vec.assign(st.begin(), st.end());
    
    
    vector<int>::iterator it;
    for (it = vec.begin(); it != vec.end(); it++)
    //& means address,* means get value
    cout << *it<<endl;
    return 0;
    }

#include<stdio.h>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<set>
    using namespace std;
    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            set<vector<int>> res;
            vector<vector<int>> res1;
            vector<int> out,visited(nums.size(),0);
            DFS(out,nums,res,visited,0);
            res1.assign(res.begin(), res.end());
            return res1;
        }
    
        void DFS(vector<int>& out,vector<int>& nums,set<vector<int>>& res,vector<int>& visited,int label)
        {
            if(label==nums.size()) {res.insert(out);return;}
            for(int i=0;i<nums.size();i++)
            {
                if(visited[i]==1) continue;
                out.push_back(nums[i]);
                visited[i]=1;
                DFS(out,nums,res,visited,label+1);
                out.pop_back();
                visited[i]=0;
            }
            return;
    
        }
    };
    int main()
    {
        Solution s;
        vector<int> v;
        vector<vector<int>> res;
        v.push_back(1);
        v.push_back(1);
        v.push_back(2);
    //    v.push_back(1);
    //    v.push_back(4);
        res=s.permute(v);
        for (vector<vector<int>>::iterator it = res.begin(); it != res.end(); ++it){
            for (int i = 0; i < (*it).size(); ++i)
                cout << (*it)[i] << " " ;
            cout <<endl ;
            }
        //cout<<res<<endl;
        return 0;
    }

Faster Version:

speciality:

1.same variables----->add condition------>if(i>0&&nums\[i\]==nums\[i-1\]&&!visited\[i-1\]) continue;

2.unoreder---->sort first avoid , 3 3 0 3 this same duplicate variable not in the ajacent position.

#include<stdio.h>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<set>
    #include<algorithm>
    using namespace std;
    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            vector<vector<int>> res;
            vector<int> out,visited(nums.size(),0);
            DFS(out,nums,res,visited);
            return res;
        }
    
        void DFS(vector<int>& out,vector<int>& nums,vector<vector<int>>& res,vector<int>& visited)
        {
            if(out.size()==nums.size()) {res.push_back(out);return;}
            for(int i=0;i<nums.size();i++)
            {
                if(visited[i]==1) continue;
                if(i>0&&nums[i]==nums[i-1]&&!visited[i-1]) continue;
                out.push_back(nums[i]);
                visited[i]=1;
                DFS(out,nums,res,visited);
                out.pop_back();
                visited[i]=0;
            }
            return;
    
        }
    };
    int main()
    {
        Solution s;
        vector<int> v;
        vector<vector<int>> res;
        v.push_back(3);
        v.push_back(3);
        v.push_back(0);
        v.push_back(3);
    //    v.push_back(4);
        res=s.permute(v);
        for (vector<vector<int>>::iterator it = res.begin(); it != res.end(); ++it){
            for (int i = 0; i < (*it).size(); ++i)
                cout << (*it)[i] << " " ;
            cout <<endl ;
            }
        //cout<<res<<endl;
        return 0;
    }

python version not quite understand,paste the website:

[https://blog.csdn.net/XX\_123\_1\_RJ/article/details/81021815][https_blog.csdn.net_XX_123_1_RJ_article_details_81021815]

48. Rotate Image

Medium

1716159FavoriteShare

You are given an *n* x *n* 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image [in-place][], which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
    [
      [1,2,3],
      [4,5,6],
      [7,8,9]
    ],
    
    rotate the input matrix in-place such that it becomes:
    [
      [7,4,1],
      [8,5,2],
      [9,6,3]
    ]

Example 2:

Given input matrix =
    [
      [ 5, 1, 9,11],
      [ 2, 4, 8,10],
      [13, 3, 6, 7],
      [15,14,12,16]
    ], 
    
    rotate the input matrix in-place such that it becomes:
    [
      [15,13, 2, 5],
      [14, 3, 4, 1],
      [12, 6, 8, 9],
      [16, 7,10,11]
    ]

Bonus：

xrange函数的循环行为类似于range函数，区别在于range函数一次创建整个序列，而xrange函数一次创建一个数。当需要迭代一个巨大的序列时，xrange会更高效一些。

\`but in python3 xrange combined with range so we only use range is OK

python code need pay attention is first change top-down one is i,another is rows-i-1,rows need to minus one

class Solution:
        def rotate(self,matrix):
            if matrix:
                rows=len(matrix)
                cols=len(matrix[0])
                for i in range(rows//2):
                    for j in range(cols):
                        matrix[i][j],matrix[rows-i-1][j]=matrix[rows-i-1][j],matrix[i][j]
                for j in range(rows):
                    for i in range(j):
                        matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
            return matrix
    
    if __name__ == '__main__':
        solu = Solution()
        matrix=[
              [1,2,3],
              [4,5,6],
              [7,8,9]
            ]
        print(solu.rotate(matrix))

转载于:https://www.cnblogs.com/Marigolci/p/11248004.html

[https_blog.csdn.net_XX_123_1_RJ_article_details_81021815]: https://blog.csdn.net/XX_123_1_RJ/article/details/81021815
[in-place]: https://en.wikipedia.org/wiki/In-place_algorithm