头像

张大迷糊爱唠叨




在线 


活动打卡代码 AcWing 831. KMP字符串

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
char p[N], s[M];
int ne[N];

int main(){

    cin >> n >> p + 1 >> m >> s + 1;

    //求next的过程
    for(int i = 2, j = 0; i <= n; i++){
        while(j && p[i] != p[j + 1]){
            j = ne[j];
        }
        if(p[i] == p[j + 1]){
            j++;
        }
        ne[i] = j;
    }
    //kmp匹配过程
    for(int i = 1, j = 0; i <= m; i++){
        while(j && s[i] != p[j + 1]){
            j = ne[j];
        }
        if(s[i] == p[j + 1]){
            j++;
        }
        if(j == n){
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

#include <iostream>

using namespace std;

const int N = 1000010;

//k表示窗口中的元素 
int n,k;
//q存储的是下标
int a[N], q[N];

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    //hh是队头,tt是队尾
    int hh = 0, tt = -1;

    for(int i = 0; i < n; i++){
        //判断队头是否已经滑出窗口,当前终点是i,起点是i - k + 1
        if(hh <= tt && i - k + 1 > q[hh]){
            hh++;
        }

        while(hh <= tt && a[q[tt]] >= a[i]){
            tt--;
        }
        q[++tt] = i;
        if( i >= k - 1){
            printf("%d ",a[q[hh]]);
        }

    }

    puts(" ");

    hh = 0, tt = -1;

    for(int i = 0; i < n; i++){
        if(hh <= tt && i - k + 1 > q[hh]){
            hh++;
        }

        while(hh <= tt && a[q[tt]] <= a[i]){
            tt--;
        }

        q[++tt] = i;

        if(i >= k - 1){
            printf("%d ",a[q[hh]]);
        }
    }

    return 0;
}



活动打卡代码 AcWing 830. 单调栈

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int stk[N], tt = 0;

int main(){
    cin >> n;
    for(int i = 0; i < n ; i++){
        int x;
        cin >> x;
        //栈非空且栈顶元素大于x,此时栈顶元素就不会被使用
        while(tt && stk[tt] >= x){
            tt--;
        }
        //栈非空
        if(tt){
            cout << stk[tt] << ' ';
        }else{
            cout << -1 << ' ';
        }

        stk[++tt] = x;
    }
    return 0;
}


活动打卡代码 AcWing 826. 单链表

#include <iostream>

using namespace std;

const int N = 100010;

//head表示头结点的下标,表示头指针
//e[i]表示结点i的值
//ne[i]表示结点i的next的下标,表示下一个指针
//idx存储当前已经使用到的下标,表示当前指针
int head, e[N], ne[N], idx;

//初始化
void init(){
    head = -1;
    idx = 0;
}

//将x插入到头结点
void add_to_head(int x){
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
    //idx++;
}

//将x插入到下标是k的点的后面
void add(int k, int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
    //idx++;
}

//将下标是k的点的后面的点删除
void remove(int k){
    ne[k] = ne[ne[k]];
}

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

    init();
    while(m--){
        int k, x;
        char op;

        cin >> op;

        if(op == 'H'){
            cin >> x;
            add_to_head(x);
        }else if(op == 'D'){
            cin >> k;
            //如果删除的是头结点,则将头结点后移
            if(!k){
                head = ne[head];
            }else{
                remove(k-1);
            }
        }else{
            cin >> k >> x;
            add(k-1, x);
        }
    }

    for(int i = head; i!= -1; i = ne[i]){
        cout << e[i] << ' ';
    }
}



活动打卡代码 AcWing 803. 区间合并

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs;
void merge(vector<PII> &segs){
    vector<PII> res;

    sort(segs.begin(),segs.end());

    int st = -2e9, ed = -2e9;

    for(auto seg : segs){
        if(ed < seg.first){
            if(st != -2e9){
                res.push_back({st, ed});
            }
                st = seg.first, ed = seg.second;

        }else{
            ed = max(ed, seg.second);
        }
    }

    if(st != -2e9){
        res.push_back({st, ed});
    }

    segs = res;
}
int main(){
    cin >> n;

    for(int i = 0; i < n; i++){
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;
    return 0;
}


活动打卡代码 AcWing 794. 高精度除法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// A / b,商是C,余数是r
vector<int> div(vector<int> &A, int b, int &r){

    vector<int> C; //C是商
    r = 0;
    for (int i = A.size() - 1; i >= 0; i--){
        r = r * 10 + A[i];
        //商从高位到低位存储
        C.push_back(r / b);
        r %= b;
    }

    //反转商的结果,此时从低位到高位存储
    reverse(C.begin(), C.end());

    while(C.size() > 1 && C.back() == 0){
        C.pop_back();
    }
    return C;
}


int main(){

    string a;
    int b;

    cin >> a >> b;

    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    int r;
    auto C = div(A, b, r);

    //商从高位到低位输出
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);

    cout << endl << r << endl;

    return 0;
}



高精度减法

y总的代码可能给我带来一些理解上的困难,我这里将t分成两个不同的字符tkt表示进位,k表示每一位的数值,对于我来说这样更好理解一些,这里分享给大家,当然大佬可以直接忽略,哈哈!!!!

#include <iostream>
#include <vector>

using namespace std;
// 判断是否有 A >= B
bool cmp(vector<int> &A, vector<int> &B) {

    //位数不同,A的位数大就大,A的位数小就小
    if (A.size() != B.size()){

        return A.size() > B.size();
    }

    //位数相同,从高位开始比较,第一位不相等,判断A与B大小
    for (int i = A.size() - 1; i >= 0; i--){

        if(A[i] != B[i]){

            return A[i] > B[i];
        }
    }
    return true;
}
//C = A - B
vector<int> sub(vector<int> &A, vector<int> &B){

    vector<int> C;

    //从个位开始计算
    //t表示的是借位,其范围是0或1
    for (int i = 0, t = 0; i < A.size(); i++){
        //k表示每一位的数值
       int k = A[i] - t;
        if(i < B.size()){
            k -= B[i];  
        }
        /*if(k >= 0){
            return k;
        }else if(k < 0){
            return k+10;
        }*/
        //将上面合为一步骤,即(k + 10) % 10
        C.push_back((k + 10) % 10);

        if(k < 0){
            t = 1;
        }else{
            t = 0;
        }
    }

    //去掉前导零
    while (C.size() > 1 && C.back() == 0){

        C.pop_back();
    }
    return C;
}

int main(){
    string a, b;
    vector<int> A, B;

    cin >> a >> b;

    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    if (cmp(A, B)){

        auto C = sub(A, B);

        for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    }else{

        auto C = sub(B, A);

        printf("-");

        for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    }
    return 0;
}


活动打卡代码 AcWing 789. 数的范围

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main(){

    scanf("%d%d", &n, &m);

    for(int i = 0; i < n; i++) scanf("%d", &q[i]);

    while(m--){

        int x;
        scanf("%d", &x);

        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >> 1;

            if(q[mid] >= x){
                r = mid;
            }else{
                l = mid + 1;
            }
        }

        if(q[l] != x) {

            cout << "-1 -1" << endl;
        }else{
            cout << l << ' ';

            int l = 0, r = n - 1;

            while(l < r){
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) {
                    l = mid;
                }else{
                    r = mid - 1;
                }
            }
            cout << l << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 786. 第k个数

#include <iostream>

using namespace std;

const int N = 100010;

int n, k;
int q[N];

int quick_sort(int l, int r, int k){
    if(l == r){
        return q[l];
    }
    int x = q[l], i = l - 1, j = r + 1;
    while(i < j){
        while(q[++i] < x);
        while(q[--j] > x);
        if(i < j){
            swap(q[i], q[j]);
        }
    }
    int sl = j - l + 1;

    if(k <= sl){
        return quick_sort(l, j, k);
    }
        return quick_sort(j+1, r,k - sl);

}
int main(){
    scanf("%d%d", &n, &k);

    for(int i = 0; i < n; i++){
        scanf("%d", &q[i]);
    }
    int res = quick_sort(0, n - 1, k);

    printf("%d",res);

    return 0;
}



在求第k个数的这个视频中,请问快速排序的分界点为什么不一定等于x?