leetcode刷题系列/2

#include <iostream>
#include <unordered_map>
#include <string>
#include <memory>
using namespace std;

// int main()
// {
//     string input="XII";
//     unordered_map<char,int> optional = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
//     int sum = 0;
//     for(int i=0; i<input.size();++i)
//     {
//         optional[input[i]] < optional[input[i+1]] ? sum-=optional[input[i]]:sum+=optional[input[i]];
//     }
//     cout<<sum<<endl;
// }

int main()
{
     string input="XII";
     int op[90]={};
     op['I']=1;
     op['V']=5;
     op['X']=10;
     op['L']=50;
     op['C']=100;
     op['D']=500;
     op['M']=1000;

      int sum = 0;
    for(int i=0; i<input.size();++i)
    {
        op[input[i]] < op[input[i+1]] ? sum-=op[input[i]]:sum+=op[input[i]];
    }
    cout<<sum<<endl;
}

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//最长公共子串

// int main()
// {
//     vector<string> strs={{"adfgh"},{"adfvbg"},{"adcv"}};

//     if(strs.empty())
//         return 0;
//     const auto p=minmax_element(strs.begin(),strs.end());
//     for(int i=0;i<p.first->size();++i)
//     {
//         if(p.first->at(i) != p.second->at(i))
//             cout<< p.first->substr(0,i)<<endl;
   
//     }
//     //cout<< *p.first<<endl;
// }


int main()
{
    vector<string> strs={{"adfgh"},{"adfvbg"},{"adcv"}};

    string res = strs.empty()? 0 : strs[0];
    for(string s: strs)
    {
        while(s.find(res) !=0)
            res=res.substr(0,res.length()-1);
    }
    cout<<res<<endl;
}

#include <iostream>
using namespace std;
#include <fstream>

//合并两个有序链表

//链表创建及初始化
struct List{
    double value;
    List *next;
    List(double _value,List *_next=NULL){
        value = _value;
        next = _next;
    }
};

//合并
List* merge(List *nl1,List *nl2)
{
    if(!nl1) return nl2;
    if(!nl2) return nl1;
    List* merger=nullptr;
    if(nl1->value < nl2->value )
    {   
        merger=nl1;
        merger->next= merge(nl1->next,nl2);
    }
    else
    {   
        merger=nl2;
        merger->next= merge(nl1,nl2->next);
    }
    return merger;
}


int main()
{
    double n1,n2;
    List *nl1 =NULL,*nl2=NULL;
    ifstream nf1("nf1.txt");
    ifstream nf2("nf2.txt");
    if(!nf1 || !nf2)
    {
        return 0;
    }

    while(nf1>>n1)//????
    {
        cout<<n1<<" ";
        nl1= new List(n1,nl1);
    }
    cout<<endl;
    //   while (nl1 !=NULL)
    // {
    //     cout<< nl1->value<<" ";
    //     nl1=nl1->next;
    // }
    // cout<<endl;

    while(nf2>>n2)
    {
        cout<<n2<<" ";
        nl2= new List(n2,nl2);
    }
    cout<<endl;
    //   while (nl2 !=NULL)
    // {
    //     cout<< nl2->value<<" ";
    //     nl2=nl2->next;
    // }
    //  cout<<endl;

    List* re = merge(nl1,nl2);//???????
    if(re == NULL)
        cout<<"000"<<endl;
    while (re !=NULL)
    {
        cout<< re->value<<" ";
        re=re->next;
    }
    
}

//删除数据中重复数字
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
// int main()
// {
//     vector<int> nums{0,0,1,2,3,3,4,5,5,6};
//     int size=nums.size();
//     int cnt=0;
//     //统计当前元素需要前移的位置 不需要移动整个数组
//     for(int i=1;i<size;++i){
//        if(nums[i] == nums[i-1])
//             cnt++;
//         nums[i-cnt] = nums[i];//向前移动cnt个位置
//     }
//     for(auto num:nums)
//         cout<<num<<" ";
//     cout<<endl;
//      for(int num=0; num<size-cnt; num++)
//         cout<<nums[num]<<" ";
//  }

 int main()
{
    vector<int> nums{0,0,1,7,3,3,4,5,5,6};
    //unique之前先排序
    sort(nums.begin(),nums.end());
    //返回一个迭代器，指向去重后容器中不重复序列的最后一个元素的下一个元素
    //并不是真的删除，重复元素的位置被不重复的占领了
    auto end_unique = unique(nums.begin(),nums.end());//nums={0,1,2,3,4,5,6,5,5,6}
    nums.erase(end_unique,nums.end());

    for(auto num:nums)
        cout<<num<<" ";
 }

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <iterator>//distance
#include <functional>
#include <bits/stdc++.h>


//移出重复元素，并返回长度
//  int main()
//  {
//      vector<int> nums{0,0,1,2,3,3,4,5,5,7};
//      int val=5;
//      for(int i=nums.size()-1; i >= 0; i--)
//      {
//          if(nums[i] == val)
//          {
//              for(int j=i; j<nums.size();j++)
//              {
//                  nums[j] = nums[j+1];
//              }
//              nums.pop_back();
//          }
//      }
//      for(auto num:nums)
//              cout<<num<<" ";
//      cout<<nums.size()<<endl;
//  }


//   int main()
//  {
//      vector<int> nums{0,0,1,2,3,3,4,5,5,7};
//      int val=5;
//      for(auto it=nums.begin();it!=nums.end();it++)
//      {
//          if(*it ==val)
//             nums.erase(it--);//it指向删除后的元素 但循环还会指针+1 要自减防止跳数
//      }

//    for(auto num:nums)
//             cout<<num<<" ";
//      cout<<nums.size()<<endl;

 //}


   int main()
{
     vector<int> nums={0,0,1,2,3,3,4,5,5,7};
     int val=5;
     
     //它接受一个谓词，对容器进行划分，使得谓词为true的值会排在容器的前半部分，而谓词为false的值会排在后半部分。
     //算法返回一个迭代器，指向最后一个使谓词为true的元素之后的位置
     cout<< distance(nums.begin(),partition(nums.begin(),nums.end(), [=](const int&a ){
         return a!=val;
     }));//????

 }

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <climits>

//最大子序列和

//暴力
int maxSum1(vector<int> &nums)
{
    int max=INT_MIN;
    int numsize = int(nums.size());
    for(int i=0; i<numsize;i++)
    {
        int sum=0;
        for(int j=i; j<numsize;j++)
        {
            sum+=nums[j];
            if(sum > max)
            {
                max =sum;
            }
        }
    }

    return max;
}

//动态规划
int maxSum2(vector<int> &nums)
{
    int result=INT_MIN;
    int numsize = int(nums.size());
    //dp[i]表示nums中以nums[i]结尾的最大子序号
    vector<int> dp(numsize);
    dp[0] =nums[0];
    result =dp[0];
    for(int i=1; i<numsize;i++)
    {
        dp[i]=max(dp[i-1]+nums[i],nums[i]);
        result=max(result,dp[i]);
    }
    return result;
}


int main()
{
    vector<int> nums={-1,2,3,4,5,6,7};
    int res1=maxSum1(nums);
    cout<<res1<<endl;

    int res2=maxSum2(nums);
    cout<<res2<<endl;
}