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

一共8题,题目链接在这儿:牛客网


Q1.回文序列

如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如:
{1, 2, 1}, {15, 78, 78, 15} , {112} 是回文序列,
{1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是回文序列。
现在给出一个数字序列,允许使用一种转换操作:
选择任意两个相邻的数,然后从序列移除这两个数,并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。
现在对于所给序列要求出最少需要多少次操作可以将其变成回文序列。


输入描述:
输入为两行,第一行为序列长度n ( 1 ≤ n ≤ 50)
第二行为序列中的n个整数item[i] (1 ≤ iteam[i] ≤ 1000),以空格分隔。

输出描述:
输出一个数,表示最少需要的转换次数

输入例子1:
4
1 1 1 3

输出例子1:
2


思路解析:可以看到题目是求最少翻转次数,结合回文串的定义,可以采用贪心策略,设定两个指针,一个从前往后,一个从后往前

  • 两者相等时,两个指针继续移动
  • 两者不等时,较小那侧指针则和邻居节点合并,并移动
  • 重复以上过程直到相遇

Tip: 根据题意,此题肯定是有解的,最坏的情况为合并所有数为一个数

下面上代码

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
28
29
30
31
32
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 n = scan.nextInt();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = scan.nextInt();
}
int i = 0, j = n - 1;
int count = 0;
while (i <= j) {
if (i + 1 < n && num[i] < num[j]) {
num[i + 1] += num[i];
i++;
count++;
} else if (j - 1 > 0 && num[i] > num[j]) {
num[j - 1] += num[j];
j--;
count++;
} else {
i++;
j--;
}
}
System.out.println(count);
}
}

Q2.优雅的点

小易有一个圆心在坐标原点的圆,小易知道圆的半径的平方。小易认为在圆上的点而且横纵坐标都是整数的点是优雅的,小易现在想寻找一个算法计算出优雅的点的个数,请你来帮帮他。
例如:半径的平方如果为25
优雅的点就有:(+/-3, +/-4), (+/-4, +/-3), (0, +/-5) (+/-5, 0),一共12个点。


输入描述:
输入为一个整数,即为圆半径的平方,范围在32位int范围内。

输出描述:
输出为一个整数,即为优雅的点的个数

输入例子1:
25

输出例子1:
12


思路解析:该题较为简单,只需遍历0~sqrt(n)判断是否符合要求即可,
需要注意的是:每对不在坐标轴上的坐标配合+-都对应4对的点,对于坐标轴上的点对应2对的点

下面上代码

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/8.
*/
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int count = 0;
int m = (int)Math.sqrt(n);
for (int i = 0; i <= m; i++) {
int j = i * i;
int k = (int) Math.sqrt(n - j);
if (j + k * k == n && k != 0) { //k!=0用来判断坐标轴上的点
count += 4;
}
}
System.out.println(count);
}
}

Q3.跳石板

小易来到了一条石板路前,每块石板上从1挨着编号为:1、2、3.......
这条石板路要根据特殊的规则才能前进:对于小易当前所在的编号为K的 石板,小易单次只能往前跳K的一个约数(不含1K)步,即跳到K+X(XK的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板,他想跳到编号恰好为M的石板去,小易想知道最少需要跳跃几次可以到达。
例如:
N = 4M = 24
4->6->8->12->18->24
于是小易最少需要跳跃5次,就可以从4号石板跳到24号石板


输入描述:
输入为一行,有两个整数N,M,以空格隔开。
(4 ≤ N ≤ 100000)
(N ≤ M ≤ 100000)

输出描述:
输出小易最少需要跳跃的步数,如果不能到达输出-1

输入例子1:
4 24

输出例子1:
5


思路解析:这题上面卡了挺久,总体思路了是利用DP,构造一个长度为N+1的数组,更新最短步数,但直接暴力是n方的复杂度,会超时,这边有个小技巧,当用i遍历N~Mi的约数的时候,j可以从2遍历到sqrt(i),同时考虑i/j,同时更新两个状态,这样就将复杂度从O(N^2)降到了O(N*sqrt(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
28
29
30
31
32
import java.util.Arrays;
import java.util.Scanner;
/**
* Created by dean on 2017/8/8.
*/
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[] step = new int[m + 1];
Arrays.fill(step, 100000);
step[n] = 0;
for (int i = n;i <= m;++i) {
for (int j = 2;j <= Math.sqrt(i);++j) {
if (i % j == 0) {
int k = i / j;
if (i + j <= m )
step[i + j] = Math.min(step[i + j], step[i] + 1);
if (i + k <= m)
step[i + k] = Math.min(step[i + k], step[i] + 1);
}
}
}
if (step[m] != 100000)
System.out.println(step[m]);
else
System.out.println(-1);
}
}

Q4.暗黑的字符串

一个只包含'A''B''C'的字符串,如果存在某一段长度为3的连续子串中恰好'A''B''C'各有一个,那么这个字符串就是纯净的,否则这个字符串就是暗黑的。例如:
BAACAACCBAAA 连续子串"CBA"中包含了'A','B','C'各一个,所以是纯净的字符串
AABBCCAABB 不存在一个长度为3的连续子串包含'A','B','C',所以是暗黑的字符串
你的任务就是计算出长度为n的字符串(只包含'A'、'B''C'),有多少个是暗黑的字符串。


输入描述:
输入一个整数n,表示字符串长度(1 ≤ n ≤ 30)

输出描述:
输出一个整数表示有多少个暗黑字符串

输入例子1:
2
3

输出例子1:
9
21


思路解析:首先暴力解法是3^30的复杂度,肯定行不通。分析一下题意,题目求的是指定长度下”暗黑字符串”的数量,也就是求长度为n的串,由A,B,C三个字母组成,满足任意一个长度为3的连续子串都不同时包含'A','B','C'的串的可能性。从DP出发分析一下

  • n<=2时,前两位都是任意的,3个字母一共有9种组合
  • n>=3时,第三位就需要考虑前两位的情况,我们可以发现
    • 当前两位字母相同时,比如前两位都是A,那么后一位就还是可以从'A','B','C'三个字母中任意选择,一共有三种情况
    • 当前两位字母不相同时,比如前两位是A,B,那么按照暗黑串的定义,后一位就不能是C,只能从 A,B中选择,一共有二种情况

所以我们可以定义dp[i][0] 代表长度为i并且最后两个字母不相同的个暗黑串个数,
dp[i][1]代表的是长度为i并且最后两个字母相同的暗黑串个数。

显然,dp[2][0]=6,dp[2][1]=3;

如果前两位相同,则dp[i][1]+=dp[i-1][1], dp[i][0]+= 2*dp[i-1][1],
如果前两位不相同,则dp[i][1]+=dp[i-][0], dp[i][0] += dp[i-1][0].
综合一下:

  1. dp[i][0] = dp[i - 1][0] + 2 * dp[i - 1][1];
  2. dp[i][1] = dp[i - 1][0] + dp[i - 1][1];

Tips: 数据较大,应使用long型,int会越界

下面贴代码:

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
28
29
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);
while (scan.hasNext()) {
int n = scan.nextInt();
if (n < 3) {
System.out.println((int) Math.pow(3, n));
continue;
}
long[][] dp = new long[n + 1][2];
dp[2][0] = 6;
dp[2][1] = 3;
for (int i = 3; i <= n; i++) {
dp[i][0] = dp[i - 1][0] + 2 * dp[i - 1][1];
dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
}
long sum = dp[n][0] + dp[n][1];
System.out.println(sum);
}
}
}

后面四题的链接在这儿:牛客网——网易2017秋招编程题集合解题报告(下)