牛客算法小题
目录
牛客.求和编辑
牛客.abb
牛客.合并k个有序链表
牛客.滑雪（暴力->递归->记忆化搜索）
牛客.旋转字符串
牛客.求和
我没想到是dfs，另外我的dfs能力确实也不强，另外难度大的是他的那个输出
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {static int m;static int n;//用来标记路径中选择了谁static boolean[]choose=new boolean[11];//标记总和static int sum=0;public static void dfs(int x){if(sum==m){for(int i=1;i<=n;i++){if(choose[i]){System.out.print(i+ " ");}}System.out.println("");return;}if(sum>m||x>n) return;//选择x或者不选择xsum+=x;
//标记已经选择choose[x]=true;dfs(x+1);choose[x]=false;sum-=x;//假如不选择x，对任何东西都没有影响dfs(x+1);}public static void main(String[] args) {Scanner in = new Scanner(System.in);n=in.nextInt();m=in.nextInt();//从1开始dfs(1);}
}
所以解法：采用如果两个相同，视为一个位置
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param str string字符串 * @return string字符串ArrayList*/boolean[]vis;char[]s;ArrayList<String>m=new ArrayList<>();int n=0;StringBuffer p=new StringBuffer();public void dfs(int pos){if(pos==n){m.add(p.toString());return ;}for(int i=0;i<n;i++){if(vis[i]==true){continue;}if(i>0&&s[i]==s[i-1]&&vis[i-1]==true){continue;}p.append(s[i]);vis[i]=true;dfs(pos+1);vis[i]=false;p.deleteCharAt(p.length()-1);}}public ArrayList<String> Permutation (String str) {n=str.length();vis=new boolean[n];s=str.toCharArray(); Arrays.sort(s);dfs(0); return m;} }
牛客.abb
解法:动态规划+哈希表（子序列问题)
1.状态表示:
dp[i]:以i位置为结尾的子序列中，有多少个_xx
2.返回值:
整张dp表的和
3.状态转移方程:
dp[i]=f[x]:应该是更新前的f[x],因为我们要统计多少个_xx应该是前面有多少个_x
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();String aa=in.next();char[]a=aa.toCharArray();int []f=new int[26];int []g=new int[26];long ret=0;for(int i=0;i<n;i++){ret+=f[a[i]-'a'];f[a[i]-'a']=f[a[i]-'a']+i-g[a[i]-'a'];g[a[i]-'a']=g[a[i]-'a']+1;}System.out.print(ret);} }
牛客.合并k个有序链表
import java.util.*;/*
// * public class ListNode {
// * int val;
// * ListNode next = null;
// * public ListNode(int val) {
// * this.val = val;
// * }
// * }
// */public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param lists ListNode类ArrayList * @return ListNode类*/public ListNode mergeKLists (ArrayList<ListNode> lists) {int n=lists.size();if(n==0||(n==1&&lists.get(0)==null)||(n==2&&lists.get(0)==null&&lists.get(1)==null)){return new ListNode(0).next;}PriorityQueue <Integer> q=new PriorityQueue<>();for(int i=0;i<lists.size();i++){ ListNode a=lists.get(i);while(a!=null){q.add(a.val);a=a.next;}} ListNode p=new ListNode(q.poll());ListNode head=p;while(!q.isEmpty()){p.next=new ListNode(q.poll());p=p.next;}return head;}
}牛客.滑雪（暴力->递归->记忆化搜索）
单纯的dfs，没有记忆化
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {static int n = 0;static int m = 0;static int [][]arr=new int[101][101];static int[]dx={0,0,1,-1};static int[]dy={1,-1,0,0};public static int dfs(int p1,int p2){int len=1;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&&arr[x][y]<arr[p1][p2]){//四种情况下点最大值len=Math.max(len,dfs(x,y)+1);}}return len;}public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();m = in.nextInt();arr=new int[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++){arr[i][j]=in.nextInt();}}int ret=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){ret=Math.max(ret,dfs(i,j));}}System.out.print(ret);}
}import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {static int n = 0;static int m = 0;static int [][]arr=new int[101][101];static int[]dx={0,0,1,-1};static int[]dy={1,-1,0,0};
//使用dp表来保存 从区域出发最长递减子序列static int[][]dp=new int[101][101]; public static int dfs(int p1,int p2){if(dp[p1][p2]!=0){
//因为最短的长度是1，所以无需初始化。dp[p1][p2]有值return dp[p1][p2];}int len=1;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&&arr[x][y]<arr[p1][p2]){//四种情况下点最大值len=Math.max(len,dfs(x,y)+1);}}//这里dfs走过之后，再dp[p1][p2]存储当前位置的最长递减子序列dp[p1][p2]=len;return len;}public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();m = in.nextInt();arr=new int[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++){arr[i][j]=in.nextInt();}}int ret=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){ret=Math.max(ret,dfs(i,j));}}System.out.print(ret);}
}牛客.旋转字符串
解法:规律+接口
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 旋转字符串* @param A string字符串* @param B string字符串* @return bool布尔型*/public boolean solve (String A, String B) {if (A.length() != B.length()) {return false;} else if (A.equals(B)) {return true;}return (A + A).contains(B);} }