题目来源：牛客网https://www.nowcoder.com/contestRoom?filter=2&page=1
一、魔法币问题
题目描述：
小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。
魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币
魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币
小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币。
输入描述:
输入包括一行,包括一个正整数n(1 ≤ n ≤ 10^9),表示小易需要的魔法币数量。
输出描述:
输出一个字符串,每个字符表示该次小易选取投入的魔法机器。其中只包含字符’1’和’2’。
输入例子1:
10
输出例子1:
122
java代码：
import java.util.Scanner;
public class Main{
/** * 解题思路： * 根据题目描述，不难发现采用倒推的原则，我们可以逐步得出输出序列的 * 的倒序序列。例如：n=10,则我们首先判断其为偶数，则应该最后一步采 * 的是机器2。接着利用递归将n修改为(n-2)/2,再判断奇数还是偶数。 * @param n * @return */
public static String printStrOfMoFa(int n){
String result ="";
//判断边界
if(n<=0 || n > Math.pow(10.0, 9.0))
return null;
if(n == 1)
return "1";
if(n == 2)
return "2";
if(n % 2 ==1){ //如果n为奇数
n = (n-1)/2;
result = printStrOfMoFa(n) + "1"; //选用１号机器
}else{ //如果n为偶数
n = (n-2)/2;
result = printStrOfMoFa(n) + "2"; //选用2号机器
}
return result;
}
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
//System.out.println("请输入需要魔法币的数量");
int numOfMfb = reader.nextInt();
String result = printStrOfMoFa(numOfMfb);
System.out.println(result);
}
}二、相反数
题目描述：
为了得到一个数的”相反数”,我们将这个数的数字顺序颠倒,然后再加上原先的数得到”相反数”。例如,为了得到1325的”相反数”,首先我们将该数的数字顺序颠倒,我们得到5231,之后再加上原先的数,我们得到5231+1325=6556.如果颠倒之后的数字有前缀零,前缀零将会被忽略。例如n = 100, 颠倒之后是1.
输入描述:
输入包括一个整数n,(1 ≤ n ≤ 10^5)
输出描述:
输出一个整数,表示n的相反数
输入例子1:
1325
输出例子1:
6556
java代码：
import java.util.Scanner;
public class Main{
/** * 网易2018编程题 * 解题思路： * 将整数转换为字符串再求倒序，问题迎刃而解 * @param n * @return */
public static int outPutReverseNumber(int n){
if(n<=0 || n> Math.pow(10.0, 5.0))
return 0;
//将整数转换为字符串
String strOfNum = String.valueOf(n);
String newStr = "";
//将字符串倒序
for(int i=0;i<strOfNum.length();i++)
newStr = strOfNum.charAt(i) + newStr;
int k=0;
for(int i=0;i<newStr.length();i++){
if(newStr.charAt(i) == '0') //如果开始字符串为0
k++;
else
break;
}
//去掉字符串开头的0
newStr = newStr.substring(k);
return Integer.parseInt(newStr)+n;
}
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
//System.out.println("输入整数：");
int n = reader.nextInt();
System.out.println(outPutReverseNumber(n));
}
}三、字符串碎片
题目描述：
一个由小写字母组成的字符串可以看成一些同一字母的最大碎片组成的。例如,”aaabbaaac”是由下面碎片组成的:’aaa’,’bb’,’c’。牛牛现在给定一个字符串,请你帮助计算这个字符串的所有碎片的平均长度是多少。
输入描述:
输入包括一个字符串s,字符串s的长度length(1 ≤ length ≤ 50),s只含小写字母(‘a’-‘z’)
输出描述:
输出一个整数,表示所有碎片的平均长度,四舍五入保留两位小数。
如样例所示: s = “aaabbaaac”
所有碎片的平均长度 = (3 + 2 + 3 + 1) / 4 = 2.25
输入例子1:
aaabbaaac
输出例子1:
2.25
java代码：
import java.util.Scanner;
public class Main{
/** * 网易2018编程题--字符串碎片 * @param str * @return */
public static double averageOfStrPieces(String str){
int numOfPieces = 1; //记录最大碎片的个数
for(int i=0;i<str.length()-1;i++){
if(str.charAt(i) != str.charAt(i+1))
numOfPieces++;
}
float length = str.length();
return length/numOfPieces;
}
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
//System.out.println("输入字符串：");
String testStr = reader.nextLine();
//DecimalFormat df = new DecimalFormat("0.00");//格式化小数
//String num = df.format(averageOfStrPieces(testStr));//返回的是String类型
System.out.println(String.format("%.2f",averageOfStrPieces(testStr)));
reader.close();
}
}四、游历魔法王国
题目描述：
魔法王国一共有n个城市,编号为0~n-1号,n个城市之间的道路连接起来恰好构成一棵树。
小易现在在0号城市,每次行动小易会从当前所在的城市走到与其相邻的一个城市,小易最多能行动L次。
如果小易到达过某个城市就视为小易游历过这个城市了,小易现在要制定好的旅游计划使他能游历最多的城市,请你帮他计算一下他最多能游历过多少个城市(注意0号城市已经游历了,游历过的城市不重复计算)。
输入描述:
输入包括两行,第一行包括两个正整数n(2 ≤ n ≤ 50)和L(1 ≤ L ≤ 100),表示城市个数和小易能行动的次数。
第二行包括n-1个整数parent[i](0 ≤ parent[i] ≤ i), 对于每个合法的i(0 ≤ i ≤ n - 2),在(i+1)号城市和parent[i]间有一条道路连接。
输出描述:
输出一个整数,表示小易最多能游历的城市数量。
输入例子1:
5 2
0 1 2 3
输出例子1:
3
java代码：
import java.util.Scanner;
public class Main{
/** * 网易2018编程题--游历魔法王国 * @param n 城市数量 * @param L 移动步长 * @param parent 各城市之间的道路连通关系 * @return */
public static int mostCityTraveld(int n,int L,int[] parent){
if(n<2 || n>50 || L<1 || L>100)
return 0;
int[] dp = new int[200]; //动态规划处理
int max=0; // 存储最大路径
//找到树中的最大路径
for(int i=0;i<n-1;i++){
dp[i+1] = dp[parent[i]]+1;
if(max < dp[i+1])
max = dp[i+1];
}
//将最大路径与小易的移动次数作比较，如果移动次数小于最大路径max，则最终结果即为L+1;
//如果移动次数L大于最大路径max,则最终结果为(L-max)/2 + max +1
//此时，最终路径选择可以理解为先在非最大路径上来回走L-d步，回到根节点；然后从根节点开始走最大路径d步
int d = Math.min(max,L); //选取路径和移动次数中较小的一个
return (L-d)/2 + d +1;
}
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
int nCity =0,nStep =0;
//输入两行参数
String ss1 = reader.nextLine();
String[] str1 = ss1.split(" ");
String ss2 = reader.nextLine();
String[] str2 = ss2.split(" ");
nCity = Integer.parseInt(str1[0]);
nStep = Integer.parseInt(str1[1]);
int[] parent = new int[nCity-1];
for(int i=0;i<nCity-1;i++)
parent[i]=Integer.parseInt(str2[i]);
System.out.println(mostCityTraveld(nCity,nStep,parent));
reader.close();
}
}