笔试强训题（7）

1. Day37

1.1 旋转字符串（字符串）

1. 题目链接： 旋转字符串
2. 题目描述：

3. 解法（字符串查找）：
   • 算法思路：
     • 第⼀种解法：按照题目的要求模拟，每次旋转⼀下 A 字符串，看看是否和 B 字符串相同。
     • 第⼆种解法：需要找到字符串旋转之后能匹配所满足的性质。如果 A 字符串能够旋转之后得到 B 字符串的话，在 A 字符串倍增之后的新串中，⼀定是可以找到 B 字符串的。 因此，我们仅需让 A 字符串倍增，然后查找 B 字符串即可。
4. C++ 算法代码：

class Solution {
public:bool solve(string A, string B) {if(A.size() != B.size()){return false;}return (A + A).find(B) != -1;}
};

1.2 合并k个已排序的链表（链表）

1. 题目链接： NC51 合并k个已排序的链表
2. 题目描述：

3. 解法：
   • 算法思路：利用堆，模拟题~
4. C++ 算法代码：

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:struct cmp{bool operator()(ListNode* l1, ListNode* l2){return l1->val > l2->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> heap;for(auto& e : lists){if(e != nullptr){heap.push(e);}}ListNode* ret = new ListNode(0);ListNode* cur = ret;while(heap.size()){ListNode* tmp = heap.top();heap.pop();cur->next = tmp;cur = cur->next;if(tmp->next != nullptr){heap.push(tmp->next);}}return ret->next;}
};

1.3 滑雪（记忆化搜索）

1. 题目链接： DP18 滑雪
2. 题目描述：

3. 解法：
   • 算法思路：矩阵最长递增路径变成矩阵最长递减路径~
4. C++ 算法代码：

#include <iostream>
using namespace std;const int N = 110;int n, m;
int arr[N][N];
int dp[N][N] = {0};
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};int dfs(int i, int j)
{if(dp[i][j]){return dp[i][j];}int len = 1;for(int k = 0; k < 4; k++){int x = i + dx[k];int y = j + dy[k];if(x >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] < arr[i][j]){len = max(len, dfs(x, y) + 1);}}dp[i][j] = len;return len;
}int main() 
{cin >> n >> m;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> arr[i][j];}}int ret = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){ret = max(ret, dfs(i, j));}}cout << ret << endl;return 0;
}

2. Day38

2.1 天使果冻（递推 + DP）

1. 题目链接： 天使果冻
2. 题目描述：

3. 解法：
   • 算法思路：需要两个数组来保存最大值和次大值，当新的元素进来就有三种情况：
     • 第一种就是比最大值还大。
     • 第二种就是大于次大值小于最大值。
     • 第三种是比次大致小。但是第三种情况不是不更新，而是把前面的最大值和次大值要保存的后面来。
4. C++ 算法代码：

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e5 + 10;
int sp[N];
int f[N];
int g[N];int main()
{int n = 0;cin >> n;for(int i = 0; i < n; i++){cin >> sp[i];}f[0] = sp[0];g[0] = -1;for(int i = 1; i < n; i++){f[i] = max(f[i - 1], sp[i]);if(sp[i] >= f[i - 1]){g[i] = f[i - 1];}else if(sp[i] >= g[i - 1] && sp[i] < f[i - 1]){g[i] = sp[i];}else{g[i] = g[i - 1];}}int q = 0;cin >> q;while(q--){int x = 0;cin >> x;cout << g[x - 1] << endl;}return 0;
}

2.2 dd爱旋转（模拟）

1. 题目链接： dd爱旋转
2. 题目描述：

3. 解法：
   • 算法思路：模拟题，但是需要不能直接无脑模拟，要思考⼀下规律~
4. C++ 算法代码：

#include <iostream>
using namespace std;const int N = 1010;
int n;
int g[N][N];void setRow()
{for(int i = 0; i < n / 2; i++){for(int j = 0; j < n; j++){swap(g[i][j], g[n - 1 - i][j]);}}
}void setCol()
{for(int j = 0; j < n / 2; j++){for(int i = 0; i < n; i++){swap(g[i][j], g[i][n - 1 - j]);}}
}int main()
{cin >> n;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cin >> g[i][j];}}int q = 0;cin >> q;int row = 0;int col = 0;while(q--){int x = 0;cin >> x;if(x == 1){row++;col++;}else{row++;}}row %= 2;col %= 2;if(row){setRow();}if(col){setCol();}for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cout << g[i][j] << " ";}cout << endl;}return 0;
}

2.3 小红取数（动态规划 - 01 背包 + 同余）

1. 题目链接： DP40 小红取数
2. 题目描述：

3. 解法：
   • 算法思路：这道题是不能用空间优化的~
     • dp[i][j]表示：前i个数中挑选，总和 %k等于 j 时，最大和是多少。j 表示的是余数。
4. C++ 算法代码：

#include <iostream>
#include <cstring>
using namespace std;const int N = 1010;int main() 
{int n, k;cin >> n >> k;long long arr[N];for(int i = 1; i <= n; i++){cin >> arr[i];}long long dp[N][N];memset(dp, -0x3f, sizeof dp);dp[0][0] = 0;for(int i = 1; i <= n; i++){for(int j = 0; j < k; j++){dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - arr[i] % k + k) % k] + arr[i]);	// j - arr[i] % k可能是负数，所以加上k修正，后面%k是修正本来是正数的值}}if(dp[n][0] <= 0){cout << -1 << endl;}else {cout << dp[n][0] << endl;}return 0;
}

3. Day39

3.1 神奇的字母（二）（哈希 + 字符串）

1. 题目链接： 神奇的字母（二）
2. 题目描述：

3. 解法：
   • 算法思路：哈希表。
4. C++ 算法代码：

#include <iostream>
using namespace std;int main()
{string s;int hash[26] = {0};char ret = 0;int maxcount = 0;while(cin >> s){for(auto& ch : s){if(++hash[ch - 'a'] > maxcount){ret = ch;maxcount = hash[ch - 'a'];}}}cout << ret << endl;return 0;
}

3.2 字符编码（哈夫曼编码）

1. 题目链接： MT7 字符编码
2. 题目描述：

3. 解法：
   • 算法思路：哈夫曼编码模板题~
4. C++ 算法代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int main() {string s;while (cin >> s) {// 1. 先统计每个字符的频次int hash[300] = { 0 };for (auto ch : s) {hash[ch]++;}// 2. 把所有的频次放⼊堆⾥⾯priority_queue<int, vector<int>, greater<int>> heap;for (int i = 0; i < 300; i++) {if (hash[i]) heap.push(hash[i]);}// 3. 哈夫曼编码int ret = 0;while (heap.size() > 1) {int t1 = heap.top();heap.pop();int t2 = heap.top();heap.pop();ret += t1 + t2;heap.push(t1 + t2);}cout << ret << endl;}return 0;
}

3.3 最少的完全平方数（动态规划）

1. 题目链接： DP43 最少的完全平方数
2. 题目描述：

3. 解法：
   • 算法思路：完全背包问题。
4. C++ 算法代码：

#include <iostream>
#include <cstring>
using namespace std;const int N = 1e4 + 0;int main() 
{int n = 0;cin >> n;int dp[N] = {0};memset(dp, 0x3f, sizeof dp);dp[0] = 0;for(int i = 1; i * i <= n; i++){for(int j = i * i; j <= n; j++){dp[j] = min(dp[j], dp[j - i * i] + 1);}}cout << dp[n] << endl;return 0;
}

4. Day40

4.1 游游的字母串（枚举）

1. 题目链接： 游游的字母串
2. 题目描述：

3. 解法：
   • 算法思路：枚举所有可能变成的字符情况。
4. C++ 算法代码：

#include <iostream>
using namespace std;int main()
{string s;cin >> s;int ret = 1e9;for(char ch = 'a'; ch <= 'z'; ch++){int sum = 0;for(auto x : s){sum += min(abs(x - ch), 26 - abs(x - ch));}ret = min(ret, sum);}cout << ret << endl;return 0;
}

4.2 体育课测验(二)（拓扑排序）

1. 题目链接： NC316 体育课测验(二)
2. 题目描述：

3. 解法：
   • 算法思路：简单拓扑排序的应⽤。
4. C++ 算法代码：

class Solution {public:vector<int> findOrder(int n, vector<vector<int> >& groups) {vector<vector<int>> edges(n); // 存储边vector<int> in(n); // ⼊度// 1. 建图for(auto v : groups) {int a = v[0], b = v[1]; // b -> aedges[b].push_back(a);in[a]++;}queue<int> q;// 2. ⼊度为 0 的点，加⼊到队列⾥⾯for(int i = 0; i < n; i++) {if(in[i] == 0) {q.push(i);}}// 3. 拓扑排序vector<int> ret;while(q.size()) {int a = q.front();q.pop();ret.push_back(a);for(auto b : edges[a]){ // a -> bif(--in[b] == 0) {q.push(b);}}}if (ret.size() == n){return ret;}else{return {};}}
};

4.3 合唱队形（动态规划）

1. 题目链接： DP16 合唱队形
2. 题目描述：

3. 解法：
   • 算法思路：最长上升子序列模型。
4. C++ 算法代码：

#include <iostream>
using namespace std;
const int N = 1010;
int n;
int arr[N], f[N], g[N];
int main() 
{cin >> n;for (int i = 1; i <= n; i++) cin >> arr[i];// 从前向后for (int i = 1; i <= n; i++) {f[i] = 1;for (int j = 1; j < i; j++) {if (arr[j] < arr[i]) {f[i] = max(f[i], f[j] + 1);}}}// 从后向前for (int i = n; i >= 1; i--) {g[i] = 1;for (int j = i + 1; j <= n; j++) {if (arr[i] > arr[j]){g[i] = max(g[i], g[j] + 1);}}}int len = 0;for (int i = 1; i <= n; i++) {len = max(len, f[i] + g[i] - 1);}cout << n - len << endl;return 0;
}

5. Day41

5.1 棋子翻转（模拟）

1. 题目链接： MT2 棋子翻转
2. 题目描述：

3. 解法：
   • 算法思路。模拟即可。注意点：
     • 如何访问上下左右四个⽅向；
     • 访问的时候不要越界；
     • 下标的对应关系；
       如何优雅地翻转~
4. C++ 算法代码：

class Solution {public:int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};vector<vector<int> > flipChess(vector<vector<int> >& A, vector<vector<int> >& f) {for(auto& v : f) {int a = v[0] - 1, b = v[1] - 1;for(int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < 4 && y >= 0 && y < 4) {A[x][y] ^= 1;}}}return A;}
};

5.2 宵暗的妖怪（动态规划）

1. 题目链接： 宵暗的妖怪
2. 题目描述：

3. 解法：
   • 算法思路：打家劫舍，但是别抢到最后⼀家就行了~
4. C++ 算法代码：

#include <iostream>
using namespace std;const int N = 1e5 + 10;
int n;
long long arr[N];
long long dp[N];int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> arr[i];}for(int i = 3; i <= n; i++){dp[i] = max(dp[i - 1], dp[i - 3] + arr[i - 1]);}cout << dp[n] << endl;return 0;
}

5.3 过桥（BFS）

1. 题目链接： 过桥
2. 题目描述：

3. 解法：
   • 算法思路：类似层序遍历的思想。
4. C++ 算法代码：

#include <iostream>
using namespace std;const int N = 2010;
int n;
int arr[N];int bfs()
{int left = 1;int right = 1;int ret = 0;while(left <= right){ret++;int r = right;for(int i = left; i <= right; i++){r = max(r, arr[i] + i);if(r >= n){return ret;}}left = right + 1;right = r;}return -1;
}int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> arr[i];}cout << bfs() << endl;return 0;
}

6. Day42

6.1 最大差值（模拟 + 贪心）

1. 题目链接： MT1 最大差值
2. 题目描述：

3. 解法：
   • 算法思路：遍历数组的过程中，使用一个变量标记⼀下当前位置之前所有元素的最小值即可。
4. C++ 算法代码：

class Solution {public:int getDis(vector<int>& arr, int n) {int ret = 0;int minPrev = arr[0];for (int i = 1; i < n; i++) {minPrev = min(minPrev, arr[i]);ret = max(ret, arr[i] - minPrev);}return ret;}
};

6.2 兑换零钱（动态规划 - 完全背包）

1. 题目链接： DP44 兑换零钱
2. 题目描述：

3. 解法：
   • 算法思路：完全背包问题。
4. C++ 算法代码：

#include <iostream>
#include <cstring>
using namespace std;const int N = 10010, M = 5010;
int n, aim;
int arr[N];
int dp[M];int main() 
{cin >> n >> aim;for (int i = 1; i <= n; i++){cin >> arr[i];}memset(dp, 0x3f, sizeof dp);dp[0] = 0;for (int i = 1; i <= n; i++) {for (int j = arr[i]; j <= aim; j++) {dp[j] = min(dp[j], dp[j - arr[i]] + 1);}}if (dp[aim] >= 0x3f3f3f3f){cout << -1 << endl;}else{cout << dp[aim] << endl;}return 0;
}

6.3 小红的子串（前缀和 + 双指针）

1. 题目链接： 小红的子串
2. 题目描述：

3. 解法：
   • 算法思路：
     • 利用前缀和的思想，求种类个数在 [l, r] 区间内子串的个数，等于求 [1, r] 区间内个数 - [1, l - 1] 区间内个数。
     • 求种类个数在 [1, count] 区间内子串的个数，可以用滑动窗口来求解。
4. C++ 算法代码：

#include <iostream>
#include <string>
using namespace std;int n, l, r;
string s;// 找出字符种类在 [1, x] 之间的⼦串的个数
long long find(int x)
{if(x == 0){return 0;}// 滑动窗⼝int left = 0;int right = 0;int hash[26] = { 0 }int kinds = 0; // 统计窗⼝内字符种类的个数long long ret = 0;while(right < n){if(hash[s[right] - 'a']++ == 0){kinds++;}while(kinds > x){if(hash[s[left] - 'a']-- == 1){kinds--;}left++;}ret += right - left + 1;right++;}return ret;
}int main()
{cin >> n >> l >> r >> s;cout << find(r) - find(l - 1) << endl;return 0;
}