头像

不是很皮

Harbin Institute of Technology: Shenzhen Graduate School




离线:9小时前


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

//这里填你的代码^^
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef pair<int, pair<double, string>> PII;


int main()
{
    int n, a;
    double d;
    string t;
    vector<PII> res;
    cin >> n;
    while(n--){
        cin >> a >> d >> t;
        res.push_back({a,{d,t}});
    }
    sort(res.begin(), res.end());

    for(auto i: res){
        printf("%d %.2lf %s\n", i.first, i.second.first, i.second.second.c_str());
    }

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
class Solution {
public:
    int NumberOf1(int n) {
        int res=0;
        unsigned int un = n;  //负数右移首位补1
        while(un)
        {
            if(un & 1)
                res++;
            un = un>>1;
        }
        return res;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

//这里填你的代码^^

class Solution {
public:
    vector<vector<int>> res;
    vector<bool> st;
    vector<int> path;
    vector<vector<int>> permutation(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        st = vector<bool>(nums.size(), false);
        path = vector<int>(nums.size());
        dfs(0, 0, nums);
        return res;
    }
    // 这里的思路是,把nums的值按顺序一个个取出来,按照st中剩下的空位进行插空。
    // 因为,nums已经是有序的。所以我每次按顺序从nums中把值挑出来,有两种情况:
    // 1.如果当前值和后一个待取值是非重复的,则可从头到尾找到空位进行插空;
    // 2.如果当前值和后一个值相同,为了避免重复,需要保持相同值的相对位置不变,因此,后一个插空的值需要在当前值插空的位置后面的位置进行插入
    // cur代表当前取到nums的第cur个值,start表示cur可以进行插入的位置的起始位置,nums就是nums
    void dfs(int cur, int start, vector<int> &nums){
        if(cur == nums.size()){
            res.push_back(path);
            return ;
        }
        for(int i=start; i<nums.size(); i++){
            if(!st[i])
            {
                st[i] = true;
                path[i] = nums[cur]; //这里不能用push_back哦,因为这里是按位置i插入的,如果push只能插最后了
                if(cur+1<nums.size() && nums[cur]==nums[cur+1]) //如果我要从nums的cur个位置挑出来的值和下一个值相同,那我就只能在我当前插入位置i之后插入了
                    dfs(cur+1, i+1, nums);
                else
                    dfs(cur+1, 0, nums);
                st[i] = false;
            }
        }
    }
};

//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
排序
class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int l=0, r=nums.size()-1;
        vector<int> res;
        while(l<r)
        {
            if(nums[l]+nums[r]==target) break;
            else if(nums[l]+nums[r]<target) l++;
            else
                r--;
        }
        res.push_back(nums[l]);
        res.push_back(nums[r]);

        return res;
    }
};

单边扫描
class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_set<int> s;
        vector<int> res;
        for(auto x: nums)
        {
            if(s.empty()) s.insert(x);
            else
            {
                if(s.count(target - x)){
                    res.push_back(x);
                    res.push_back(target-x);
                }
                else
                    s.insert(x);
            }
        }
        return res;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

//这里填你的代码^^
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        priority_queue <int, vector<int>, less<int> > q;
        for(auto x: input)
        {
            if(k){
                q.push(x);
                k--;
            }
            else
                if(q.top() > x)
                {
                    int temp = q.top();
                    q.pop();
                    q.push(x);
                }
        }
        while(!q.empty())
        {
            res.push_back(q.top());
            q.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> stk, cache;

    MyQueue() {

    }

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

    void copy(){
        while(!stk.empty())
        {
            auto x = stk.top();
            cache.push(x);
            stk.pop();
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(cache.empty()) copy();
        int res = cache.top();
        cache.pop();
        return res;
    }

    /** Get the front element. */
    int peek() {
        if(cache.empty()) copy();
        return cache.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return stk.empty() && cache.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();
 */
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> res;
        while(head)
        {
            res.push_back(head->val);
            head = head->next;
        }
        reverse(res.begin(), res.end());

        return res;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
class Solution {
public:
    void reOrderArray(vector<int> &array) {
         vector<int> odd, even;
         for(auto x: array)
         {
             if(x%2==0) even.push_back(x);
             else odd.push_back(x);
         }
         int i=0;
         for(auto x: odd)
            array[i++] = x;
        for(auto x: even)
            array[i++] = x;

    }
};

双指针(快排)
class Solution {
public:
    void reOrderArray(vector<int> &array) {
         int l=0, r=array.size()-1;
         while(l<r)
         {
             while(l<r && array[l]%2==1) l++;
             while(l<r && array[r]%2==0) r--;
             if(l<r) swap(array[l], array[r]);
         }
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        int l=0, r=nums.size();
        while(l<r)
        {
            int mid = (l + r) >> 1;
            if(nums[mid] == mid) l = l+1;
            else
                r = mid;
        }
        return l;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int sum;
        for(auto n: nums){
            if(n==k)
                sum++;
        }
        return sum;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~