头像

nihaotian


访客:9432

离线:1个月前



nihaotian
2个月前
#include<iostream>

using namespace std;

const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    cin >> n >> m >> a+1 >> b+1;

    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
        {
            f[i][j] = max(f[i-1][j],f[i][j-1]);
            if(a[i] == b[j])
            {
                f[i][j] = max(f[i][j],f[i-1][j-1]+1);
            }
        }
    cout << f[n][m] << endl;
    return 0;
}


活动打卡代码 AcWing 3. 完全背包问题

nihaotian
2个月前
#include<iostream>

using namespace std;

const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];

    for(int i = 1;i <= n;i++)
        for(int j = v[i];j <= m;j++)
            f[j] = max(f[j],f[j-v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

nihaotian
2个月前
#include<iostream>

using namespace std;

const int N = 1010;

int n,m;
int f[N];
int v[N],w[N];

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];
    for(int i = 1;i <= n;i++)
        for(int j = m;j >= v[i];j--)
            f[j] = max(f[j],f[j-v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}



nihaotian
2个月前
class Solution{
public:
    unordered_map<char,int> count;
    queue<int> q;
    //Insert one char from stringstream
    void insert(char ch){
        if(++ count[ch] > 1) //当ch出现过时
        {
            while(q.size() && count[q.front()] > 1) q.pop(); //弹出队列中所有出现过不止一次的字母
        }
        else
        q.push(ch); //加入没有出现过的字母
    }
    //return the first appearence once char in current stringstream
    char firstAppearingOnce(){
        if(q.empty()) return '#';
        return q.front();
    }
};



nihaotian
2个月前
class Solution {
public:
    char firstNotRepeatingChar(string s) {
        unordered_map<char,int> m;
        for(auto c : s) m[c]++;
        for(auto c : s)
        if(m[c] == 1) return c;
        return '#';
    }
};


活动打卡代码 AcWing 62. 丑数

nihaotian
2个月前
class Solution {
public:
    int getUglyNumber(int n) {
        vector<int> q(1,1);
        int i = 0,j = 0,k = 0;
        while(--n)
        {
            int t = min(q[i] * 2,min(q[j] * 3,q[k] * 5));
            q.push_back(t);
            if(q[i] * 2 == t) i++;
            if(q[j] * 3 == t) j++;
            if(q[k] * 5 == t) k++;
        }
        return q.back();
    }
};



nihaotian
2个月前
class Solution {
public:
    int getTranslationCount(string s) {
        int n = s.size();
        vector<int> f(n+1);
        f[0] = 1;
        f[1] = 1;
        for(int i = 2;i <= n;i++)
        {
            int t = (s[i-2] - '0') * 10 + s[i-1] - '0';
            if(t >= 10 && t <= 25)
            f[i] = f[i-1] + f[i-2];
            else f[i] = f[i-1];
        }
        return f[n];
    }
};


活动打卡代码 AcWing 78. 左旋转字符串

nihaotian
2个月前
class Solution {
public:
    string leftRotateString(string str, int n) {
        reverse(str.begin(),str.end());
        reverse(str.begin(),str.end()-n);
        reverse(str.end()-n,str.end());
        return str;
    }
};


活动打卡代码 AcWing 77. 翻转单词顺序

nihaotian
2个月前
class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(),s.end()); //先翻转整个句子
        for(int i = 0;i < s.size();i++)
        {
            int j = i; //i指向单词开头,j指向单词末尾的空格
            while(j < s.size() && s[j] != ' ') j++; //指出每个单词的范围
            reverse(s.begin()+i,s.begin()+j); //翻转单词
            i = j;
        }
        return s;
    }
};



nihaotian
2个月前
class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int>> res;
        for(int i = 1,j = 1,s = 1;i < sum;i++) //双指针算法
        {
            while(s < sum) s += ++j; //先固定i,j往后移
            if(s == sum){ //直到s==sum
                vector<int> line;
                for(int k = i;k <= j ; k++) line.push_back(k); //保存结果
                res.push_back(line);
            }
            s-=i; //如果已经s超过sum,则把i往后移
        }
        return res;
    }
};