写在前面
本篇博客主要是解答这次校招中京东的笔试编程题，这次京东的笔试编程题比较难，涉及KMP算法、manacher算法等。文中的解法也是在观看了左神（左程云）9月20号在牛客网的直播后，自己花时间写出来的。本篇博客不涉及算法的具体分析，主要是解题代码及简单的思路，关于其中的一些算法我会在后面的博客中详细介绍。
题目及解答
题目一
题目描述：
东东从京京那里了解到有一个无限长的数字序列: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, …(数字k在该序列中正好出现k次)。东东想知道这个数字序列的第n项是多少，你能帮帮他么。
输入描述：
输入包括一个整数n(1 ≤ n ≤ $10^{18}$) 。
输出描述：
输出一个整数，即数字序列的第n项。
示例：
输入
169
输出
18
解题思路：
这个主要是等差数列的求和，假设给的输入为k，则
$n(n-1)/2 < k < n(n+1)/2$，化简得到$\frac{1+\sqrt{1+8k}}{2} > 0$，即求上式满足时的最小正整数。同时此题要注意数的范围。
具体代码：1
2
3public long findNum(long input){
return (long)Math.ceil((Math.sqrt(1 + 8 * input) -1)/2);
}
题目二
题目描述：
东东在一本古籍上看到有一种神奇数，如果能够将一个数的数字分成两组，其中一组数字的和等于另一组数字的和，我们就将这个数称为神奇数。例如242就是一个神奇数，我们能够将这个数的数字分成两组,分别是{2,2}以及{4},而且这两组数的和都是4。东东现在需要统计给定区间中有多少个神奇数，即给定区间[l, r]，统计这个区间中有多少个神奇数，请你来帮助他。
输入描述：
输入包括一行，，一行中两个整数l和r(1 ≤ l，r ≤ $10^9$，0 ≤ r - l ≤ $10^6$)，以空格分割。
输出描述：
输出一个整数，即区间内的神奇数个数。
示例：
输入
1 50
输出
4
解题思路：
这个题主要是判断一个数是不是神奇数，且时间复杂度尽量低。一个数判断神奇数的问题其实是一个背包问题，比如242这个数，就是数组arr[2,2,4]中每个数可以用也可以不用，是否能组成sum(arr) = 8的一半，能则是神奇数，反之则不能。还有如果和为奇数则也不能。
具体代码：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
36public int findMagicNumber(int start, int end) {
int ans = 0;
int[] digitals = new int[10];
boolean[] dp = new boolean[9 * 9];
Arrays.fill(digitals, -1);
Arrays.fill(dp, false);
dp[0] = true;
for (int i = start; i <= end; i++) {
int num = i;
int sum = 0;
int index = 0;
while (num > 0) {
int temp = num % 10;
digitals[index++] = temp;
sum += temp;
num = num / 10;
}
// 当各位数字和为偶数时，才存在神奇数
if ((sum & 1) == 0){
for (int j = 0; j < digitals.length && digitals[j] != -1; j++) {
for (int k = sum; k >= 0; k--) {
// 用一维数组进行更新
dp[k] = dp[k] || j == 0 ? sum == digitals[j] : (k - digitals[j] < 0 ? false : dp[k-digitals[j]]);
}
if(dp[sum / 2]) {
ans++;
break;
}
}
}
Arrays.fill(digitals, -1);
Arrays.fill(dp, false);
dp[0] = true;
}
return ans;
}
题目三
题目描述：
给定一个字符串s，请计算输出含有连续两个s作为子串的最短字符串。注意两个s可能有重叠部分。例如，”ababa”含有两个”aba”。
输入描述：
输入包括一个字符串s，字符串长度length(1 ≤ length ≤ 50)，s中每个字符都是小写字母。
输出描述：
输出一个字符串，即含有连续两个s作为子串的最短字符串。
示例：
输入
abracadabra
输出
abracadabracada
解题思路：
这个题目是关于KMP算法中求next数组的问题，我们只需求出字符串最后一个字符后一位的next值。这个能算出来这个题目就解决了。
具体代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public String shortestRepeatString(String str){
int[] next = new int[str.length() + 1];
Arrays.fill(ne xt, 0);
next[0] = -1;
next[1] = 0;
for (int i = 2; i < next.length; i++) {
char pre = str.charAt(i - 1);
int k = next[i - 1];
while (k != -1){
if (str.charAt(k) == pre) {
next[i] = next[i - 1] + 1;
break;
}
k = next[k];
}
}
return str + str.substring(next[str.length()]);
}
题目四
题目描述：
合法的括号匹配序列被定义为:
- 空串””是合法的括号序列。
- 如果”X”和”Y”是合法的序列，那么”XY”也是一个合法的括号序列。
- 如果”X”是一个合法的序列，那么”(X)”也是一个合法的括号序列。
- 每个合法的括号序列都可以由上面的规则生成。
例如””，”()”，”()()()”， “(()())”，”(((())))”都是合法的。 东东现在有一个合法的括号序列s，一次移除操作分为两步: - 移除序列s中第一个左括号。
- 移除序列s中任意一个右括号，保证操作之后s还是一个合法的括号序列。
东东现在想知道使用上述的移除操作有多少种方案可以把序列s变为空。
如果两个方案中有一次移除操作移除的是不同的右括号就认为是不同的方案。
例如: s = “()()()()()”，输出1，因为每次都只能选择被移除的左括号所相邻的右括号。
s = “(((())))”，输出24，第一次有4种情况，第二次有3种情况，… ，依次类推，4 3 2 1 = 24。
*输入描述：
输入包括一行，一个合法的括号序列s，序列长度length(2 ≤ length ≤ 20)。
输出描述：
输出一个整数，表示方案数。
示例：
输入
(((())))
输出
24
解题思路：
从右往左遍历，遇到左括号看左括号右边右括号数量与左括号数量的差，并将这些差乘起来，即为方案数。
具体代码：1
2
3
4
5
6
7
8
9
10
11
12
13public int removeSolutions(String str){
int ans = 1;
int count = 0;
for (int i = str.length() - 1; i >= 0; i--) {
if (str.charAt(i) == ')') {
count++;
} else {
ans *= count;
count--;
}
}
return ans;
}
题目五
题目描述：
京京和东东是好朋友。东东很喜欢回文。回文是指从前往后读和从后往前读是一样的词语。京京准备给东东一个惊喜，先取定一个字符串s，然后在后面附上0个或者更多个字母形成回文，京京希望这个回文越短越好。请帮助京京计算他能够得到的最短的回文长度。
输入描述：
输入包括一个字符串s，字符串s长度length(1 ≤ length ≤ 50)。
输出描述：
输出一个整数，表示京京能够得到的最短的回文长度。
示例：
输入
abab
输出
5
解题思路：
这个题目主要是manacher（马拉车）算法的变形，主要是要求以最后一个字符结尾的时候的最大回文子串。
具体代码：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
32public int longestPalindrome(String str){
int ans = 0;
// 字符串预处理
String strend = "$#";
for (int i = 0; i < str.length(); i++) {
strend += str.charAt(i);
strend += "#";
}
strend += "@";
// manacher算法
int[] radius = new int[strend.length()];
Arrays.fill(radius, 0);
int right = 0; //回文最右边界
int center = 0; //回文中心
int left = 0; //回文左边界
for (int i = 1; i < strend.length(); i++) {
radius[i] = right > i ? Math.min(radius[2 * center - i], right - i): 1;
while (strend.charAt(i + radius[i]) == strend.charAt(i - radius[i])) {
radius[i] += 1;
}
if (right < i + radius[i]) {
right = i + radius[i];
center = i;
}
if(right == strend.length() - 1){
break;
}
}
return 2*str.length() - (radius[center] * 2 - 1)/2;
}
欢迎大家交流和批评指正！
