T1:竖着读
给n个数字字符串，每个字符串长度都为m，然后按照每一列从上往下读构成m个字符串，求这m个排序后的字符串，排序输出。
直接按列存储，然后将其转换为long long类型的值，排序即可，顺便解决了前导0问题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
const int MAXN = 1e5 + 10;
int T;
int main(int argc, char * argv[]){
int n, len;
cin >> n;
vector<string> g(MAXN);
for(int i = 0; i < n; i++){
string str;
cin >> str;
len = str.size();
for(int j = 0; j < len; j++){
g[j].push_back(str[j]);
}
}
vector<ll> nums;
for(int i = 0; i < len; i++){
nums.push_back(stoll(g[i]));
}
sort(nums.begin(),nums.end());
for(int i = 0; i < len; i++){
cout << nums[i];
if(i != len-1) cout << " ";
}
return 0;
}
T2: 删除非质数下标后的最终元素
给一个数组，下标从1-n，每次淘汰下标非质数的数字，问最后剩下的一个数字是什么？
这里没想到暴力可以解决的，直接先把小于1e5的所有质数筛出来，这里我用了质数筛，然后每次模拟删除即可。直至最后元素个数为1
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;
}
}
}
class Solution {
public:
int getNumber(vector<int>& a) {
getPrime();
//将所有素数存入set中
unordered_set<int> st;
for(int i = 1; i <= prime[0]; i++) st.insert(prime[i]);
//这里使用两个交替数组，用来存储剩余数字
vector<int> old = a, neww;
while(neww.size() != 1){
neww.clear();
for(int i = 1; i <= old.size(); i++){
if(st.count(i)) neww.push_back(old[i-1]);
}
old = neww;
}
cout << neww[0];
return neww[0];
}
};
T3:防御攻击最小距离
给一堆字符串代表一排士兵，士兵编号1~n，字符串中’0’的士兵代表进攻性的，‘1’的代表防御性的，每个士兵的攻击力或守备力为其下标值。将士兵分组，0~pos的是进攻组，只算攻击力，pos+1~n的是防御组，只算防御力。pos可以取0~n。求攻击组的攻击力和防御组的防御力的差的绝对值的最小值。
这里分别对攻击值做前缀，防御值做后缀，然后遍历下标即可，取最小即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
int n, len;
int main(int argc, char * argv[]){
string str;
cin >> n >> str;
len = n;
vector<ll> attack(n+2, 0), protect(n+2, 0);
//攻击做前缀
for(int i = 1; i <= len; i++){
attack[i] = attack[i-1];
if(str[i-1] == '0') attack[i] += i;
}
//防御做后缀
for(int i = len; i >= 1; i--){
protect[i] = protect[i+1];
if(str[i-1] == '1') protect[i] += i;
}
ll value = INT_MAX;
for(int i = 0; i <= len; i++){
ll cur = abs(attack[i] - protect[i+1]);
if(cur < value) value = cur;
}
cout << value;
return 0;
}
T4:构造链表
给一个链表数组，数组中的每个链表是一个循环链表中的破碎的部分，且每个链表结点的值唯一且为数值类型，求将这个循环链表复原以后，从链表中任意一个结点正序或逆序遍历 字典序 最小的那个链表，并返回。
思路：链表中结点的值唯一，使用字典记录结点的前驱和后继，并记录最小值，然后从最小值开始遍历，并判断最小值的前驱和后继哪个更小，从更小的开始顺序遍历。
主要分为4步骤，感觉为了出题者凑题意加入了一个链表的概念，其实把链表看成数组就好了。。。。
- 这里我们可以先用map来维护当前节点的值和下一节点的值的状态，
- 随便找一个切入点，通过map遍历所有元素存到一个数组，
- 找到数组中最小值，作为我们的头节点
- 判断头节点的前驱或者后继节点的值的大小
- 如果前驱小，那么逆序构造
- 如果后继小，那么顺序构造。
class Solution {
public:
ListNode* solve(vector<ListNode*>& a) {
unordered_map<int, int> mp;
vector<int> v;
//存储此节点和后继节点的值，key：当前节点的值 value:后继节点的值
for(auto nodes : a){
ListNode* cur = nodes;
while(cur){
if(cur->next) mp[cur->val] = cur->next->val;
cur = cur->next;
}
}
//转换为数组
int cur = (mp.begin()->first), start = cur;
v.push_back(cur);
cur = mp[cur];
while(cur != start){
v.push_back(cur);
cur = mp[cur];
}
//找到最小元素下标
int len = v.size();
auto minn = min_element(v.begin(),v.end());
int startIdx = std::distance(std::begin(v), minn);
//查看前驱或者后继，如果前驱小，那么inv=-1， 如果后继小，那么inv = 1
int inv = 1;
if(v[(startIdx+1)%len] > v[(startIdx-1+len)%len]) inv = -1;
//构造链表
ListNode* fake = new ListNode(-1), *curr = fake;
for(int i = 0 ; i < len; i++){
curr->next = new ListNode(v[(startIdx + inv + len) % len]);
curr = curr->next;
}
return fake->next;
}
};
T5: 股票问题
股票问题进阶版本，没时间写了，最后判断了一下如果股票价格是逆序的，那么就输出初始资金，过20%。
表示第i天拥有j支股票的现金金额
转移方程：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
int T;
int main(int argc, char * argv[]){
int n, m;
cin >> n >> m;
vector<int> price(n);
for(int i = 0 ; i < n; i++) cin >> price[i];
ll dp[n][n];
//初始化
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dp[i][j] = -1;
//第0天为m
dp[0][0] = m;
if(m >= price[0]){
dp[0][1] = m - price[0];
}
for(int i = 1; i < n; i++){
for(int j = 0; j < n; j++){
dp[i][j] = dp[i-1][j];
//买一
if(j > 0 and dp[i-1][j-1] != -1 and dp[i-1][j-1] >= price[j]){
dp[i][j] = max(dp[i][j], dp[i-1][j-1] - price[i]);
}
//卖一
if(j < n-1 and dp[i-1][j + 1] != -1){
dp[i][j] = max(dp[i][j], dp[i-1][j+1] + price[i]);
}
}
}
ll ans = 0;
for(int i = 0; i < n; i++){
if(dp[n-1][i] == -1) continue;
ans = max(ans, dp[n-1][i] + i * price[n-1]);
}
cout << ans;
return 0;
}
有思路的小伙伴可以评论区分享一下呀！
牛客上Java版本题解:题解
