帆软

帆软

100分钟：单选5道+不定项选择6道+填空2道+编程题2道

第一道：回文串

题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

回文字符定义为：首尾对称的字符，例如"a","baab","aba"。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1： 输入：s = "bbbab" 输出：4

解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2： 输入：s = "cbacbd" 输出：3

解释：一个可能的最长回文子序列为 "bab" 。

代码实现

import java.util.Scanner;

public class Main {
    public static int longestPalindromeSubseq(String s) {
        int n = s.length();
        // dp[i][j] 表示 s[i..j] 中最长回文子序列的长度
        int[][] dp = new int[n][n];

        // 从字符串的末尾开始遍历
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1; // 单个字符的回文子序列长度为1
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    // 如果字符相等，长度加2
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    // 如果字符不相等，取两种情况的最大值
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        // 返回整个字符串的最长回文子序列长度
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取输入字符串
        String s = scanner.nextLine();
        scanner.close();
        // 计算最长回文子序列的长度
        int result = longestPalindromeSubseq(s);
        // 输出结果
        System.out.println(result);
    }
}

第二题

题目描述

输入一个正整数N (1 ≤ N ≤ 44,777,444)，请你返回 k 个正整数 \(a_1, a_2, a_3..., a_k\)，满足 \({a_1}^3+a_2^3+a_3^3+...+a_k^3 = N\)，同时保证 k 的值最小。

返回长度为k的数组，并降序排序

示例： 输入：42 输出：2 2 2 2 2 1 1

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取输入的正整数 N
        int N = scanner.nextInt();
        scanner.close();

        // 预处理：生成所有不超过 N 的立方数
        List<Integer> cubes = new ArrayList<>();
        int maxCubeRoot = (int) Math.cbrt(N);
        for (int i = 1; i <= maxCubeRoot; i++) {
            cubes.add(i * i * i);
        }

        // 使用 BFS 或 A* 搜索最小的 k
        List<Integer> result = findMinCubes(N, cubes);

        // 将结果降序排序并输出
        Collections.sort(result, Collections.reverseOrder());
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i));
            if (i != result.size() - 1) {
                System.out.print(" ");
            }
        }
    }

    private static List<Integer> findMinCubes(int N, List<Integer> cubes) {
        // 使用 HashMap 存储每个状态的最小 k 值
        Map<Integer, List<Integer>> memo = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(N, new ArrayList<>()));

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            int remainder = current.remainder;
            List<Integer> path = current.path;

            // 如果已经计算过且当前路径长度不小于已存在的路径长度，跳过
            if (memo.containsKey(remainder) && memo.get(remainder).size() <= path.size()) {
                continue;
            }

            memo.put(remainder, path);

            if (remainder == 0) {
                return path;
            }

            // 尝试所有可能的立方数
            for (int i = cubes.size() - 1; i >= 0; i--) {
                int cube = cubes.get(i);
                if (cube <= remainder) {
                    List<Integer> newPath = new ArrayList<>(path);
                    newPath.add((int) Math.cbrt(cube));
                    queue.offer(new Node(remainder - cube, newPath));
                }
            }
        }

        // 理论上不会到这里，保证一定有解
        return new ArrayList<>();
    }

    static class Node {
        int remainder;
        List<Integer> path;

        Node(int remainder, List<Integer> path) {
            this.remainder = remainder;
            this.path = path;
        }
    }
}