头像

Spare

QZTC




离线:9小时前


最近来访(32)
用户头像
潇潇暮雨
用户头像
重生之幻影
用户头像
标致
用户头像
LonelyLove
用户头像
acwing_74240
用户头像
窗外的麻雀
用户头像
西瓜干
用户头像
cxposition
用户头像
光无影
用户头像
凤凰院酸菜
用户头像
Finn2009
用户头像
RealDish
用户头像
做题必ac
用户头像
本人和硕
用户头像
富贵
用户头像
太雪菜
用户头像
Fatin
用户头像
人生如戏ba
用户头像
su尔
用户头像
yxc


Spare
11小时前

题意:

给一个长度为n+1的空数组和一个初始为1的ptr,每次调用insert函数时,将value添加到下标为idKey的位置,如果ptr指向的位置非空,则返回从ptr开始的最长的非空序列,并将ptr置于之后的的第一个空位

C++代码

class OrderedStream {
protected:
    vector<string> arr;
    int ptr;
public:
    OrderedStream(int n) : ptr(1) {
        arr.resize(n + 1);
    }

    vector<string> insert(int idKey, string value) {
        arr[idKey] = value;
        vector<string> res;
        while (ptr < arr.size() && !arr[ptr].empty()) {
            res.emplace_back(arr[ptr ++]);
        }
        return res;
    }
};

Java代码

class OrderedStream {
    private int ptr = 1;
    private String[] arr;
    public OrderedStream(int n) {
        arr = new String[n + 1];
    }

    public List<String> insert(int idKey, String value) {
        List<String> res = new ArrayList<String>();
        arr[idKey] = value;
        while (ptr < arr.length && arr[ptr] != null) 
        {
            res.add(arr[ptr++]);
        }
        return res;
    }
}
/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream obj = new OrderedStream(n);
 * List<String> param_1 = obj.insert(idKey,value);
 */


活动打卡代码 LeetCode 1656. 设计有序流

Spare
11小时前
const int N = 1e3 + 7;

class OrderedStream {
protected:
    string arr[N];
    int ptr;
    int size;
public:
    OrderedStream(int n) : ptr(1), size(n) {}

    vector<string> insert(int idKey, string value) {
        arr[idKey] = value;
        vector<string> res;
        while (ptr <= size && !arr[ptr].empty()) {
            res.emplace_back(arr[ptr ++]);
        }
        return res;
    }
};



Spare
1天前

算法1 数组模拟

时空复杂度分析 :

  • 时间复杂度:初始化和每项操作的时间复杂度均为 $O(1)$。

  • 空间复杂度:$O(k)$,其中 k 为给定的队列元素数目。

class MyCircularDeque {
    int *arr;  //数组模拟
    int front; //队头指针
    int rear;  //队尾指针
    int size;  //容量
public:
    MyCircularDeque(int k) {
        size = k + 1;
        arr = new int[size];
        front = rear = 0;
    }

    bool insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + size) % size;
        arr[front] = value;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        arr[rear] = value;
        rear = (rear + 1) % size;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        //front被设计在数组开头 所以+1
        front = (front + 1) % size; //防止溢出
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        //rear被设计在数组末尾 所以-1
        rear = (rear - 1 + size) % size;
        return true;
    }

    int getFront() {
        if (isEmpty()) return -1; //注意判空
        return arr[front];
    }

    int getRear() {
        if (isEmpty()) return -1; //注意判空
        int index = (rear - 1 + size) % size; //rear为0时候防止越界
        return arr[index];
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return (rear + 1) % size == front;
    }
};

算法2 $deque / vector$

$deque实现$

注意点:

  • emplace_back() 插入队列尾部一个元素
  • emplace_front()插入队列头部一个元素
  • pop_back() 删除队尾元素
  • pop_front() 删除队头元素
  • back() 获得队尾元素
  • front() 获得队头元素
class MyCircularDeque {
    deque<int> Q;
    int capacity;
public:
    MyCircularDeque(int k) {
        this->capacity = k;
    }

    bool insertFront(int value) {
        if (Q.size() == capacity) return false;
        Q.emplace_front(value);
        return true;
    }

    bool insertLast(int value) {
        if (Q.size() == capacity) return false;
        Q.emplace_back(value);
        return true;
    }

    bool deleteFront() {
        if(Q.empty()) return false;
        Q.pop_front();
        return true;
    }

    bool deleteLast() {
        if(Q.empty()) return false;
        Q.pop_back();
        return true;
    }

    int getFront() {
        if (Q.empty()) return -1; //注意判空
        return Q.front();
    }

    int getRear() {
        if (Q.empty()) return -1; //注意判空
        return Q.back();
    }

    bool isEmpty() {
        return Q.empty();
    }

    bool isFull() {
        return Q.size() == this->capacity;
    }
};

$vector$

注意点:

  • insert() 插入队列头部一个元素
  • erase() 删除队列头部的元素
class MyCircularDeque {
    vector<int> Q;
    int capacity;
public:
    MyCircularDeque(int k) {
        this->capacity = k;
    }

    bool insertFront(int value) {
        if (Q.size() == capacity) return false;
        Q.insert(Q.begin(), value);
        return true;
    }

    bool insertLast(int value) {
        if (Q.size() == capacity) return false;
        Q.emplace_back(value);
        return true;
    }

    bool deleteFront() {
        if(Q.empty()) return false;
        Q.erase(Q.begin());
        return true;
    }

    bool deleteLast() {
        if(Q.empty()) return false;
        Q.pop_back();
        return true;
    }

    int getFront() {
        if (Q.empty()) return -1; //注意判空
        return Q.front();
    }

    int getRear() {
        if (Q.empty()) return -1; //注意判空
        return Q.back();
    }

    bool isEmpty() {
        return Q.empty();
    }

    bool isFull() {
        return Q.size() == this->capacity;
    }
};



Spare
1天前
class MyCircularDeque {
    int *arr;  //数组模拟
    int front; //队头指针
    int rear;  //队尾指针
    int size;  //容量
public:
    MyCircularDeque(int k) {
        size = k + 1;
        arr = new int[size];
        front = rear = 0;
    }

    bool insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + size) % size;
        arr[front] = value;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        arr[rear] = value;
        rear = (rear + 1) % size;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        //front被设计在数组开头 所以+1
        front = (front + 1) % size; //防止溢出
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        //rear被设计在数组末尾 所以-1
        rear = (rear - 1 + size) % size;
        return true;
    }

    int getFront() {
        if (isEmpty()) return -1; //注意判空
        return arr[front];
    }

    int getRear() {
        if (isEmpty()) return -1; //注意判空
        int index = (rear - 1 + size) % size; //rear为0时候防止越界
        return arr[index];
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return (rear + 1) % size == front;
    }
};



Spare
1天前
再回顾一下
BFS写法
#include <iostream>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 1e3 + 7;
int n, m, res;
char g[N][N];
bool st[N][N];
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0}; //八方向偏移量
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

void bfs(int x, int y) {
    queue<PII> q;
    q.emplace(x, y);
    st[x][y] = true;

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 8; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue; //越界
            if(st[a][b]) continue;  //已经标记过
            if(g[a][b] == '.') continue;    //注意不含雨水则跳过

            st[a][b] = true;
            q.emplace(a, b);
        }
    }
}

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(!st[i][j] && g[i][j] == 'W') //找到未被标记过且是积水 进行FLOOD FILL
            {
                res ++;
                bfs(i, j);
            }
        }
    }

    cout << res << endl;

    return 0;
}
DFS写法
#include <iostream>

using namespace std;

const int N = 1e3 + 7;
int n, m, res;
char g[N][N];
bool st[N][N];
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

void dfs(int x, int y) {
    st[x][y] = true;

    for (int i = 0; i < 8; i++) {
        int a = x + dx[i], b = y +dy[i];
        if(a < 0 || a >= n || b < 0 || b >= m) continue;
        if(st[a][b]) continue;
        if(g[a][b] == '.') continue;
        g[a][b] == 'W';
        dfs(a, b);
    }
}

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(!st[i][j] && g[i][j] == 'W') 
            {
                dfs(i, j);
                res ++;
            }
        }
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 4582. Yih的线段树

Spare
1天前
/*
* @Author: Spare Lin
* @Project: AcWing2022
* @Date: 2022/8/14 15:51
* @Description: AcWing 4582. Yih的线段树
* @URL:https://www.acwing.com/problem/content/4585/
*/

//二进制的最后一位一定是个1
//11111000....000
#pragma GCC optimize(2)
#include <iostream>

using namespace std;

bool check(int x) {
    if (x % 2 == 0) return false;
    x--;
    //判断时候二进制数 是不是两段由111111 00000组成的
    bool meet_one = false;
    while (x) {
        if (x & 1) meet_one = true;
        else if (meet_one) return false;
        x >>= 1;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        cout << (check(x) ? "Y\n" : "N\n");
    }
    return 0;
}


活动打卡代码 AcWing 1027. 方格取数

Spare
2天前
/*
* @Author: Spare Lin
* @Project: AcWing2022
* @Date: 2022/8/13 23:52
* @Description:AcWing 1027. 方格取数
* @URL: https://www.acwing.com/problem/content/1029/
*/

/*
如何处理同一个格子不能被重复选择
只有在i1 + j1 = i2 + j2 时候两条路径的格子才可能重合
由摘花生的问题可以推出三维状态转移方程 :
    f[i1, k-i1, i2, k -i2] - > f[k, i1, i2]
f[k, i, j] 表示所有从(1,1)分别走到(i1, k - i1), (i2, k - i2)的路径的最大值
k表示两条路线当前走到的格子的横纵坐标之和  (k = i1 + j1 = i2 + j2)

难点:格子仅能取一次. 两个小朋友在同一个格子必有i1==i2,j1==j2,
    而后边状态限制同时走,所以当i1==i2时便走到同一格.
    判断(i1,j1),(i2,j2)是否是同一个格子,若是则仅需要加上一个权重,反之两个都需要
*/

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

const int N = 15;
int n;
int g[N][N];
int f[2 * N][N][N];

signed main() {
    cin >> n;
    int a, b, w;
    while (cin >> a >> b >> w, a || b || w) g[a][b] = w;

    for (int k = 2; k <= n + n; k++) {
        for (int i1 = 1; i1 <= n; i1++) {
            for (int i2 = 1; i2 <= n; i2++) {
                int j1 = k - i1, j2 = k - i2;
                if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) { //防止越界
                    int t = g[i1][j1];
                    if (i1 != i2) t += g[i2][j2]; //不重合则两条路径都需要加权重
                    int &x = f[k][i1][i2];
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1 - 1][i2] + t);
                    x = max(x, f[k - 1][i1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1][i2] + t);
                }
            }
        }
    }
    cout << f[n + n][n][n];
    return 0;
}


活动打卡代码 AcWing 1018. 最低通行费

Spare
2天前
/*
* @Author: Spare Lin
* @Project: AcWing2022
* @Date: 2022/8/13 23:00
* @Description: 1018. 最低通行费
* @URL: https://www.acwing.com/problem/content/1020/
*/
#include <bits/stdc++.h>

#define closeSync ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)

using namespace std;

const int N = 110;
int g[N][N], f[N][N];

signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &g[i][j]);
        }
    }
    //要求我们在 2n-1 的时间内,从起点走到终点 就相当于不能走回头路 走的是一个最短路 只能向下或向右走
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j == 1) f[i][j] = g[i][j]; //特判左上角
            else {
                f[i][j] = 0x3f3f3f3f;
                if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + g[i][j]);
                if (j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + g[i][j]);
            }
        }
    }
    printf("%d\n", f[n][n]);
    return 0;
}



活动打卡代码 AcWing 1015. 摘花生

Spare
2天前
/*
* @Author: Spare Lin
* @Project: AcWing2022
* @Date: 2022/8/13 22:35
* @Description: 1015. 摘花生
* @URL: https://www.acwing.com/problem/content/1017/
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int r, c;
int a[N][N];
int f[N][N];

signed main() {
    int T;
    cin >> T;
    while (T--)
    {
        cin >> r >> c;
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                cin >> a[i][j];
            }
        }
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                f[i][j] = a[i][j] + max(f[i - 1][j], f[i][j - 1]);
            }
        }
        cout << f[r][c] << endl;
    }

    return 0;
}



活动打卡代码 AcWing 4507. 子数组异或和

Spare
2天前
#include <iostream>

using namespace std;

#define int long long
const int N = 3e5 + 7, M = 1 << 20;
int s[2][M];
int n, x, sum, res;

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    s[0][0] ++;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        sum ^= x;
        res += s[i & 1][sum];
        s[i & 1][sum] ++;
    }
    /*
    for (int i = 2; i <= n; i += 2) { //求长度为i的区间的异或
        for (int j = 1; i + j - 1 <= n; j ++) {
            int left = sum[(i + j - 1) / 2] ^ sum[j - 1];
            int right = sum[i + j - 1] ^ sum[(i + j - 1) / 2];
            if(left == right) cnt++;
        }
    }*/
    cout << res << endl;
    return 0;
}