京东2019春招编程题参考代码
数内排序
分析
字符串读入,逆序排序即可。
时间复杂度
O(len(x)*log(len(x)))
参考代码
#include <bits/stdc++.h> using namespace std; int main() { string x; cin >> x; sort(x.begin(), x.end()); reverse(x.begin(), x.end()); cout << x << endl; return 0; }
幸运时刻
分析
按题意模拟即可。
时间复杂度
O(n)
参考代码
#include <bits/stdc++.h> using namespace std; int n; int main() { cin >> n; string s; int cnt = 0; int flag; for(int i = 0; i < n; i++) { cin >> s; flag = 0; if(s[0] == s[3] && s[1] == s[4]) flag = 1; if(s[0] == s[1] && s[3] == s[4]) flag = 1; if(s[0] == s[4] && s[1] == s[3]) flag = 1; if(flag) cnt++; } cout << cnt << endl; }
有趣的硬币
分析
根据有趣硬币的定义,挨着判断统计即可。
时间复杂度
O(n)
参考代码
#include <bits/stdc++.h> using namespace std; string s; int main() { cin >> s; s = s[0] + s; s = s + s[s.size() - 1]; int cnt = 0; for(int i = 1; i < s.size() - 1; i++) { if(s[i] != s[i - 1] || s[i] != s[i + 1]) { cnt++; } } cout << cnt << endl; return 0; }
整除
分析
本质是找1~n的最小公倍数,
根据唯一分解定理和最小公倍数的定义。。。
求每个素因子的最大个数相乘即可。
时间复杂度
O(n*sqrt(n))
参考代码
#include <bits/stdc++.h> using namespace std; const int maxn = 100000 + 5; int tmp[maxn]; int n; int main() { cin >> n; for(int i = 1; i <= n; i++) { int k = i; for(int j = 2; j * j <= n; j++) { int s = 0; while(k % j == 0) { s++; k /= j; } tmp[j] = max(tmp[j], s); } if(k > 1) tmp[k] = max(tmp[k], 1); } long long res = 1; for(int i = 1; i <= 100000; i++) { for(int j = 0; j < tmp[i]; j++) { res = res * i % 987654321; } } cout << res << endl; return 0; }
牛牛下象棋
分析
dp[i][a][b]表示i次移动后,马位于坐标(a,b)的情况数。
考虑下一步的八种移动方式对应的8个坐标分别为(a1,b1)...(a8,b8),则状态转移方程如下:
dp[i+1][a1][b1] += dp[i][a][b]
dp[i+1][a2][b2] += dp[i][a][b]
...
dp[i+1][a8][b8] += dp[i][a][b]
初始状态为除了dp[0][0][0] = 1,其余都为0。答案就是dp[K][X][Y]。
时间复杂度
O(81*K)
参考代码
#include <bits/stdc++.h> using namespace std; long long dp[100005][10][10]; int d[10][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}; int main() { int k, X, Y, tx, ty; scanf("%d%d%d", &k, &X, &Y); dp[0][0][0] = 1; for(int i = 0; i < k; i++) { for(int x = 0; x <= 8; x++) { for(int y = 0; y <= 8; y++) { for(int j = 0; j < 8; j++) { tx = x + d[j][0]; ty = y + d[j][1]; if(0 <= tx && tx <= 8 && 0 <= ty && ty <= 8) dp[i+1][tx][ty] = (dp[i + 1][tx][ty] + dp[i][x][y]) % 1000000007; } } } } printf("%lld\n", dp[k][X][Y]); return 0; }
牛牛的括号匹配
分析
考虑如何判断一个串是否合法的过程: 依次处理字符,若是'('则入栈,若是')'则从栈中弹出一个'('. 若没有'('则不合法. 那么此题就是上述过程的变种,在处理过程中允许两次变换.可以只考虑')'->'('的方向. 1、如果当前是'(',直接入栈. 2、如果当前是')',如果栈非空,则弹出一个'('; 如果栈空就把当前的')'变成'('入栈. (标记最多只能变化一次). 用flag标记是否有将')'变为'('的操作. 结果栈要么为空,要么全是'('.
- 如果整个字串没有被处理完,那么肯定是"No".
- 如果flag=0, 那么要求没有'('剩下.
- 如果flag=1, 那么结果栈中的'('只能是两个. "((" -> "()".
时间复杂度
O(len(s))
参考代码
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; char str[maxn]; stack<char> s; int main() { int t; cin >> t; while(t--) { while(!s.empty()) s.pop(); scanf("%s", str); int n = strlen(str); if(n == 2) { if(str[0] == '(' && str[1] == ')') { puts("No"); continue; } } int i; int flag1 = 0; for(i = 0; i < n; i++) { if(str[i] == '(') { s.push('('); } else { if(!s.empty()) s.pop(); else { if(flag1) break; flag1 = 1; s.push('('); } } } if(i == n) { if(!flag1) { if(s.empty()) puts("Yes"); else puts("No"); } else { if(s.size() != 2) puts("No"); else puts("Yes"); } } else puts("No"); } return 0; }
分解整数
分析
范围巨大。。
但是直觉上觉得可以很快出答案,
于是答案枚举一个数,判断另外一个数的合法性。
就跑过了。。
时间复杂度
O(跑得过)
参考代码
#include <bits/stdc++.h> int main() { int t; long long n, x, y; scanf("%d", &t); while(t--) { scanf("%lld", &n); if(n & 1) printf("No\n"); else { for(y = 2; y <= n; y += 2) { if(n % y == 0 && ((n / y) & 1)) { x = n / y; break; } } printf("%lld %lld\n", x, y); } } return 0; }
生成回文串
分析
dp[l][r]表示区间 [l, r] 内的回文串数目。
于是dp[l][r] = dp[l][r - 1] + dp[l + 1][r],
根据s[l] ?= s[r], 来看是+1还是减掉重复的部分。
时间复杂度
O(n^2)
参考代码
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 50 + 5; LL dp[maxn][maxn]; char s[maxn]; int main() { scanf("%s", s + 1); int len = strlen(s + 1); memset (dp, 0, sizeof(dp)); for(int i = 1; i <= len; i++) { for(int l = 1; l + i - 1 <= len; l++) { int r = l + i - 1; dp[l][r] += dp[l + 1][r]; dp[l][r] += dp[l][r - 1]; if (s[l] == s[r]) dp[l][r] += 1; else dp[l][r] -= dp[l + 1][r - 1]; } } printf ("%lld\n", dp[1][len]); return 0; }#春招#