头像

隐姓埋名学算法




离线:1个月前


最近来访(31)
用户头像
jasonho
用户头像
回忆总是那么欣慰
用户头像
@_29
用户头像
故渊.
用户头像
阿伟的假期
用户头像
AK自动机
用户头像
acwing_gza
用户头像
不拿周赛牌不改名
用户头像
Serendipity_31
用户头像
U+9E4F
用户头像
玖月
用户头像
ljlhandsome
用户头像
鲜参
用户头像
章北海_z
用户头像
Self.
用户头像
DPH
用户头像
柒月栗子
用户头像
且听龙吟
用户头像
东玉家的熊猫
用户头像
huyuun


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if(!l1 && !l2) {
            return nullptr;
        }
        ListNode* head = new ListNode(-1);
        ListNode* dummy = head;
        while(l1 || l2){
            if(l1 && l2){
                if(l1->val > l2->val){
                    head->next = l2;
                    l2 = l2->next;
                }
                else {
                    head->next = l1;
                    l1 = l1->next;
                }
                head = head->next;
            }
            else if(l1){
                head->next = l1;
                l1 = l1->next;
                head = head->next;
            }
            else {
                head->next = l2;
                l2 = l2->next;
                head = head->next;
            }
        }
        return dummy->next;
    }
};



/**
 * 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* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        ListNode* dummy = new ListNode(0,head);
        ListNode* cur = dummy;
        while(cur->next && cur->next->next){
            if(cur->next->val == cur->next->next->val){
                int x = cur->next->val;
                while(cur->next && cur->next->val == x){
                    cur->next = cur->next->next;
                }
            }
            else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};



#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;

int n;
int h[N], l[N], r[N], q[N];

int main()
{
    while (scanf("%d", &n), n)
    {
        for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
        h[0] = h[n + 1] = -1;
        int tt = 0;
        q[0] = 0;
        for (int i = 1; i <= n; i ++ )
        {
            while (h[i] <= h[q[tt]]) tt -- ;
            l[i] = q[tt];
            q[ ++ tt] = i;
        }

        tt = 0;
        q[0] = n + 1;
        for (int i = n; i; i -- )
        {
            while (h[i] <= h[q[tt]]) tt -- ;
            r[i] = q[tt];
            q[ ++ tt] = i;
        }

        LL res = 0;
        for (int i = 1; i <= n; i ++ )
            res = max(res, (LL)h[i] * (r[i] - l[i] - 1));
        printf("%lld\n", res);
    }

    return 0;
}


活动打卡代码 LeetCode 456. 132模式

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) {
            return false;
        }

        // 左侧最小值
        int left_min = nums[0];
        // 右侧所有元素
        multiset<int> right_all;

        for (int k = 2; k < n; ++k) {
            right_all.insert(nums[k]);
        }

        for (int j = 1; j < n - 1; ++j) {
            if (left_min < nums[j]) {
                auto it = right_all.upper_bound(left_min);
                if (it != right_all.end() && *it < nums[j]) {
                    return true;
                }
            }
            left_min = min(left_min, nums[j]);
            right_all.erase(right_all.find(nums[j + 1]));
        }

        return false;
    }
};


活动打卡代码 AcWing 1497. 树的遍历

#include<iostream>
#include<queue>
#include<unordered_map>

using namespace std;

const int N = 35;

int n;
int posorder[N],inorder[N];
unordered_map<int,int> l,r,pos;

int build(int il, int ir, int pl, int pr){
    int root = posorder[pr];
    int k = pos[root];
    if(il < k) l[root] = build(il, k - 1, pl, pl + k - 1 - il);
    if(ir > k) r[root] = build(k + 1, ir, pl + k - il, pr - 1);
    return root;
}

void dfs(int root){
    queue<int> q;
    q.push(root);
    while(q.size()){
        int t = q.front();
        cout << t << ' ';
        if(l[t]){
            q.push(l[t]);
        }
        if(r[t]){
            q.push(r[t]);
        }
        q.pop();
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> posorder[i];
    for(int i = 1; i <= n; i++){
        cin >> inorder[i];
        pos[inorder[i]] = i;
    }
    int root = build(1, n, 1, n);
    dfs(root);
    return 0;
}



/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */

class NestedIterator {
    vector<int> num;
    vector<int>::iterator cur;

    void dfs(vector<NestedInteger> &nestedList){
        for(auto &nest : nestedList){
            if(nest.isInteger()){
                num.push_back(nest.getInteger());
            }
            else {
                dfs(nest.getList());
            }
        }
    }
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        dfs(nestedList);
        cur = num.begin();
    }

    int next() {
        return *cur++;
    }

    bool hasNext() {
        return cur != num.end();
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */


活动打卡代码 AcWing 1470. 水桶传递队列

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int main()
{
    int rx,ry,lx,ly,bx,by;
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            char t;
            cin >> t;
            if(t == 'R') rx = i,ry = j;
            if(t == 'B') bx = i,by = j;
            if(t == 'L') lx = i,ly = j;
        }
    }
    int ans = abs(bx-lx)+abs(by-ly)-1;
    if((bx == lx && rx == lx && ry > min(ly,by) && ry < max(ly,by)) || (by == ly && ry == ly && rx > min(lx,bx) && rx < max(lx,bx))){
        ans += 2;
    }
    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 1683. 困牛放牧

#include<iostream>
#include<algorithm>

using namespace std;

int g[5];

int main()
{
    for(int i = 0; i < 3; i++){
        cin >> g[i];
    }
    sort(g,g+3);
    if(g[0] == g[1]-1 && g[2] == g[1]+1){
        cout << 0 << endl;
    }
    else if(g[2] == g[1]+2 || g[0] == g[1]-2){
        cout << 1 << endl;
    }
    else {
        cout << 2 << endl;
    }

    if(g[1]-g[0] > g[2]-g[1]){
        cout << g[1]-g[0]-1 << endl;
    }
    else {
        cout << g[2]-g[1]-1 << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1695. 果壳游戏

#include<iostream>

using namespace std;

const int N = 110;

int n,ans;
int a[N],b[N],g[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i] >> g[i];
    }

    for(int j = 1; j <= 3; j++){
        int t = j;
        int anst = 0;
        for(int i = 0; i < n; i++){
            if(a[i] == t){
                t = b[i];
            }
            else if(b[i] == t){
                t = a[i];
            }
            if(g[i] == t) anst ++;
        }
        ans = max(ans,anst);
    }
    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 1714. 混合牛奶

#include<iostream>
#include<algorithm>

using namespace std;

int c[5],m[5];

int main()
{
    for(int i = 0; i < 3; i++){
        cin >> c[i] >> m[i];
    }
    int k = 0;
    for(int i = 0; i < 100; i++){
        int j = (k+1)%3;
        int t = min(m[k],c[j]-m[j]);
        m[k] -= t;
        m[j] += t;
        k = j;
    }
    for(int i = 0; i < 3; i++){
        cout << m[i] << endl;
    }

    return 0;
}