LeetCode

1470. 重新排列数组

时间O(N) 空间O(N)

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> res;
        int i=0;
        int j=n;
        for(i=0;i<n;++i)
        {
            res.push_back(nums[i]);
            res.push_back(nums[j]);
            ++j;
        }
        return res;
    }
};

1471. 数组中的 k 个最强值

善于把问题复杂化...

class Solution {
public:
    struct number{
        int val;
        int distance;
    };
    bool static cmp(number a,number b)
    {
        if(a.distance==b.distance)
            return a.val>b.val;
        else
            return a.distance>b.distance;
    }
    vector<int> getStrongest(vector<int>& arr, int k) {
        sort(arr.begin(),arr.end());
        int N=arr.size();
        int m=arr[(N-1)/2];
        vector<number> vec;
        for(int i=0;i<N;++i)
        {
            number num;
            num.val=arr[i];
            num.distance=abs(arr[i]-m);
            vec.push_back(num);
        }
        sort(vec.begin(),vec.end(),cmp);
        vector<int> res(arr.begin(), arr.begin() + k);
        return res;
    }
};

Lambda

class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        sort(arr.begin(),arr.end());
        int N=arr.size();
        int m=arr[(N-1)/2];
        sort(arr.begin(), arr.end(), [&](int a, int b) {
            return abs(a-m)>abs(b-m)||abs(a-m)==abs(b-m)&&a>b;
            });
        vector<int> ans(arr.begin(), arr.begin() + k);
        return ans;
    }
};

双指针

class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        sort(arr.begin(),arr.end());
        int N=arr.size();
        int m=arr[(N-1)/2];
        int left=0;
        int right=N-1;
        vector<int> ans;
        for(int i = 0;  i < k; i ++)
        {
            if(m-arr[left]>arr[right]-m)
            {
                ans.push_back(arr[left]);
                ++left;
            }
            else if(m-arr[left]<arr[right]-m)
            {
                ans.push_back(arr[right]);
                --right;
            }
            else
            {
                ans.push_back(arr[right]);
                --right;
            }
        }
        return ans;
    }
};

1472. 设计浏览器历史记录

很有意思的模拟，双向链表

看似medium，实为easy

struct node{
    string url;
    node* pre;
    node* next;
};

class BrowserHistory {
public:
    node* head=new node();
    node* cur=new node();
    BrowserHistory(string homepage) {
        head->url=homepage;
        head->pre=NULL;
        head->next=NULL;
        cur=head;
    }
    
    void visit(string url) {
        node* temp=new node();
        temp->url=url;
        temp->pre=cur;
        temp->pre->next=temp;
        temp->next=NULL;
        cur=temp;
    }
    
    string back(int steps) {
        if(!cur->pre)
            return cur->url;
        node* p=cur;
        for(int i=0;i<steps;++i)
        {
            p=p->pre;
            if(!p->pre)
                break;
        }
        cur=p;
        return p->url;
    }
    
    string forward(int steps) {
        if(!cur->next)
            return cur->url;
        node* p=cur;
        for(int i=0;i<steps;++i)
        {
            if(!p->next)
                break;
            p=p->next;
        }
        cur=p;
        return p->url;
    }
};