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

【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 hashMap = new HashMap<>(); // 遍历 array for (int i = 0; i < array.length; i++) { // 如果不包含 key 那么 put key，value 为1 if(!hashMap.containsKey(array[i])) { hashMap.put(array[i],1); }else { // 如果包含 key，先得到 key所对应的value 再在原来的基础上 value + 1 int count = hashMap.get(array[i]); hashMap.put(array[i],count+1); } } // 使用迭代器 打印 key 和 value Iterator 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 大于 总数的一半 返回 key if(value > array.length/2) { return key; } } return 0; }}

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

​​牛客——简单记录错误​​

输入描述:每组只包含一个测试用例。一个测试用例包含一行或多行字符串。每行包括带路径文件名称，行号，以空格隔开。输出描述:将所有的记录统计并将结果输出，格式：文件名 代码行数 数目，一个空格隔开，如：示例1输入D:\zwtymj\xccb\ljj\cqzlyaszjvlsjmkwoqijggmybr 645E:\je\rzuwnjvnuz 633C:\km\tgjwpb\gy\atl 637F:\weioj\hadd\connsh\rwyfvzsopsuiqjnr 647E:\ns\mfwj\wqkoki\eez 648D:\cfmwafhhgeyawnool 649E:\czt\opwip\osnll\c 637G:\nt\f 633F:\fop\ywzqaop 631F:\yay\jc\ywzqaop 631D:\zwtymj\xccb\ljj\cqzlyaszjvlsjmkwoqijggmybr 645输出rzuwnjvnuz 633 1atl 637 1rwyfvzsopsuiqjnr 647 1eez 648 1fmwafhhgeyawnool 649 1c 637 1f 633 1ywzqaop 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 map = new HashMap<>(); // 用 顺序表来存储 顺序 ArrayList 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 CDEABCDGEAS CDECDE输出YesNo

解题思路：

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

​​看到次数，我们脑海中就应该往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 map = new HashMap<>(); HashMap map2 = new HashMap<>(); String A = sc.next();// A 框 String B = sc.next();// B 框 char[] a = A.toCharArray(); char[] b = B.toCharArray(); // 遍历字符穿 A for (char ch:a) { if(!map.containsKey(ch)) { map.put(ch,1); }else { map.put(ch,map.get(ch) + 1); } } // 遍历字符串 B for (char ch:b) { if(!map2.containsKey(ch)) { map2.put(ch,1); }else { map2.put(ch,map2.get(ch)+1); } } // 遍历 B // 判断 A 中是否 包含B 并且 A每种求的种类个数是否大于等于B boolean 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"); }else System.out.println("No"); } }}

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

​​牛客——查找兄弟单词​​

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

解题思路：

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

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

判定兄弟单词的规则:

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

代码实现：

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();// 最后输入的整数k List 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_worldnice_to_meet_you输出helloWorldniceToMeetYou

解题思路：

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

补充：

方法一：

使用：substringimport 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); } }}

方法二：

不使用 substringimport 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 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)​​

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

方法一：

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输入124873279ITS-EASY888-45673-10-10-10888-GLOPTUT-GLOP967-11-11310-GINOF101010888-1200-4-8-7-3-2-7-9-487-32794UTT-HELPTUT-GLOP310-GINO000-1213输出310-1010310-4466487-3279888-1200888-4567967-1111000-1213310-4466888-4357888-4567

解题思路：

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

先用 hash 表 存储 字母和数字之间的映射关系每次读到一个字符，去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 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 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-xxxx line = 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 42 35

解题思路：

dfs+回溯

如果curSum（累加和）刚好等于所求 m，直接打印，每个结果用空格隔开，注意最后一个位置，我们单独处理如果不等于就继续累加，用 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 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 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输入61 65 1002 75 803 80 1004 60 955 82 1016 81 70输出4

解题思路：

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

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

代码实现：

import java.util.*;// 创建个node类，属性为身高体重，链接 Comparable 接口进行比较class node implements Comparable { 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) = 1 int[] maxLength = new int[n]; for(int i = 0;i maxLength[i] = 1; } for(int i = 1;i < n;i++){ for(int j = 0;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; }}

总结

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

所以,

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

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

​

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。