牛客练习小题,牛客. 矩阵最长递增路径牛客.奇数位丢弃牛客.天使果冻牛客.dd爱旋转

牛客. 矩阵最长递增路径

牛客.奇数位丢弃

牛客.天使果冻

牛客.dd爱旋转

牛客. 矩阵最长递增路径

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 递增路径的最大长度* @param matrix int整型二维数组 描述矩阵的每个数* @return int整型*/static int []dx={0,0,1,-1};static int []dy={1,-1,0,0};static int n;static int m;static int[][]dp=new int[10004][1004];public static int dfs(int[][]matrix,int p1,int p2){int len=1;if(dp[p1][p2]!=0){return dp[p1][p2];}for(int i=0;i<4;i++){int x=p1+dx[i];int y=p2+dy[i];if(x>=0&&x<n&&y>=0&&y<m&&matrix[x][y]<matrix[p1][p2]){len=Math.max(len,dfs(matrix,x,y)+1);}}dp[p1][p2]=len;return len;}public int solve (int[][] matrix) {int ret=0;n=matrix.length;m=matrix[0].length;for(int i=0;i<n;i++){for(int j=0;j<n;j++){ret=Math.max(ret,dfs(matrix,i,j));}}return ret;}
}

牛客.奇数位丢弃

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt()) { // 注意 while 处理多个 caseint n = in.nextInt();int ret=1;//找到所有2^x-1最大的时候while(ret-1<=n) ret*=2;//在最后ret是等于>n的2^x次幂，我们需要把这个幂，进行除2，然后-1，因为ret代表的是2^xSystem.out.println(ret/2-1);}}
}

牛客.天使果冻

假如说问一遍，我们就排序一遍，那么耗费时间度就是n*q

这样是会超时的，所以预处理

采用g[i]:来存这个某一个位置的次大值

那么下次问，就是O(q)了。

如何在一堆数字中，求出第二大/小的值

f[i]来表示当前位置的最大值
import java.util.*;
public class Main{public static void main(String[]args){Scanner in=new Scanner(System.in);int n=in.nextInt();int[]a=new int[n];for(int i=0;i<n;i++){a[i]=in.nextInt();}int q=in.nextInt();int []f=new int[n];int []g=new int[n];f[0]=a[0];//注意初始化，最大值，以及次大值，最大值默认第一个有数字就行//次大值只有一个数字，没有次大值，无穷小，默认为0；for(int i=1;i<n;i++){f[i]=Math.max(f[i-1],a[i]);if(a[i]>=f[i-1]){g[i]=f[i-1];}else if( a[i]<f[i-1]&&a[i]>=g[i-1]){g[i]=a[i];   }else{g[i]=g[i-1];}}while(q>0){int x=in.nextInt();System.out.println(g[x-1]);q--;}}
}

牛客.dd爱旋转

一定是模拟，但是开始的时候，我没想到怎么做

这么做，+快速读写

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();public static void main(String[]args) throws IOException{int n = in.nextInt();int[][] a = new int[n][n];Stack<Integer> s = new Stack<>();Queue<Integer> qlist = new LinkedList<>();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {a[i][j] = in.nextInt();s.add(a[i][j]);}}int q = in.nextInt();int count1 = 0;int count2 = 0;while (q != 0) {int x = in.nextInt();if (x == 1) {count1++;}//当他等于2的时候else {count2++;}q--;}if (count1 % 2 != 0) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {a[i][j] = s.pop();}}}if (count2 % 2 != 0) {for (int i = n - 1; i >= 0; i--) {for (int j = 0; j < n; j++) {qlist.add(a[i][j]);}}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {a[i][j] = qlist.poll();}}}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {out.print(a[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();}int nextInt() throws IOException{return Integer.parseInt(next());}
}

上面和下面的换

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[][]a;static int n=0;static  void setRow(){for(int i=0; i<n/2;i++){for(int j=0;j<n;j++){//行交换int tmp=a[i][j];a[i][j]=a[n-1-i][j];a[n-1-i][j]=tmp;}}}static void setCol(){//列交换for(int j=0;j<n/2;j++){for(int i=0;i<n;i++){//行不变，列变成n-1-jint tmp=a[i][j];a[i][j]=a[i][n-1-j];a[i][n-1-j]=tmp;}}}public static void main(String[]args) throws IOException{n = in.nextInt();a = new int[n][n];Stack<Integer> s = new Stack<>();Queue<Integer> qlist = new LinkedList<>();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {a[i][j] = in.nextInt();}}int q = in.nextInt();int row = 0;int col = 0;while (q != 0) {int x = in.nextInt();if (x == 1) {row++;col++;}//当他等于2的时候else {row++;}q--;}if (row % 2 != 0) {      setRow();        }if (col % 2 != 0) {      setCol(); }for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {out.print(a[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();}int nextInt() throws IOException{return Integer.parseInt(next());}
}