Spring 2021 daily question [week3 not finished]

190. Invert binary bit

class Solution {
    
public:
    uint32_t reverseBits(uint32_t n) 
    {
    
        uint32_t sum=0;
        for(int i=0;i<=31;i++)
        {
    
            if(n>>i&1) sum=sum*2+1;
            else sum=sum*2;
        }
        return sum;
    }
};

77. Flip word order

class Solution {
    
public:
    string reverseWords(string s) 
    {
    
        reverse(s.begin(),s.end());
        stringstream l(s);
        string ans,a;
        while(l>>a) 
        {
    
            reverse(a.begin(),a.end());
            if(ans.size()) ans+=" ";
            ans+=a;
        }
        return ans;
    }
};

74. Search for a two-dimensional matrix

class Solution {
    
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target)
    {
    
        int x=0,y=0;
        int n=matrix.size();
        int m=matrix[0].size();
        for(int i=0;i<n;i++)
        {
    
            for(int j=0;j<m;j++) 
            if(matrix[i][j]==target) return true;
        }
        return false;
    }
};

15. Search in a two-dimensional array 【 thinking Double pointer 】

class Solution {
    
public:
    bool searchArray(vector<vector<int>> array, int target) {
    
        if(!array.size()) return false;
        int n=array.size(),m=array[0].size();
        int i=0,j=m-1;
        while(i<n&&j>=0)
        {
    
            if(array[i][j]==target) return true;
            else if(array[i][j]>target) j--;
            else i++;
        }
        return false;
    }
};

90. A subset of II【dfs】

class Solution {
    
public:
    set<vector<int>>st;
    vector<int>ve;
    int a[105]={
    0};
    void dfs(int index,vector<int> nums)
    {
    
        if(index==nums.size())
        {
    
            st.insert(ve);
            return;
        }
        ve.push_back(nums[index]);
        dfs(index+1,nums);
        ve.pop_back();
        dfs(index+1,nums);
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
    
        sort(nums.begin(),nums.end());
        dfs(0,nums);
        vector< vector<int> > ans;
        for(auto i=st.begin();i!=st.end();i++)
            ans.push_back(*i);
        return ans;
    }
};

93. Recursive implementation of combinatorial enumeration

#include<bits/stdc++.h>
using namespace std;
const int N=35;
int a[N],st[N],n,m;
void dfs(int s,int index)
{
    
    if(index==m)
    {
    
        for(int i=0;i<index;i++) cout<<a[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i=s;i<=n;i++)
    {
    
        if(!st[i])
        {
    
            st[i]=1;a[index]=i;
            dfs(i,index+1);
            st[i]=0;
        }
    }
}
int main(void)
{
    
    cin>>n>>m;
    dfs(1,0);
    return 0;
}

1006. Stupid factorials 【 Stack 】

class Solution {
    
public:
    int clumsy(int n) 
    {
    
        if(n==1) return 1;
        char s[10]="*/+-";
        int k=0;
        bool flag=true;
        stack<int>st1; st1.push(n);
        stack<int>st2;
        for(int i=n-1;i>=1;i--)
        {
    
            if(flag)
            {
    
                if(st2.size())
                {
    
                    int temp=st1.top()-st2.top();
                    st1.pop(),st2.pop();
                    st1.push(temp);
                }
                if(k==0) 
                {
    
                    int temp=st1.top()*i;
                    st1.pop(); st1.push(temp);
                    k++;
                }else if(k==1)
                {
    
                    int temp=st1.top()/i;
                    st1.pop(); st1.push(temp);
                    k++;
                }else if(k==2)
                {
    
                    int temp=st1.top()+i;
                    st1.pop(); st1.push(temp);
                    k++;
                 }
                 if(k==3) flag=!flag,k=0;
            }
            else
            {
    
                if(!st2.size()) 
                {
    
                    st2.push(i);
                    continue;
                }
                if(k==0) 
                {
    
                    int temp=st2.top()*i;
                    st2.pop(); st2.push(temp);
                    k++;
                }else if(k==1)
                {
    
                    int temp=st2.top()/i;
                    st2.pop(); st2.push(temp);
                    k++;
                }
                if(k==2) flag=!flag;
            }
        }
        int ans=st1.top();
        if(st2.size()) ans-=st2.top();
        return ans;
    }
};

1381. Factorial 【 thinking 】

#include<bits/stdc++.h>
using namespace std;
int main(void)
{
    
    int sum=1,cnt2=0,cnt5=0,n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    
        int x=i;
        while(x%2==0) cnt2++,x/=2;
        while(x%5==0) cnt5++,x/=5;
        sum=sum*x%10;
    }
    for(int i=1;i<=cnt2-cnt5;i++) sum=sum*2%10;
    cout<<sum;
    return 0;
}

Interview questions 17.21. The amount of water in the histogram 【 Hang in the air 】

592. rain 【 Hang in the air 】

1143. Longest common subsequence 【DP】

class Solution {
    
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
    
        int f[1010][1010]={
    0};
        int n=text1.size(),m=text2.size();
        text1="0"+text1,text2="0"+text2;
        for(int i=1;i<=n;i++)
        {
    
            for(int j=1;j<=m;j++)
            {
    
                f[i][j]=max({
    f[i-1][j-1],f[i-1][j],f[i][j-1]});
                if(text1[i]==text2[j]) 
                    f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            }
        }
        return f[n][m];
    }
};

1222. The password fell off 【 Hang in the air DP】

781. Rabbits in the forest 【 thinking 】

class Solution {
    
public:
    int numRabbits(vector<int>& answers) 
    {
    
        map<int,int>mp;
        int sum=0;
        for(int i=0;i<answers.size();i++) mp[answers[i]]++;
        for(auto i=mp.begin();i!=mp.end();i++)
        {
    
            int a=i->first;
            int b=i->second;
            int temp=(b+a)/(a+1)*(a+1);
            sum+=temp;
        }
        return sum;
    }
};

3192. The most frequent number of occurrences 【 Sign in 】

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,x,a[N];
int main(void)
{
    
    cin>>n;
    for(int i=0;i<n;i++) cin>>x,a[x]++;
    int ans=0,cnt=0;
    for(int i=0;i<N;i++)
        if(a[i]>cnt) cnt=a[i],ans=i;
    cout<<ans;
    return 0;
}