牛客上一些笔试题

1.最高分是多少

注释了一些调试信息

这题就熟悉输入输出流程

还有就是单元测试中不准使用 System.out 来进行人肉验证，必须使用 assert 来验证。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int N = in.nextInt();
            int M = in.nextInt();
            int [] score = new int[N];
//            System.out.println();
//            System.out.println(N+" "+M);
            for (int i = 0; i < N ; i++) {
                score[i] = in.nextInt();
                //System.out.print(score[i] + " ");
            }
            String c = null;
            int A = 0;
            int B = 0;
            for (int j = 0; j < M ; j++) {
                c = in.next();
                A = in.nextInt();
                B = in.nextInt();
                //System.out.print("修改前：" + Arrays.toString(score));
                process(c, A, B, score);
            }
        } 
    }
    private static void process(String c, int a, int b, int[] score) {
        int begin, end;
        if (c.equals("Q")) {
            begin = Math.min(a, b) - 1;
            end = Math.max(a, b);
            int max = score[begin];
            for (int i = begin ; i < end; i++) {
                if (max < score[i]) {
                    max = score[i];
                }
            }
            //System.out.println();
            System.out.println(max);
        } else if (c.equals("U")) {
            score[a - 1] = b;
            //System.out.print("修改后：" + Arrays.toString(score));
        }
    }
}

2.简单错误记录

HashMap中的根据value排序，还要重写compare算法，醉了

import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.LinkedHashMap;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        HashMap<String, Integer> map = new LinkedHashMap<>();
        while (in.hasNext()) {
            String str = in.nextLine();
            //System.out.println(str);
            int lastIndex = str.lastIndexOf("\\");
            str = str.substring(lastIndex + 1);
            if (str.length() > 16) {
                str = str.substring(str.length() - 16);
            }
            //System.out.println(str);
            if (map.containsKey(str)) {
                map.put(str, map.get(str) + 1);
            } else {
                map.put(str, 1);
            }
        }

        List<Map.Entry<String, Integer>> list = new
        ArrayList<Map.Entry<String, Integer>>(map.entrySet()); //转换为list
        Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1,
                               Map.Entry<String, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        int count = 0;
        for (Map.Entry<String, Integer> mapping : list) {
            count ++;
            if (count > map.keySet().size() - 8) {
                System.out.println(mapping.getKey() + " " + mapping.getValue());
            }
        }
    }
}

3.扑克牌消除

从一副扑克牌中随机抽取n张牌组成一个序列，规定连续3张相同牌号的卡牌可以消除，剩余卡牌按照当前顺序里新合井成新的序列后继续消除，重奥以上步票直到无法消除，最后清输出结束后剩余的卡牌序列，注:存在连续4张相同牌号的情况，消除后剩余一张

public class card {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.nextLine();
        String [] s = scan.nextLine().split(" ");
        ArrayList<String> list = new ArrayList<>(Arrays.asList(s));
        while(true){
            boolean flag = false;
            for (int i = 0; i < list.size()-2; i++) {
                if(Objects.equals(list.get(i), list.get(i + 1)) && Objects.equals(list.get(i), list.get(i + 2))){
                    list.remove(i);
                    list.remove(i);
                    list.remove(i);
                    flag = true;
                    break;
                }
            }
            if(list.size() < 3 || !flag) {
                break;
            }
        }
        for (String s1 : list){
            System.out.print(s1+ " ");
        }
    }
}

思路就是，暴力，转为List集合，外层死循环while（true）

内层for（）判断三个相等就删跳出for循环

对新集合继续for（）

没被删除过，或者集合长度小于3，break跳出while（true

4.计算云服务的DI值

现有一批云服务树，已给出云服务树各节点的问题数量，请通过计算输出风险云服务的个数。计算公式: DI值<=5严重问题数+2一般问题数，其中每个节点的不同级别问题数量需要将该节点及该节点为根节点的所有子节点的相应级别问题数量求和。

输入：第一行输入M和N，表示云服务阈值N，和接下来的N行数据

剩下N行输入为N4矩阵，行内使用空格分隔，第一列为服务节点，第二列为父节点（如果没有父节点用代替），第三列为问题（0表示严重问题，1表示一般问题），第四列表示当前问题的数量

输出：计算输出风险云服务的DI值

例如：输入：

2 5
a * 0 2
a * 1 2 
b a 0 2 
c b 0 2
d * 0 2

输出：2（表示有2个风险云服务,分别为a,d）

解释： a为云服务节点,有两个严重，两个一般问题，b为a的子节点,有两个严重问题，c为b的子节点，有两个严重问题，a服务器一共有6个严重问题，两个一般问题，DI值为：65+22=32>2。是风险云服务

d云服务节点，有2个严重，0个一般，DI值为2*2=4>2，是风险云服务

import java.util.*;

class TreeNode {
    String name;
    List<TreeNode> children;
    int severeProblems;
    int minorProblems;

    public TreeNode(String name) {
        this.name = name;
        this.children = new ArrayList<>();
        this.severeProblems = 0;
        this.minorProblems = 0;
    }

    // 添加问题数据
    void addProblems(int type, int count) {
        if (type == 0) { // 严重问题
            this.severeProblems += count;
        } else if (type == 1) { // 一般问题
            this.minorProblems += count;
        }
    }

    // 计算包括所有子节点的问题总数
    int[] getTotalProblems() {
        int totalSevere = severeProblems;
        int totalMinor = minorProblems;
        for (TreeNode child : children) {
            int[] childProblems = child.getTotalProblems();
            totalSevere += childProblems[0];
            totalMinor += childProblems[1];
        }
        return new int[]{totalSevere, totalMinor};
    }
}

public class demo1 {
    private static Map<String, TreeNode> nodeMap = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int threshold = scanner.nextInt();
        int n = scanner.nextInt();
        scanner.nextLine();

        // 读取并构建树
        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            String[] parts = line.split(" ");
            String nodeName = parts[0];
            String parentNode = parts[1];
            int problemType = Integer.parseInt(parts[2]);
            int problemCount = Integer.parseInt(parts[3]);

            TreeNode node = nodeMap.getOrDefault(nodeName, new TreeNode(nodeName));
            node.addProblems(problemType, problemCount);
            nodeMap.put(nodeName, node);

            if (!parentNode.equals("*")) {
                TreeNode parent = nodeMap.getOrDefault(parentNode, new TreeNode(parentNode));
                if (!parent.children.contains(node)) {
                    parent.children.add(node);
                }
                nodeMap.put(parentNode, parent);
            }
        }

        // 计算风险云服务
        int riskServiceCount = 0;
        for (TreeNode node : nodeMap.values()) {
            int[] totalProblems = node.getTotalProblems();
            int diValue = 5 * totalProblems[0] + 2 * totalProblems[1];
            if (diValue > threshold) {
                riskServiceCount++;
            }
        }

        System.out.println(riskServiceCount);
    }
}

5.球队射门能力

球队有n个足球队员参与m次射门训练，每次射门进球用1表示，射失则用0表示，依据如下规则对该n个队员的射门能力做排序

1、进球总数更多的队员射门能力更强

2、若进球总数一样多，则比较最多一次连续进球的个数，最多的队员能力更游

3、若最多一次连续进球的个数一样多，则比较第一次射失的先后顺序，其中后射失的队员更强，若第一次射失顺序相同，则按继续比较第二次射失的顺序，后丢球的队员能力更强，依次类推

4、若前3个规则排序后还能力相等，则队员编号更小的能力更强

输入：第1行，足球队员数n，射门训练次数m。(队员编号从1开始，依次递增)第2行，第1-n个队员从第1到m次训练的进球情况，每个队员进球情况为连续的1和0的组合，不同队员用空格分隔n和m均为正整数，0xn<=10个3，0<m<=10^3

输出：射门能力从强到弱的队员编号，用空格分隔

import java.util.*;

public class FootballPlayerRanking {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取球员数
        int m = scanner.nextInt(); // 读取射门次数
        scanner.nextLine(); // 跳过行尾

        String line = scanner.nextLine(); // 读取所有球员的射门结果
        String[] allResults = line.split(" "); // 按球员分割射门结果

        List<Player> players = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            players.add(new Player(i + 1, allResults[i]));
        }

        // 根据规则对球员进行排序
        Collections.sort(players);

        // 输出球员编号
        StringBuilder output = new StringBuilder();
        for (int i = 0; i < players.size(); i++) {
            if (i > 0) output.append(" ");
            output.append(players.get(i).id);
        }
        System.out.println(output.toString());
        scanner.close();
    }

    static class Player implements Comparable<Player> {
        int id;
        int goals;
        int maxConsecutiveGoals;
        List<Integer> misses;

        public Player(int id, String shootingResults) {
            this.id = id;
            this.goals = 0;
            this.maxConsecutiveGoals = 0;
            this.misses = new ArrayList<>();
            int currentStreak = 0;

            for (int i = 0; i < shootingResults.length(); i++) {
                if (shootingResults.charAt(i) == '1') {
                    currentStreak++;
                    this.goals++;
                } else {
                    this.misses.add(i);
                    if (currentStreak > this.maxConsecutiveGoals) {
                        this.maxConsecutiveGoals = currentStreak;
                    }
                    currentStreak = 0;
                }
            }

            if (currentStreak > this.maxConsecutiveGoals) {
                this.maxConsecutiveGoals = currentStreak;
            }
        }

        @Override
        public int compareTo(Player other) {
            if (this.goals != other.goals) {
                return Integer.compare(other.goals, this.goals);
            }
            if (this.maxConsecutiveGoals != other.maxConsecutiveGoals) {
                return Integer.compare(other.maxConsecutiveGoals, this.maxConsecutiveGoals);
            }
            for (int i = 0; i < Math.min(this.misses.size(), other.misses.size()); i++) {
                if (!this.misses.get(i).equals(other.misses.get(i))) {
                    return Integer.compare(other.misses.get(i), this.misses.get(i));  // 修改比较射失顺序，使其正确比较
                }
            }
            if (this.misses.size() != other.misses.size()) {
                return Integer.compare(other.misses.size(), this.misses.size());  // 若misses数量不同，则比较数量
            }
            return Integer.compare(this.id, other.id);  // 最后比较ID
        }
    }
}

理解问题

首先，需要完全理解题目的要求和所有排序规则。这个问题要求我们根据足球队员在多次射门训练中的表现来排序。排序的依据有四个层级：

总进球数（多的优先）。
最大连续进球次数（多的优先）。
射失的顺序（射失越晚越好）。
队员编号（编号小的优先）。
解析输入

从输入中读取球员数量和射门次数，然后读取所有球员的射门结果。每个球员的射门结果都是一个由 ‘1’（进球）和 ‘0’（未进球）组成的字符串。

设计数据结构

为了方便管理和排序球员的射门数据，我定义了一个 Player 类，包括：

id：球员的编号。
goals：总进球数。
maxConsecutiveGoals：最大连续进球数。
misses：记录每次未进球的具体位置，以便比较射失顺序。

计算排序关键值

对每个球员，解析其射门结果字符串，计算总进球数和最大连续进球数。同时，记录所有射失（即 ‘0’ 的位置）的索引，这些索引后续用于比较射失顺序。

实现比较逻辑

在 Player 类中实现 Comparable 接口，具体比较逻辑按照题目要求的四个层级顺序：

首先比较总进球数。
若进球数相同，比较最大连续进球数。
若最大连续进球数也相同，依次比较每次射失的顺序。
若所有射失顺序也相同，最后比较球员编号。

排序和输出

使用 Collections.sort 根据定义好的比较逻辑对球员列表进行排序。最后，输出排序后的球员编号。

package package3;

import java.util.*;

class Player {
    int id;
    int goals;
    int maxStreak;
    List<Integer> missTimes; // 存储每次失误的时间点

    Player(int id, String record) {
        this.id = id;
        this.goals = 0;
        this.maxStreak = 0;
        this.missTimes = new ArrayList<>();
        int streak = 0;
        for (int i = 0; i < record.length(); i++) {
            if (record.charAt(i) == '1') {
                goals++;
                streak++;
                maxStreak = Math.max(maxStreak, streak);
            } else {
                streak = 0;
                missTimes.add(i);
            }
        }
    }
}

public class demo3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 读取玩家数量
        int m = sc.nextInt(); // 读取比赛次数，虽然这个值没有直接用途
        sc.nextLine();
        Player[] players = new Player[n];
        for (int i = 0; i < n; i++) {
            players[i] = new Player(i + 1, sc.next());
        }
        Arrays.sort(players, new Comparator<Player>() {
            @Override
            public int compare(Player p1, Player p2) {
                if (p1.goals != p2.goals) {
                    return p2.goals - p1.goals;
                }
                if (p1.maxStreak != p2.maxStreak) {
                    return p2.maxStreak - p1.maxStreak;
                }
                // 比较最早的失误时间点
                if (!p1.missTimes.isEmpty() && !p2.missTimes.isEmpty()) {
                    int minSize = Math.min(p1.missTimes.size(), p2.missTimes.size());
                    for (int i = 0; i < minSize; i++) {
                        if (p1.missTimes.get(i) != p2.missTimes.get(i)) {
                            return p2.missTimes.get(i) - p1.missTimes.get(i); // 修改比较方式，最早失误的排在后面
                        }
                    }
                    return p1.missTimes.size() - p2.missTimes.size(); // 较少失误次数的排前面
                }
                return p1.id - p2.id;
            }
        });
        for (int i = 0; i < n; i++) {
            System.out.print(players[i].id);
            if (i != n - 1) {
                System.out.print(" ");
            }
        }
        sc.close();
    }
}

对上述代码修改，用Lambda表达式代替匿名实现类

/*
分析：排序的四个层级
1.总进球数（越多越好）
2，最大连续进球数（越多越好）
3.射失的顺序（后射失越好）
4.队员编号（越小越好）

数据结构：定义Player类
字段包括：ID：编号 int
        goals：总进球数 int
        goalsNumber:连续进球数 int
        misses :丢球的具体位置，List<Integer>
* */
class Player {
    int id;
    int goals;
    int goalsNumber;
    List<Integer> misses;

    Player(int id, String record) {
        this.id = id;
        this.goals = 0;
        this.goalsNumber = 0;
        this.misses = new ArrayList<>();
        int temp = 0; //记录临时的连续进球最大值
        for (int i = 0; i < record.length(); i++) {
            if (record.charAt(i) == '1') {
                goals++;
                temp++;
                goalsNumber = Math.max(temp, goalsNumber);
            } else {
                temp = 0;
                misses.add(i);
            }
        }
    }
}

public class Demo1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();
        Player[] players = new Player[n];
        for (int i = 0; i < n; i++) {
            players[i] = new Player(i + 1, scanner.next());
        }
        /*在Java中，当使用Comparator接口来定制排序时，compare方法需要返回三种类型的值来指示两个元素的相对顺序：
            返回一个负数，表示第一个参数应该排在第二个参数之前。
            返回零，表示两个参数相等。
            返回一个正数，表示第一个参数应该排在第二个参数之后。
        * */
        Arrays.sort(players, (p1, p2) -> {
            if (p1.goals != p2.goals) {
                //降序排序
                return p2.goals - p1.goals;
            }
            if (p1.goalsNumber != p2.goalsNumber) {
                return p2.goalsNumber - p1.goalsNumber;
            }
            //都一样的情况下，比较最小的失误点
            for (int i = 0; i < p1.misses.size(); i++) {
                if (p1.misses.get(i) != p2.misses.get(i)) {
                    return p2.misses.get(i) - p1.misses.get(i);
                }
            }
            //最后比较ID，ID小的排在前面
            return p1.id - p2.id;
        });

        for (int i = 0; i < n; i++) {
            System.out.print(players[i].id);
            if (i != n - 1) {
                System.out.print(" ");
            }
        }
    }
}

面经笔试题

409.最长回文串

给定一个包含大写字母和小写字母的字符串 s ，返回通过这些字母构造成的 最长的回文串 。

//思路，用set集合，去重，偶数的必能组成回文，基数的加1即可
class Solution {
    public int longestPalindrome(String s) {
        int l = s.length();
        if (l == 0)
            return 0;
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < l; i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                set.remove(c);
            } else {
                set.add(c);
            }
        }
        int ans = l - set.size();
        if (set.size() == 0) {
            return ans;
        } else {
            return ans + 1;
        }
    }
}

9.回文数

判断一个数字是否是回文数组

//思路：反过来求，判断两个数是否相等
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int a = 0, b = x;
        while (b != 0) {
            a = a * 10 + b % 10;
            b /= 10;
        }
        return a == x;
    }
}
//利用StringBuffer的reverse函数
class Solution {
    public boolean isPalindrome(int x) {
        String s1 = String.valueOf(x);
        String s2 = new StringBuilder(s1).reverse().toString();
        return s1.equals(s2);
    }
}

674.最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

//思路：两层暴力循环，找到，count++，找不到，跳出循环
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int l = nums.length;
        int ans = 1;
        for (int i = 0; i < l - 1; i++) {
            int count = 1;
            for (int j = i + 1; j < l; j++) {
                if (nums[j] > nums[j - 1]) {
                    count++;
                } else {
                    break;
                }
            }
            ans = Math.max(ans, count);
        }
        return ans;
    }
}

49.字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 排序后将String作为key，List<String>作为value
        // 寻找相同的String，添加到List<String>中，最后返回map中的List集合即可
        // 相等于用，map去重
        HashMap<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] array = s.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> value = map.getOrDefault(key, new ArrayList<>());
            value.add(s);
            map.put(key, value);
        }
        return new ArrayList<>(map.values());
    }
}

1019.链表下一个更大的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        int[] ans = new int[length];
        current = head;
        int index = 0;
        while (current != null) {
            ListNode next = current.next;
            int nextBigger = 0;
            while (next != null) {
                if (next.val > current.val) {
                    nextBigger = next.val;
                    break;
                }
                next = next.next;
            }
            ans[index++] = nextBigger;
            current = current.next;
        }
        return ans;
    }
}

53，最大子序和

//暴力模拟，超时
class Solution {
    public int maxSubArray(int[] nums) {
        int l = nums.length;
        int ans = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < l; i++) {
            sum = 0;
            for (int j = i ; j < l; j++) {
                sum += nums[j];
                ans = sum > ans ? sum : ans;
            }
        }
        return ans;
    }
}