头像

一叶扁舟




离线:9天前


活动打卡代码 LeetCode 1. 两数之和

一叶扁舟
1个月前
class Solution {

public:
vector<int> results;
    vector<int> twoSum(vector<int>& nums, int target) {
          //vector 用size求长度
        int length=nums.size();
        for(int i=0;i<length;i++) {
            for(int j=0;j<length;j++){
                if(i!=j){
                    if(nums[i]+nums[j]==target) {
                        //vector 用push_back添加
                        results.push_back(i);
                        results.push_back(j);
                         return results;
                    }
                }
            }
        }
       return results;
    }
};


活动打卡代码 AcWing 842. 排列数字

一叶扁舟
1个月前
#include<iostream>
using namespace std;
//定义全局变量
int n;
const int N=10;
int path[N];
//定义占位状态,占了就设为true
bool state[N];
void dfs(int u){
    //如果超过最大深度,说明所有位置已经填满了
    if(u==n) {
        for(int i=0;i<n;i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
        //返回
        return;
    }
    //如果没到最大深度
    for(int i=1;i<=n;i++) {
        //如果第i个位置是空
        if(!state[i]) {
            path[u]=i;
            state[i]=true;
            dfs(u+1);
            //恢复现场
            state[i]=false;
        }
    }
}
int main() {
    cin >> n;
    //从0深度开始
    dfs(0);
}


活动打卡代码 AcWing 840. 模拟散列表

一叶扁舟
2个月前
#include<iostream>
#include<cstring>
using namespace std;
const int M=100003;
int h[M],e[M],ne[M],idx;
void insert(int x){
    //取模,为了余数是正的所以+M
    int k=((x%M)+M)%M;
    e[idx]=x;
    //?为什么不是ne[k]
    ne[idx]=h[k];
    h[k]=idx++;
}
bool query(int x) {
      int k=((x%M)+M)%M;
      //i=ne[i]
      for(int i=h[k];i!=-1;i=ne[i]) {
          if(e[i]==x) {
              return true;
          }


      }
      //遍历都没有就返回false
       return false;
}
int main() {
    int n;
   scanf("%d", &n);
   memset(h, -1,sizeof h);
   while(n--) {
       //定义字符数组,防止空格
       char ss[2];
       int m;
       scanf("%s%d", &ss, &m);
       if(ss[0]=='I'){
           insert(m);
       }else {
           if(query(m)) puts("Yes");
           else puts("No");
       }
   }
}


活动打卡代码 AcWing 838. 堆排序

一叶扁舟
2个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int M=100010;
int h[M],hsize;
int n,m;
void down(int x) {
    int t=x;
    if(2*x<=hsize && h[t]>h[2*x]) t=2*x;
    if(2*x+1<=hsize && h[t]>h[2*x+1]) t=2*x+1;
    //如果根节点不是t,说明要交换
    if(x!=t) {
       swap(h[x],h[t]); 
       down(t);
    }

}
int main() {

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%d", &h[i]);
    }
    hsize=n;
     for(int i=n/2;i;i--) {
        down(i);
    }
    while(m--) {
        printf("%d ", h[1]);
        h[1]=h[hsize];
        hsize--;
        down(1);
    }
}


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

一叶扁舟
2个月前
#include<iostream>
using namespace std;
const int M=1000010;
int a[M],q[M];
int main() {
    int n,k;
    scanf("%d%d", &n,&k);
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
    }
    int hh=0,tt=-1;
    for(int i=0;i<n;i++){
         //q[hh]如果大于i-k+1就滑出窗口了
        if(hh<=tt&&q[hh]<i-k+1) hh++;
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt]=i;
        //不足k个数就不用输出了
        if(i>=k-1) printf("%d ", a[q[hh]]);
    }
    cout<<endl;
    hh=0,tt=-1;
     for(int i=0;i<n;i++){
         //q[hh]如果大于i-k+1就滑出窗口了
        if(hh<=tt&&q[hh]<i-k+1) hh++;
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++tt]=i;
        if(i>=k-1) printf("%d ", a[q[hh]]);
    }

}


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

一叶扁舟
2个月前
#include<iostream>
using namespace std;
const int N = 100010;
int stk[N],tt;
int main() {
    int m,x;
    cin>>m;
    while(m--) {
        cin>>x;
        //当栈尾>0且栈中数大于等于x
       while(tt&&stk[tt]>=x){
           tt--;
       }
       if(tt) {
               cout<<stk[tt]<<' ';
           }else {
               cout<<"-1"<<' ';
           }
           //栈尾插入x
          stk[++tt]=x;
    }
}


活动打卡代码 AcWing 829. 模拟队列

一叶扁舟
2个月前
#include<iostream>
using namespace std;
const int M=100010;
int queue[M],hh,tt=-1;
void push(int x) {
    queue[++tt]=x;
}
//头坐标向右边移动,最左边的就弹出
void pop() {
    hh++;
}
string empty() {
    if(hh<=tt) return "NO";
    else return "YES";
}
int query() {
    return queue[hh];
}
int main() {
    int m,x;
    cin>>m;
    while(m--){
        string ss;
        cin>>ss;
        if(ss=="push"){

            cin>>x;
            push(x);
        }
        if(ss=="pop"){
            pop();
        }
        if(ss=="empty"){
           cout<< empty()<<endl;
        }
        if(ss=="query"){
            cout<<query()<<endl;
        }
    }
}


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

一叶扁舟
2个月前
#include<iostream>
using namespace std;
const int M=100010; 
int stk[M],tt=0;
void push(int x) {
  //++t是先赋值再+1,插入x
  stk[++tt] = x;
}
void pop() {
    tt--;
}
string empty() {
    if(tt>0) return "NO";
    else return "YES";
}
int query() {
   return stk[tt];
}
int main() {
    int n;
    cin>>n;
    while(n--) {
        string m;
        int x;
        cin >>m;
        if(m=="push"){
            cin>>x;
            push(x);
        }
        if(m=="pop") {

            pop();
        }
        if(m=="empty"){
           cout<< empty() <<endl;
        }
        if(m=="query"){
            cout<< query() <<endl;
        }
    }
}


活动打卡代码 AcWing 827. 双链表

一叶扁舟
2个月前
#include<iostream>
using namespace std;
const int M = 100010;
int idx,l[M],r[M],e[M];
void init() {
    l[1]=0;
    r[0]=1;
    idx=2;
}
//表示将k坐标的数删除
void remove(int k) {
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}
//k右侧插入x
void add(int k, int x) {
    e[idx]=x;
    r[idx]=r[k];
    l[r[k]]=idx;
    l[idx]=k;
    r[k]=idx++;
}
int main() {
    int n,k,x;
    //多个字符,使用字符串
    string m;
    //初始化
    init();
    cin>>n;
    while(n--) {
        cin>>m;
        if(m=="L") {
            cin >>x;
            add(0,x);
        }
        if(m=="R") {
            cin >>x;
            add(l[1],x);
        }
        //删除第k个数
        if(m=="D") {
            cin >>k;
            remove(k+1);
        }
        if(m=="IL") {
            cin >>k>>x;
            add(l[k+1],x);
        }
        //表示在第k个插入的数右侧插入一个数
        if(m=="IR") {
             cin >>k>>x;
            add(k+1,x);
        }
    }
    //0的右侧开始,往右边递增,知道与1相等
    for(int i=r[0];i!=1;i=r[i]) {
        cout << e[i] << " ";
    }
}


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

一叶扁舟
2个月前
#include<iostream>
using namespace std;
const int M =100010;  
int e[M],ne[M],head,idx;
void init() {
    //head是头指针,即头结点下标,初始化为-1
    head=-1;
    idx=0;
}
//向链表头插入一个数x。
void insert_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}
//删除下标k后面的数
void remove(int k) {

    ne[k]=ne[ne[k]];
}
//下标k后插入一个数
void insert(int k, int x) {
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
int main() {
    init();
    int n,x,k;
    cin>>n;
    while(n--) {
        char m;
        cin>>m;
        //向链表头插入一个数x
        if(m=='H'){
            cin>>x;
            insert_head(x);
        }
        if(m=='D'){
            cin>>k;
            //当k为0,第0个结点的下标就是head
            if(!k){
                head=ne[head];
            }else {
              remove(k-1);
            }

        }
        if(m=='I'){
            cin>>k>>x;
            insert(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i]) {
        cout<<e[i]<<" ";
    }
}