给了2个小时时间。
30道选择题，2道编程题。
（上一篇帖子我删了 差点成了答案分享区🤣
编程题第一题:
题面
某人只喜欢数字 2， 3， 5这三个数字，如222，333，235这样的。但是12345这样就不是他喜欢的，因为包含了除了2，3，5以外的数字。
现询问这个人喜欢的第n个数字（升序排列的第n个数字）是多少。 n <= 1000；
思路
考虑1000的数据范围并不大。所以可以直接预处理前1000项。
可以以数字的位数作为枚举量，弄出所有的组合而成的数字。
如数字长度为1位时，有2，3，5，这3种情况。
数字长度为2时，有22，23，25，33，32，35，55，52，53。这9种情况。
考虑到这里，我们就不难想到，我们可以枚举第i位的数字，直到长度为预期值即可。
以长度为2举例，首位可能是2，3，5.第二位可能是2，3，5。所以直接深搜即可。
参考代码:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[] vis = new int[100];
public static void main(String[] args) {
int[] arr = solve();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(arr[n - 1]);
}
public static int[] solve(){
ArrayList<Integer> arr = new ArrayList<>();
demo:
for(int i = 1; arr.size() <= 1000; i++){
dfs(0, i, arr);
}
int[] result = new int[arr.size()];
for(int i = 0; i < arr.size(); i++){
result[i] = arr.get(i);
}
Arrays.sort(result);
return result;
}
public static void dfs(int k, int n, ArrayList<Integer> arr){
if(k == n){
int val = 0;
for(int i = 0; i < n; i++){
val = val * 10 + vis[i];
}
arr.add(val);
return ;
}
vis[k] = 2;
dfs(k + 1, n, arr);
vis[k] = 3;
dfs(k + 1, n, arr);
vis[k] = 5;
dfs(k + 1, n, arr);
}
}
第二题
题目：
给你一个二维数组，每次可以往左下，正下，右下走。 询问得到的最大值。
输入n， 代表n行， 每行2 * n - 1个元素。
示例如下图:
思路:
类似于经典的那个三角形之类的dp。
比较简单的做法就是在原数组上直接做；
我们考虑这个过程，第二行第二列这个元素，只能到达第三行1，2，3列这三个元素中的某一个。
所以我们可以倒推，若得到的最大值经过了第二行第二列这个元素，那么第三行取到的一定是max(arr[3][1],arr[3][2],arr[3][3]);
Ok,同理若取了arr[2][3]这个元素，且得到了最大值，那么，则第三行取的必是max(arr[3][2], arr[3][3], arr[3][4]);
。。。。。
都是这样，
对于第k行的每个元素，其整个链取最大时，则必取第k+1行的左下，下方，右下三个元素中的最大值。
即 arr[i][j] = arr[i][j] + max(arr[i + 1][j - 1], arr[i + 1][j], arr[i + 1][j + 1]);
从第n-1行开始转移，直到转移到arr[1][n]这个元素，那么arr[1][n]这个元素，就是整个链的最大值。
参考代码:
import java.util.Scanner;
public class Two {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[][] arr = new long[n + 1][2 * n];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= 2 * i - 1; j++){
arr[i][n - i + j] = sc.nextLong();
}
}
for(int i = n - 1; i >= 1; i--){
for(int j = 1; j <= 2 * i - 1; j++){
arr[i][n - i + j] += Math.max(Math.max(arr[i + 1][n - i + j - 1], arr[i + 1][n - i + j]), arr[i + 1][n - i + j + 1]);
}
}
System.out.println(arr[1][n]);
}
}
代码中的n - i， 为每列的前缀空个数。
全部评论
(15) 回帖