一共5道题，两个小时。整体难度偏低，一道模拟题，三道贪心题，一道动态规划题。
第一题（模拟题）：
给一个链表，每个链表有一个数字i，i%m代表节点的颜色（因此一共m种颜色）
将链表按m种颜色拆分成m个链表，如果某种颜色未出现过就返回空链表。
直接按题意模拟即可。
为了简化时间复杂度，可以考虑缓存链表尾部的节点，方便插入。
时间复杂度O(N)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param m int整型
* @param a ListNode类 指向彩带的起点，val表示当前节点的val，next指向下一个节点
* @return ListNode类vector
*/
vector<ListNode*> solve(int m, ListNode* a) {
vector<ListNode*> ret;
vector<ListNode**> bck;
ret.resize(m);
bck.resize(m);
while (a!=nullptr)
{
if (ret[a->val%m]==nullptr)
{
ret[a->val%m]=new ListNode(a->val);
bck[a->val%m]=&ret[a->val%m];
}
else
{
(*bck[a->val%m])->next=new ListNode(a->val);
bck[a->val%m]=&((*bck[a->val%m])->next);
}
a=a->next;
}
return ret;
}
}; 第二题（贪心题）：
有n个魔法球，每个球有一个能量，每次可以选一个球，获得这个球的所有能量，然后这个球消失。吸取一个球的时候，其他每个球的能量会增加，增量等于被吸取的能量。求能吸取的最多能量。
不难发现，应该尽可能先吸取能量最大的魔法球。因此按从大到小排序，然后模拟吸取的过程即可。注意取模来防止溢出。
时间复杂度O(TNlogN)，这里N和T都小于1000，时间复杂度满足题目要求
#include <bits/stdc++.h>
using namespace std;
#define maxn 5005
#define mod 1000000007
int ar[maxn];
int main(void)
{
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%d", &ar[i]);
}
sort(ar, ar + n, std::greater<int>());
long long ans = 0, inc = 0;
for (int i = 0; i < n; ++i)
{
ar[i] = (ar[i] + inc) % mod;
inc = (inc + ar[i]) % mod;
ans = (ans + ar[i]) % mod;
}
printf("%lld", ans);
}
return 0;
} 第三题（贪心题）： 乘船问题，每个船可以坐一个或者坐两个人，如果坐两个人，体重的和一定要是偶数。
每艘船都有相同的最大载重限制，不能超载。
问最少需要多少船才能把人都运走。
首先，把人按照体重的奇偶分成两类人。显然奇数体重的人只能和奇数体重的人一起，偶数只能和偶数一起。因此我们分别计算两类人的结果然后相加即可得出结果。
搭配时，使用贪心的思想，每个人的搭档都应该尽可能的重（但是不至于超载）。因此首先对体重排序，然后利用双指针的思想，一头一尾，两面夹击扫描。
最终时间复杂度O(TNlogN)，这里N和T都小于1000，时间复杂度满足题目要求
#include<bits/stdc++.h>
using namespace std;
#define maxn 5005
vector<int> g[2];
int solve(vector<int>& g,int w)
{
sort(g.begin(), g.end());
auto backit = --g.end();
int ans = g.size();
for (auto it = g.begin(); it != g.end();++it)
{
while (*it+*backit>w)
{
if (backit<=it)
return ans;
--backit;
}
if (backit<=it)
return ans;
--ans;
--backit;
if (backit<=it)
return ans;
}
return ans;
}
int main(void)
{
int t;
scanf("%d", &t);
while (t--)
{
int n,w;
scanf("%d%d", &n,&w);
g[0].clear();
g[1].clear();
for (int i = 0; i < n;++i)
{
int temp;
scanf("%d", &temp);
g[temp % 2].push_back(temp);
}
int ans = solve(g[0],w) + solve(g[1],w);
printf("%d", ans);
}
return 0;
} 第四题（贪心题）：
给一个长度为n的字符串，求字典序最大的长度为k的子序列（子序列意味着可以不连续）
字典序最大，意味着我们应该在保证有解的情况下，尽可能的使得当前选取的字母最大。这是明显的贪心思想。
为了保证有解，当前选取的字母的右边剩下的字母必须大于等于len-1个，否则后面的字母不够用了。
一直贪心选取N次即可得到最优子序列。
每次选取时，可以一个for循环直接暴力遍历，则每次选取的时间复杂度O(N),也可以使用树状数组加速选取，每次选取的时间复杂度为O(logN)。
最终时间复杂度：暴力选取：O(N^2)，树状数组加速贪心：O(NlogN)
这道题显然放水了，N=1000,因此直接暴力即可，不需要写树状数组加速。
#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
char str[maxn];
int len;
char solve(int &pos, int minlen)
{
for (int i = pos + 1, lim = len - minlen + 1; i < lim; ++i)
{
if (str[i] > str[pos])
{
pos = i;
}
}
pos += 1;
return str[pos-1];
}
int main(void)
{
int n, k, pos = 0;
scanf("%d%d%s", &n, &k, str);
len = strlen(str);
for (int i = 0; i < k; ++i)
{
putchar(solve(pos, k - i));
}
putchar('\n');
return 0;
} 第五题（动态规划题）：
n 个图块，每个图块有一个数字，数字代表一种颜色。初始选择一个魔法图块，如果包含该图块的连续个图块数字相同，就可以变色。变色需要花费的代价是两个颜色的数字的差的绝对值。求把所有图块变成相同颜色的最小代价。
首先，不难发现，在变色的过程中会出现一个包含魔法图块的同颜色的区间。我们变色的过程就是不断左右扩张这个区间。变色只有两个选择，要么变成区间左边图块的颜色，要么变成右边的颜色，别的变色都是没有意义的。
因此，这显然是一个区间动态规划问题。
设dp[i][j][0/1]为所有可能的状态。第一维i代表区间左端点，第二维j代表区间右端点，第三维0/1代表区间的颜色是左端点的颜色还是右端点的颜色。设c为颜色的数组。
显然我们可以列出状态转移方程：
dp[i][j][0]=min(dp[i+1][j][0]+abs(c[i]-c[i+1]),dp[i+1][j][1]+abs(c[i]-c[j]))
dp[i][j][1]=min(dp[i][j-1][0]+abs(c[j]-c[i]),dp[i][j-1][1]+abs(c[j]-c[j-1]))
初始边界条件：当i==j时，dp[i][j][0]=dp[i][j][1]=0
根据状态转移方程，我们可以很容易求出最后的答案，即dp[0][n-1][0]和dp[0][n-1][1]中的最小值。
为了简化代码量，可以使用记忆化搜索。
最终时间复杂度为O(N^2)。题目给了N=500，说明更差的O(N^3)级别的算法也是能通过此题的。
#include<bits/stdc++.h>
using namespace std;
#define maxn 505
int ar[maxn],n;
int dp[maxn][maxn][2];
int magic = 0x3f3f3f3f;
int search(int i,int j,int k)
{
if (dp[i][j][k]==magic)
{
if (k==0)
{
dp[i][j][k] = min
(
search(i + 1, j, 0)+abs(ar[i]-ar[i+1]),
search(i + 1, j, 1)+abs(ar[i]-ar[j])
);
}
else
{
dp[i][j][k] = min
(
search(i, j - 1, 0)+abs(ar[j]-ar[i]),
search(i, j - 1, 1)+abs(ar[j]-ar[j-1])
);
}
}
return dp[i][j][k];
}
int main(void)
{
int totans=magic;
scanf("%d", &n);
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < n;++i)
{
scanf("%d", &ar[i]);
dp[i][i][0] = dp[i][i][1] = 0;
}
totans = min(search(0, n-1, 0), search(0, n-1, 1));
printf("%d", totans);
return 0;
}
全部评论
(7) 回帖