第一题
某人只喜欢数字 2， 3， 5这三个数字，如222，333，235这样的。但是12345这样就不是他喜欢的，因为包含了除了2，3，5以外的数字。
现询问这个人喜欢的第n个数字（升序排列的第n个数字）是多少。 n <= 1000；
例如 n 等于 5 时，答案为 23。
因为升序排序依次为 2，3，5，22，23。。。所以第5个数字为23.
思路：
N<=3特殊处理，N>3时，先将2,3,5加入列表，并使N=N-3,
每次循环先记录列表长度size，从2,3,5中一次取一个数num，如num=2，列表中为22,23,25，则可依次组成222,223,225，每生成一个数执行N=N-1，当N==0及当前生成的数为所求的数，N！=0就将该数加入列表末端；
当2，3,，5都遍历完再将列表前size个数移除；
public class Test {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
long result=getResult(n);
System.out.print(result);
}
static int[] nums={2,3,5};
private static long getResult(int n) {
if (n<=0)return -1;
if(n==1)return 2;
if(n==2)return 3;
if(n==3)return 5;
List<Long> list=new LinkedList<Long>();
list.add(2L);
list.add(3L);
list.add(5L);
n-=3;
while (!list.isEmpty()&&n>0){
int size=list.size();
for (int i = 0; i < nums.length; i++) {
long num=nums[i];
for (int j = 0; j < size; j++) {
long item=Long.valueOf(num+""+list.get(j));
n--;
if (n==0){
return item;
}
list.add(item);
}
}
for (int i = 0; i < size; i++) {
list.remove(0);
}
}
return -1;
}
}
第二题
某滚球游戏规则如下：球从入口处（第一层）开始向下滚动，每次可向下滚动一层，直到滚至最下面一层为止。球每次可滚至左下、下方或右下三个方格中的任意一个，每个方格都有一个得分，如下图所示。第1层有1个方格，第2层有3个方格，……，以此类推，第n层有2*n-1个方格。设计一个算法，使得球从入口滚至最下面一层的总得分和最大思路
从倒数第二层开始遍历，nums[i][j]=max(nums[i+1][j-1],nums[i+1][j],nums[i+1][j+1])+nums[i][j];然后返回nums[0][nums.length-1],
public class Test2 {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
if (n>=1){
long[][] nums=new long[n][2*n-1];
for (int i = 0; i < n; i++) {
int startIndex=n-i-1;
for (int j = 0; j <2*(i+1)-1; j++) {
nums[i][startIndex++]=input.nextInt();
}
}
long result=getResult(nums);
System.out.println(result);
}else {
System.out.println(-1);
}
}
private static long getResult(long[][] numbers) {
for (int i = numbers.length - 2; i >=0 ; i--) {
int start=numbers.length-i-1;
for (int j = 0; j < (i+1) * 2 - 1; j++) {
numbers[i][start]+=Math.max(numbers[i+1][start-1],Math.max(numbers[i+1][start],numbers[i+1][start+1]));
start++;
}
}
return numbers[0][numbers.length-1];
}
}
下面的代码需要n*n的矩阵进行存储，其实还可以优化，直接只存输入的数就行了列入
i=0--1
i=1--1 2 1
i=2--2 3 4 1 3
i=3--5 2 4 6 7 8 6
nums[i][j]=max(nums[i+1][j-1],nums[i+1][j],nums[i+1][j+1])+nums[i][j];然后返回nums[0][nums.length-1],
i=1--1 2 1
i=2--2 3 4 1 3
i=3--5 2 4 6 7 8 6
nums[i][j]=max(nums[i+1][j-1],nums[i+1][j],nums[i+1][j+1])+nums[i][j];然后返回nums[0][nums.length-1],
全部评论
(0) 回帖