1.竖着读
给n个数字字符串，每个字符串长度都为m，然后按照每一列从上往下读构成m个字符串，求这m个排序后的字符串，排序输出。
思路：按列存储到 string中（前导0要去掉），这里用string是考虑到 这个整数可能超出int 甚至long long范围，但是用long long即可，并没有超出范围；然后对string数组排序，输出结果。
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
|
/***
* @Date: 2022-04-24 20:01:30
* @Author: yufeng
* @GitHub: https://github.com/fzhiy
* @Email: fzhiy270@163.com
* @LastEditTime: 2022-04-24 20:11:51
*/
#include <bits/stdc++.h>
using namespace std;
bool cmp(string a, string b) {
if (a.size() != b.size()) {
return a.size() < b.size();
} else {
return a < b;
}
}
int main() {
int n;
cin >> n;
vector<string> str(n);
for (int i = 0; i < n; i ++) {
cin >> str[i];
}
int len = str[0].size();
vector<string> s;
for (int i = 0; i < len; i ++) {
string temp("");
for (int j = 0; j < n; j ++) {
if (str[j][i] == '0') {
continue;
} else {
while (j < n) {
temp += str[j++][i];
}
}
s.push_back(temp);
}
if (temp == "") {
s.push_back("0");
}
}
sort(s.begin(), s.end(), cmp);
for (int i = 0; i < s.size() - 1; i ++) {
cout << s[i] << " ";
}
cout << s[s.size() - 1] << endl;
return 0;
}
|
2. 删除非质数下标后的最终元素
给一个数组，下标从1-n，每次淘汰下标非质数的数字，问最后剩下的一个数字是什么？
思路：最简单的思路直接判断是否为 非质数，暴力AC。
也可以利用质数筛法。
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
|
/***
* @Date: 2022-04-24 20:16:09
* @Author: yufeng
* @GitHub: https://github.com/fzhiy
* @Email: fzhiy270@163.com
* @LastEditTime: 2022-04-24 20:34:14
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
set<int> st;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param a int整型vector
* @return int整型
*/
int getNumber(vector<int>& a) {
// write code here
int n = a.size();
int index = n;
while (index > 1) {
n = index;
a[0] = -1;
for (int i = 2; i <= n; i ++) {
bool flag = true; // 素数
for (int j = 2; j * j <= i; j ++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (!flag) {
// cout <<"i : " << i << " ";
a[i - 1] = -1;
// a.erase(a.begin() + i - 1);
}
}
// cout << endl;
// cout << a.size() << " ";
index = 0;
for (int i = 0; i < n; i ++) {
if (a[i] != -1) {
a[index++] = a[i];
}
}
// cout << "index = " << index << endl;
// cout << a.size() << endl;
}
return a[0];
}
};
// void getPrime() {
// int n2 = 0, n3 = 0, n5 = 0;
// int num1 = 2, num2 = 3, num5 = 5;
// st.insert(1);
// for (int i = 2; i <= N; i++) {
// int minx = min(num1 * )
// }
// }
int main() {
// getPrime();
// vector<int> a = {3,1,1,4,5,6};
vector<int> a = {1, 2, 3, 4};
Solution sol;
int res = sol.getNumber(a);
cout << res << endl;
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
const int MAXN = 1e5+10;
int prime[MAXN+1];
//prime[0]表示小于MAXN的素数的个数
void getPrime(){
memset(prime, 0, sizeof(prime));
for(int i = 2; i <= MAXN; i++){
if(!prime[i]) prime[++prime[0]] = i;
for(int j = 1; j <= prime[0] and prime[j] <= MAXN /i; j++){
prime[prime[j]*i] = 1;
if(i % prime[j] == 0) break;
}
}
}
|
参考：https://tans.fun/archives/tecent-2022-exam
3.防御攻击最小距离
给一堆字符串代表一排士兵，士兵编号1~n，字符串中’0’的士兵代表进攻性的，‘1’的代表防御性的，每个士兵的攻击力或守备力为其下标值。将士兵分组，0~pos的是进攻组，只算攻击力，pos+1~n的是防御组，只算防御力。pos可以取0~n。求攻击组的攻击力和防御组的防御力的差的绝对值的最小值。
思路：这里直接用的前缀和。
O(n) / O(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
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
|
/***
* @Date: 2022-04-24 20:38:41
* @Author: yufeng
* @GitHub: https://github.com/fzhiy
* @Email: fzhiy270@163.com
* @LastEditTime: 2022-04-24 20:56:57
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void print(vector<ll> a) {
for (auto num : a) {
cout << num << " ";
}
cout << endl;
}
int main() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> a(n);
vector<ll> attack(n + 2);
// for (int i = 0; i < n; i ++) {
// cin >> a[i];
// }
// for (int x : a) {
// cout << x << " ";
// }
// cout << endl;
for (int i = 0; i < n; i ++) {
if (s[i] - '0' == 0) {
attack[i + 1] += (i + 1); // 前缀和
}
attack[i + 1] += attack[i];
}
vector<ll> defend(n + 2);
for (int i = n; i > 0; i --) {
if (s[i - 1] -'0' == 1) {
defend[i] += i;
}
defend[i] += defend[i + 1];
}
// print(attack);
// print(defend);
ll ans = INT_MAX;
for (int i = 0; i <= n; i ++) {
ans = min(ans, abs(attack[i] - defend[i + 1]));
// if (abs(attack[i] - defend[i + 1]) < ans) {
// ans = abs(attack[i + 1] - defend[i + 1]);
// }
}
cout << ans << endl;
return 0;
}
|
4.构造链表
没过。其实思路差不多，应该转化为数组 操作的，链表给自己增加了debug难度。
给一个链表数组，数组中的每个链表是一个循环链表中的破碎的部分，且每个链表结点的值唯一且为数值类型，求将这个循环链表复原以后，从链表中任意一个结点正序或逆序遍历 字典序 最小的那个链表，并返回。
思路：链表中结点的值唯一，使用字典记录结点的前驱和后继，并记录最小值，然后从最小值开始遍历，并判断最小值的前驱和后继哪个更小，从更小的开始顺序遍历。
5. 股票问题
dp[i][j]表示第i天拥有j支股票的现金金额
转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - price[i], dp[i-1][j+1] + price[i])
