蘑菇街2016校园招聘之编程题解析-技术类

回文串

NO1

解题思路:既然通过添加一个字母可以变为回文串,那么通过删除与添加的字母相对位置的字符,应该亦为回文串。

例如:

  • ‘abcb’在末尾添加’a’ –> ‘abcba’为回文串
    ‘abcb’删除与想要添加的字符’a’对应位置的字符 –> ‘bcb’亦为回文串

  • ‘aabbaab’在头部添加’b’ –> ‘baabbaab’为回文串
    ‘aabbaab’删除与想要添加的字符’b’对应位置的字符 –> ‘aabbaa’亦为回文串

Java算法实现:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.Scanner;
/**
* <p>
* Created with IntelliJ IDEA. 2015/9/23 13:35
* </p>
* <p>
* ClassName:Main
* </p>
* <p/>
* Description:给定一个串,通过添加一个字母将其变成“回文串”
* </P>
*
* @author Wang Xu
* @version V1.0.0
* @since V1.0.0
*/
public class Main {
final String Y = "YES";
final String N = "NO";
public String isPalindrome(String input) {
if (input == null || "".equals(input)) {
return Y;
}
int length = input.length();
//题目说明不超过10个字符,那么超过的话,直接返回NO
if (length > 10) {
return N;
}
StringBuilder sb = new StringBuilder(input);
for (int i = 0; i < length; i++) {
sb.deleteCharAt(i);
String temp = sb.toString();
if (sb.reverse().toString().equals(temp)) {
return Y;
} else {
sb = new StringBuilder(input);
continue;
}
}
return N;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
String input;
while (cin.hasNext()) {
input = cin.next();
System.out.println(new Main().isPalindrome(input));
}
}
}

聊天

NO2

解题思路:

  1. 小蘑的时间假设为[a,b],小菇的时间假设是[c+t,d+t],小菇起床的时间是t∈[l,r]
  2. 那么当"a < b < (c+t) < (d+t)"或者"(c+t) < (d+t) < a < b"的情况时,小蘑和小菇无法聊天,由题目条件已知"a < b""c < d",那么推出"(c+t) < (d+t)"
  3. 所以仅仅当"b < (c+t)"或者"(d+t) < a"时无法聊天,其余情况都是可以聊天的

Java算法实现:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.util.Scanner;
/**
* <p>
* Created with IntelliJ IDEA. 2015/9/23 13:35
* </p>
* <p>
* ClassName:Main2
* </p>
* <p/>
* Description:求小菇合适的起床时间,有一个非常奇葩的问题,在牛客网上测试,如果main中写
* <pre>
* Scanner cin = new Scanner(System.in);
* while (cin.hasNextInt()) {}//正确
* </pre>
* 写
* <pre>
* while(true){}//报错
* </pre>
* </P>
*
* @author Wang Xu
* @version V1.0.0
* @since V1.0.0
*/
public class Main2 {
private static void isLegal(int num, boolean flag) {
// flag为true标识判断[1,50],flag为false标识判断[0,1000]
if (flag) {
if (!(1 <= num && num <= 50)) {
// System.out.println("数据非法");
System.exit(0);
}
} else {
if (!(0 <= num && num <= 1000)) {
// System.out.println("数据非法");
System.exit(0);
}
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNextInt()) {
int p = 0, q = 0, l = 0, r = 0;
p = cin.nextInt();
isLegal(p, true);
q = cin.nextInt();
isLegal(q, true);
l = cin.nextInt();
isLegal(l, false);
r = cin.nextInt();
isLegal(r, false);
int[] time_A_B = new int[p * 2];//标识小蘑的时间
int[] time_C_D = new int[q * 2];//标识小菇的时间
for (int i = 0; i < time_A_B.length; i++) {
// 接收p行的数据,每一行数据是一个时间对
int temp = cin.nextInt();
isLegal(temp, false);
time_A_B[i] = temp;
}
for (int i = 0; i < time_C_D.length; i++) {
int temp = cin.nextInt();
isLegal(temp, false);
time_C_D[i] = temp;
}
int count = 0;//标识小菇能有多少个合适的起床时间
begin:
for (int t = l; t <= r; t++) {
for (int i = 0; i < time_A_B.length; i += 2) {
for (int j = 0; j < time_C_D.length; j += 2) {
if (!(time_C_D[j] + t > time_A_B[i + 1] || time_C_D[j + 1] + t < time_A_B[i])) {
count++;
continue begin;
}
}
}
}
System.out.println(count);
}
}
}

搬圆桌

NO3

解题思路:

  1. length = sqrt((x1-x2)^2+(y1-y2)^2)先计算两个圆心点之间的距离
  2. 参考上图,以(2 0 0 0 4)作为输入数据进行说明,当两个圆心点之间的距离lenght<(2*r+1)的时候,我们是不能够沿着两个圆心之间的连线进行移动的,而由两点之间直线最短,可知,沿两圆心的连线进行移动是最短的距离,换句话说,旋转一次移动的最长距离就是2*r,而在旋转之前需要先移动一步,所以阈值设为2*r+1
  3. 那么当lenght<(2*r+1)的时候,我们该如何进行旋转呢?正确的做法是以(x1,y1)为圆心r为半径作圆,与以(x,y)为圆心的圆的交叉点就是支点,固定此点旋转即可
  4. 根据以上的分析,再以(2 0 0 0 5)作为输入数据进行说明,当length>=(2*r+1),那么length中有几个(2*r+1),我们就需要走几步,如果相除不为整数,那么加1即可

Java算法实现:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.Scanner;
/**
* <p>
* Created with IntelliJ IDEA. 2015/9/23 16:54
* </p>
* <p>
* ClassName:Main3
* </p>
* <p/>
* Description:求圆桌移动到目标位置的步数
* </P>
*
* @author Wang Xu
* @version V1.0.0
* @since V1.0.0
*/
public class Main3 {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNextInt()) {
int r = cin.nextInt();
if (r < 1 || r > 100000) {
System.exit(0);
}
int x = cin.nextInt();
int y = cin.nextInt();
int x1 = cin.nextInt();
int y1 = cin.nextInt();
if (x < -100000 || x > 100000) {
System.exit(0);
}
if (y < -100000 || y > 100000) {
System.exit(0);
}
if (x1 < -100000 || x1 > 100000) {
System.exit(0);
}
if (y1 < -100000 || y1 > 100000) {
System.exit(0);
}
double length = Math.sqrt(Math.pow(x - x1, 2) + Math.pow(y - y1, 2));
int count;
//向上取整之后强转为int型即可
count = (int) Math.ceil(length / (2 * r + 1));
System.out.println(count);
}
}
}

本文代码均在牛客网在线OJ测试通过。算法如有疏漏或不妥之处,还望不吝赐教!

坚持原创技术分享,您的支持将鼓励我继续创作!