秋招面/笔试题目集合——08

第一题

思路：递归——》记忆化搜索

public class 第一题08 {
public static void main(String[] args) {
int[] A = {1,3,8,6,9,7,8};
int[] B = {2,3,7,9,4,6,7};
int res1 = minCost1(A, B);
System.out.println(res1);
int res2 = minCost1(A, B);
System.out.println(res2);
}
public static int minCost1(int[] A,int[] B){
return process1(A,B,0,0);
}
private static int process1(int[] A, int[] B, int ai, int bi) {
if (ai == A.length && bi == B.length){
return 0;
}
if (ai == A.length && bi != B.length){
return Math.abs(B[bi]) + process1(A,B,ai,bi + 1);
}
if (ai != A.length && bi == B.length){
return Math.abs(A[ai]) + process1(A,B,ai + 1,bi);
}
int p1 = Math.abs(B[bi]) + process1(A,B,ai,bi + 1);
int p2 = Math.abs(A[ai]) + process1(A,B,ai + 1,bi);
int p3 = Math.abs(A[ai] - B[bi]) + process1(A,B,ai + 1,bi + 1);
return Math.min(p1,Math.min(p2,p3));
}
public static int minCost2(int[] A,int[] B){
int n = A.length;
int m = B.length;
int[][] dp = new int[n][m];
for (int i = 0;i < n;i++){
for (int j = 0;j < m;j++){
dp[i][j] = -1;
}
}
return process2(A,B,0,0,dp);
}
private static int process2(int[] A, int[] B, int ai, int bi, int[][] dp) {
if (ai == A.length && bi == B.length){
return 0;
}
if (dp[ai][bi] != -1){
return dp[ai][bi];
}
if (ai == A.length && bi != B.length){
return Math.abs(B[bi]) + process2(A,B,ai,bi + 1, dp);
}
if (ai != A.length && bi == B.length){
return Math.abs(A[ai]) + process2(A,B,ai + 1,bi, dp);
}
int p1 = Math.abs(B[bi]) + process2(A,B,ai,bi + 1, dp);
int p2 = Math.abs(A[ai]) + process2(A,B,ai + 1,bi, dp);
int p3 = Math.abs(A[ai] - B[bi]) + process2(A,B,ai + 1,bi + 1, dp);
dp[ai][bi] = Math.min(p1,Math.min(p2,p3));
return dp[ai][bi];
}
}

第二题

思路：递归——》记忆化搜索

public class 第二题08 {
static class Info{
public int value;
public int cost;
public Info(int value,int cost){
this.value = value;
this.cost = cost;
}
}
public static int minCost1(String str) {
int n = str.length();
if (n < 3){
return -1;
}
int[] arr = new int[n];
for (int i = 0;i < n;i++){
char cur = str.charAt(i);
if (cur == 'd') {
arr[i] = 0;
} else if (cur == 'e') {
arr[i] = 1;
} else {
arr[i] = 2;
}
}
int maxValue = 0;
int minCost = Integer.MAX_VALUE;
for (int i = 0;i < 3;i++){
for (int j = 0;j < 3;j++){
int cost = arr[0] == i ? 0 : 1;
cost += arr[1] == j ? 0 : 1;
Info info = process1(arr,i,j,2);
if (info.value > maxValue){
maxValue = info.value;
minCost = info.cost + cost;
}else if (info.value == maxValue){
minCost = Math.min(info.cost,minCost);
}
}
}
return minCost;
}
private static Info process1(int[] arr, int prepre, int pre, int index) {
if (index == arr.length){
return new Info(0,0);
}
// 可能性1 ： [i] -> 0
int cost_1 = arr[index] == 0 ? 0 : 1;
int value_1 = prepre == 2 && pre == 1 ? 1 : 0;
Info p1 = process1(arr, pre, 0, index + 1);
// 可能性2 ： [i] -> 1
int cost_2 = arr[index] == 1 ? 0 : 1;
int value_2 = 0;
Info p2 = process1(arr, pre, 1, index + 1);
// 可能性3 ： [i] -> 2
int cost_3 = arr[index] == 2 ? 0 : 1;
int value_3 = prepre == 0 && pre == 1 ? 1 : 0;
Info p3 = process1(arr, pre, 2, index + 1);
int maxValue = 0;
int minCost = Integer.MAX_VALUE;
int p1_value = value_1 + p1.value;
int p1_cost = cost_1 + p1.cost;
int p2_value = value_2 + p2.value;
int p2_cost = cost_2 + p2.cost;
int p3_value = value_3 + p3.value;
int p3_cost = cost_3 + p3.cost;
if (p1_value > maxValue){
maxValue = p1_value;
minCost = p1_cost;
}else if (p1_value == maxValue){
minCost = Math.min(minCost,p1_cost);
}
if (p2_value > maxValue){
maxValue = p2_value;
minCost = p2_cost;
}else if (p2_value == maxValue){
minCost = Math.min(minCost,p2_cost);
}
if (p3_value > maxValue){
maxValue = p3_value;
minCost = p3_cost;
}else if (p3_value == maxValue){
minCost = Math.min(minCost,p3_cost);
}
return new Info(maxValue,minCost);
}
public static int minCost2(String str) {
int n = str.length();
if (n < 3){
return -1;
}
int[] arr = new int[n];
for (int i = 0;i < n;i++){
char cur = str.charAt(i);
if (cur == 'd') {
arr[i] = 0;
} else if (cur == 'e') {
arr[i] = 1;
} else {
arr[i] = 2;
}
}
int maxValue = 0;
int minCost = Integer.MAX_VALUE;
Info[][][] dp = new Info[n][3][3];
for (int i = 0;i < 3;i++){
for (int j = 0;j < 3;j++){
int cost = arr[0] == i ? 0 : 1;
cost += arr[1] == j ? 0 : 1;
Info info = process2(arr,i,j,2,dp);
if (info.value > maxValue){
maxValue = info.value;
minCost = info.cost + cost;
}else if (info.value == maxValue){
minCost = Math.min(info.cost,minCost);
}
}
}
return minCost;
}
private static Info process2(int[] arr, int prepre, int pre, int index, Info[][][] dp) {
if (index == arr.length){
return new Info(0,0);
}
if (dp[index][prepre][pre] != null){
return dp[index][prepre][pre];
}
// 可能性1 ： [i] -> 0
int cost_1 = arr[index] == 0 ? 0 : 1;
int value_1 = prepre == 2 && pre == 1 ? 1 : 0;
Info p1 = process2(arr, pre, 0, index + 1, dp);
// 可能性2 ： [i] -> 1
int cost_2 = arr[index] == 1 ? 0 : 1;
int value_2 = 0;
Info p2 = process2(arr, pre, 1, index + 1, dp);
// 可能性3 ： [i] -> 2
int cost_3 = arr[index] == 2 ? 0 : 1;
int value_3 = prepre == 0 && pre == 1 ? 1 : 0;
Info p3 = process2(arr, pre, 2, index + 1, dp);
int maxValue = 0;
int minCost = Integer.MAX_VALUE;
int p1_value = value_1 + p1.value;
int p1_cost = cost_1 + p1.cost;
int p2_value = value_2 + p2.value;
int p2_cost = cost_2 + p2.cost;
int p3_value = value_3 + p3.value;
int p3_cost = cost_3 + p3.cost;
if (p1_value > maxValue){
maxValue = p1_value;
minCost = p1_cost;
}else if (p1_value == maxValue){
minCost = Math.min(minCost,p1_cost);
}
if (p2_value > maxValue){
maxValue = p2_value;
minCost = p2_cost;
}else if (p2_value == maxValue){
minCost = Math.min(minCost,p2_cost);
}
if (p3_value > maxValue){
maxValue = p3_value;
minCost = p3_cost;
}else if (p3_value == maxValue){
minCost = Math.min(minCost,p3_cost);
}
dp[index][prepre][pre] = new Info(maxValue,minCost);
return dp[index][prepre][pre];
}
public static void main(String[] args) {
int res1 = minCost1("redeeerreredeeerre");
System.out.println(res1);
int res2 = minCost2("redeeerreredeeerre");
System.out.println(res2);
}
}

最后

以上就是饱满香烟为你收集整理的秋招面/笔试题目集合——08的全部内容，希望文章能够帮你解决秋招面/笔试题目集合——08所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。