LeetCode算法刷题计划（1）— 基础50题

转x33g5p2x  于2021-10-06 转载在 其他  
字(13.0k)|赞(0)|评价(0)|浏览(239)

LeetCode算法刷题计划（1）— 基础50题

自己近几天在LeetCode上面刷的50道基础算法题，下面按照算法类型进行分类

一、malloc

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        
        int n=nums.size();
        for(int i=0;i<n;i++){
            nums.push_back(nums[i]);
        }

        return nums;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {

        for(int i=0;i<2*n;i++){
            if(nums[i]>0){
                int j=i;
                while(nums[i]>0){
                    j=j<n?2*j:2*(j-n)+1;
                    swap(nums[i],nums[j]);
                    nums[j]=-nums[j];
                }
            }
        }

        for(auto &num:nums){
            num=-num;
        }

        return nums;
    }
};

//时间复杂度：O(10^n)
//空间复杂度：O(10^n)
class Solution {
public:
    vector<int> printNumbers(int n) {

        vector<int>ans;
        int side=0;

        while(n--){
            side=side*10+9;
        }

        for(int i=1;i<=side;i++){
            ans.push_back(i);
        }

        return ans;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {

        for(int i=1;i<nums.size();i++){
            nums[i]=nums[i]+nums[i-1];
        }

        return nums;
    }
};

//时间复杂度：O(n*logn)
//空间复杂度：O(n)
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {

        vector<pair<int,int>>pairs;

        for(int i=0;i<nums.size();i++){
            pairs.push_back(make_pair(nums[i],i));
        }
        sort(pairs.begin(),pairs.end());

        vector<int>ans(nums.size());
        int pre=-1;
        for(int i=0;i<pairs.size();i++){
            if(pre==-1||pairs[i].first!=pairs[i-1].first){
                pre=i;
            }
            ans[pairs[i].second]=pre;
        }

        return ans;
    }
};

二、位运算

//时间复杂度：O(2^n)
//空间复杂度：O(n)
class Solution {
public:

    int ans=0;

    void dfs(int val,int idx,vector<int>&nums){
        if(idx==nums.size()){
            ans+=val;
            return;
        }
        dfs(val^nums[idx],idx+1,nums);
        dfs(val,idx+1,nums);
    }

    int subsetXORSum(vector<int>& nums) {   
        dfs(0,0,nums);
        return ans;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {

        vector<int>ans(encoded.size()+1);

        ans[0]=first;
        for(int i=1;i<=encoded.size();i++){
            ans[i]=encoded[i-1]^ans[i-1];
        }

        return ans;
    }
};

//时间复杂度：O(1)
//空间复杂度：O(1)
class Solution {
public:
    vector<int> swapNumbers(vector<int>& numbers) {

        numbers[0]=numbers[0]^numbers[1];
        numbers[1]=numbers[0]^numbers[1];
        numbers[0]=numbers[0]^numbers[1];

        return numbers;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
     int hammingWeight(uint32_t n) {
        
        int count=0;

        while(n!=0){
            if((n&1)==1){
                count++;
            }
            n>>=1;
        }

        return count;
    }
};

//时间复杂度：O(logn)
//空间复杂度：O(1)
class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {

        int count=0;

        while(left<right){
            left>>=1;
            right>>=1;
            count++;
        }

        return left<<count;
    }
};

//时间复杂度：O(logn)
//空间复杂度：O(1)
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        
        uint32_t ans=0;

        for(int i=0;i<32&&n>0;i++){
            ans |= (n&1) << (31-i);
            n >>= 1; 
        }
        
        return ans;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    vector<int> countBits(int n) {

        vector<int>dp(n+1,0);

        for(int i=1;i<=n;i++){
            dp[i]=dp[i>>1]+(i&1);
        }

        return dp;
    }
};

三、计数

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        
        int ans=0;
        unordered_map<int,int>mp;
        mp[nums[0]]=1;

        for(int i=1;i<nums.size();i++){        
            ans+=mp[nums[i]];
            mp[nums[i]]++;     
        }

        return ans;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    bool checkIfPangram(string sentence) {

        int ans=0;

        for(auto c:sentence){
            ans|=1<<(c-'a');
            if((ans^0x3ffffff)==0){
                return true;
            }
        }

        return false;
    }
};

四、字符串

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    int finalValueAfterOperations(vector<string>& operations) {

        int x=0;

        for(auto str:operations){
            if(str=="++X"||str=="X++"){
                x++;
            }else{
                x--;
            }
        }

        return x;
    }
};

//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {
public:
    string defangIPaddr(string address) {

        for(int i=0;i<address.length();i++){
            if(address[i]=='.'){
                address.insert(i+1,"]");
                address.insert(i,"[");
                i++;
            }
        }

        return address;
    }
};

//时间复杂度：O(n^2)
//空间复杂度：O(n)
class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {

        int count=0;
        unordered_set<char>s;

        for(auto c:allowed){
            s.insert(c);
        }
        for(auto word:words){
            int flag=1;
            for(auto c:word){
                if(s.count(c)==0){
                    flag=0;
                    break;
                }
            }
            if(flag)
                count++;
        }

        return count;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i=0,j=s.size()-1;i<j;i++,j--){
            swap(s[i],s[j]);
        }
    }
};

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
    string reverseLeftWords(string s, int n) {

        string ans=s;

        for(int i=0;i<s.length();i++){
            ans[(i+s.length()-n)%s.length()]=s[i];
        }

        return ans;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {

        string s1="",s2="";

        for(auto word:word1){
            s1+=word;
        }
        for(auto word:word2){
            s2+=word;
        }

        return s1==s2;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    string complexNumberMultiply(string num1, string num2) {

        string s1_z="",s1_f="",s2_z="",s2_f="";
        int flag=1;
        for(int i=0;i<num1.length();i++){
            if(num1[i]!='+'&&flag){
                s1_z+=num1[i];
            }else{
                flag=0;
            }
            if(num1[i]=='+')
                continue;
            if(flag==0&&num1[i]!='i'){
                s1_f+=num1[i];
            }
        }
        flag=1;
        for(int i=0;i<num2.length();i++){
            if(num2[i]!='+'&&flag){
                s2_z+=num2[i];
            }else{
                flag=0;
            }
            if(num2[i]=='+')
                continue;
            if(flag==0&&num2[i]!='i'){
                s2_f+=num2[i];
            }
        }
        int n1_z=stoi(s1_z),n1_f=stoi(s1_f),n2_z=stoi(s2_z),n2_f=stoi(s2_f);

        string ans=to_string(n1_z*n2_z-n1_f*n2_f)+"+"+to_string(n1_f*n2_z+n1_z*n2_f)+"i";

        return ans;
    }
};

五、递归

//时间复杂度：O(n)
//空间复杂度：O(n)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:

    unordered_set<int>s;

    void search(TreeNode *root){
        if(root!=NULL){
            s.insert(root->val);
            search(root->left);
            search(root->right);
        }
    }

    int numColor(TreeNode* root) {
        search(root);
        return s.size();
    }
};

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
    int count=0;
    int numberOfSteps(int num) {
        if(num%2==0&&num!=0){
            count++;
            numberOfSteps(num/2);
        }
        if(num%2==1){
            count++;
            numberOfSteps(num-1);
        }

        return count;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(H)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
public:

    int maxdepth=-1,ans=0;

    void dfs(TreeNode *root,int depth){
        if(root==NULL){
            return;
        }
        if(depth>maxdepth){
            ans=root->val;
            maxdepth=depth;
        }else if(depth==maxdepth){
            ans+=root->val;
        }
        dfs(root->left,depth+1);
        dfs(root->right,depth+1);
    }

    int deepestLeavesSum(TreeNode* root) {
        dfs(root,1);
        return ans;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(H)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        int left_dep=maxDepth(root->left);
        int right_dep=maxDepth(root->right);
        return max(left_dep,right_dep)+1;
    }
};

六、公式

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
    int sum=0;
    int sumNums(int n) {
        n>0&&(sum=n+sumNums(n-1));
        return sum;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
    int multiply(int A, int B) {
        if(B==1){
            return A;
        }
        return A+multiply(A,B-1);
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:

    int fib(int n) {
        if(n<2){
            return n;
        }
        int p=0,q=1,ans;
        for(int i=2;i<=n;i++){
            ans=p+q;
            p=q;
            q=ans;
        }
        return ans;
    }
};

//时间复杂度：O(sqrt(n))
//空间复杂度：O(1)
class Solution {
public:
    int kthFactor(int n, int k) {

        int ans;

        for(ans=1;ans<=sqrt(n);ans++){
            if(n%ans==0){
                k--;
                if(k==0){
                    return ans;
                }
            }
        }
        ans--;
        if(ans*ans==n){
            ans--;
        }
        for(;ans>0;ans--){
            if(n%ans==0){
                k--;
                if(k==0){
                    return n/ans;
                }
            }
        }

        return -1;
    }
};

//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {
public:
    int countTriples(int n) {

        int count=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int c=sqrt(i*i+j*j);
                if(c<=n&&c*c==i*i+j*j){
                    count++;
                }
            }
        }
        return count;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:

    int gcd(int a,int b){
        int t;
        while(t!=0){
            t=a%b;
            a=b;
            b=t;
        }
        return a;
    }

    int findGCD(vector<int>& nums) {
        int maxn=-1,minn=5555;
        for(int i=0;i<nums.size();i++){
            maxn=max(maxn,nums[i]);
            minn=min(minn,nums[i]);
        }
        return gcd(maxn,minn);
    }
};

//时间复杂度：O(n^3)
//空间复杂度：O(1)
class Solution {
public:

    double area(vector<int>a,vector<int>b,vector<int>c){
        return 0.5*abs(a[0]*b[1]+b[0]*c[1]+c[0]*a[1]-a[1]*b[0]-b[1]*c[0]-c[1]*a[0]);
    }

    double largestTriangleArea(vector<vector<int>>& points) {

        double maxarea=0;
        int n=points.size();

        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                for(int k=j+1;k<n;k++)
                    maxarea=max(maxarea,area(points[i],points[j],points[k]));

        return maxarea;
    }
};

七、枚举

//时间复杂度：O(n)。这里用一重循环对n个数字进行异或。
//空间复杂度：O(1)。这里只是用了常量级别的辅助空间。
class Solution {
public:
    int xorOperation(int n, int start) {

        int ans=0;

        for(int i=0;i<n;i++){
            ans=ans^(start+2*i);
        }

        return ans;
    }
};

//时间复杂度：O(logn)
//空间复杂度：O(1)
class Solution {
public:
    int subtractProductAndSum(int n) {

        int sum=0,mut=1;

        while(n!=0){
            sum+=(n%10);
            mut*=(n%10);
            n/=10;
        }

        return mut-sum;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    int findNumbers(vector<int>& nums) {

        int count=0;
        for(auto num:nums){
            if((int)(log10(num)+1)%2==0){
                count++;
            }
        }

        return count;
    }
};

//时间复杂度：O(logn)
//空间复杂度：O(1)
class Solution {
public:
    int search(vector<int>& nums, int target) {

        int n=nums.size();
        int left=0,right=n-1;

        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[0]<=nums[mid]){
                if(target>=nums[0]&&target<=nums[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else{
                if(target>=nums[mid]&&target<=nums[n-1]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
        }

        return -1;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
    int countKDifference(vector<int>& nums, int k) {
    
        unordered_map<int,int>mp;
        int count=0;

        for(int i=0;i<nums.size();i++){
            int a=nums[i]+k,b=nums[i]-k;
            if(mp.find(a)!=mp.end()){
                count+=mp[a];
            }
            if(mp.find(b)!=mp.end()){
                count+=mp[b];
            }
            mp[nums[i]]++;
        }
        
        return count;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {

        unordered_set<char>s;
        int count=0;

        for(auto jewel:jewels){
            s.insert(jewel);
        }
        for(auto stone:stones){
            if(s.count(stone)){
                count++;
            }
        }

        return count;
    }
};

//时间复杂度：O(n^2)
//空间复杂度：O(n)
class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {

        int n=arr.size();
        int dp[n];
        int sum=arr[0];
        dp[0]=arr[0];

        for(int i=1;i<n;i++){
            sum+=arr[i];
            dp[i]=dp[i-1]+arr[i];
        }
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if((j-i+1)%2==1){
                    sum+=dp[j]-dp[i]+arr[i];                   
                }
            }
        }

        return sum;
    }
};

八、进制

//时间复杂度：O(n)
//空间复杂度：O(1)
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int ans=0;
        while(head!=NULL){
            ans|=head->val;
            ans<<=1;
            head=head->next;
        }
        ans>>=1;
        return ans;
    }
};

//时间复杂度：O(logn)
//空间复杂度：O(1)
class Solution {
public:
    int sumBase(int n, int k) {
        
        int sum=0;

        while(n!=0){
            sum+=(n%k);
            n/=k;
        }

        return sum;
    }
};

//时间复杂度：O(1)
//空间复杂度：O(1)
class Solution {
public:
    int addDigits(int num) {
        if(num>0&&num%9==0){
            return 9;
        }
        return num%9;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    string convertToBase7(int num) {

        string s="";
        int  flag=0;

        if(num<0){
            flag=1;
            num=-num;
        }
        if(num==0){
            return "0";
        }
        while(num!=0){
            s+=(num%7)+'0';
            num/=7;
        }
        reverse(s.begin(),s.end());
        if(flag){
            s.insert(0,"-");
        }

        return s;
    }
};

//时间复杂度：O(k) k为十六进制的位数
//空间复杂度：O(k)
class Solution {
public:
    string toHex(int num) {

        if(num==0){
            return "0";
        }

        string s="";
        for(int i=7;i>=0;i--){
            int tmp=(num>>(4*i))&15;
            if(tmp>0||s.length()>0){
                s+=tmp<10?(tmp+'0'):('a'+tmp-10);
            }
        }

        return s;
    }
};

九、排序

//时间复杂度：O(nlogn)
//空间复杂度：O(1)
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums;
    }
};

//时间复杂度：O(nlogn)
//空间复杂度：O(n)
class Solution {
public:

    static bool cmp(pair<char,int>a,pair<char,int>b){
        return a.second>b.second;
    }

    string frequencySort(string s) {

        unordered_map<char,int>mp;
        vector<pair<char,int>>pairs;
        string ans="";
        
        for(auto c:s){
            mp[c]++;
        }
        for(auto it:mp){
            pairs.push_back(it);
        }
        sort(pairs.begin(),pairs.end(),cmp);
        for(auto [ch,num]:pairs){
            for(int i=0;i<num;i++){
                ans+=ch;
            }
        }

        return ans;
    }   
};

//时间复杂度：O(nlogn)
//空间复杂度：O(1)
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {

        int cnt=1,idx=0;

        sort(nums.begin(),nums.end());

        while(idx<nums.size()&&nums[idx]<=0){
            idx++;
        }

        for(int i=idx;i<nums.size();i++){
            if(nums[i]!=cnt){
                return cnt;
            }
            if(i+1<nums.size()&&nums[i]!=nums[i+1]){
                cnt++;
            }else if(i+1==nums.size()){
                cnt++;
            }
                
        }

        return cnt;
    }
};

十、思维

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    int arraySign(vector<int>& nums) {
        
        int flag=1;
        
        for(auto num:nums){
            if(num==0){
                return 0;
            }
            if(num<0){
                flag=-flag;
            }
        }

        return flag;
    }
};

//时间复杂度：O(1)
//空间复杂度：O(1)
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val=node->next->val;
        node->next=node->next->next;
    }
};

//时间复杂度：O(n)
//空间复杂度：O(1)
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {

        ListNode *h=head;

        if(head->val==val){
            return head->next;
        }
        while(h!=NULL){
            if(h->next->val==val){
                h->next=h->next->next;
                return head;
            }
            h=h->next;
        }

        return head;
    }
};

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/weixin_47511190/article/details/120601406

内容来源于网络，如有侵权，请联系作者删除！

leetcode算法

相关文章

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com