头像

nihaotian




离线:1个月前


活动打卡代码 LeetCode 7. 整数反转

nihaotian
4个月前
class Solution {
public:
    int reverse(int x) {
        int r = 0;
        while(x)
        {
            if(x > 0 && r > (INT_MAX - x%10)/10) return 0;
            if(x < 0 && r < (INT_MIN - x%10)/10) return 0;
            r = r*10 + x%10;
            x /= 10;
        }
        return r;
    }
};



nihaotian
4个月前
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> hash;
        int res = 0;
        for(int i = 0,j = 0;i < s.size();i++)
        {
            hash[s[i]]++;
            while(hash[s[i]]>1) hash[s[j++]]--;
            res = max(res,i - j + 1);
        }
        return res;
    }
};


活动打卡代码 LeetCode 2. 两数相加

nihaotian
4个月前
/**
 * 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:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1),cur = dummy;
        int t = 0;
        while(l1 || l2 || t)
        {
            if(l1) t += l1->val,l1 = l1->next;
            if(l2) t += l2->val,l2 = l2->next;
            cur = cur->next = new ListNode(t%10);
            t /= 10;
        }
        return dummy->next;
    }
};


活动打卡代码 LeetCode 1. 两数之和

nihaotian
4个月前
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash;
        for(int i = 0; i < nums.size();i++)
        {
            if(hash.count(target - nums[i])) return {hash[target - nums[i]],i};
            hash[nums[i]] = i;
        }
        return {};
    }
};



nihaotian
11个月前
#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
11个月前
#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
11个月前
#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
11个月前
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
11个月前
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
11个月前
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();
    }
};