牛客，笔试小题

目录

牛客.游游的字符串

牛客.体育课测验(二)

牛客.KY73合唱队形

牛客.棋子翻转

---

牛客.游游的字符串

因为他的范围非常小，所以直接暴力枚举即可

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别char[]s=in.next().toCharArray();int ret=0x3f3f3f3f;for( char ch='a';ch<='z';ch++){
//依次变成aaa,到zzzint sum=0;for(int i=0;i<s.length;i++){
//我们发现他的往左走，还是往右走，他的位置都是左右相加等于26sum+=Math.min(Math.abs(s[i]-ch),26-Math.abs(s[i]-ch));}ret=Math.min(sum,ret);}System.out.print(ret);}
}

牛客.体育课测验(二)

开始我的思路是，活动安排，先排序，然后看冲突，但是我发现找冲突这个问题，很难找，根本找不到冲突

解法:拓扑排序:

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numProject int整型 * @param groups int整型ArrayList<ArrayList<>> * @return int整型ArrayList*/public ArrayList<Integer> findOrder (int n, ArrayList<ArrayList<Integer>> groups) {int[][]g=new int[groups.size()][2];
//存储边Map<Integer,List<Integer>>edge=new HashMap<>();//存储边for(int i=0;i<groups.size();i++){for(int j=0;j<2;j++){g[i][j]=groups.get(i).get(j);}}int[]in=new int[n];for(int i=0;i<groups.size();i++){int a=g[i][0];int b=g[i][1];   //b->aif(!edge.containsKey(b)){edge.put(b,new ArrayList<>());}in[a]++;edge.get(b).add(a);}
//拓扑排序Queue<Integer>q=new LinkedList<>();for(int i=0;i<n;i++){if(in[i]==0){
//检查入度为0的进入节点。q.add(i);}}ArrayList<Integer>ret=new ArrayList<>();//bfswhile(!q.isEmpty()){int t=q.poll();ret.add(t);//假如我们在这个map表里面找到了，那么就减去边for(int a:edge.getOrDefault(t,new ArrayList<>())){in[a]--;if(in[a]==0){q.add(a);}}}if(ret.size()==n){return ret;}else{return new ArrayList<>();}}
}

牛客.KY73合唱队形

解法:动态规划-最长上升子序列

f[i]:表示以i同学为结尾的最长上升子序列

下降的模式，假如给他反过来，那么她就是最长的下降子序列，不过是填表顺序不同

g[i]:以i位置同学为结尾的最长上升子序列的长度(从后往前看）

n-max(f[i]+g[i]-1)        (1<=i<=n)

如何求最长上升子序列

1.状态表示:

dp[i]表示:以i位置为结尾的所有子序列中，最长的上升子序列长度

状态转移方程:

当i改变找j的时候，不断的变大，就会到了最后就慢慢变成最大了,f[i]会找上一个状态的最佳状态

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n=in.nextInt();int[]a=new int[n+1];int[]f=new int[n+1];int[]g=new int[n+1];for(int i=1;i<=n;i++){a[i]=in.nextInt();}//以i位置为结尾，最长上升子序列的长度for(int i=1;i<=n;i++){f[i]=1;//两种可能不管前面的东西，我自己玩，或者连接的话，那么我们需要一个j的位置，在i的位置前面，连接上即可for(int j=1;j<i;j++){if(a[i]>a[j]){f[i]=Math.max(f[i],f[j]+1);}}}//以i为起点枚举到位置n，最长下降子序列//从右往左，从n位置开始遍历，往回找for(int i=n;i>=1;i--){
//每个都初始化为1g[i]=1;
//从i+1的位置开始找，但是我们是反过来遍历的，因为反过来的升序，就是降序，代码不用改动for(int j=i+1;j<=n;j++){if(a[i]>a[j]){g[i]=Math.max(g[i],g[j]+1);}}}int len=0;for(int i=1;i<=n;i++){len=Math.max(len,f[i]+g[i]-1);}System.out.print(n-len);}
}

牛客.棋子翻转

模拟+bfs，问题不是很难，重要是体会这个过程，当两次反转就会回到原位

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param A int整型二维数组 * @param f int整型二维数组 * @return int整型二维数组*/int[]dx={0,0,1,-1};int[]dy={1,-1,0,0};public int[][] flipChess (int[][] A, int[][] f) {int n=A.length;int m=A[0].length;boolean[][]k=new boolean[n][m];for(int i=0;i<f.length;i++){int a=f[i][0]-1;int b=f[i][1]-1;for(int j=0;j<4;j++){int x=a+dx[j];int y=b+dy[j];if(x>=0&&x<n&&y>=0&&y<m&&k[x][y]==false){k[x][y]=true;}else if (x>=0&&x<n&&y>=0&&y<m&&k[x][y]==true){k[x][y]=false;}}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(k[i][j]==true){if(A[i][j]==0){A[i][j]=1;}else{A[i][j]=0;}}}}return A;}
}