牛客网题霸原创系列算法题(2.5w字吐血整理)
简单难度面试题
1. 车站建造问题
有10^8个村庄排在一条公路上，依次编号为010^8-1，相邻村庄距离为1，其中有n个村庄居住着牛牛，居住着牛牛的村庄从小到大依次为a0an-1，其中保证a0=0.
现在需要建设车站，有两个要求必须被满足：
1、每个有牛牛居住的村庄必须修建车站。
2、相邻车站的距离必须为1或为某个质数。
现给出n和a数组，求需要建设车站的最小数量。
没过40%
public int work (int n, int[] a) {
// write code here
int len=a.length;
int last=a[len-1];
//生成一个存放检测质数的数组 0代表质数 1不是
int[] num=new int[last+1];
for(int i=2;i<=last;i++){
if(num[i]==0){
for(int j=i+i;j<=last;j+=i){
num[j]=1;
}
}
}
for(int i=1;i<len;i++){
int j=a[i]-a[i-1];
while(j!=1&&num[j]==1){
//寻找最近的质数减去，直到符合条件
for(int k=j;k>0;k--){
if(num[k]==0){
j-=k;
n++;
break;
}
}
}
}
return n;
}AC:
1、当该非质数为偶数时，可以表示为两个质数的和（根据哥德巴赫猜想）；
2、当该非质数为奇数时，分解为p=(p-2)+2：
若p-2为质数，则可表示为两个质数的和
若p-2为非质数，则可表示为三个质数的和（为什么，就是这么神奇！！！）
public int work (int n, int[] a) {
// write code here
int len=a.length;
for(int i=1;i<len;i++){
int j=a[i]-a[i-1];
if(j!=1&&!isOk(j)) {
if (j % 2 == 0) {
n += 1;
} else {
if (isOk(j - 2)) {
n += 1;
} else {
n += 2;
}
}
}
}
return n;
}
boolean isOk(int num){
if(num==1||num==2) return true;
for(int i=2;i*i<=num;i++){
if(num%i==0) return false;
}
return true;
}2.回路
题意
牛牛在一个迷宫中，迷宫有 nn 个格子，有 mm 条通道，每条通道连接两个格子 uu, vv，编号为 uu 的格子与编号为 vv 的格子可互相到达，每人每条通道只能走一次。
牛牛想知道，他是否能从 11 号格子出发回到 11 号格子。
输入
第一行给定两个整数 nn , mm 。
接下来 mm 行，每行有两个整数 uu，vv 。
1 \leq n \leq 100,000 \quad 0 \leq m \leq 100,000\quad 0 \leq L \leq m1≤n≤100,0000≤m≤100,0000≤L≤m
m**对 u, v 互不相同
输出
若能回到 11 号格子则返回Yes，否则返回No。
DFS
public String solve (int[] param, Point[] edge) {
// write code here
int n=param[0],m=param[1];
boolean[] visitn=new boolean[n+1];
if(backToOne(edge,1,visitn,n,m)){
return "Yes";
}else{
return "No";
}
}
public boolean backToOne(Point[] edge,int i,boolean[] visitn,int n,int m){
for(int j=0;j<m;j++){
Point p=edge[j];
if(p.x==i){
if(p.y==1) return true;
if(visitn[p.y]) continue;
visitn[p.x]=true;
boolean res = backToOne(edge,p.y,visitn,n,m);
if(res){
return true;
}
visitn[p.x]=false;
}
}
return false;
}
并查集
public String solve (int[] param, Point[] edge) {
// write code here
int n=param[0],m=param[1];
UnionFindSet unionFindSet=new UnionFindSet(n);
HashSet<Integer> set=new HashSet<>();
Integer[] arr=new Integer[n];
for(int i=0;i<arr.length;i++){
arr[i]=i+1;
}
unionFindSet.makeSets(arr);
for(int i=0;i<m;i++){
Point p=edge[i];
if(p.x!=1&&p.y!=1&&!unionFindSet.isSameSet(p.x,p.y)){
unionFindSet.union(p.x,p.y);
}
}
for(int i=0;i<m;i++){
Point p=edge[i];
if(p.x==1||p.y==1){
Integer head = unionFindSet.findHead(p.x==1 ? p.y:p.x);
if(set.contains(head)) return "Yes";
set.add(head);
}
}
return "No";
}
public static class UnionFindSet {
public HashMap<Integer, Integer> fatherMap;
public HashMap<Integer, Integer> sizeMap;
public UnionFindSet(int n) {
fatherMap = new HashMap<Integer, Integer>(n);
sizeMap = new HashMap<Integer, Integer>(n);
}
public void makeSets(Integer[] nodes) {
fatherMap.clear();
sizeMap.clear();
for (Integer node : nodes) {
fatherMap.put(node, node);
sizeMap.put(node, 1);
}
}
private Integer findHead(Integer node) {
Integer father = fatherMap.get(node);
if (father != node) {
father = findHead(father);
}
fatherMap.put(node, father);
return father;
}
public boolean isSameSet(Integer a, Integer b) {
return findHead(a) == findHead(b);
}
public void union(Integer a, Integer b) {
if (a == null || b == null) {
return;
}
Integer aHead = findHead(a);
Integer bHead = findHead(b);
if (aHead != bHead) {
int aSetSize= sizeMap.get(aHead);
int bSetSize = sizeMap.get(bHead);
if (aSetSize <= bSetSize) {
fatherMap.put(aHead, bHead);
sizeMap.put(bHead, aSetSize + bSetSize);
} else {
fatherMap.put(bHead, aHead);
sizeMap.put(aHead, aSetSize + bSetSize);
}
}
}
}
3. 枪打出头鸟
现在有n个人站成一列，第i个人的身高为a_{i-1}a*i*−1。
他们人手一把玩具枪，并且他们喜欢把枪举在头顶上。
每一次练习射击，他们都会朝正前方发射一发水弹。
这个时候，第i个人射击的水弹，就会击中在他前面第一个比他高的人。
牛牛认为这样的练习十分的荒唐，完全就是对长得高的人的伤害。
于是它定义了一个荒唐度，初始为0。
对于第i个人，如中他击中了第j个人，则荒唐度加j，如果没有击中任何人，则荒唐度加0.
牛牛想问你，你能计算出荒唐度是多少吗？
输入
一个整数n(1 \leq\ n \leq\ 10^{7}1≤ n≤ 107)
一个数组a(1 \leq\ a_i \leq\ 10^{7}1≤ a*i≤ 107)
a下标从0开始，a_{i-1} 代表第i个人身高a*i−1代表第i个人身高
输出
一个整数X(代表荒唐度的大小)
单调栈 递减 AC
public long solve (int n, int[] a) {
// write code here
if(n<=0||a==null||a.length==0||n!=a.length) return 0;
Stack<Integer> stack=new Stack<>();
long res=0;
for(int i=0;i<n;i++){
//直到栈顶元素大于压栈元素
while(!stack.isEmpty()&&a[stack.peek()]<=a[i]){
stack.pop();
//计算荒唐度
if(!stack.isEmpty())
res+=stack.peek()+1;
}
//压栈元素入栈
stack.push(i);
}
//计算栈中剩余的
while(!stack.isEmpty()){
stack.pop();
if(!stack.isEmpty())
res+=stack.peek()+1;
}
return res;
}4. 牛牛的超市
牛牛最近在家闲的无聊，所以决定在家开一个小超市，为了方便卖东西，牛牛发明了一种用来兑换东西的新型货币，牛牛给这种新型货币起了个名字叫牛币，现在牛牛有n(n<=50)种不同的币值，其中币值为 value(value<=50) 的有 w(w<=20) 个，现在牛妹来到牛牛的超市买东西，牛妹有 x(x<=100) 元牛币，但是牛妹想将 x 元牛币换成若干零钱，请问有多少种换钱的方案？
暴力超时 90%
public int solve (int n, int x, int[][] a) {
// write code here
if(a==null||a.length==0||x<0) return 0;
return solve(n,x,a,0);
}
int solve (int n, int x, int[][] a,int i){
if(x==0) return 1;
if(i==n) return 0;
int value=a[i][0];
int w=a[i][1];
int res=0;
for(int j=0;j<=w&&x-value*j>=0;j++){
res+=solve(n,x-value*j,a,i+1);
}
return res;
}DP AC
public int solve (int n, int x, int[][] a) {
// write code here
if(a==null||a.length==0||x<0) return 0;
int[][] dp=new int[n][x+1];
for(int i=0;i<n;i++){
dp[i][0]=1;
}
for(int j=1,v=a[n-1][0],w=a[n-1][1];j*v<=x&&w>0;j++,w--){
dp[n-1][j*v]=1;
}
for(int i=n-2;i>=0;i--){
int v=a[i][0],w=a[i][1];
for(int j=1;j<=x;j++){
for(int k=j,y=0;k>=0&&y<=w;k-=v,y++) {
dp[i][j] += dp[i + 1][k];
}
}
}
return dp[0][x];
}5.牛牛算数
题意：
牛牛现在在学习计算机，他想通过计算机计算n个数的和。
但是计算机计算数字的和是有花费的，比如计算x，y两个数的和，需要花费(cx+cy)(c∗x+c∗y)秒。
计算机一次只能计算一次，牛牛想知道自己怎么合理安排计算的顺序，可以使得花费的时间最短。
输入：
给定n,c。
给定a数组，ai表示第i个数的大小。
(1 \leq n\leq 210^{5}1≤n≤2∗105 , 1 \leq c\leq 1001≤c≤100 )
(1 \leq a_{i} \leq 10^{2}1≤ai*≤102)
输出：
一个数字表示输出计算n个数字和的最小花费的时间。
堆 AC
public long solve (int n, int c, int[] a) {
// write code here
if(n==0||a==null||a.length==0) return 0;
PriorityQueue<Integer> queue=new PriorityQueue<Integer>(n);
for(int i:a){
queue.offer(i);
}
long sum=0;
while (queue.size()>1){
Integer e=queue.poll()+queue.poll();
sum+=e;
queue.offer(e);
}
return c*sum;
}6.分组
牛牛有一个n个数字的序列a_1,a_2,\dots,a_na1,a2,…,an，现在牛牛想把这个序列分成k段连续段，牛牛想知道分出来的k个连续段的段内数字和的最小值最大可以是多少？er
首先明白我们要找的这个值一定是处于[0,sum(a)]这个区间的一个值,但具体是多少不知道.
那么我们首先可以判断mid1 = sum(a)/2这个值能不能划分出大于等于k个组,
如果可以那么我们其实可以缩小区间至[mid1,sum(a)],再次判断mid2 = (sum(a)+mid1)/2 能否得到k个组.如果不可以,那自然的,只能将区间改写为[mid1,mid2],
依次循环直到某一时刻.我们找到一个能将整个组划分为k个且对应区间的左右两端差值极小.(理论上小于1就可以.)
那么这个时候,自然的我们就找到了对应可以划分出来的数字和的最大最小值.(均分情况下明显最小值会大于别的情况嘛~)
二分 AC
public int solve (int n, int k, int[] a) {
// write code here
int l=0,r=0,t=0,m,cnt=0;
for(int i=0;i<n;i++){
r+=a[i];
}
if(k==1) return r;
while(l+1<r){
m=(l+r)>>1;
cnt=0;
t=0;
for(int i=0;i<n;i++){
t+=a[i];
if(t>=m){
cnt++;
t=0;
}
}
if(cnt>=k){
l=m;
}else{
r=m;
}
}
return (l+r)>>1;
}7. 单词消消乐
题意：
"一清二白，白头偕老，老当益壮....."，牛牛和牛妹在玩成语接龙，但是牛妹因为语文不好总是输，于是她想出了一个新的游戏去和牛牛玩，牛妹会给牛牛n个单词，牛妹要求牛牛将这n个单词按照以下方式合并：
1.从左往右合并单词，将合并后的单词作为第一个单词再与后面单词合并
例如有三个单词"a"，"b"，"c"，先将"ab"合并，最后将合并后的"ab"与"c"合并得到"abc"。
2.如果最左边单词结尾字母与其后面一个的单词的开始字母相同，则最左边单词的结尾字母与之后一个单词的开始字母都会抵消掉而消失，重复上述操作直到某一个单词为空或者最左端的结尾字母与之后单词的开始字母不同，然后合并这两个单词作为一个单词放置再最左边。
例如 "aab" "bac"合并之后会得到"ac"
输入：
以vector< string > WordsWords的形式给定n个单词
1\leq\sum_{i=0}^{n-1}Words[i].size\leq 10^61≤∑i=0n−1Words[i].size≤106
输出：
返回最终合并后的单词。
若为空则返回一个空串。
栈 AC
public String WordsMerge (String[] Words) {
// write code here
if(Words==null) return "";
Stack<Character> stack=new Stack<>();
for(String s:Words){
int i=0;
for(i=0;i<s.length();i++){
if(!stack.isEmpty()&&stack.peek()==s.charAt(i)){
stack.pop();
}else{
break;
}
}
for(;i<s.length();i++){
stack.push(s.charAt(i));
}
}
StringBuilder sb=new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pop());
}
return sb.reverse().toString();
}8. 打字
题意：
牛妹在练习打字，现在按照时间顺序给出牛妹按下的键（以字符串形式给出,'<'代表回退backspace，其余字符均是牛妹打的字符，字符只包含小写字母与'<'），牛妹想知道最后在屏幕上显示的文本内容是什么。
在文本内容为空的时候也可以按回退backspace（在这种情况下没有任何效果）。
输入：
给定一个字符串s，代表牛妹所按下的按键。
1<s.length\leq10^51<s.length≤105
输出：
返回一个字符串代表最后在屏幕上显示的文本内容。
若为空则返回一个空串。
队列 AC
public String Typing (String s) {
// write code here
if(s==null) return "";
LinkedList<Character> queue=new LinkedList<>();
for(int i=0;i<s.length();i++){
if(s.charAt(i)!='<'){
queue.addLast(s.charAt(i));
}else if(!queue.isEmpty()){
queue.removeLast();
}
}
StringBuilder sb=new StringBuilder();
while(!queue.isEmpty()){
sb.append(queue.removeFirst());
}
return sb.toString();
}9．好多牛牛
给出一个字符串S，牛牛想知道这个字符串有多少个子序列等于"niuniu"
子序列可以通过在原串上删除任意个字符(包括0个字符和全部字符)得到。
为了防止答案过大，答案对1e9+7取模
AC
//暴力
int solve (String s,String t,int i,int j) {
if(i==s.length()&&j!=t.length()) return 0;
if(j==t.length()) return 1;
if(s.charAt(i)==t.charAt(j)){
return solve(s,t,i+1,j+1)+solve(s,t,i+1,j);
}else{
return solve(s,t,i+1,j);
}
}
//dp
int solve1(String s){
String t="niuniu";
int[][] dp=new int[s.length()+1][t.length()+1];
int m=(int)(1e9+7);
for(int i=0;i<dp.length;i++){
dp[i][t.length()]=1;
}
for(int i=dp.length-2;i>=0;i--){
for(int j=dp[i].length-2;j>=0;j--){
if(s.charAt(i)==t.charAt(j)){
dp[i][j]=dp[i+1][j+1]+dp[i+1][j];
dp[i][j]%=m;
}else{
dp[i][j]=dp[i+1][j];
dp[i][j]%=m;
}
}
}
return dp[0][0];
}
//dp压缩空间
int solve2(String s){
String t="niuniu";
int m=(int)(1e9+7);
int[] dp=new int[t.length()+1];
dp[t.length()]=1;
for(int i=s.length()-1;i>=0;i--){
for(int j=0;j<t.length();j++){
if(s.charAt(i)==t.charAt(j)){
dp[j]=dp[j]+dp[j+1];
dp[j]%=m;
}else{
dp[j]=dp[j];
dp[j]%=m;
}
}
}
return dp[0];
}10.简单变向
牛牛准备在一个3行n列的跑道上跑步。一开始牛牛位于(1,1)。
当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：
\1. 跑到第i行第j+1列
\2. 跑到第i-1行第j+1列（如果i=1则不可以这么跑）。
\3. 跑到第i+1行第j+1列（如果i=3则不可以这么跑）。
跑道上有一些格子设置了路障(一个格子可能有多个路障)，牛牛不能跑到路障上。现在牛牛想知道，从(1,1)到(3,n)有多少条不同的路径？
为了防止答案过大，答案对1e9+7取模。
//**暴力
public int solve (int n, int m, int[] x, int[] y) {
// write code here
int[][] arr=new int[4][n+1];
for(int i=0;i<m;i++){
arr[x[i]][y[i]]=1;
}
return solve(arr,1,1,3,n);
}
int solve(int[][] arr,int row,int col,int rows,int cols){
if(row==0||col==0||row>rows||col>cols||arr[row][col]==1){
return 0;
}
if(row==3&&col==cols){
return 1;
}
return solve(arr,row,col+1,rows,cols)+
solve(arr,row-1,col+1,rows,cols)+
solve(arr,row+1,col+1,rows,cols);
}
//dp
int solve1(int n, int m, int[] x, int[] y){
int[][] arr=new int[4][n+1];
for(int i=0;i<m;i++){
arr[x[i]][y[i]]=1;
}
int[][] dp=new int[4][n+1];
int e=(int)(1e9+7);
dp[3][n]=1;
for(int j=n-1;j>=1;j--){
for(int i=3;i>=1;i--){
if(arr[i][j]==1){
continue;
}
dp[i][j]=dp[i][j+1]+dp[i-1][j+1];
dp[i][j]%=e;
if(i!=3){
dp[i][j]+=dp[i+1][j+1];
dp[i][j]%=e;
}
}
}
return dp[1][1];
}11. 魔法货车
牛妹是鸡蛋商人。由于疫情严重，于是牛妹准备向疫情地区捐赠n个鸡蛋。牛妹请了m辆货车来运送这些鸡蛋，其中第i辆货车能运输x[i]个鸡蛋。因为预料到货车可能装不下所有的鸡蛋，于是牛妹请来了哈利波特·牛，哈利波特·牛使用一次魔法可以来让一辆货车的容量翻倍，牛妹想知道最少需要哈利波特·牛出手几次？
输入：
给定n,mn,m，xx数组
(1 \leq m=x.size \leq 210^{5}1≤*m=x.size≤2∗105)
(1 \leq n,x[i] \leq 10^91≤n,x[i]≤109)
输出：
返回需要哈利波特·牛最少出手次数
public int Holy (int n, int m, int[] x) {
// write code here
Arrays.sort(x);
long sum=0;
for(int i=0;i<m;i++){
sum+=x[i];
}
int count=0;
while (sum<n){
count++;
sum+=x[m-1];
if((x[m-1]<<1)<0){
m--;
}else{
x[m-1]<<=1;
}
}
return sum>=n ? count:-1;
}12.变向
牛牛准备在一个3行n列的跑道上跑步。一开始牛牛可以自己选择位于(1,1)还是(2,1)还是(3,1)。
跑道的每一格都有一些金币，当牛牛跑到一个格子，他会获得这个格子的所有金币。
当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：
\1. 不花费金币跑到第i行第j+1列
\2. 花费m_jmj的金币跑到第i-1行第j+1列（如果i=1则不可以这么跑）。
\3. 花费m_jmj的金币跑到第i+1行第j+1列（如果i=3则不可以这么跑）。
（牛牛是一个富豪，本身带了很多的金币，所以你不用担心他钱不够用）
现在告诉你所有格子的金币数量和每一列的金币花费，牛牛想知道他跑到第n列最多可以赚得多少金币（赚得金币=获得金币-消耗金币）
//暴力
public int solve (int n, int[] a1, int[] a2, int[] a3, int[] m) {
// write code here
int[][] arr=new int[4][n+1];
for(int j=1;j<=n;j++){
arr[1][j]=a1[j-1];
}
for(int j=1;j<=n;j++){
arr[2][j]=a2[j-1];
}
for(int j=1;j<=n;j++){
arr[3][j]=a3[j-1];
}
return Math.max(solve(arr,1,1,1,n,m),
Math.max(solve(arr,2,1,1,n,m),solve(arr,3,1,1,n,m)));
}
int solve(int[][] arr,int row,int col,int rows,int cols,int[] m){
if(row==0||row==4){
return 0;
}
if(col==cols){
return arr[row][col];
}
int t1=solve(arr,row-1,col+1,rows,cols,m)-m[col-1];
int t2=solve(arr,row,col+1,rows,cols,m);
int t3=solve(arr,row+1,col+1,rows,cols,m)-m[col-1];
return Math.max(t1,Math.max(t2,t3))+arr[row][col];
}
//dp
public int solve1 (int n, int[] a1, int[] a2, int[] a3, int[] m) {
int[][] dp=new int[4][n+1];
int[][] arr=new int[4][n+1];
for(int j=1;j<=n;j++){
arr[1][j]=a1[j-1];
}
for(int j=1;j<=n;j++){
arr[2][j]=a2[j-1];
}
for(int j=1;j<=n;j++){
arr[3][j]=a3[j-1];
}
for(int i=1;i<=3;i++){
dp[i][n]=arr[i][n];
}
for(int j=n-1;j>=1;j--){
for(int i=1;i<=3;i++){
int t1=dp[i][j+1];
int t2=i==1? Integer.MIN_VALUE:dp[i-1][j+1]-m[j-1];
int t3=i==3? Integer.MIN_VALUE:dp[i+1][j+1]-m[j-1];
dp[i][j] = Math.max(t1,Math.max(t2,t3))+arr[i][j];
}
}
return Math.max(dp[1][1],Math.max(dp[2][1],dp[3][1]));
}13.火柴拼图
题意：
牛妹有n根火柴，她想用这些火柴去拼正三角形或者正四边形。牛妹想让最后拼出的总面积尽可能大的，请你帮帮她。
输入：
给定n，Stick数组
Stick[i]表示第i根火柴的长度，一共有n根火柴 1 \leq Stick[i] \leq 10^51≤Stick[i]≤105
1 \leq n \leq 10^51≤n≤105
输出：
返回一个Vector，Vector中存有两个数字。
其中最大面积S=Vector[0]\sqrt3/4+Vector[1]*S=Vector[0]∗3/4+Vector[1]。
思路：计数排序 数量/4计算正方形个数 数量%4/3计算三角形个数 注意返回值long计算时转为long
AC
public long[] MaxArea (int n, int[] Stick) {
// write code here
int[] arr=new int[100001];
int max=Integer.MIN_VALUE;
for(int s:Stick){
arr[s]++;
max=Math.max(s,max);
}
long[] res=new long[2];
for(int i=1;i<=max;i++){
if(arr[i]!=0){
int t1=arr[i]/4;
int t2=arr[i]%4/3;
res[0]+=(long)i*i*t2;
res[1]+=(long)i*i*t1;
}
}
return res;
}14.扩散
牛牛作为牛客王国的探险先锋，来到了一片新的大陆。
这是一个工业化程度很高的大陆，遍地都是工厂，有些工厂之间有管道相连。
这片大陆一共有n个工厂，有n-1对工厂之间有管道相连，因为工厂之间需要合作，所以这n-1个管道保证任意两个工厂都可以通过管道互相抵达。
牛牛发现，从这片大陆开始工业化以来，一共发生了m次原始生产力提升。每一次原始生产力提升在一个工厂u发生，它会让工厂u以及和工厂u直接通过管道相连的工厂的生产力加1。
每个工厂最开始的生产力都是0。
现在牛牛知道了m次生产力提升发生的工厂位置。牛牛想知道这m次提升发生之后每个工厂的生产力是多少。
90% 可以优化空间
public int[] solve (int n, int m, int[] u, int[] v, int[] q) {
// write code here
HashMap<Integer,HashSet<Integer>> map=new HashMap<>();
int[] res=new int[n];
for(int i=0;i<n-1;i++){
HashSet<Integer> set=null;
if(map.containsKey(u[i])){
set=map.get(u[i]);
}else{
set=new HashSet<>();
}
set.add(v[i]);
map.put(u[i],set);
if(map.containsKey(v[i])){
set=map.get(v[i]);
}else{
set=new HashSet<>();
}
set.add(u[i]);
map.put(v[i],set);
}
for(int i=0;i<m;i++){
if(map.containsKey(q[i])){
HashSet<Integer> set=map.get(q[i]);
for(Integer j:set){
res[j-1]++;
}
res[q[i]-1]++;
}
}
return res;
}
90%
int[] res=new int[n];
int[] help=new int[n];
for(int i=0;i<m;i++){
help[q[i]-1]++;
res[q[i]-1]++;
}
for(int i=0;i<n-1;i++){
res[v[i]-1]+=help[u[i]-1];
res[u[i]-1]+=help[v[i]-1];
}
return res;15. 魔力转圈圈
牛牛很喜欢玩二叉树。这天牛能送给了他一个以1为根结点的{n}n个结点的二叉树，他想对这个二叉树进行一些加工。
牛牛刚刚学会转圈圈，所以很喜欢旋转。现在他想对这颗二叉树进行m次旋转。
每次旋转牛牛会指定一个结点，并让以这个结点为根的子树中的所有结点的左右儿子互换。
多次操作之后，牛牛希望以中序遍历的方式输出操作完之后的二叉树。
90%
public int[] solve (int n, int m, int[] l, int[] r, int[] k) {
// write code here
for(int i=0;i<m;i++){
solve(k[i]-1,l,r);
}
int[] res=new int[n];
InOrder(l,r,0,res,0);
return res;
}
void solve(int i,int[] l,int[] r){
if(i<0||(l[i]==0&&r[i]==0)){
return;
}
int t=l[i];
l[i]=r[i];
r[i]=t;
solve(l[i]-1,l,r);
solve(r[i]-1,l,r);
}
int InOrder(int[] l,int[] r,int i,int[] res,int n){
if(i<0){
return n;
}
n = InOrder(l,r,l[i]-1,res,n);
res[n++]=i+1;
n= InOrder(l,r,r[i]-1,res,n);
return n;
}16. 最大数
给定一个包含大写英文字母和数字的句子，找出这个句子所包含的最大的十六进制整数，返回这个整数的值。数据保证该整数在int表示范围内
AC
public int solve (String s) {
// write code here
int max=Integer.MIN_VALUE;
for(int i=0;i<s.length();i++){
int j=i+1,sum=0;
while (j<=s.length()){
sum=getInt(s.substring(i,j));
if(sum==-1||sum==-2) {
break;
}
max = Integer.max(sum, max);
j++;
}
}
return max;
}
String num="0123456789ABCDEF";
public int getInt(String s){
long sum=0;
int t=1,v;
for(int i=s.length()-1;i>=0;i--,t<<=4){
v=num.indexOf(s.charAt(i));
if(v==-1) return -2;
sum+=v*t;
if(sum>Integer.MAX_VALUE){
return -1;
}
}
return (int) sum;
}
17. 远亲不如近邻
牛牛最近搬到了一座新的城镇，这个城镇可以看成是一个一维的坐标系。城镇上有n个居民，第i个居民的位置为a_iai。现在牛牛有m个搬家方案，在第i个方案中他会搬到位置x_ixi。
俗话说的好，远亲不如近邻。现在牛牛想知道，对于每个搬家方案，搬家后与最近的居民的距离为多少。
二分 AC
思路:分三种情况讨论
1. 搬家位置大于居民位置最大值
2. 搬家位置小于居民位置最小值
3. 搬家位置在居民位置中间
public int[] solve (int n, int m, int[] a, int[] x) {
// write code here
Arrays.sort(a);
int low,high,mid,k=0,min=a[0],max=a[n-1];
int[] res=new int[m];
for(int i=0;i<m;i++){
//j等于搬家位置
int j=x[i];
low=0;
high=n-1;
//当j大于最大的居民位置
if(j>max) {
res[k++]=j-max;
//当j小于最小的居民位置
}else if(j<min){
res[k++]=min-j;
}else{
//二分找到最近的居民
while (high - low > 1) {
mid = low + ((high - low) >> 1);
if (a[mid] < j) {
low = mid;
} else if (a[mid] > j) {
high = mid;
} else {
//如果等于j,说明最近距离等于0
low = mid;
break;
}
}
//计算相邻居民的最短距离
res[k++]= Math.min(j-a[low],a[high]-j);
}
}
return res;
}
18. 神奇的数字
在这个特殊的假期里，由于牛牛在家特别无聊，于是他发明了一个小游戏，游戏规则为：将字符串数字中为偶数位的数字进行翻转，将翻转后的结果进行输出。
AC 双指针
public String change (String number) {
// write code here
int low=0,high=number.length()-1;
char[] c=number.toCharArray();
while (low<high){
while (low<high&&(c[low]-'0')%2==1){
low++;
}
while (low<high&&(c[high]-'0')%2==1){
high--;
}
char temp=c[low];
c[low]=c[high];
c[high]=temp;
low++;high--;
}
return new String(c,0,c.length);
}19. 递增数组
牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？
输入：
给定arrayarray数组
1 \leq array.size \leq 210^{5}1≤*array.size≤2∗105
1 \leq array[i] \leq 110^{9}1≤*array[i]≤1∗109
输出：
返回最小次数
AC 贪心 121321 –> 002022 增量数组
public long IncreasingArray (int[] array) {
// write code here
long num=0;
for(int i=1;i<array.length;i++){
if(array[i]<array[i-1]){
num+=array[i-1]-array[i]+1;
}
}
return num;
}20. 牛妹的礼物
众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。
地板是N\times MN×M的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。
地板的坐标是左上角(1,1) 右下角（N, M）。
牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步
每次走过一个格子，拿起（并且必须拿上）这个格子上的礼物。
牛妹想知道，她能走到最后拿起的所有礼物体积最小和是多少？
AC
// 暴力
public int selectPresent (int[][] presentVolumn) {
// write code here
return selectPresent(presentVolumn,0,0,presentVolumn.length-1,presentVolumn[0].length-1);
}
int selectPresent (int[][] presentVolumn,int row,int col,int rows,int cols) {
if(row>rows||col>cols){
return Integer.MAX_VALUE;
}
if(row==rows&&col==cols){
return presentVolumn[row][col];
}
int right=selectPresent(presentVolumn, row, col+1, rows, cols);
int bottom=selectPresent(presentVolumn, row+1, col, rows, cols);
int bottomright=selectPresent(presentVolumn, row+1, col+1, rows, cols);
return Math.min(right,Math.min(bottom,bottomright))+presentVolumn[row][col];
}
// dp
public int selectPresent1 (int[][] presentVolumn) {
// write code here
if(presentVolumn==null||presentVolumn.length==0) return 0;
int rows=presentVolumn.length-1,cols=presentVolumn[0].length-1;
int[][] dp=new int[rows+1][cols+1];
dp[rows][cols]=presentVolumn[rows][cols];
for(int i=cols-1;i>=0;i--){
dp[rows][i]=dp[rows][i+1]+presentVolumn[rows][i];
}
for(int i=rows-1;i>=0;i--){
dp[i][cols]=dp[i+1][cols]+presentVolumn[i][cols];
}
for(int i=rows-1;i>=0;i--){
for(int j=cols-1;j>=0;j--){
dp[i][j]=Math.min(dp[i][j+1],Math.min(dp[i+1][j],dp[i+1][j+1]))+presentVolumn[i][j];
}
}
return dp[0][0];
}
// dp空间压缩
public int selectPresent2 (int[][] presentVolumn) {
// write code here
if(presentVolumn==null||presentVolumn.length==0) return 0;
int rows=presentVolumn.length-1,cols=presentVolumn[0].length-1;
int[] dp=new int[cols+1];
dp[cols]=presentVolumn[rows][cols];
for(int i=cols-1;i>=0;i--){
dp[i]=dp[i+1]+presentVolumn[rows][i];
}
for(int i=rows-1;i>=0;i--){
int pre=0,t=0;
for(int j=cols;j>=0;j--){
pre=dp[j];
if(j==cols){
dp[j]+=presentVolumn[i][j];
}else{
dp[j]=Math.min(dp[j+1],Math.min(dp[j],t))+presentVolumn[i][j];
}
t=pre;
}
}
return dp[0];
}21. 牛妹的蛋糕
众所周知，牛妹非常喜欢吃蛋糕。
第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。
牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？
AC
double num=1;
for(int i=n-1;i>0;i--){
num= Math.ceil(num*1.5)+1.0;
}
return (int) num;22. 下象棋
题意：
牛妹在和牛牛下牛客象棋。现在轮到牛妹了，牛妹想知道她在这一回合能否战胜牛牛。
棋盘chessboard上只可能包含：炮，将，车，兵
牛客象棋的规则解释：
炮：炮在不吃子的时候，走动与车完全相同，但炮在吃棋子时，必须跳过一个棋子，我方的和敌方的都可以
兵：可以上下左右移动，每次只能移动一格
车：上下左右均可走，只要无棋子阻拦，步数不受限制。
将：可以上下左右移动，每次只能移动一格
接下来给出一个棋盘，牛妹的棋子用大写字母表示，牛牛的棋子用小写字母表示。
将用J,jJ,j表示，炮用P,pP,p表示，车用C,cC,c表示，兵用B,bB,b表示，没有棋子的格子用..表示
保证棋盘上一定同时包含JJ与jj各一个。
输入：
给定chessboard数组
6 \leq chessboard.size \leq 10^{3}6≤chessboard.size≤103
6 \leq chessboard[i].length \leq 10^{3}6≤chessboard[i].length≤103
输出：
牛妹能胜利则返回"Happy"，否则返回"Sad"
AC 从将军位置判断
enum Direction{
TOP(-1,0),DOWN(1,0),LEFT(0,-1),RIGHT(0,1);
int a;
int b;
private Direction(int a,int b){
this.a=a;
this.b=b;
}
}
public String playchess (String[] chessboard) {
// write code here
String happy="Happy";
String sad="Sad";
for(int i=0;i<chessboard.length;i++){
for(int j=0;j<chessboard[i].length();j++){
if(chessboard[i].charAt(j)=='j'){
if(BJMove(Direction.TOP,chessboard,i,j)||
BJMove(Direction.DOWN,chessboard,i,j)||
BJMove(Direction.LEFT,chessboard,i,j)||
BJMove(Direction.RIGHT,chessboard,i,j)){
return happy;
}
if(PMove(Direction.TOP,chessboard,i,j)||
PMove(Direction.DOWN,chessboard,i,j)||
PMove(Direction.LEFT,chessboard,i,j)||
PMove(Direction.RIGHT,chessboard,i,j)){
return happy;
}
if(CMove(Direction.TOP,chessboard,i,j)||
CMove(Direction.DOWN,chessboard,i,j)||
CMove(Direction.LEFT,chessboard,i,j)||
CMove(Direction.RIGHT,chessboard,i,j)){
return happy;
}
return sad;
}
}
}
return sad;
}
private static boolean BJMove(Direction d,String[] chessboard,int row,int col){
int rows=chessboard.length;
int cols=chessboard[0].length();
if(row+d.a>=0&&row+d.a<rows&&col+d.b>=0&&col+d.b<cols&&
(chessboard[row+d.a].charAt(col+d.b)=='B'||chessboard[row+d.a].charAt(col+d.b)=='J'))
return true;
else
return false;
}
private static boolean PMove(Direction d,String[] chessboard,int row,int col){
int rows=chessboard.length;
int cols=chessboard[0].length();
boolean hasOne=false;
int i=row+d.a;
int j=col+d.b;
while (i>=0&&i<rows&&j>=0&&j<cols){
if(hasOne&&chessboard[i].charAt(j)=='P'){
return true;
}else if(hasOne&&chessboard[i].charAt(j)!='.'&&!(chessboard[i].charAt(j) =='P')){
return false;
}
if(chessboard[i].charAt(j)!='.'){
hasOne=true;
}
i+=d.a;
j+=d.b;
}
return false;
}
private static boolean CMove(Direction d,String[] chessboard,int row,int col){
int rows=chessboard.length;
int cols=chessboard[0].length();
int i=row+d.a;
int j=col+d.b;
while (i>=0&&i<rows&&j>=0&&j<cols){
if(chessboard[i].charAt(j)=='C'){
return true;
}
i+=d.a;
j+=d.b;
}
return false;
}23. 算法交流群
牛牛有一个算法交流群，它是这个群的群主，也是这个群实力最强的人。
算法交流群里一共有n个人，每个人都有一个等级a_iai表示它能解决难度小于等于a_iai的算法问题。
除了牛牛以外，群里的每个编号为i的人都在群里有一个等级比他高的朋友编号为p_ipi。群友 i 会解决那些他产生和接收的等级小于等于a_iai的问题，并把解决不了的问题全部交给p_ipi。
保证牛牛的编号为1。保证牛牛的等级全场唯一且全场最高。如果牛牛解决不了他接收的问题，他将不管这些问题。
这天群里的每个人都产生了一个问题，牛牛知道了每个人产生问题等级k_iki，他想知道群里的每个人在这天解决了多少问题。
90%
public int[] solve (int n, int[] a, int[] p, int[] k) {
// write code here
int[] res=new int[n];
for(int i=n-1;i>=0;i--){
int j=i;
while (j>0&&k[i]>a[j]){
j=p[j-1]-1;
}
if(j>=0&&k[i]<=a[j]) res[j]++;
}
return res;
}24、Pokemon
牛牛是励志成为世界第一宝可梦大师的宝可梦训练家。现在他遇到了一个强劲的野生宝皮卡丘，野生宝皮卡丘的生命值是HP，攻击力是ACK，牛牛召唤的宝可梦是杰尼龟。杰尼龟的生命值是HP2，攻击力是ACK2，除此之外身为训练家还可以给宝可梦吃药让他满血复活(吃药发生在双方发动攻击之前，并且吃药一方不得在本回合发动攻击)。牛牛想知道他最少多少回合才能能打败野生宝皮卡丘？因为皮卡丘会电光一闪，所以皮卡丘总是比杰尼龟先发动攻击。如果牛牛无法战胜野生皮卡丘则返回-1。
输入：
包括HP ACK HP2 ACK2 1 \leq HP,ACK,HP2,ACK2 \leq 10^{12}1≤HP,ACK,HP2,ACK2≤1012
输出：
若能成功击败野生皮卡丘则返回最少回合数，否则返回-1。
贪心 注意特殊情况
public long Pokemonfight (long HP, long ACK, long HP2, long ACK2) {
// write code here
if(HP2<=ACK){
return -1;
}else if (ACK2>=HP){
return 1;
}else{
if(2*ACK>=HP2) {
return -1;
}
long res=0;
long t1 = (long) Math.ceil(HP2*1.0/ACK)-1; //回合数
long stepHP=(t1-1)*ACK2;
long lessHP=HP%stepHP;
long baseRes= (long) Math.floor(HP*1.0/stepHP)*t1;
if(lessHP<=ACK2){
res=baseRes;
}else{
res=baseRes+(long)Math.ceil(lessHP*1.0/ACK2);
}
res+=stepHP==1?-2:0;
return res;
}
}中高等难度面试题
1、数组求和统计
牛牛有两个长度为nn的数组a, ba,b，牛牛希望统计有多少数对(l, r)(l,r)满足：
1，0 \leq l \leq r \leq n - 10≤l≤r≤n−1
2，\sum_{i= l}^{r}{a_i} = b_l + b_r∑i=lr**ai=bl+br
AC
生成一个辅助数组c求a数组的前缀和 利用数组可以直接求出a[i]~a[j]的和
public int countLR (int[] a, int[] b) {
// write code here
int len=a.length;
int[] c=new int[len];
c[0]=a[0];
//生成a数组的前缀和 {a[0],a[0]+a[1]...}
for(int i=1;i<len;i++){
c[i]=c[i-1]+a[i];
}
int count=0;
for(int l=0;l<len;l++){
for(int r=l;r<len;r++){
//比较b[l]加b[r]等于a[l]+..+a[r]
// c[r] 0+..+a[l-1]+a[l]+..+a[r] - c[l-1] 0+..+a[l-1]等于a[l]+..+a[r]
if(l>0&&b[l]+b[r]==c[r]-c[l-1]){
count++;
//特殊情况l==0 直接等于c[r]
}else if(l==0&&b[l]+b[r]==c[r]){
count++;
}
}
}
return count;
}2.那些插队的人
题目背景：
随着社会整体素质的提高，插队的现象已经越来越少了。但是仍旧有一个特殊情况，需要对于某些人进行优先处理。当这些人完成了自己插队的壮举之后，队伍的形态就变得千变万化。这个时候，得知每个人在哪里就变得尤为重要的，聪明的你一定可以完成这个艰巨的任务的，加油吧！
简明题意：
你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。
AC
显然，这题需要将插队序列倒过来处理，假设有一个人插了很多次队，那么最后一次插队才是他最终的位置。比如样例 15 [10,4,6,5,9,7,3,3,9,10] 根据插队序列模拟其最后排队形成过程：
- 10
- 10 9
- 10 9 3
- 10 9 3 7
- 10 9 3 7 5
- 10 9 3 7 5 6
- 10 9 3 7 5 6 4
- 10 9 3 7 5 6 4 1 2 3
对于插队序列中的每一个人，我们只需要考虑其最后一次插队即可。
接下来求解答案，插队序列中最大值为10， 那么大于等于10的部分队伍序列肯定都是对的，所以我们要找就是[1,10]这个区间有多少个人不在自己的位置上，可以反过来求[1,10]里有多少人在正确的位置上，因为能在正确的位置上出现的人，一定是属于插队序列里的人，所以我们可以比较插队后的位置和实际位置判断这个人是否在正确的位置。（不插队的话，肯定会被从原来的位置挤开，那么就不可能出出现在正确的位置）
public int countDislocation (int n, int[] cutIn) {
// write code here
int right=0,count=0,max=0;
for(int i=cutIn.length-1;i>=0;i--){
//判断是否找到最后一次插队
if(findLast(cutIn,i)){
//如果当前元素位置等于原来的位置
if(right+1==cutIn[i]){
count++;
}
//插入位置加一
right++;
}
//计算插入元素最大值
max=Math.max(max,cutIn[i]);
}
return max-count;
}#算法##算法题##刷题#
