拼多多8.2笔试（第四题添加非回溯算法）
比较菜，笔试四道题一道都没有Ac.
1. 90%
2. 0%
3. 50%
4. 0% 刚刚把这道题磕出来了
第一题一直是90%，好像是哪里的边界不太对。把自己代码发出来给大家分享一下。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* @Description:
* @Create 2020-08-02 19:02
* @Email:
*/
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = null;
while ((s = br.readLine()) != null) {
String[] s1 = s.split(" ");
int K = Integer.valueOf(s1[0]);
int N = Integer.valueOf(s1[1]);
int[] arr = new int[N];
s1 = br.readLine().split(" ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.valueOf(s1[i]);
}
String res = function1(K, N, arr);
System.out.println(res);
}
br.close();
}
private static String function1(int k, int n, int[] arr) {
int now = 0;
int count = 0;
boolean isRight = true;
for (int i = 0; i < n; i++) {
if (i == n - 1 && now == k) {
return "paradox";
}
// 每次开始都是往右走
isRight = true;
for (int j = 0; j < arr[i]; j++) {
if (now == k) {
// 换方向
isRight = false;
count++;
}
if (now == 0) {
// 换方向
isRight = true;
}
if (isRight) {
now++;
} else {
now--;
}
}
}
int dis = k - now;
return dis + " " + count;
}
}
第二题没有写，自己太菜看不太懂，第三题食堂营养餐的那个题，我暴力过了50%，想不到好的思路，不知道有没有大佬分享一下代码。
import java.awt.event.MouseAdapter;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* @Description:
* @Create 2020-08-02 19:57
* @Email:
*/
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = null;
while ((s = br.readLine()) != null) {
String[] s1 = s.split(" ");
int N = Integer.valueOf(s1[0]);
int M = Integer.valueOf(s1[1]);
int T = Integer.valueOf(s1[2]);
int[][] lunch = new int[N][2];
int[][] dinner = new int[M][2];
int max = Integer.MIN_VALUE; // 中餐最大营养值
int max2 = Integer.MIN_VALUE; // 晚餐最大营养值
for (int i = 0; i < N; i++) {
s1 = br.readLine().split(" ");
lunch[i][0] = Integer.valueOf(s1[0]);
lunch[i][1] = Integer.valueOf(s1[1]);
max = Math.max(max, lunch[i][1]);
}
for (int i = 0; i < M; i++) {
s1 = br.readLine().split(" ");
dinner[i][0] = Integer.valueOf(s1[0]);
dinner[i][1] = Integer.valueOf(s1[1]);
max2 = Math.max(max2, dinner[i][1]);
}
if (max + max2 < T) {
System.out.println(-1);
continue;
}
int res = function(lunch, dinner, T);
System.out.println(res);
}
br.close();
}
private static int function(int[][] lunch, int[][] dinner, int t) {
if (t == 0) return 0;
int n = lunch.length;
int m = dinner.length;
int dis = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (lunch[i][1] >= t) {
dis = Math.min(dis, lunch[i][0]);
}
for (int j = 0; j < m; j++) {
if (lunch[i][1] + dinner[j][1] >= t) {
dis = Math.min(dis, lunch[i][0] + dinner[j][0]);
}
}
}
for (int j = 0; j < m; j++) {
if (dinner[j][1] >= t) {
dis = Math.min(dis, dinner[j][0]);
}
}
if (dis != Integer.MAX_VALUE) return dis;
return -1;
}
}
第四题，就是种菜问题，能种的地方用'#'表示，每个地方中的菜不能和周围四个方向的菜相同，总共有6中菜可供选择，大概是这个意思，求出6*6矩阵中总共可能的次数
考完后磕了半天做出来了，题目用例都是对的，分享一下，不知道有没有人分享一下优化思路。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
用例1
##****
##****
******
******
******
******
* 630 1000000009
*
*
*
*/
/*
用例2
#*****
******
******
******
******
*****#
* 36
*/
/**
* @Description:
* @Create 2020-08-02 20:16
* @Email:
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = null;
char[][] matrix = new char[6][6];
while ((s = br.readLine()) != null) {
matrix[0] = s.toCharArray();
for (int i = 0; i < 5; i++) {
matrix[i + 1] = br.readLine().toCharArray();
}
int res = function(matrix);
System.out.println(res);
}
br.close();
}
static int[][] dd = new int[36][6];
static int res = 0;
static int Num = 0;
private static int function(char[][] matrix) {
res = 0;
int num = 0;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
if (matrix[i][j] == '#') {
num++;
}
}
}
Num = num;
backTrack(matrix, 0, 0, 0);
return res;
}
private static void backTrack(char[][] matrix, int count, int row, int col) {
if (count == Num) {
res++;
res %= 1000000009;
return;
}
int before = row*6 + col;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
if (i * 6 + j < before) { // 保证往后遍历 避免重复
continue;
}
if (matrix[i][j] == '#') {
int index = i * 6 + j;
for (int t = 0; t < 6; t++) {
if (check(i, j, t)) {// 如果能放
matrix[i][j] = '*'; // 打个标记
dd[index][t] = 1; // 记录这个位置中的植物
backTrack(matrix, count + 1, i, j);
dd[index][t] = 0; // 撤销
matrix[i][j] = '#'; // 撤销
}
}
}
}
}
return;
}
// 周围四个方向
static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
/**
* 检查周围 看看当前位置能不能中这类植物
*
* @param row
* @param col
* @param kind
* @return */
private static boolean check(int row, int col, int kind) {
for (int[] arr : dir) {
int x = row + arr[0];
int y = col + arr[1];
if (x >= 0 && x < 6 && y >= 0 && y < 6) {
int index = x * 6 + y;
if (dd[index][kind] == 1) return false;
}
}
return true;
}
}
第四题，添加一个非回溯算法，回溯确实很花时间，大家感兴趣可以看看这个算法。加了点注释，代码我测了，和回溯结果一样的
结果没问题。感兴趣可以自己可以测一下，可能有的逻辑想的不太好，所以代码写的很繁琐。
/**
* 一个一个往后检测
*
* @param matrix
* @return
*/
private static int dpFunction(char[][] matrix) {
int[][] dp = new int[6][6];
boolean flag = false;
int pre = 0; // 保存前一个点可能的数
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
pre %= 1000000009;
if (matrix[i][j] == '*') {
//如果不能种直接跟随前一个状态
dp[i][j] = pre;
continue;
} else {
if (!flag) {//保证这里代码只执行一次
dp[i][j] = 6;
pre = 6;
flag = true;
} else {
// 如果能种并且在第一列时
if (j == 0) {
// 如果还在第一行
if (i == 0) {
dp[i][j] = pre * 5;
pre = dp[i][j];
continue;
}
// 如果不在第一行
/*
** *
* #
*/
if (matrix[i - 1][j] == '*') {
dp[i][j] = pre * 6;
pre = dp[i][j];
} else {
dp[i][j] = pre * 5;
pre = dp[i][j];
}
} else {
// 如果能种 且不在第一列的情况
// 如果还在第一行
if (i == 0) {
if (matrix[i][j - 1] == '#') {
dp[i][j] = pre * 5;
} else {
dp[i][j] = pre * 6;
}
pre = dp[i][j];
continue;
}
// 然后四种情况讨论
if (matrix[i][j - 1] == '*' && matrix[i - 1][j] == '*') {
dp[i][j] = pre * 6;
pre = dp[i][j];
continue;
}
if (matrix[i][j - 1] == '*' && matrix[i - 1][j] == '#') {
dp[i][j] = pre * 5;
pre = dp[i][j];
continue;
}
if (matrix[i][j - 1] == '#' && matrix[i - 1][j] == '*') {
dp[i][j] = pre * 5;
pre = dp[i][j];
continue;
}
// 主要是这一种的判断
/*
* **#
* *##
*
* 当左边和上边相同的菜时 要乘以5
* 不同时乘以4 根据前一个状态写出下边递推方程
*/
if (matrix[i][j - 1] == '#' && matrix[i - 1][j] == '#') {
dp[i][j] = pre * 4 + dp[i - 1][j];
pre = dp[i][j];
continue;
}
}
}
}
}
}
return pre % 1000000009;
} 
投递阿里云等公司10个岗位