✨✨【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<>();
        // 遍历 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 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();
            // 遍历字符穿 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
输出
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();// 最后输入的整数k
            List<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-1111

000-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-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 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) = 1
        int[] 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;
    }
}

---

总结

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

所以,

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

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

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

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