第一题 第n个数
2，3，5组合成数字，可重复使用，求从小到大第n个
思路：从全排列树找规律，组成的数字从小到大就是全排列树层次遍历的顺序。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n+1];
nums[1] = 2;
nums[2] = 3;
nums[3] = 5;
for (int i = 4; i < n + 1; i++) {
if(i % 3 == 1){
nums[i] = nums[(i-1)/3] * 10 + 2;
}else if(i % 3 == 2){
nums[i] = nums[(i-2)/3] * 10 + 3;
}else{
nums[i] = nums[(i-3)/3] * 10 + 5;
}
}
System.out.println(nums[n]);
}
} 第二题
在金字塔中找路径和最大值，从顶部开始，可向下，左下，右下。
思路：从顶部开始遍历，计算当前结点可移动到的位置，也就是下一层对应的三个结点。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] nums = new int[n][2*n+1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2 * i + 1; j++) {
nums[i][j] = scanner.nextInt();
}
}
int[][] dp = new int[n][2*n+1];
dp[0][0] = nums[0][0];
int res = 0;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < 2 * i + 1; j++) {
dp[i+1][j] = Math.max(dp[i+1][j],dp[i][j]+nums[i+1][j]);
dp[i+1][j+1] = Math.max(dp[i+1][j+1],dp[i][j]+nums[i+1][j+1]);
dp[i+1][j+2] = Math.max(dp[i+1][j+2],dp[i][j]+nums[i+1][j+2]);
}
}
for (int i = 0; i < 2*n+1; i++) {
res = Math.max(res,dp[n-1][i]);
}
System.out.println(res);
}
} 第一次写，写的不好请见谅😅😅
全部评论
(2) 回帖