头像

暗号34708


访客:148

离线:3天前


活动打卡代码 AcWing 143. 最大异或对

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010, M = 3000000;

int n , son[M][2], a[N], idx;

void insert(int x) {
    int p = 0;
    //当我们想写i >= 0的时候我们可以写成~i,因为-1的取反i是0
    for(int i = 30; ~i; i--) { 
         int &s = son[p][x >> i & 1];
         if(!s) s = ++ idx; //创建新节点
         p = s;

    }
}
int query(int x) {
    int res = 0, p = 0;

    for(int i = 30; ~i; i--) {
        int s = x >> i & 1;

        if(son[p][!s]) {

            res += 1 << i;
            p = son[p][!s];
        }
        else 
            p = son[p][s];
    }

    return res;
}
int main() {

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

    int res = 0;
    for(int i = 0; i < n; i++) res = max(res, query(a[i])); 

    cout << res << endl;

    return 0;
}



活动打卡代码 AcWing 835. Trie字符串统计

/*
Trie Tree: A high-efficiency data structure to deal with strings or finding string sets
*/
#include<iostream>

using namespace std;

const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];

void insert(char str[]) {
    int p = 0;
    for(int i = 0; str[i]; i++) {
        int u = str[i]- 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];

    }
    cnt[p] ++;

}

int query(char str[]) {
    int p = 0;
    for(int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];

}
int main() {
    int n = 0;
    scanf("%d", &n);
    while(n--) {
        char op[2];
        scanf("%s%s", op, str);
        if(op[0] == 'I') insert(str);
        else printf("%d\n", query(str));

    }
    return 0;
}



请问一下各位大佬
我如果想把一个字母变成数字
比如在C++里面
int u = str[i] - ‘a’,
那么java里面应该怎么实现呢。。
求解



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

/*
如何思考单调队列
*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n, k;

//index in q[N]
int arr[N], q[N];

int main() {

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

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

    //循环
    for(int i = 0 ; i < n; i++) {

        if (hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && arr[q[tt]] >= arr[i]) tt--;
        q[++tt] = i;

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

    puts("");

    return 0;
} 


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

暗号34708
1个月前
/**
 *判断一个序列的一个数字最小的最近的左边的数是多少 
*/
#include <iostream>
using namespace std;

const int N = 100010;

int stk[N], tt;
int n;

int main() { 
    cin >> n;

    //利用的是栈的原理
    for(int i = 0; i < n ; i++) {
        int x;
        cin >> x;
        while(tt != 0 && stk[tt] >=x) tt--;
        if(tt != 0) cout << stk[tt] << endl;
        else cout << "-1" << endl;

        //最后再把这个数字放在栈的最后面
        stk[++i] = x;
    }    

}


活动打卡代码 AcWing 828. 模拟栈

暗号34708
1个月前
#include <iostream>
using namespace std;

const int N = 100010;

int stk[N], tt;

void add(int x) {
    stk[++tt] = x;
}

void delete() {
    tt--;
}
if(tt > 0) empty;
    else not empty;

int main() {

    //插入操作
    return 0;

}

~



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

暗号34708
1个月前
import java.util.Scanner;

public class Binary_Search {

    private static final int N = 100010;
    static int [] arr = new int[N];
    static int n, m;
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }

        while( m-- != 0) {

            int x = scan.nextInt();

            int left = 0, right = n - 1;

            while (left < right) {

                int mid = left + right >> 1;
                if(arr[mid] >= x) right = mid;
                else left = mid + 1;
            }

            if(arr[left] != x) System.out.println("-1, -1");

            else {

                System.out.print(left + " ");

                left = 0; right = n -1;
                while(left < right) {

                    int mid = left + right >> 1;
                    if(arr[mid] <= x) left = mid;
                    else right = mid  - 1;
                }

                System.out.println(right);

            }
        }

        scan.close();
    }

}



暗号34708
1个月前
#include <iostream>

using namespace std;

int lowbit(int x) {
    return x & -x;
}

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

    while(n--) {

        int x;
        cin >> x;
        int res = 0;
        while(x) x -= lowbit(x), res++;

        cout<<res<< " ";
    }

    return 0;

}



暗号34708
1个月前
const int  N = 100010;

int q[N];

int n , m ;


bool check(int start, int now) {

    int count = 0;

    for(int i =  now -1 ; i > start; i--) {
        if(q[now] != q[i]) count++;
    } 
    return count == now - start ? true : false;  

}


int main() {

    scanf("%d",&n);

    int count = 0;

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

    for(int i = 0, j = 0; i < n; i++) {

        while(check(i , j)) {



            count = max(count, j - i + 1 );

            j++; 

        }



    }

}


活动打卡代码 AcWing 797. 差分

暗号34708
1个月前
import java.util.Scanner;

public class Difference {

    private static final int N = 100010;

    static int [] given = new int[N];
    static int [] res = new int[N];

    static int m , n;
    public static void main(String[] args) {

        Scanner scan1 = new Scanner(System.in);
        Scanner scan2 = new Scanner(System.in);
        Scanner scan3 = new Scanner(System.in);

        m = scan1.nextInt();
        n = scan3.nextInt();
        for(int i = 1; i <= m; i++) given[i] = scan2.nextInt();

        for(int i = 1; i <= m ; i++) insert(i , i, given[i]);


        while(n-- > 0) {

            int l, r, c;
            Scanner scan4 = new Scanner(System.in);
            Scanner scan5 = new Scanner(System.in);
            Scanner scan6 = new Scanner(System.in);
            l = scan4.nextInt();
            r = scan5.nextInt();
            c = scan6.nextInt();

            insert(l , r, c);

            scan4.close();
            scan5.close();
            scan6.close();

        }

        for(int i = 1; i <= m; i++) res[i] += res[i -1];
        for(int i = 1; i <= m; i++) System.out.print(res[i] + " ");

        scan1.close();
        scan2.close();
        scan3.close();
    }

    static void insert(int left, int right, int c) {

        res[left] = res[left] + c;
        res[right + 1] = res[right + 1] - c;

    }
}