今晚做了科大讯飞的笔试题，题型是4道编程题，时长为120分钟，第一次ak，无比激动~
1. 礼物价值的最大化
这是剑指offer的一道关于动态规划的题目，前不久才做过，所以很快就做出来了
/**
* @Author Baker.chen
* @create 2020/8/29 20:31
*
* 礼物价值最大化
* 思路：创建一个二维数组dp[][],dp[i][j]代表的是从二维数组的左上角元素走到dp[i][j]这个单元格的最大价值
* 状态转移方程为：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + dp[i][j]
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String[] str = s.split(",");
int m = Integer.parseInt(str[0]);
int n = Integer.parseInt(str[1]);
int[][] arr = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
}
}
int res = max(arr);
System.out.println(res);
}
public static int max(int[][] arr) {
for (int i = 1; i < arr.length; i++) {
arr[i][0] = arr[i][0] + arr[i - 1][0];
}
for (int j = 1; j < arr[0].length; j++) {
arr[0][j] = arr[0][j] + arr[0][j - 1];
}
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j < arr[0].length; j++) {
arr[i][j] = arr[i][j] + Math.max(arr[i - 1][j], arr[i][j - 1]);
}
}
return arr[arr.length - 1][arr[0].length - 1];
}
} 2. 排序 不得不说，这道题的题意有点点坑，第一个坑就是给出了部分序列的变化情况采样，一开始还以为是快速排序；第二个坑就是数组的输入竟然是以逗号隔开的，刚开始没注意这个细节，出现case通过为0，百思不得其解，最后认真读了一遍题意，才发现（细心读题很重要啊~）
/**
* @Author Baker.chen
* @create 2020/8/29 19:09
*
* 选择排序
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if (n <= 0) {
return;
}
sc.nextLine();
int[] arr = new int[n];
String s = sc.nextLine();
String[] str = s.split(",");
for (int i = 0; i < str.length; i++) {
arr[i] = Integer.parseInt(str[i]);
}
selectSort(arr);
for (int j = 0; j < arr.length; j++) {
if (j == arr.length - 1) {
System.out.print(arr[j]);
}else {
System.out.print(arr[j] + ",");
}
}
}
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp =arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
} 3. 字符串的过滤 这道题是花费最长时间的，一开始是想用暴力的方法，用多个if循环进行判断过滤，case通过始终只有75%，（还是不知道原因出在哪里），最后有剩余时间回过头来继续做这道题，才想起可以使用正则表达式进行过滤，代码十分简洁
/**
* @Author Baker.chen
* @create 2020/8/29 19:36
*
* 字符串过滤
* 思路：先用java的正则表达式将下划线超过2的替换成一个下划线； * 再判断过滤后的字符串前后是否还有一个下划线，有则进一步过滤
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String str = s.replaceAll("[_]{2,}", "_");
if (str.charAt(0) == '_') {
str = str.substring(1, str.length());
}
if (str.charAt(str.length() - 1) == '_') {
str = str.substring(0, str.length() - 1);
}
System.out.println(str);
}
}
4. 分解质因数 这道题也是以前做过的，只不过之前用的是非递归实现，这次题目要求的是要用递归实现
/**
* @Author Baker.chen
* @create 2020/8/29 20:13
*
* 分解质因数
*
* 思路：
* 1. 首先设置一个变量k，k的值等于最小素数2，注意变量k应该声明为类成员变量，不能声明在方法中，否则多次递归调用方***导致栈内存溢出
* 2. 如果质数恰好等于n，代表分解已结束
* 3. 若n>k，但n能被k整除，先打印k值，并用n除以k的商作为新的n，然后递归执行
* 4. 若n不能被k整除，则用k+1作为k的值，然后递归执行
*/
public class Main {
private static int k = 2;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
f(n);
}
public static void f(int n) {
while (k <= n) {
if (k == n) {
System.out.print(n);
break;
} else if (n > k && n % k == 0) {
System.out.print(k + "*");
n = n / k;
f(n);
break;
} else if(n > k && n % k != 0) {
k = k + 1;
f(n);
break;
}
}
}
} 
全部评论
(1) 回帖