牛客网——网易2017秋招编程题集合解题报告(下)

前四题的解答:牛客网——网易2017秋招编程题集合解题报告(上)

Q5.数字翻转

题目描述:对于一个整数X,定义操作rev(X)为将X按数位翻转过来,并且去除掉前导0。例如:
如果 X = 123,则rev(X) = 321;
如果 X = 100,则rev(X) = 1.
现在给出整数xy,要求rev(rev(x) + rev(y))为多少?


输入描述:
输入为一行,x、y(1 ≤ x、y ≤ 1000),以空格隔开。

输出描述:
输出rev(rev(x) + rev(y))的值

输入例子1:
123 100

输出例子1:
223


思路解析:此题较为简单,用Java实现的话只需使用StringBuilderreverse()结合Integer.parseInt()即可AC

直接贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Scanner;
/**
* Created by dean on 2017/8/9.
*/
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int x = scan.nextInt();
int y = scan.nextInt();
StringBuilder sbX = new StringBuilder(String.valueOf(x));
StringBuilder sbY = new StringBuilder(String.valueOf(y));
StringBuilder sb = new StringBuilder(String.valueOf(Integer.parseInt(sbX.reverse().toString()) + Integer.parseInt(sbY.reverse().toString())));
System.out.println(Integer.parseInt(sb.reverse().toString()));
}
}

Q6.最大的奇约数

题目描述:小易是一个数论爱好者,并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题: 定义函数f(x)x最大的奇数约数,x为正整数。 例如:f(44) = 11.
现在给出一个N,需要求出 f(1) + f(2) + f(3).......f(N)
例如: N = 7
f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 1 + 3 + 1 + 5 + 3 + 7 = 21
小易计算这个问题遇到了困难,需要你来设计一个算法帮助他。


输入描述:
输入一个整数N (1 ≤ N ≤ 1000000000)

输出描述:
输出一个整数,即为f(1) + f(2) + f(3).......f(N)

输入例子1:
7

输出例子1:
21


思路解析:首先N的范围是1 ≤ N ≤ 1000000000,暴力肯定会超时。从偶数和奇数分开考虑:

  1. 对于奇数,本身就是最大的奇数约数,只需要加上其本身,所以这部分可以使用等差数列的求和公式计算
  2. 对于偶数,求其最大的约数,首先2是所有偶数除了1以外的最小约数,可以考虑将偶数除以2,再去判断其奇偶性。然后重复1、2过程

根据上面的分析,显然可以考虑使用递归解决
Tips:对于N本身的奇偶性需要判断处理,另外int会越界,需要使用long

下面贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Scanner;
/**
* Created by dean on 2017/8/9.
*/
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long n = scan.nextLong();
System.out.println(helper(n));
}
public static long helper(long n) {
if (n == 1) return 1;
long res = 0;
long k = n / 2;
if (n % 2 == 1) {
n--;
k += 1;
}
res += (k + k * (k - 1));
return res + helper(n / 2);
}
}

Q7.买苹果

题目描述:小易去附近的商店买苹果,奸诈的商贩使用了捆绑交易,只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果,小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果,小易将不会购买。


输入描述:
输入一个整数n,表示小易想购买n(1 ≤ n ≤ 100)个苹果

输出描述:
输出一个整数表示最少需要购买的袋数,如果不能买恰好n个苹果则输出-1

输入例子1:
20

输出例子1:
3


思路分析:求的是最少需要购买的袋数,从题意可知,8个每袋的数量越多则总袋数越少,可从这一点出发使用贪心策略,设i为8个每袋的数量并初始化为合法最大值n/8,设j为6个每袋的数量,然后循环通过减小i和增大j直到总数量等于n

下面上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Scanner;
/**
* Created by dean on 2017/8/9.
*/
public class Item7 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int i = n / 8;
int j = (n - i * 8) / 6;
int count = i * 8 + j * 6;
while (count != n) {
if (i == 0) {
System.out.println(-1);
return;
}
if (count < n) {
j++;
} else if (count > n) {
i--;
}
count = i * 8 + j * 6;
}
System.out.println(i + j);
}
}

Q8.计算糖果

题目描述:A,B,C三个人是好朋友,每个人手里都有一些糖果,我们不知道他们每个人手上具体有多少个糖果,但是我们知道以下的信息:
A - B, B - C, A + B, B + C. 这四个数值.每个字母代表每个人所拥有的糖果数.
现在需要通过这四个数值计算出每个人手里有多少个糖果,即A,B,C。这里保证最多只有一组整数A,B,C满足所有题设条件。


输入描述:
输入为一行,一共4个整数,分别为A - BB - CA + BB + C,用空格隔开。
范围均在-30到30之间(闭区间)。

输出描述:
输出为一行,如果存在满足的整数A,B,C则按顺序输出A,B,C,用空格隔开,行末无空格。
如果不存在这样的整数A,B,C,则输出No

输入例子1:
1 -2 3 4

输出例子1:
2 1 3


思路分析:本题较为简单。通过给定的四个数的定义

  1. A - B
  2. B - C
  3. A + B
  4. B + C

可以得到①+③=2A,②+④=2B,④-②=2C,求出·A,B,C·之后,再对条件进行验证即可


下面上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
/**
* Created by dean on 2017/8/9.
*/
public class Item8 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n1 = scan.nextInt();
int n2 = scan.nextInt();
int n3 = scan.nextInt();
int n4 = scan.nextInt();
int a = (n1 + n3) / 2;
int b = (n2 + n4) / 2;
int c = (n4 - n2) / 2;
if (a - b == n1 && b - c == n2 && a + b == n3 && b + c == n4) {
System.out.printf("%d %d %d\n", a, b, c);
} else {
System.out.println("No");
}
}
}