【Java牛客力扣刷题特辑第五期】——诸佬们这些坑你们都踩过了吗？牛客网经典笔试题目每天刷两道，快乐充实一整天

✨✨【Java牛客&力扣刷题特辑第五期】——诸佬们这些坑你们都踩过了吗？

---

✔✨前言

🎉🎉大家好！好久不见我是青花瓷，今天你刷题了吗？文章目录,从易到难,层层递进,如果每一道题都吃透,你一定会在做题方面有质的飞跃,关注我,一起学习算法,一起分享好的题型。博主将持续更新算法,大厂笔试题,经典算法题,易错题,如果觉得不错,点点赞支持一下,如果有错误的地方,欢迎指正✨✨
下一期：算法篇之回溯算法

---

作者介绍:

🎓作者:偷偷敲代码的青花瓷✨
👀作者的Gitee:代码仓库
📌系列文章推荐:
✨1. Java牛客&力扣刷题特辑第一期
✨2.Java牛客&力扣刷题特辑第二期
✨3. Java牛客&力扣刷题特辑第三期
✨4.Java牛客&力扣刷题特辑第四期
✨✨每天进步一点点，祝诸君在笔试场上力压群雄，期末考试运筹帷幄，你要相信你所做的努力都不会白费，一起加油吧！🎉🙌💕

---

文章目录

• 1.数组中出现次数超过一半的数字 （数组 哈希） 牛客难度：3星
• • 代码实现:
  • 方法一
  • 方法二
• 2.简单记录错误 （字符串 哈希）牛客难度：4星
• • 解题思路：
  • 代码实现：
• 3.乒乓球框 （查找 哈希）牛客难度：3星
• • 解题思路：
  • 代码实现：
• 4.查找兄弟单词（查询 list） 牛客难度：3星
• • 解题思路：
  • 代码实现：
• 5.骆驼命名法（字符串 subString） 牛客难度：2星
• • 解题思路：
  • 方法一：
  • 方法二：
• 6.单词倒排 (字符串 正则) 牛客难度：2星
• • 解题思路：
  • 方法一：
  • 方法二:
• 7.电话号码 （哈希 Map和Set） 牛客难度：3星
• • 解题思路：
  • 代码如下：
• 8.求和 （回溯+dfs） 牛客难度：5星
• • 解题思路：
  • 代码如下：
• 9.马戏团 （DP）牛客难度：5星
• • 解题思路：
  • 代码实现：
• 总结

---

1.数组中出现次数超过一半的数字 （数组 哈希） 牛客难度：3星

牛客——数组中出现次数超过一半的数字

示例1
输入
[1,2,3,2,2,2,5,4,2]
输出
2
示例2
输入
[3,3,3,3,2,2,2]
输出
3
示例3
输入
[1]
输出
1

代码实现:

方法一

对数组进行排序，如果一个数出现的次数超过总数的一半，那么它就是中间的那个数

import java.util.*;
public class Solution {public int MoreThanHalfNum_Solution(int [] array) {// 1. 先对数组进行排序Arrays.sort(array);// 2. 判断中间的数出现的次数是否超过总数的一半int count = 0;for (int i = 0; i < array.length; i++) {if(array[i] == array[array.length/2]) {count++;}}if(count > array.length/2) {return array[array.length/2];}else {return 0;}}
}

方法二

使用 HashMap,通过迭代器打印出 key 和 value，用value去和总长度的一般比较，如果大于总长度的一般，返回key，否则返回0

import java.util.*;
public class Solution {public int MoreThanHalfNum_Solution(int [] array) {// 使用 HashMap 来存储HashMap<Integer,Integer> hashMap = new HashMap<>();// 遍历 arrayfor (int i = 0; i < array.length; i++) {// 如果不包含 key 那么 put key，value 为1if(!hashMap.containsKey(array[i])) {hashMap.put(array[i],1);}else {// 如果包含 key，先得到 key所对应的value 再在原来的基础上 value + 1int count = hashMap.get(array[i]);hashMap.put(array[i],count+1);}}// 使用迭代器 打印 key 和 valueIterator iterator = hashMap.entrySet().iterator();while (iterator.hasNext()) {Map.Entry entry = (Map.Entry) iterator.next();Integer key = (Integer) entry.getKey();Integer value = (Integer) entry.getValue();// 判断 如果 value 大于 总数的一半 返回 keyif(value > array.length/2) {return key;}}return 0;}
}

---

2.简单记录错误 （字符串 哈希）牛客难度：4星

牛客——简单记录错误

输入描述:
每组只包含一个测试用例。一个测试用例包含一行或多行字符串。每行包括带路径文件名称，行号，以空格隔开。输出描述:
将所有的记录统计并将结果输出，格式：文件名 代码行数 数目，一个空格隔开，如：示例1
输入
D:\zwtymj\xccb\ljj\cqzlyaszjvlsjmkwoqijggmybr 645
E:\je\rzuwnjvnuz 633
C:\km\tgjwpb\gy\atl 637
F:\weioj\hadd\connsh\rwyfvzsopsuiqjnr 647
E:\ns\mfwj\wqkoki\eez 648
D:\cfmwafhhgeyawnool 649
E:\czt\opwip\osnll\c 637
G:\nt\f 633
F:\fop\ywzqaop 631
F:\yay\jc\ywzqaop 631
D:\zwtymj\xccb\ljj\cqzlyaszjvlsjmkwoqijggmybr 645输出
rzuwnjvnuz 633 1
atl 637 1
rwyfvzsopsuiqjnr 647 1
eez 648 1
fmwafhhgeyawnool 649 1
c 637 1
f 633 1
ywzqaop 631 2说明
由于D:\cfmwafhhgeyawnool 649的文件名长度超过了16个字符，达到了17，所以第一个字符'c'应该被忽略。
记录F:\fop\ywzqaop 631和F:\yay\jc\ywzqaop 631由于文件名和行号相同，因此被视为同一个错误记录，哪怕它们的路径是不同的。
由于循环记录时，只以第一次出现的顺序为准，后面重复的不会更新它的出现时间，仍以第一次为准，所以D:\zwtymj\xccb\ljj\cqzlyaszjvlsjmkwoqijggmybr 645不会被记录。  

解题思路：

最开始，我做这道题的时候，说真的，有点头疼（小声BB语文没学好，理解能力有点差！🤣）导致这道题，一开始有思路，做着做着，就卡壳了，后面我听老师讲课，我突然就恍然大悟，这道题，原来就是想太复杂了，所以这里我直接用上课的笔记，这样就能更好的理解

先看看题目想表达什么意思（一定要耐心）：

看懂题目想表达的意思，我们再来思考方法，很明显这道题，读懂题意，就可以编写出来，没有包含算法什么的，就是基于一个理解能力，和代码编写能力

代码实现：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;/***  牛客——简单记录错误*/
public class TestDemo4 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 用 HashMap 来存储 次数HashMap<String,Integer> map = new HashMap<>();// 用 顺序表来存储 顺序ArrayList<String> arr = new ArrayList<>();while (sc.hasNext()) {// 文件名String name  = sc.next();// 行号String index = sc.next();// 文件名 预处理 通过反斜杠 分割字符串String[] strA = name.split("\\\\");// 只保留 最后一个反斜杠之后的内容name = strA[strA.length-1];// 判断长度是否大于16(题上给的超过16个字符只保留最后16个字符if(name.length() > 16) {name = name.substring(name.length() - 16);}// 加上行号name = name + " " + index;// 判断是否为第一次出现if(!map.containsKey(name)) {// 第一次 出现 加入 新记录arr.add(name);map.put(name,1);}else {// 不是第一次 次数累加map.put(name, map.get(name) + 1);}}// 打印最后8条记录int start = 0;if(arr.size() > 8) {start = arr.size() - 8;}for (;start < arr.size();start++) {System.out.println(arr.get(start) + " " + map.get(arr.get(start)));}}
}

---

3.乒乓球框 （查找 哈希）牛客难度：3星

牛客——乒乓球筐

示例1
输入
ABCDFYE CDE<br/>ABCDGEAS CDECDE
输出
Yes<br/>No

解题思路：

题目比较明确，注意审题就好了

看到次数，我们脑海中就应该往Map方向想。借助 map 统计出每个盒子中的每种球的种类和数目，然后遍历其中的一个map和另外一个map进行对比

代码实现：

import java.util.HashMap;
import java.util.Scanner;/*** 牛客乒乓球筐*/
public class TestDemo5 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {HashMap<Character,Integer> map = new HashMap<>();HashMap<Character,Integer> map2 = new HashMap<>();String A = sc.next();// A 框String B = sc.next();// B 框char[] a = A.toCharArray();char[] b = B.toCharArray();// 遍历字符穿 Afor (char ch:a) {if(!map.containsKey(ch)) {map.put(ch,1);}else {map.put(ch,map.get(ch) + 1);}}// 遍历字符串 Bfor (char ch:b) {if(!map2.containsKey(ch)) {map2.put(ch,1);}else {map2.put(ch,map2.get(ch)+1);}}// 遍历 B// 判断 A 中是否 包含B 并且 A每种求的种类个数是否大于等于Bboolean flg = true;for (char ch:b) {if(!map.containsKey(ch) || map.get(ch) < map2.get(ch)) {flg = false;break;}}if(flg) {System.out.println("Yes");}elseSystem.out.println("No");}}
}

---

4.查找兄弟单词（查询 list） 牛客难度：3星

牛客——查找兄弟单词

输入描述:
输入只有一行。
先输入字典中单词的个数n，再输入n个单词作为字典单词。
然后输入一个单词x
最后后输入一个整数k输出描述:
第一行输出查找到x的兄弟单词的个数m
第二行输出查找到的按照字典顺序排序后的第k个兄弟单词，没有符合第k个的话则不用输出。
示例1
输入
3 abc bca cab abc 1
输出
2
bca

解题思路：

说真的这道题，主要还是考察一个对题意的理解

兄弟单词的含义：两个单词不同，长度相同，但是构成的字母顺序不同

判定兄弟单词的规则:

1. 先判断长度
2. 如果长度相同，再看是否是完全相同的（完全相同的不算兄弟）
3. 然后将两个单词排序，排序相同才是真兄弟单词

代码实现：

import java.util.*;
public class TestDemo6 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();// 字典中单词个数String[] dist = new String[n];// 给数组赋值for (int i = 0; i < n; i++) {dist[i] = sc.next();}String XWord = sc.next();// 兄弟单词char[] XWordA = XWord.toCharArray();Arrays.sort(XWordA);int k = sc.nextInt();// 最后输入的整数kList<String> list = new ArrayList<>();// 判断是不是 兄弟单词方法// 1: 先判断两个 单词长度是否 相同  2：在判断两个单词是否一样 3: 对两个单词进行排序，排序结果相同那么就是兄弟单词for (String word:dist) {if(word.length() == XWord.length() && !word.equals(XWord)) {// 先根据字典序跑排序，如果排序后与给出的单词一样那么就是兄弟单词char[] tmp = word.toCharArray();Arrays.sort(tmp);// 比较两个if(Arrays.equals(tmp,XWordA)) {list.add(word);}}}// 输出// 1. 先输出 兄弟单词的个数System.out.println(list.size());// 2. 按照字典序输出 第 k个if(list.size() >=k) {Collections.sort(list);System.out.println(list.get(k-1));}}}
}

---

5.骆驼命名法（字符串 subString） 牛客难度：2星

牛客——骆驼命名法

示例1
输入
hello_world
nice_to_meet_you
输出
helloWorld
niceToMeetYou

解题思路：

这道题的解题思路很明确，遍历字符串，用StringBuilder 存储，如果遇到下划线，那么下划线下一个值转为大写

补充：

subString 左闭右开
i++ : 先输出 i 然后 i自增 1
++i : 先自增 1 在输出

方法一：

使用：substring
import java.util.*;
public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()) {String str = sc.nextLine();StringBuilder sb = new StringBuilder();for(int i=0;i < str.length();i++) {if(str.charAt(i) == '_') {sb.append(str.substring(++i,i+1).toUpperCase());}else{sb.append(str.charAt(i));}}System.out.println(sb);}}
}

方法二：

不使用 substring
import java.util.*;
public class Main{public static void main(String[] args) {Scanner sc=new Scanner(System.in);while (sc.hasNext()){String s=sc.nextLine();getName(s);}}private static void getName(String s) {char[] c=s.toCharArray();StringBuilder sb=new StringBuilder();for (int i = 0; i <c.length ; i++) {if (c[i]=='_'){sb.append(Character.toUpperCase(c[i+1]));i++;}else {sb.append(c[i]);}}System.out.println(sb.toString());}
}

---

6.单词倒排 (字符串 正则) 牛客难度：2星

牛客——单词倒排

输入描述:
输入一行，表示用来倒排的句子
输出描述:
输出句子的倒排结果
示例1
输入
I am a student
输出
student a am I
示例2
输入
$bo*y gi!r#l
输出
l r gi y bo

解题思路：

这个问题是包含了字符串常见操作的 切分 和 合并 ，根据题意，不难理解，是字母就应该满足>= A (a）<= Z(z)

1. 先切分（切分前先对分隔符做处理，统一分隔符）
2. 再合并（逆序合并）直接字符串拼接即可

补充：

方法一：

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String str1 = sc.nextLine();char[] ch = str1.toCharArray();StringBuilder sb = new StringBuilder();for (int i = 0; i < str1.length(); i++) {if((ch[i]>='a'&&ch[i]<='z') || (ch[i]>='A'&&ch[i]<='Z')) {sb.append(ch[i]);}else {sb.append(" ");}}String[] str2 = sb.toString().split(" ");//按照空格分隔for (int i = str2.length-1; i >=0 ; i--) {if(i!=0) {System.out.print(str2[i] + " ");}else {System.out.print(str2[i]);}}}}
}

方法二:

/*** 思路：* 需要用到正则表达式：[^a-zA-Z] （去匹配目标字符串中非a—z也非A—Z的字符）* 所以将字符串用split以正则表达式包含的字符分隔开，剩下的全是可以组成单词的字符。再将这些字符串逆序输出即可。* @param args*/import java.util.Arrays;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);String input = in.nextLine();String[] words = input.split("[^a-zA-z]");for (int i = words.length - 1; i >= 0; i--) {if ("".equals(words[i])) {continue;}System.out.print(words[i] + " ");}System.out.println();}
}

---

7.电话号码 （哈希 Map和Set） 牛客难度：3星

牛客——电话号码

示例1
输入
12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279
4
UTT-HELP
TUT-GLOP
310-GINO
000-1213
输出
310-1010
310-4466
487-3279
888-1200
888-4567
967-1111000-1213
310-4466
888-4357
888-4567

解题思路：

这个题目描述的比较直接明了，借助 hash 表完成 字母和 数字之间的转换即可，注意大小写的情况

1. 先用 hash 表 存储 字母和数字之间的映射关系
2. 每次读到一个字符，去hash表中查找，并进行处理

代码如下：

import java.util.HashMap;
import java.util.Scanner;
import java.util.TreeSet;/*** 牛客电话号码*/
public class TestDemo10 {public static void main(String[] args) {// 建立映射String str1 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";String str2 = "22233344455566677778889999";HashMap<Character,Character> hashMap = new HashMap<>();char[] str1Arr = str1.toCharArray();char[] str2Arr = str2.toCharArray();for (int i = 0; i < str1.length(); i++) {hashMap.put(str1Arr[i],str2Arr[i]);}Scanner sc = new Scanner(System.in);while (sc.hasNext()) {// 用 set 存储结果（去重），这里使用TreeSet（排序,TreeSet树形结构）TreeSet<String> set = new TreeSet<>();int n = sc.nextInt();for (int i = 0; i < n; i++) {String line = sc.next();// 对字母进行转换 用StringBuilder 存储char[] lineArr = line.toCharArray();StringBuilder sb = new StringBuilder();for (char ch:lineArr) {if(isDist(ch)) {// 如果是数字直接存入 sb中sb.append(ch);}else if(isUPPer(ch)) {// 如果不是数字 转化为 数字 在放入 sb中sb.append(hashMap.get(ch));}}// 调整格式 : xxx-xxxxline = sb.substring(0,3)+ "-" + sb.substring(3);// 保存结果set.add(line);}//打印结果for (String str:set) {System.out.println(str);}// 每组数据用空格 隔开System.out.println();}}// 判断是不是 数字public static boolean isDist(char ch) {return ch>='0' && ch<='9';}// 判断是不是 字母public static boolean isUPPer(char ch) {return ch >= 'A' && ch <= 'Z';}
}

---

8.求和 （回溯+dfs） 牛客难度：5星

牛客——求和

示例1
输入
5 5
输出
1 4<br/>2 3<br/>5

解题思路：

dfs+回溯

1. 如果curSum（累加和）刚好等于所求 m，直接打印，每个结果用空格隔开，注意最后一个位置，我们单独处理
2. 如果不等于就继续累加，用 List 存储累加的对象，如果两个累加的结果大于 m，回退到上一个位置，并且删除 之前 累加的对象（递归）

注意：

题目给出的隐藏条件：1,数不能重复使用，2.一个组合内容：数值递增，3.组合之间： 字典序

代码有详细注释，跟着代码来理解，就非常容易了，最近刷了很多回溯算法相关的题目，下一章节，博主将更新算法篇之回溯算法，对回溯感兴趣的友友们别忘记关注博客哟😜

代码如下：

import java.util.ArrayList;
import java.util.Scanner;/*** 牛客 求和 好未来*/
public class Demo13 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {int n = scanner.nextInt();int m = scanner.nextInt();ArrayList<Integer> list = new ArrayList<>();int curSum = 0;getFunc(list,1,m,n,curSum);}}/**** @param list 用来存储 数字 组成* @param post 最开始的位置 i* @param dest 输入的 m* @param n  输入的 n* @param curSum 求和的值*/public static void getFunc(ArrayList<Integer> list,int post,int dest,int n,int curSum) {if(curSum >= dest) {// 如果求和的值 等于 输入的 m，打印if(curSum == dest) {// 每个数用空格 隔开，对最后一个数单独处理for (int i = 0; i < list.size()-1; i++) {System.out.print(list.get(i) + " ");}System.out.println(list.get(list.size()-1));}return;}// 如果求和的值没有大于 dest 累加for (int i = post; i <= n ; i++) {// 保存当前数据list.add(i);getFunc(list,i+1,dest,n,curSum+i);// 如果 累加数据 大于 dest ，回退，删除当前数据list.remove(list.size()-1);}}
}

---

9.马戏团 （DP）牛客难度：5星

牛客——马戏团

示例1
输入
6
1 65 100
2 75 80
3 80 100
4 60 95
5 82 101
6 81 70
输出
4

解题思路：

我们不要被这道题的表面所迷惑，看到这么多文字，可能会头疼，不要着急，慢慢来理解题意分析

1. 首先读懂题意，在上面的人需要满足什么样的条件？
   
   

2. 读懂题意以后，我们在来继续思考，这道题，要求能叠出的最大高度，我们先对体重进行升序排序，体重相同时，按照身高的降序排序，这个时候你想到了什么？这不就是求身高最长子序列的长度？？想到子序列长度之后，肯定就是动态规划啊（当时做了很久用的01背包问题转化，但是这个最长子序列思路，最好理解），那么这道题的本质就是：求身高的最长升序子序列（可以不连续）的长度，知道是动态规划以后，我们来找它的状态转移方程
   
   

3. DP思路我们理清楚了，那么如何对体重进行排序?这里有两个属性呀（身高和体重）咋个办呢？(当时做这道题，我也不知道哈哈哈😂)`创建一个类，实现Comparable接口，对身高体重进行比较

补充：

话不多说，我们直接编写代码吧

代码实现：

import java.util.*;
// 创建个node类，属性为身高体重，链接 Comparable 接口进行比较
class node implements Comparable<node> {int w;int h;public node(int w,int h) {this.w = w;this.h = h;}public int compareTo(node obj) {// 对体重进行升序排序int ret = w - obj.w;// 如果体重相等，对身高进行降序排序if(ret == 0) {return obj.h - h;}return ret;}
}
public class Demo144{public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNextInt()) {// 输入数据int n = sc.nextInt();node[] arr = new node[n];for(int i = 0;i < n;i++) {sc.nextInt();
//                arr[i].w = sc.nextInt();
//                arr[i].h = sc.nextInt();arr[i] = new node(sc.nextInt(),sc.nextInt());}System.out.println(getMaxLength(arr,n));}}public static int getMaxLength(node[] arr,int n) {// 排序Arrays.sort(arr);// 计算最大子序列长度int ret = 0;// F（i）:以第i个元素结尾的最大子序列长度// 初始值： F(i) = 1int[] maxLength = new int[n];for(int i = 0;i<n;i++) {maxLength[i] = 1;}for(int i = 1;i < n;i++){for(int j = 0;j<i;j++){if(arr[j].h <= arr[i].h) {maxLength[i] = Math.max(maxLength[i],maxLength[j]+1);}// 更新最值 ret = Math.max(ret,maxLength[i]);}}return ret;}
}

---

总结

“种一颗树最好的是十年前,其次就是现在”

所以,

“让我们一起努力吧,去奔赴更高更远的山海”

如果有错误❌,欢迎指正哟😋

🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉

你要相信，你说做的一切，都不会白费