8.27京东笔试AC记录 Java岗
第一题
找规律，跟leetcode上的一道题比较相似，题号记不清了....
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int digit = 1;
int i = 3;
String res = "";
while(n-i > 0) {
n -= i;
i*=3;
digit++;
}
while(digit>0) {
int count = (int)Math.pow(3, digit-1);
int num = (n-1)/count;
res += num==0? "2":num==1? "3":"5";
n -= (num*count);
digit--;
}
System.out.println(res);
} 第二题
倒推dp应该是最优解法，我直接暴力dfs....居然过了
import java.util.*;
public class Main {
static int max = 0;
static int[][] map;
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n = sc.nextInt();
map = new int[n][2 * n-1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 2 * i -1; j++) {
map[i-1][j-1] = sc.nextInt();
}
}
dfs(0,0,0,n);
System.out.println(max);
}
private static void dfs(int i, int j, int sum,int n) {
if(i == n) max = Math.max(max,sum);
else{
for(int k = 0; k < 3; k++) {
dfs(i+1,j+k,sum + map[i][j],n);
}
}
}
} 