秋招笔试算法题汇总

中兴

1.字符排序

给定一个正整数及非负整数 nus 的列表，第一个正整数表示nums列表中数字的总个数，需要将nums列表中数据排列组合出一个最大的数并返回它

思路：排序，拼接，再输出，按照拼接的字符排序

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 输入第一个数字，表示待组合数据的总个数
        int n = scanner.nextInt();
        
        // 输入待组合的数字
        String[] nums = new String[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.next();
        }
        
        // 自定义排序，按拼接后的字符串降序排序
        Arrays.sort(nums, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                String order1 = a + b;
                String order2 = b + a;
                // 按照组合后的字符串降序排序
                return order2.compareTo(order1);
            }
        });
          
        // 处理特殊情况：如果最大的数是"0"，直接返回"0"
        if (nums[0].equals("0")) {
            System.out.println("0");
            return;
        }
        
        // 拼接排序后的数组
        StringBuilder result = new StringBuilder();
        for (String num : nums) {
            result.append(num);
        }
        
        // 输出结果
        System.out.println(result.toString());
    }
}

上述代码中的自定义比较器可以用Java8简写

1
2
3

// 使用Lambda表达式自定义排序，按拼接后的字符串降序排序
Arrays.sort(nums, (a, b) -> (b + a).compareTo(a + b));

compareTo 是 String 类中的一个方法，作用是比较两个字符串的字典顺序。

如果字符串 s1 大于字符串 s2，s1.compareTo(s2) 返回正整数。
如果 s1 等于 s2，返回0。
如果 s1 小于 s2，返回负整数。

2.动态规划问题

新郎可以一次走一个或者两个台阶，每个台阶都要花费钱这种问题

给定每个台阶的花费，然后求最小花费

思路：动态规划数组，dp[i] = min{dp[i-1]*cost[i-1], dp[i-2],cost[i-2]};

import java.util.*;

public class topic {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + arr[i - 1], dp[i - 2] + arr[i - 2]);
        }
        System.out.println(dp[n]);
    }
}

深信服

1.石头问题

桌子上放了一排石头，有n个，每块石头的颜色可以是红色，绿色或蓝色。现在要从这排石头取出的数个石头，以便剩余的石头里面，任何两颗相邻的石头具有不同的颜色的(取出1块石头后，就认为两边的石头是相邻的)请根据输入的石头数量、排序和颜色，计算最少要取出几块石头?

思路：遇到重复的，取出，count++

import java.util.*;

public class topic1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String next = scanner.next();
        int count = 0;
        for (int i = 0; i < next.length() - 1; i++) {
            if(next.charAt(i) == next.charAt(i+1)){
                count++;
            }
        }
        System.out.println(count);
    }
}