头像

米多奇香米饼




离线:2小时前


最近来访(8)
用户头像
LeetcodeForever
用户头像
yxc的小迷妹
用户头像
suzichen
用户头像
牛神
用户头像
落月成孤倚灬
用户头像
sergey
用户头像
不为人知的小钱


# 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;
}



双指针做法思路

s 数组存储整数序列中每个数所出现的次数,一旦发现有某个数在s数组里面出现了两次,马上清除掉前面的记忆(也就是把前面所有的数从s数组里删掉,为了下一次求字符串的长度做准备,同时把指针j移动过来,最后的结果就是i和j移到了一起。相当于初始状态,但此时的 s[a[ i ]] 为 1,为下次寻找结果做准备
# include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N],s[N];
int main(){
    int n;//整数序列个数
    cin>>n;
    for(int i = 0;i < n;i++) cin>>a[i];
    int res=1;//最短长度为1
    for(int i = 0,j = 0;i < n;i++){
        s[a[i]]++;
        while(s[a[i]] > 1){
            s[a[j]]--;
            j++;
        }
        res = max(res,i - j + 1);
    }
    cout<<res;
    return 0;
}



# include<iostream>
# include<cstdio>
using namespace std;

int main(){
    int n,m;//n代表行,m代表列
    cin>>n>>m;
    int mutex[n][m];
    int flag = 1;
    int ax=0,ay=0,bx=n,by=m;
    while(true){
        for(int i = ay;i<by;i++) {mutex[ax][i] = flag++;}
        for(int i = ax+1;i<bx;i++) mutex[i][by-1] = flag++;
        for(int i = by-2;i>=ay&&bx-1>ax;i--) mutex[bx-1][i] = flag++;
        for(int i = bx-2;i>ax&&by-1>ay;i--) mutex[i][ay] = flag++;
        //进入下一圈
        ax++;ay++;bx--;by--;
        if(ax>=bx||ay>=by) break;
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++) cout<<mutex[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 798. 差分矩阵

# include<iostream>
using namespace std;

const int N = 1010;
int a[N][N],s[N][N];
void insert(int x1,int y1,int x2,int y2,int c){
    s[x1][y1] += c;
    s[x1][y2+1] -= c;
    s[x2+1][y1] -= c;
    s[x2+1][y2+1] += c;
}
int main(){
    int n,m,q;//n行m列q个询问
    cin>>n>>m>>q;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            cin>>a[i][j];
    //构建差分数组
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            insert(i,j,i,j,a[i][j]);
    while(q--){
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);//使得s[x1][y1]加上c
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            s[i][j] += s[i][j-1] + s[i-1][j] - s[i-1][j-1];//求前缀和
            cout<<s[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 797. 差分

# include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
int main(){
    int n,m;
    cin>>n>>m;//长度为n,询问数为m
    for(int i = 1;i <= n;i++) cin>>a[i];
    //f
    for(int i = 1;i <= n;i++) b[i]=a[i]-a[i-1];
    while(m--){
        int l,r,c;
        cin>>l>>r>>c;
        b[l] += c;
        b[r+1] -= c;

    }
    for(int i = 1;i <= n;i++){
        b[i] += b[i-1];
        cout<<b[i]<<" ";
    }
    // int t = 0;
    // for(int i = 1;i <= n;i++){
    //     t += b[i];
    //     cout<<t<<" ";
    // } 
    return 0;
}


活动打卡代码 AcWing 796. 子矩阵的和

# include<iostream>
using namespace std;
const int N = 1010;
int a[N][N],s[N][N];
int main(){
    int n,m,q;
    cin>>n>>m>>q;//n行m列q个询问
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            cin>>a[i][j];
    //构建前缀和数组
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++) 
            s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j]; 
    while(q--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]<<endl;
    }


    return 0;
}


活动打卡代码 AcWing 795. 前缀和

# include <iostream>
using namespace std;
const int N=1e5+10;
int a[N],s[N];
int main(){
    int m,n;
    cin>>n>>m;//n为数列中数字的个数,m为询问个数
    for(int i = 1;i <= n;i++) cin>>a[i];
    //求前缀和数组
    for(int i = 1;i <= n;i++) s[i] = s[i-1] + a[i];
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;//求区间[l,r]之间所有数字的和
    }

    return 0;
}


活动打卡代码 AcWing 792. 高精度减法

# include<iostream>
# include<vector>
using namespace std;
bool cmp(vector<int> A,vector<int> B){
    if(A.size() != B.size()) return A.size()>B.size();
    for (int i = A.size() - 1; i >= 0; i -- ){
        if(A[i] != B[i]) return A[i] > B[i]; 
    }
    return true;
} 
vector<int> sub(vector<int> &A,vector<int> &B){
    vector<int> C;
    int t = 0;//表示借位
    for(int i = 0;i < A.size();i++){
        t = A[i]-t;
        if(i<B.size()) t = t - B[i];
        C.push_back((t+10)%10);
        if(t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main(){
    string a,b;
    cin>>a>>b;
    vector<int> 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');
    vector<int> C;
    if(cmp(A,B)) C = sub(A,B);
    else{
        C = sub(B,A);
        cout<<'-';
    }
    for(int i = C.size()-1;i >= 0;i--) cout<<C[i];
    return 0;
}


活动打卡代码 AcWing 791. 高精度加法

# include<iostream>
# include<vector>
using namespace std;
vector<int> add(vector<int> &A,vector<int> &B){

    if (A.size() < B.size()) return add(B, A);
    vector<int> C;//存取进位后的数字
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}
int main(){
    string m,n;
    cin>>m>>n;
    vector<int> A,B;
    for(int i = m.size()-1;i>=0;i--) A.push_back(m[i]-'0');
    for(int i = n.size()-1;i>=0;i--) B.push_back(n[i]-'0');
    auto C = add(A,B);
    for(int i = C.size()-1;i>=0;i--) printf("%d",C[i]);
    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

# include<iostream>
using namespace std;

int main(){
    double n;
    scanf("%lf",&n);
    double l=-1e4,r=1e4;
    while(r-l>1e-8){
        double mid = (l+r)/2;
        if(mid*mid*mid>n) r = mid;
        else l=mid;
    }
    printf("%.6lf",l);

    return 0;
}