外观
帆软
约 778 字大约 3 分钟
2025-02-27
帆软
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 个正整数 a1,a2,a3...,ak，满足 a13+a23+a33+...+ak3=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;
}
}
}