头像

摆烂哲学家




离线:3天前


最近来访(26)
用户头像
不高兴的兽奶
用户头像
ROKANARBITER
用户头像
松鼠会
用户头像
海粟
用户头像
锦素流年
用户头像
Fatin
用户头像
九月1368458
用户头像
hyy29
用户头像
潘潘_the_panda
用户头像
鸡蛋酱
用户头像
lzqlzq
用户头像
听凭风引_2
用户头像
v_viggins
用户头像
陌上花开Charlie
用户头像
songszh
用户头像
不拿周赛牌不改名
用户头像
Schafe
用户头像
你怎么睡得着的

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

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int v[N], w[N]; // 开两个分别表示物品体积的价值的两个数组
int f[N][N]; // 用来表示前i 个 物品在j 体积下的最优决策

int main()
{
    int n, m; // 物品数量和背包容积
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

    // 两个集合, 一个集合表示不选第i个物品, 在 j 体积下的 最有决策
    // 另一个集合表示选第i个物品(当 背包容积 大于 物品体积时成立), 在 j 体积下的最优决策
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;
    return 0;
}


活动打卡代码 AcWing 862. 三元组排序

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

struct Data
{
    int x;
    double y;
    string z;

    bool operator < (const Data &t) const
    {
        return x < t.x;
    }
}a[N];

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i ++) cin >> a[i].x >> a[i].y >> a[i].z;

    sort(a, a + n);

    for (int i = 0; i < n; i ++)
        printf("%d %.2lf %s\n", a[i].x, a[i].y, a[i].z.c_str());


    return 0;
}



class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        for (int i = 0; i < 32; i ++)
            if (n >> i &1)
                res ++;
        return res;
    }
};
class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;

        while (n) n -= n & -n, res ++ ;

        return res;
    }
};


活动打卡代码 AcWing 51. 数字排列

class Solution {
public:
    vector<vector<int>> permutation(vector<int>& nums) {
        sort(nums.begin(),nums.end());

        vector<vector<int>> res;
        do
        {
            res.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));

        return res;
    }
};



class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_set<int> S;
        for (auto x : nums)
        {
            if (S.count(target - x)) return {x, target - x};
            S.insert(x);
        }
    }
};


活动打卡代码 AcWing 53. 最小的k个数

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        sort(input.begin(), input.end());

        vector<int> res;
        for (int i = 0; i < k; i ++) res.push_back(input[i]);

        return res;
    }
};



class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> s1, s2;
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while (s1.size() > 1) s2.push(s1.top()), s1.pop();
        int t = s1.top();
        s1.pop();
        while (s2.size()) s1.push(s2.top()), s2.pop();
        return t;
    }

    /** Get the front element. */
    int peek() {
        while (s1.size() > 1 ) s2.push(s1.top()), s1.pop();
        int t = s1.top();
        while (s2.size()) s1.push(s2.top()), s2.pop();
        return t;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> res;
        for (auto p = head; p; p = p -> next) res.push_back(p -> val);
        reverse(res.begin(), res.end());
        return res;
    }
};



class Solution {
public:
    void reOrderArray(vector<int> &array) {
         int i = 0, j = array.size() - 1;
         while (i < j)
         {
             while (i < j && array[i] % 2 ) i ++;
             while (i < j && array[j] % 2 == 0) j --;
             if (i < j) swap(array[i],array[j]);
         }
    }
};



class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        unordered_set<int> S;
        for (int i = 0; i <= nums.size(); i ++) S.insert(i);

        for (auto x : nums ) S.erase(x);

        return *S.begin();
    }
};