牛客算法小题

目录

牛客.装箱问题

牛客.数组变换 

牛客.添加字符

牛客.城市群数量

判断是否是平衡二叉树

---

牛客.装箱问题

第一眼的直觉就是动态规划，但是不知道这东西该怎么推导了

最重要的一步，我认为是动态规划:

我开始时候这么定义dp[i][j]:表示从i个物品中挑选，总体积不超过j时，剩余的最小空间

（发现推着推着不会推了)

然后题解上写的是dp[i][j]:从前i个物品中挑选，总体积不超过j，此时的最大体积是多少,然后用总体积减去最大的体积即可。

import java.util.*;
public class Main{public static void main(String[]args){Scanner in = new Scanner(System.in);int V = in.nextInt();int n = in.nextInt();int[]a=new int[n];for(int i=0;i<n;i++){a[i]=in.nextInt();}//i个物品中剩下的最小剩余空间为jint[][]dp=new int[n+1][V+1];for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){dp[i][j]=dp[i-1][j];if(j-a[i-1]>=0){dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-a[i-1]]+a[i-1]);}}}System.out.print(V-dp[n][V]);}
}

牛客.数组变换 

 

思路:贪心

[2,4,1,3,6,16,7]

 2号解法

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 []a=new int[n];int max=0;for(int i=0;i<n;i++){a[i]=in.nextInt();max=Math.max(max,a[i]);}boolean flag=true;for(int i=0;i<n;i++){if(max%a[i]!=0){flag=false;break;}else{int x=max/a[i];if((x - (x&-x))==1){flag=false;break;}}}if(flag==false){System.out.print("NO");}else{System.out.print("YES");}}
}

三号解法 

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 []a=new int[n];int max=0;for(int i=0;i<n;i++){a[i]=in.nextInt();max=Math.max(max,a[i]);}boolean flag=true;for(int i=0;i<n;i++){if(max%a[i]!=0){flag=false;break;}else{int x=max/a[i];if((x & (x-1))!=0){flag=false;break;}}}if(flag==false){System.out.print("NO");}else{System.out.print("YES");}}
}

牛客.添加字符

在这里我们选择的是暴力枚举

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[]a=in.next().toCharArray();char[]b=in.next().toCharArray();int m=a.length;int n=b.length;int ret=666;for(int i=0;i<=n-m;i++){//枚举b的起始位置int tmp=0;//每次j的移动，都要清空差异值for(int j=0;j<m;j++){if(a[j]!=b[i+j]){
//i+j是对应从i位置开始到j结束tmp++;}}ret=Math.min(ret,tmp);  （最小的差异值)}System.out.println(ret);}
}

牛客.城市群数量

刚开始的时候，看题意思，懵住了，一下子就不知道怎么处理了，后来看题解，下面的示例是这个意思。

考察:图的遍历bfs,或者dfs floodfill算法

dfs

import java.util.*;public class Solution {boolean[]vis=new boolean[210];int n;public int citys (ArrayList<ArrayList<Integer>> m) {// write code heren=m.size();int ret=0;for(int i=0;i<n;i++){if(vis[i]==false){ret++;  dfs(m,i);}}return ret;}public void dfs(ArrayList<ArrayList<Integer>>m,int pos){vis[pos]=true;for(int i=0;i<n;i++){if(m.get(pos).get(i)==1&&vis[i]==false){dfs(m,i);}}}
}

判断是否是平衡二叉树

 public boolean IsBalanced_Solution (TreeNode root) {if(root==null){return true;}else{
//这一步的意思，首先abs，判断了当前节点是否符合平衡二叉树，我们最后是返回全部的是否符合return Math.abs(height(root.left)-height(root.right))
<=1&&
//注意这里的意思是，假如你当前的节点符合，那么需要看你的左子树和右子树是否符合平衡二叉树的情况，直到最后那个节点位null为止
IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);}}public int height(TreeNode root){if(root==null){return 0;}else{
//这里就是单纯的计算高度，返回的是左子树的长度和右子树的长度最长的那个，然后在加上本层就是长度本身return Math.max(height(root.left),height(root.right))+1;}}