Writing in the front
This blog is mainly to answer the written programming questions of JINGdong in this school enrollment. The written programming questions of Jingdong are relatively difficult, involving KMP algorithm, Manacher algorithm and so on. The solution of the article is also in watching the Left god (left Cheng Yun) on September 20 in niuke.com after the live broadcast, their own time to write out. This blog is not about the specific analysis of the algorithm, but mainly about the problem solving code and simple ideas. I will introduce some of the algorithms in detail in a later blog.
Questions and Solutions
Subject to a
Dongdong learns from Jingjing that there is an infinite sequence of numbers: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5… (The number k occurs exactly k times in the sequence). Dongdong wants to know what the NTH term of this sequence of numbers is. Can you help him?
Input description: Input consists of an integer n(1 ≤ n ≤ $10^{18}$).
Output description: Output an integer, that is, the NTH term of a sequence of numbers.
Example: Input 169 Output 18
${frac{1+ SQRT {1+8k}}{2} > 0${frac{1+ SQRT {1+8k}}{2} > 0${frac{1+ 8k}}{2} > 0$ Also pay attention to the range of numbers.
Specific code:
public long findNum(long input){
return (long)Math.ceil((Math.sqrt(1 + 8 * input) -1) /2);
}Copy the codeTopic 2
Dongdong saw a magic number in an ancient book. If the numbers of a number can be divided into two groups, and the sum of one group of numbers is equal to the sum of the other group of numbers, we call this number a magic number. For example, 242 is a magic number. We can divide the numbers into two groups, {2,2} and {4}, and the sum of both groups is 4. Dongdong now needs to count the number of magic numbers in a given interval, i.e., given interval [L, r], and count the number of magic numbers in this interval, please help him.
Input description: The input consists of one line, and two integers L and r(1 ≤ L, r ≤ $10^9$, 0 ≤ r-L ≤ $10^6$), separated by Spaces.
Output description: Output an integer, that is, the number of magic numbers in the interval.
Example: Input 1 50 Output 4
The time complexity of a number should be as low as possible. The problem of determining the magic number of a number is actually a knapsack problem, such as the number 242, which is the array arr[2,2,4], each number can be used or not, can form a half of sum(arr) = 8, yes is the magic number, vice versa is not. And not if the sum is odd.
Specific code:
public 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;
}
// Magic numbers exist only when the sum of the digits is even
if ((sum & 1) = =0) {for (int j = 0; j < digitals.length && digitals[j] ! = -1; j++) {
for (int k = sum; k >= 0; k--) {
// Update with a one-dimensional array
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;
}Copy the codeThe title three
Given a string s, compute the shortest output string with two consecutive s as substrings. Notice that the two S’s may overlap. For example, “ababa” contains two “aba”.
Input description: The input contains a string s. The length of the string is length(1 ≤ length ≤ 50). Each character in s is lowercase.
Output description: Outputs a string, that is, the shortest string with two consecutive S as substrings.
Example: Enter abracadabra and output abracadabracada
The KMP algorithm is used to find the next array. We only need to find the next value after the last character of the string. If we can figure this out, we’re done with this problem.
Specific code:
public 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()]);
}Copy the codeThe title four
Description: A valid parenthesis matching sequence is defined as:
- The empty string “” is a legal parenthesis sequence.
- If “X” and “Y” are legal sequences, then “XY” is also a legal parenthesis sequence.
- If “X” is a legal sequence, then “(X)” is also a legal parenthesis sequence.
- Each valid parenthesis sequence can be generated by the rule above. “, “()”, “()”, “()()() ()()”, “(((())))” are all legal. Dongdong now has a legal parenthesis sequence S, with a two-step removal operation:
- Removes the first open parenthesis in sequence S.
- Remove any closing parenthesis from sequence S to ensure that s remains a valid parenthesis sequence.
Dongdong now wants to know how many ways the sequence S can be null using the above removal operation.
If one of the two schemes removes a different closing bracket it is considered to be a different scheme. For example, s = “()()()()() ()()”, printing 1, because only the close parenthesis adjacent to the removed open parenthesis can be selected each time. S = “(((())))”, output 24, the first time has 4 cases, the second time has 3 cases,… And so on, 4, 3, 2, 1 = 24. * Input description: Input consists of one line, a valid parenthesis sequence s, and sequence length length(2 ≤ length ≤ 20).
Output description: Output an integer, indicating the number of schemes.
For example, enter (((()))) and output 24
Traversing from right to left, see the difference between the number of right parentheses and the number of left parentheses, and multiply these differences, that is, the number of schemes.
Specific code:
public 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;
}Copy the codeTopic five
Jingjing and Dongdong are good friends. Dongdong likes palindromes very much. Palindromes are words that are the same as reading backwards and forwards. Jingjing plans to surprise Dongdong by selecting a string s and then attaching 0 or more letters to form a palindrome. Jingjing hopes that the palindrome will be as short as possible. Please help Jingjing calculate the shortest palindrome length he can get.
Input description: The input contains a string s. The length of the string s is length(1 ≤ length ≤ 50).
Output description: Output an integer indicating the shortest palindrome length that can be obtained.
Example: Enter abab and output 5
The manacher algorithm is a variant of the manacher algorithm, which requires the maximum number of substrings that end with the last character.
Specific code:
public int longestPalindrome(String str){
int ans = 0;
// String preprocessing
String strend = "$#";
for (int i = 0; i < str.length(); i++) {
strend += str.charAt(i);
strend += "#";
}
strend += "@";
/ / manacher algorithm
int[] radius = new int[strend.length()];
Arrays.fill(radius, 0);
int right = 0; // The rightmost boundary of palindromes
int center = 0; // Palindrome center
int left = 0; // Palindrome left boundary
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;
}Copy the codeWelcome to exchange and criticism!
Ps: Some formulas in this article are not correct, you can visit jingdong 2018 school recruitment programming answers (Java).
For more articles, please visit my blog with links to articles on gold digging techniques