头像

头号玩家




离线:7小时前


最近来访(47)
用户头像
老爹古董店
用户头像
aki_96
用户头像
Loki
用户头像
坚持自己的目标
用户头像
自律
用户头像
jinyc
用户头像
Bbbtt04
用户头像
Confidentinvincible
用户头像
虔诚_
用户头像
WangJY
用户头像
Mr_J
用户头像
此用户已注销
用户头像
小郭自律一点
用户头像
TStark
用户头像
Nickdd
用户头像
Q晨
用户头像
Idmnvcxzlkhdsaoiutrew
用户头像
雨落听弦声
用户头像
slzs
用户头像
zyrfff


[//]: # (打卡模板,上面预览按钮可以展示预览效果 ^^)
当数据范围很小的时候(n<=30),可以考虑状态压缩Dp
本题中当我们考虑第i位的数字放置什么时,往往只需要关心前面i-1位都放了哪些数,然后从剩下的数挑选放置到第j位置
所以可以用一个二进制序列来表示哪些位置已经被使用过,然后尝试将没有使用过的数字放置到第k+1位

class Solution {
public int countArrangement(int n) {
int [] f=new int[1<[HTML_REMOVED]>j&1)==1) k++;
}
for(int j=0;j[HTML_REMOVED]>j&1)==0){
if(k%(j+1)==0||(j+1)%k==0){
f[i|(1<<j)]+=f[i];
}
}
}
}

    return f[(1<<n)-1];

}

}




活动打卡代码 LeetCode 526. 优美的排列

当数据范围很小的时候(n<=30),可以考虑状态压缩Dp
本题中当我们考虑第i位的数字放置什么时,往往只需要关心前面i-1位都放了哪些数,然后从剩下的数挑选放置到第j位置
所以可以用一个二进制序列来表示哪些位置已经被使用过,然后尝试将没有使用过的数字放置到第k+1位

class Solution {
    public int countArrangement(int n) {
        int [] f=new int[1<<n];
        f[0]=1;
        for(int i=0;i<1<<n;i++){ //1<<n所有可能的情况
            int k=1;
            for(int j=0;j<n;j++){
                if((i>>j&1)==1) k++; 
            }
            for(int j=0;j<n;j++){
                if((i>>j&1)==0){
                    if(k%(j+1)==0||(j+1)%k==0){
                        f[i|(1<<j)]+=f[i];
                    }
                }
            }
        }

        return f[(1<<n)-1];

    }
}



class Solution {
    public int distinctSequences(int n) {
        long[][][] f=new long[n+1][7][7];
        int mod=1000000007;
        if(n==1) return 6;
        for(int k=1;k<=6;k++){
            for(int j=1;j<=6;j++){
                if(gca(k,j)==1&&k!=j){
                    f[2][j][k]=1;
                }
            }
        }

        long ans=0;
        for(int i=3;i<=n;i++){
            for(int k=1;k<=6;k++){
                for(int j=1;j<=6;j++){
                     if(gca(j,k)==1&&k!=j){
                         for(int u=1;u<=6;u++){
                             if(gca(u,j)==1&&u!=j&&u!=k){
                                 f[i][j][k]=(f[i][j][k]+f[i-1][u][j])%mod;
                             }
                         }
                     }

                }
            }
        }
        for(int i=1;i<=6;i++){
            for(int j=1;j<=6;j++){
                ans=(ans+f[n][i][j])%mod;
            }
        }

         return (int)(ans%mod); 
    }

    int gca(int x,int y){
        return y==0?x:gca(y,x%y);
    }
}


活动打卡代码 LeetCode 22. 括号生成

1.png

class Solution {
    List<String> list=new ArrayList();
    public List<String> generateParenthesis(int n) {
        String sb=new String();
        dfs(n,0,0,sb);
        return list;
    }

    void dfs(int n,int lc,int rc,String sb){
        if(lc==n&&rc==n) list.add(sb);
        if(lc<n) dfs(n,lc+1,rc,sb+"(");
        if(rc<n&&lc>rc) dfs(n,lc,rc+1,sb+")");
    }
}



1.jpg

class Solution {
    public int maximumXOR(int[] nums) {
        int ans=0;
        for(int i=0;i<nums.length;i++){
            ans|=nums[i];
        }
        return ans;
    }
}



稀疏图,将原问题转化为了所有节点对的个数-能相互连通的节点对的个数,即求同一个集合中点的个数

class Solution {
    int N=100010;
    int [] f=new int[N];
    int [] size=new int[N];
    public long countPairs(int n, int[][] e) {
          for(int i=0;i<n;i++){
              f[i]=i;
              size[i]=1;
          }
          for(int i=0;i<e.length;i++){
              int a=find(e[i][0]);
              int b=find(e[i][1]);
              if(a!=b){
                  size[b]+=size[a];
                  f[a]=b;

              } 
          }
          long ans=(long)n*(n-1)/2;
          for(int i=0;i<f.length;i++){
             if(f[i]==i) ans-=(long)size[i]*(size[i]-1)/2;
          }
          return ans;
    }

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

dfs求一个连通集中点的个数,核心是要有对每个结点的判断数组,如果该结点已经走过那么不再走

class Solution {
    int [] h=new int[100010];
    int [] e=new int[400010];
    int [] ne=new int[400010];
    boolean [] f=new boolean[100010];
    int idx=0;
    long ans=0;
    long sum=0;
    public long countPairs(int n, int[][] edges) {
         for(int i=0;i<n;i++){
             h[i]=-1;
         }
         for(int i=0;i<edges.length;i++){
             int a=edges[i][0]; int b=edges[i][1];
             add(a,b); add(b,a);
         }
         for(int i=0;i<n;i++){
             int num=dfs(i);
             ans+=sum*num;
             sum+=num;
         }
         return ans;

    }

    int dfs(int a){
        if(f[a]) return 0;
        f[a]=true;
        int cnt=1;
        for(int i=h[a];i!=-1;i=ne[i]){
            int b=e[i];
            if(!f[b]) cnt+=dfs(b);
        }
        return cnt;
    }

    void add(int a,int b){
        e[idx]=b; ne[idx]=h[a];h[a]=idx++;
    }
}

BFS求连通图的最小点数

class Solution {
    int [] h=new int[100010];
    int [] e=new int[400010];
    int [] ne=new int[400010];
    boolean [] f=new boolean[100010];
    int idx=0;
    long ans=0;
    long sum=0;
    public long countPairs(int n, int[][] edges) {
         for(int i=0;i<n;i++){
             h[i]=-1;
         }
         for(int i=0;i<edges.length;i++){
             int a=edges[i][0]; int b=edges[i][1];
             add(a,b); add(b,a);
         }
         for(int i=0;i<n;i++){
             int num=bfs(i);
             ans+=sum*num;
             sum+=num;
         }
         return ans;

    }

    int bfs(int a){
        if(f[a]) return 0;
        Deque<Integer> q=new LinkedList<Integer>();
        q.add(a); f[a]=true;
        int cnt=1;
        while(q.size()!=0){
            int b=q.poll();
            for(int i=h[b];i!=-1;i=ne[i]){
                int c=e[i];
                if(!f[c]){
                    cnt++;
                    f[c]=true;
                    q.add(c);
                }
            }
        }
        return cnt;
    }

    void add(int a,int b){
        e[idx]=b; ne[idx]=h[a];h[a]=idx++;
    }
}


活动打卡代码 LeetCode 198. 打家劫舍

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        int [] f=new int[n+2];
        for(int i=2;i<=n+1;i++){
            f[i]=Math.max(nums[i-2]+f[i-2],f[i-1]);
        }
        return f[n+1];
    }
}



线段树,
a的意义为每一排实际坐着的人数
f的意义为0~n-1中某段区间中坐着的人数最小值,那么显然如果最小值如果小于m-k,那么我们可以深入这段区间中寻找坐着的人数小于m-k的最靠前的排-----对应gather操作
p的意义为0~n-1中某段区间中坐着人数和,如果此段区间中的作为减去人数和<K,那么显然无法再坐人----对应scatter操作
同时每一次成功坐人我们都要更新a/f/p数组
同时要注意数组的数据范围,p是记录人数和的数组所以会爆Int

class BookMyShow {
    int N=50010;
    int [] a=new int[N];
    int [] f=new int[4*N];
    long [] p=new long[4*N];
    int n=0;
    int m=0;

    public BookMyShow(int n1, int m1) {
        n=n1;
        m=m1;
    }

    public int check(int c,int l,int r,int num){ //check函数返回人数小于等于num的最小排号
         if(f[c]>num) return 0x3f3f3f3f; 
         if(l==r) return l;
         int mid=l+r>>1;
         if(f[c+c]<=num)   return check(c+c,l,mid,num);
         if(f[c+c+1]<=num) return check(c+c+1,mid+1,r,num);

         return 1;
    }


    /*
    public void add(int c,int l,int r,int x,int k){
     }
     */


    public void add(int c,int l,int r,int x,int k){
        if(l==r){
            a[l]+=k;
            f[c]+=k;
            p[c]+=k;
            return;
        }
        int mid=l+r>>1;
        if(x<=mid) add(c+c,l,mid,x,k);
        else add(c+c+1,mid+1,r,x,k);
        f[c]=Math.min(f[c+c],f[c+c+1]);
        p[c]=p[c+c]+p[c+c+1];

    }


    public int[] gather(int k, int maxRow) {
        List<Integer> list=new ArrayList();
        int c=check(1,0,n-1,m-k);
        if(c>maxRow) return list.stream().mapToInt(Integer::intValue).toArray();
        else{

            list.add(c);
            list.add(a[c]);
            add(1,0,n-1,c,k);
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
    }

    public long sum(int c,int l,int r,int kl,int kr){
        if(l==kl&&r==kr) return p[c];
        int mid=l+r>>1;
        if(kr<=mid) return sum(c+c,l,mid,kl,kr);
        if(kl>=mid) return sum(c+c+1,mid,r,kl,kr);
        return sum(c+c,l,mid,kl,mid)+sum(c+c+1,mid+1,r,mid+1,kr);
    }

    public boolean scatter(int k, int maxRow) {
        if((maxRow+1)*(long)m-sum(1,0,n-1,0,maxRow)<k) return false;
        else{
            int d=0;
            while(k>0){
                if(a[d]==m) {
                    d++;
                    continue;
                }
                else{
                   int left=m-a[d];
                   if(left>=k){
                       add(1,0,n-1,d,k);
                       return true;
                   }else{
                       k-=m-a[d];
                       add(1,0,n-1,d,left);
                       d++;
                   }
                }

            }
            return true;
        } 

    }
}


活动打卡代码 LeetCode 486. 预测赢家

class Solution {
    public boolean PredictTheWinner(int[] nums) {
       int n=nums.length;
       int [][] f=new int[n][n];
       for(int len=1;len<=n;len++){
           for(int i=0;i+len-1<n;i++){
               int j=i+len-1;
               if(len==1){
                   f[i][j]=nums[i];
               }else{
                   f[i][j]=Math.max(-f[i+1][j]+nums[i],-f[i][j-1]+nums[j]);
               }
           }
       }
       return f[0][n-1]>=0;
    }
}


分享 链表

2022.6.22 8 周赛.设计一个文本编辑器 https://leetcode.cn/problems/design-a-text-editor/