牛客.dd爱旋转牛客.小红取数(dp）牛客.字符编码力扣1262.能被三整除的最大和（正难则反）2025年9月5日中通快递第一题生产者消费者模型
牛客.dd爱旋转牛客.小红取数(dp）牛客.字符编码力扣1262.能被三整除的最大和（正难则反）2025年9月5日中通快递第一题生产者消费者模型
·
目录
牛客.dd爱旋转
模拟旋转谁都会，但是会超时，所以就没写出来
优化:
操作1:180度旋转 可以理解为行+列对称
其余的就是对称，对称两次就不看了，就相当于对称两次就是不用操作。
import java.util.*; import java.io.*; public class Main{ public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); public static Read in=new Read(); static int n; // 1 2 3 321 12 21 // 4 5 6 654 // 7 8 9 987 //col 要么省1 要么不剩 有可能row%2==0 public static int[][] col1(int[][]a) { int[][]target=new int[n][n]; for (int i = 0; i <=n-1; i++) { for (int j = 0; j <=n-1; j++) { int last=n-1-j; target[i][j]=a[i][last]; } } return target; } public static int[][] row1(int[][]a) { ArrayList<Integer>tem = new ArrayList<>(); for (int i = n-1; i >=0; i--) { for (int j = 0; j <=n-1; j++) { tem.add(a[i][j]); } } int count=0; int[][]target=new int[n][n]; for (int i = 0; i <n; i++) { for (int j = 0; j <n; j++) { target[i][j]=tem.get(count++); } } return target; } public static void main(String[] args)throws IOException { Read in = new Read(); n = in.nextInt(); int[][] a = new int[n][n]; int[][]target = new int[n][n]; for (int i = 0; i <n; i++) { for (int j = 0; j <n; j++) { a[i][j] = in.nextInt(); target[i][j]=a[i][j]; } } int q=in.nextInt(); int col=0; int row=0; for (int i = 0; i < q; i++) { int p = in.nextInt(); if (p == 1) { col++; row++; }else{ row++; } } if(col%2==1)target=col1(target); if(row%2==1)target=row1(target); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ out.print(target[i][j]+" "); } out.println(); } out.close(); } } class Read{ //字符串裁剪工具 StringTokenizer st=new StringTokenizer(""); //带内存缓冲的字符流，先刷新到缓冲区里面 BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); //字符流转化为字节流 String next()throws IOException{ //为啥有循环 while(!st.hasMoreTokens()){ //其实直接这个就行，但是因为有可能有些他还有一行，因此，我们是看下一行有没有东西 st=new StringTokenizer(bf.readLine()); } return st.nextToken(); } String nextLine() throws IOException{ return bf.readLine(); } int nextInt()throws IOException{ return Integer.parseInt(next()); } long nextLong() throws IOException{ return Long.parseLong(next()); } }
牛客.小红取数(dp）
感觉是01背包，在满足xx条件下，条件最大
状态表示
dp[i]:从前i个物品挑选，总和为k的倍数，此时的最大和是多少
但是假如1维，不知道dp[i]：咋选的，选没选
我的01困难，背包的体积不知道多少
k=5
同余原理
如果:a%k=x,b%k=y 假如 (a+b)%k==0 那么(x+y)%k==0
- (a + b + c) % k = (a % k + b % k + c % k) % k
- 如果(a - b) % k = 0，那么a % k = b % k
- 整数乘法需转成long，再进行相乘从而避免溢出
dp[i][j]:从前i个数挑选，总和%k==j时候，最大的和为多少
j-a[i]%k即可
因此确定了01背包+同余原理
状态表示
dp[i][j]=(不选a[i]) dp[i-1][j]
选a[i] dp[i-1][ (j-a[i]%k+k )%k ] +a[i]
j-a[i]%k(很有可能是5)
j开始可能是1 ，因此再去加上k ( (j-a[i]%k+k )%k )
同时初始化也要注意，
初始化，前0个里面，余数应该是0，但是前0个里面余数不可以是别的，所以别的不合法，直接初始化最小值
返回值，从前0个数拿，然后最后，总和应该是k的倍数，那么余数应该是0.
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n=in.nextInt(); int k=in.nextInt(); //前i个数中余数为j的 long[]a=new long[n+1]; for(int i=1;i<=n;i++){ a[i]=in.nextLong(); } long[][]dp=new long[n+1][k]; for(int i=0;i<=n;i++){ for(int j=0;j<k;j++){ dp[i][j]=-0x3f3f3f3f3f3f3f3fL; } } dp[0][0]=0; //从前i个数中挑选，总和%k等于j时，最大和是多少 for(int i=1;i<=n;i++){ for(int j=0;j<k;j++){ int p=(int)(j-a[i]%k+k)%k; dp[i][j]=Math.max(dp[i-1][j],dp[i-1][(int)(j-a[i]%k+k)%k]+a[i]); } } if(dp[n][0]<=0)System.out.println(-1); else System.out.print(dp[n][0]); } }
牛客.字符编码
这题更是私人，-也算进去，想半天没想出来
只要剩2个，及2个以上，就去合并，然后放到堆顶
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // M=2 // T=3 // E=2 // C=1 // H=1 // A=1 StringBuffer sb=new StringBuffer(); while(in.hasNext()){ sb.append(in.next()); String a=sb.toString(); int[]hash=new int[300]; for(int i=0;i<a.length();i++){ //这里需要注意，我直接把a.charAt(i)++ 这样不管是a还是-还是z啥的，直接全覆盖了，还省事 hash[a.charAt(i)]++; } PriorityQueue<Integer>q=new PriorityQueue<>(); int sum=0; for(int i=0;i<300;i++){ if(hash[i]!=0)q.add(hash[i]); } while(q.size()>1){ int x=q.poll(); int y=q.poll(); sum+=x+y; q.add(x+y); } System.out.print(sum); } } }
力扣1262.能被三整除的最大和（正难则反）
正着也可以做
假如 1 ， 6 ，9 ，12 ，17， 21， 39 ，40
只要能挑选一个数，我们就%3找最大值
我们直接默认全部加一起，然后找是否可以删除值，
这里面%3
存在几种情况
1、x%3==1
2、y%3==2
2025年9月5日中通快递第一题
生产者消费者模型
为什么使用notifyAll而不是notify,可以避免出现死锁，假如出现不合规，比如超出库存，那么就去给他while(){ wait(); 一下}。
也要考虑一件事情，假如我先去notify了，那么是否应该我来一个标记，比如notify()了时候，没人唤醒，
设置一个标记位，比如notify之后，不要让他死等
class Solution { public int maxSumDivThree(int[] nums) { // Arrays.sort(nums); int n=nums.length; // int[]dp=new int[n]; // dp[0]=nums[0]; // for(int i=1;i<n;i++){ // dp[i]=dp[i-1]+nums[i]; // } // //1 3 6 10 14 // //能被三整除的三个数，即 前缀和+当前值，当前值, 前面一个+当前值 // int sum=0; // //当前值 // if(dp[0]%3==0){sum=dp[0];} // for(int i=1;i<n;i++){ // if(dp[i]%3==0){ // sum=Math.max(sum,dp[i]); // continue; // } // for(int j=0;j<i;j++){ // if((dp[i]-dp[j])%3==0) sum=Math.max(sum,dp[i]-dp[j]); // } // } int sum=0; for(int i=0;i<n;i++){ sum+=nums[i]; } int x1=0x3f3f3f; int x2=0x3f3f3f; int y1=0x3f3f3f; int y2=0x3f3f3f; if(sum%3==0)return sum; else if(sum%3==1){ //删除一个余数为1的数字，或者 y1+y2 for(int i=0;i<n;i++){ if(nums[i]%3==1) { //肯定会有一个元素余数为1 x1=Math.min(x1,nums[i]); }else if(nums[i]%3==2){ if(nums[i]<y1){ y2=y1; y1=nums[i]; }else if(nums[i]<y2){ y2=nums[i]; } } } return sum=Math.max(sum-x1,Math.max(sum-y1-y2,0)); } else{ for(int i=0;i<n;i++){ if(nums[i]%3==2) { //肯定会有一个元素余数为1 y1=Math.min(y1,nums[i]); }else if(nums[i]%3==1){ if(nums[i]<x1){ x2=x1; x1=nums[i]; }else if(nums[i]<x2){ x2=nums[i]; } } } return sum=Math.max(sum-x1-x2,Math.max(sum-y1,0)); } } }
电商企业物流数字化转型必备！快递鸟 API 接口，72 小时快速完成物流系统集成。全流程实战1V1指导，营造开放的API技术生态圈。
更多推荐
11
0- 0
已为社区贡献1条内容
所有评论(0)