头像

George




离线:23天前


最近来访(4)
用户头像
花月夜月花
用户头像
Avakos
用户头像
zombotany
用户头像
cd_feng

分享 l+r>>1的坑

George
6个月前

在快排或者二分时,我们经常需要取中间值

int x = q[l+r>>1];
int index = l+r>>1;
int x = q[index];

第二种方法可能会出错。比如下列快排版本:

quick_sort(int q[], int l, int r){
    if(l>=r) return ;

    int mid = l+r>>1;
    int i = -1, j = r+1;
    while(i < r){
        do i++; while(q[i] < q[mid]);
        do j--; while(q[j] > q[mid]);
        if(i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q. j+1, r);
}

由于数组会被修改,虽然mid不变,但q[mid]是变化的。

感谢SolitudeAlma 同学的帮助。



分享 稳态

George
6个月前

假设nums长度的为n,所有元素的值均属于[0,n-1],没有重复值。将其排序。

    for(int i = 0; i < nums.size(); i++)
        while(nums[nums[i]] != nums[i]) swap(nums[num[i]], nums[i]);

f(f(x)) = f(x),等价于f(x)=x (在大多数情况下成立,起码在代码空间可以近似成立,欢迎数学大佬补充)
nums[nums[i]] = nums[i],等价于nums[i]=i。 也就是最终稳态条件

    for(int i = 0; i < nums.size(); i++)
        while(nums[i] != i) swap(nums[nums[i]], nums[i]); 

上诉的解法不够鲁棒,当nums存在重复元素时,会出现死循环。
而nums[nums[i]] != nums[i]条件不仅可以达到nums[i]=i的稳态,同时还可以避免死循环。



分享 并查集

George
7个月前
const int N =  1e6+10;
int q[N];

// 封装了q[x]。
// 如果x已经是祖宗(所在集合的根节点),则返回自己,也就是祖宗
// 否则会通过迭代的方式修改父辈族谱(让所有父辈都成为祖宗的直接子节点),但仍是返回祖宗。
int find(int x){
    if(x != q[x]) q[x] = find(q[x]) // 要修改父辈族谱,所以先调用find(q[x]),后给q[x]赋值。
    return q[x];
}



// 将A所在的族谱并入B所在的族谱,不是只把A加入到B族谱。
void mergeA2B(int a, int b){
    q[find(a)] = find(b);           // 合并操作由祖宗执行,子孙没有资格参与家族之间的交互。
}

// 是否同一族谱。
bool isFamily(int a, int b){
    return find(a)==find(b);
}



George
7个月前
#include<iostream>
using namespace std;

const int N = 1e5+10;

int p[N], s[N];


int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}


int main(){
    int n, m;

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

    for(int i = 1; i <= n; i++){
        p[i] = i;
        s[i] = 1;
    }

    while(m--){
        char op[5];
        scanf("%s", op);
        if(op[0] == 'C'){
            int a, b;
            scanf("%d%d", &a, &b);
            if(find(a) == find(b)) continue;
            s[find(b)] += s[find(a)];
            p[find(a)] = find(b);

        }
        else{
            if(op[1] == '1'){
                int a, b;
                scanf("%d%d", &a, &b);
                if(find(a) == find(b)) puts("Yes");
                else puts("No");
            }else{
                int a;
                scanf("%d", &a);
                printf("%d\n", s[find(a)]);
            }
        }
    }

    return 0;
}


活动打卡代码 AcWing 836. 合并集合

George
7个月前
#include <iostream>
using namespace std;

const int N = 1e5+10;
int p[N];


int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main(){
    int n, m;


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

    for(int i = 1; i <= n; i++)
        p[i] = i;

    for(int i = 1; i <= m; i++){
        char op[2];
        int a, b;

        scanf("%s%d%d", op, &a, &b);
        if(op[0] == 'M') p[find(a)] = find(b);
        else{
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }

    }

    return 0;
}

字符和数字混合,用string来读取字符,否则会出现未知bug



活动打卡代码 LeetCode 42. 接雨水

George
9个月前
class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int n = height.size();
        stack<int> stk;

        for(int i = 0; i < n; i++){
            while(stk.size() && height[stk.top()] <= height[i]){
                int cur = stk.top();
                stk.pop();
                if(stk.size())
                    res += (i-stk.top()-1) * ( min(height[i], height[stk.top()]) - height[cur]);
            }
            stk.push(i);
        }

        return res;

    }
};


活动打卡代码 LeetCode 85. 最大矩形

George
9个月前
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if(!n)  return 0;
        int m = matrix[0].size();


        vector<int> heights(m+1);
        heights[m] = -1;

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

            for(int j = 0; j < m; j++)
                if(matrix[i][j] == '0')   heights[j] = 0;
                else heights[j]++;        

            stack<int> stk;
            for(int j = 0; j <= m; j++){
                while(stk.size() && heights[j] < heights[stk.top()]){
                    int cur = stk.top();
                    stk.pop();

                    if(stk.size())
                        res = max(res, heights[cur]*(j-stk.top()-1));
                    else  
                        res = max(res, heights[cur]*(j));
                }

                stk.push(j);
            }

        }

        return res;

    }
};


活动打卡代码 LeetCode 85. 最大矩形

George
9个月前
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if(!n)  return 0;
        int m = matrix[0].size();


        vector<int> heights(m+1);
        heights[m] = -1;

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

            for(int j = 0; j < m; j++)
                if(matrix[i][j] == '0')   heights[j] = 0;
                else heights[j]++;        

            stack<int> stk;
            for(int j = 0; j <= m; j++){
                while(stk.size() && heights[j] < heights[stk.top()]){
                    int cur = stk.top();
                    stk.pop();

                    if(stk.size())
                        res = max(res, heights[cur]*(j-stk.top()-1));
                    else  
                        res = max(res, heights[cur]*(j));
                }

                stk.push(j);
            }

        }

        return res;

    }
};



George
9个月前
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(-1);
        int res = 0;
        stack<int> stk;


        for(int i = 0; i < heights.size(); i++){
            while(stk.size() && heights[i] < heights[stk.top()]){
                int cur = stk.top();
                stk.pop();

                if(stk.size()){
                    res = max(res, heights[cur]*(i-stk.top()-1));
                }else
                    res = max(res, heights[cur]*i);
            }
            stk.push(i);
        }

        return res;
    }
};


活动打卡代码 LeetCode 5. 最长回文子串

George
9个月前
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        int n = s.size();
        for(int i = 0; i < n; i++){
            int l = i-1, r = i+1;
            while(l>=0 && r<n && s[l]==s[r]) l--, r++;
            if(res.size() < r-l-1) res = s.substr(l+1, r-l-1);

            l = i, r = i+1;
            while(l>=0 && r<n && s[l]==s[r]) l--, r++;
            if(res.size() < r-l-1) res = s.substr(l+1, r-l-1);
        }

        return res;
    }
};