笔试题——第五周

目录

Day1

排序子序列

消减整数

最长上升子序列

Day2

爱吃素

相差不超过k的最多数

最长公共子序列(一)

Day3

小红的口罩

春游

数位染色

Day4

素数回文

活动安排

合唱团

Day5

跳台阶扩展问题

包含不超过两种字符的最长子串

字符串的排列

Day6

ISBN号码

kotori和迷宫

矩阵最长递增路径

Day7

奇数位丢弃

求和

计算字符串的编辑距离

---

Day1

排序子序列

解法：贪心 + 模拟

定义一个指针i：

如果 a[i] < a[i+1] ：序列呈现非递增一直走，直到走到波峰后停止，进行统计；

如果 a[i] > a[i+1] ：序列呈现非递减一直走，直到走到波谷后停止，进行统计；

但出现 a[i] == a[i+1]怎么办？

如果是开头出现的：要跳过这段连续相等序列；

其它地方出现就不用管

之后让i++

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int arr[N];
int main()
{cin >> n;for (int i = 0; i < n; i++)cin >> arr[i];int ret = 0, i = 0;while (i < n){if (i == n - 1){ret++;break;}if (arr[i] < arr[i + 1]){while (i + 1 < n && arr[i] <= arr[i + 1])i++;ret++;}else if (arr[i] > arr[i + 1]){while (i + 1 < n && arr[i] >= arr[i + 1])i++;ret++;}else{// 开始位置出现连续水平就要跳过while (i == 0 && i + 1 < n && arr[i] == arr[i + 1])i++;}i++;}cout << ret << endl;return 0;
}

消减整数

解法：贪心 + 数学

贪心：每次减去前面数的两倍，使数尽可能得小；

但是 ： 8 -> 7 -> 5 -> 4 -> -4 就不行

所有我们要判断是否要减去前面数的两倍：

假设X减完a后变成y：

y减去2a的情况：（看看是否能够恰好变成0）

1.y - n1* 2* a = 0

2.y - n2* 2* 2 *a = 0

3.y - n3* 2* 2 *2 *a = 0

...

整理得：y - n*2*a = 0 ，即 y% (2*a) == 0时就能走减2a的路让最后结果恰好为0

#include <iostream>
using namespace std;long long T, H;long long Fun()
{H--; // 第一次一定减-1long long ret = 1, cur = 1;while (H){if (H % (2 * cur) == 0){cur *= 2;H -= cur;}elseH -= cur;ret++;}return ret;
}int main()
{cin >> T;while (T--){cin >> H;cout << Fun() << endl;}return 0;
}

最长上升子序列

解法：贪心 + 二分

解法具体参考：贪心算法题

class Solution
{
public:int LIS(vector<int> &a){vector<int> ret;int n = a.size();for (int i = 0; i < n; i++){if (ret.empty() || ret.back() < a[i])ret.push_back(a[i]);else{int left = 0, right = ret.size() - 1;while (left < right){int middle = (left + right) / 2;if (ret[middle] < a[i])left = middle + 1;elseright = middle;}ret[left] = a[i];}}return ret.size();}
};

Day2

爱吃素

解法：模拟

由于所给数据太大，不能直接相乘进行判断，进行分类讨论：

1. a>1 && b>1  所有两个数相乘的数一定不是素数（a和b是他们的因子）

2. a==1&&b是素数 || b==1&&a是素数 说明一定是素数

3.其它情况都不是素数

#include <iostream>
#include <cmath>
using namespace std;long long T, a, b;bool IsTrue(long long x)
{if (x < 2)return false; // 素数 != 质数for (long long i = 2; i <= sqrt(x); i++){if (x % i == 0)return false;}return true;
}int main()
{cin >> T;while (T--){cin >> a >> b;if (a > 1 && b > 1)cout << "NO" << endl;else{if ((a == 1 && IsTrue(b)) || (IsTrue(a) && b == 1))cout << "YES" << endl;elsecout << "NO" << endl;}}return 0;
}

相差不超过k的最多数

解法：滑动窗口

滑就完了

#include <iostream>
#include <algorithm>
using namespace std;long long n, k, a[200010], ret;int main()
{cin >> n >> k;for (long long i = 0; i < n; i++)cin >> a[i];sort(a, a + n);for (long long left = 0, right = 0; right < n; right++){// 进窗口// 出窗口while (a[right] - a[left] > k)left++;// 统计结果ret = max(ret, right - left + 1);}cout << ret << endl;return 0;
}

最长公共子序列(一)

解法：动态规划

两个字符串的dp问题

#include <iostream>
#include <string>
using namespace std;int n, m, dp[1010][1010];
string s1, s2;int main()
{cin >> n >> m;cin >> s1 >> s2;s1 = ' ' + s1;s2 = ' ' + s2;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (s1[i] == s2[j])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}}cout << dp[n][m] << endl;return 0;
}

Day3

小红的口罩

解法：贪心 + 小根堆

每次找当前最小不舒适度使用：把全部数据扔到小根堆中每次找堆顶即可

#include <iostream>
#include <queue>
using namespace std;long long n, k, tmp, sum, ret;
priority_queue<long long, vector<long long>, greater<long long>> q;int main()
{cin >> n >> k;for (int i = 0; i < n; i++){cin >> tmp;q.push(tmp);}while (true){tmp = q.top();q.pop();sum += tmp;if (sum > k)break;q.push(tmp * 2);ret++;}cout << ret << endl;return 0;
}

春游

解法：分情况讨论

a把人数全分配到2人船，剩下的人坐便宜的其中一条船：看看要多少钱；

b把人数全分配到3人船，剩下的人坐便宜的其中一条船：看看要多少钱；

返回两者的最小花费；

但当你按照这样的思路去写，进行提交时发现只过了40%，为什么？

因为剩下的人可以和前面分配好的人一起去拼船的情况没有讨论到：

例如：如果a剩下人数是1人，它可以去和前面的分配好的2人拼3人船，即：b - a

同理b中的情况也需要讨论到...

#include <iostream>
using namespace std;long long T, n, a, b;int main()
{cin >> T;while (T--){cin >> n >> a >> b;long long sum1 = 0, sum2 = 0;if (n < 3){cout << min(a, b) << endl;}else{sum1 = n / 2 * a + (n % 2 == 0 ? 0 : min(a, min(b, b - a)));sum2 = n / 3 * b;if (n % 3 == 1)sum2 += min(a, min(b, 2 * a - b));else if (n % 3 == 2)sum2 += min(a, min(b, 3 * a - b));cout << min(sum1, sum2) << endl;}}return 0;
}

数位染色

解法：动态规划

01背包的应用~

注意空间开辟的大小

#include <iostream>
#include <string>
using namespace std;int sum, n, dp[20][200];
string s;int main()
{cin >> s;for (auto &e : s)sum += (e - '0');if (sum % 2 != 0){cout << "No" << endl;return 0;}s = " " + s;n = s.size();sum /= 2;dp[0][0] = 1;for (int i = 1; i <= n; i++){for (int j = 0; j <= sum; j++){dp[i][j] = dp[i - 1][j];if (j - (s[i - 1] - '0') >= 0){dp[i][j] = dp[i][j] || dp[i - 1][j - (s[i - 1] - '0')];}}}if (dp[n][sum])cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}

Day4

素数回文

解法：模拟

读入数据便string，用string进行操作；

将n-1个字符串倒插到string后面；

转为long long 类型，判断是否是素数即可

#include <iostream>
#include <string>
#include <cmath>
using namespace std;string s;int main()
{cin >> s;for (int i = s.size() - 2; i >= 0; i--)s += s[i];long long ret = stol(s);for (int i = 2; i <= sqrt(ret); i++){if (ret % i == 0){cout << "noprime" << endl;return 0;}}cout << "prime" << endl;return 0;
}

活动安排

解法：排序 + 贪心

按照左端点进行排序；

按第一个活动的结束时间cur，遍历2~n个活动：

如果cur <= 遍历到活动的开始时间：有重叠，选择最快结束时间的活动与下一个活动比较；

如果没重叠，则得到了一个活动，更新cur（此时cur为这个活动的结束时间）

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;long long n,b,c,cur,ret=1;
// vector<vector<long long>> a;
vector<pair<long long,long long>> a;
int main()
{cin>>n;while(n--){cin>>b>>c;a.push_back({b,c});}// sort(a.begin(),a.end(),[](vector<long long>&p1,vector<long long>&p2){//     return p1[0]<p2[0];// });sort(a.begin(),a.end());cur=a[0].second;for(int i=1;i<a.size();i++){if(cur<=a[i].first)//无重叠{ret++;cur=a[i].second;}else cur=min(cur,a[i].second);//重叠了}cout<<ret<<endl;return 0;
}

合唱团

解法：动态规划

#include <cstring>
#include <iostream>
using namespace std;typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;int n, k, d;
LL a[60], Mx[60][20], Mn[60][20], ret = -INF;int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];cin >> k >> d;// memset(Mx, -INF, sizeof(Mx));// memset(Mn, INF, sizeof(Mn));// 初始化边界值 ->放在填表进行了//  for(int i=1;i<=n;i++)//  {//      Mx[i][1]=a[i];//      Mn[i][1]=a[i];//  }for (int i = 1; i <= n; i++){Mx[i][1] = Mn[i][1] = a[i];for (int j = 2; j <= min(k, i); j++) // 选j个人不可能 j>i 或者 j>k{// LL MaxVal=-INF,MinVal=INF;// prev个人选j-1 -> prev>j-1Mx[i][j] = -INF, Mn[i][j] = INF;for (int prev = max(j - 1, i - d); prev <= i - 1; prev++){Mx[i][j] = max(Mx[i][j], max(Mx[prev][j - 1] * a[i], Mn[prev][j - 1] * a[i]));Mn[i][j] = min(Mn[i][j], min(Mx[prev][j - 1] * a[i], Mn[prev][j - 1] * a[i]));// MaxVal=max(MaxVal,Mx[prev][j-1]);// MinVal=min(MinVal,Mn[prev][j-1]);}// long long tmp1=MaxVal*a[i],tmp2=MinVal*a[i];// Mx[i][j]=max(tmp1,tmp2);// Mn[i][j]=min(tmp1,tmp2);}}// 返回值 第k~n个人中必选时的最大值for (int i = k; i <= n; i++){ret = max(ret, Mx[i][k]);}cout << ret << endl;return 0;
}

Day5

跳台阶扩展问题

解法：找规律

台阶数n满足：2^（n-1）种跳法

#include <iostream>
#include <cmath>
using namespace std;int main()
{int n;cin >> n;cout << pow(2, n - 1) << endl;return 0;
}

包含不超过两种字符的最长子串

解法：滑动窗口

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;int ret = 2;
string s;
unordered_map<char, int> h;int main()
{cin >> s;for (int left = 0, right = 0; right < s.size(); right++){// 进窗口if (h.size() <= 2)h[s[right]]++;// 出窗口while (h.size() > 2){h[s[left]]--;if (h[s[left]] == 0)h.erase(s[left]);left++;}ret = max(ret, right - left + 1);}cout << ret << endl;return 0;
}

字符串的排列

解法：排序 + dfs

先排序：把相同字符靠在一起；

画出决策树后发现两种特殊情况（字符相同时）：

a.每层有相同字符时要进行剪枝；

b.dfs时遇到相同字符却是合法的；

两者的不同：

a情况下遇到的字符与前面相同，但前面字符没被标记过（不dfs）

b情况下遇到相同字符前面相同，但前面字符被标记过的（继续dfs）

class Solution
{
public:vector<string> ret;string path;bool vis[10] = {false};void dfs(string &str){if (path.size() == str.size()){ret.push_back(path);return;}for (int i = 0; i < str.size(); i++){if (i - 1 >= 0 && str[i - 1] == str[i] && vis[i - 1] == false)continue;if (!vis[i]){vis[i] = true;path += str[i];dfs(str);path.pop_back();vis[i] = false;}}}vector<string> Permutation(string str){sort(str.begin(), str.end());dfs(str);return ret;}
};

Day6

ISBN号码

解法：模拟

注意%11=10变成X的判断

#include <iostream>
#include <string>
using namespace std;string s;
int sum = 0, pos = 1;int main()
{cin >> s;for (int i = 0; i < s.size() - 1; i++){if (s[i] != '-'){sum += (s[i] - '0') * pos;pos++;}}if (sum % 11 == (s.back() - '0') || (sum % 11 == 10 && s.back() == 'X'))cout << "Right" << endl;else{s.pop_back();if (sum % 11 == 10)s.push_back('X');elses.push_back((sum % 11) + '0');cout << s << endl;}return 0;
}

kotori和迷宫

 解法：bfs

单源最短路问题：例外还要统计能否到达出口的个数

#include <iostream>
#include <climits>
#include <queue>
using namespace std;char a[38][38];
int n, m, arrive, ret = INT_MAX, step;
bool vis[38][38];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
queue<pair<int, int>> q;void dfs(int i, int j)
{if (a[i][j] == 'e'){arrive++;ret = min(ret, step);return;}for (int k = 0; k < 4; k++){int x = dx[k] + i, y = dy[k] + j;if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && a[x][y] != '*'){step++;vis[x][y] = true;dfs(x, y);vis[x][y] = false;step--;}}
}void bfs()
{while (q.size()){int sz = q.size();while (sz--){auto [i, j] = q.front();q.pop();if (a[i][j] == 'e'){arrive++;ret = min(ret, step);continue;}for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && a[x][y] != '*'){vis[x][y] = true;q.push({x, y});}}}step++;}
}int main()
{cin >> n >> m;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> a[i][j];}}for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (a[i][j] == 'k'){vis[i][j] = true;// dfs(i,j); //超时q.push({i, j});bfs();// break;}}}if (arrive)cout << arrive << ' ' << ret << endl;elsecout << -1 << endl;return 0;
}

矩阵最长递增路径

解法：dfs（记忆化搜索）

dfs太耗时间了，添加备忘录加快dfs

#include <vector>
class Solution
{
public:int n, m, ret = 0, sum;bool vis[1010][1010] = {false};int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int memo[1010][1010];// void dfs(vector<vector<int>>& matrix,int i,int j)int dfs(vector<vector<int>> &matrix, int i, int j){if (memo[i][j] != -1)return memo[i][j];// ret=max(ret,sum);int len = 1;for (int k = 0; k < 4; k++){int x = dx[k] + i, y = dy[k] + j;if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && matrix[x][y] > matrix[i][j]){vis[x][y] = true;// sum++;len = max(len, dfs(matrix, x, y) + 1);// memo[i][j]=dfs(matrix,x,y)+1;// return memo[i][j];// sum--;vis[x][y] = false;}}// return 1;memo[i][j] = len;return memo[i][j];}int solve(vector<vector<int>> &matrix){n = matrix.size(), m = matrix[0].size();memset(memo, -1, sizeof(memo));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){vis[i][j] = true;// sum=1;ret = max(dfs(matrix, i, j), ret);vis[i][j] = false;}}return ret;}
};

Day7

奇数位丢弃

解法：模拟/规律

举例：0~10 

第一次丢弃：0 2 4 6 8 10 剩下：1 3 5 7 9 

第二次丢弃：1 5 9 剩下：3 7 

第三次丢弃：3 剩下：7

返回7

第x次丢弃的数的第一个数：2^x-1

所以要返回的数为：2^（x+1）-1 

#include <iostream>
using namespace std;int n;int main()
{while (cin >> n){int ret = 1;while (ret - 1 < n)ret *= 2;cout << ret / 2 - 1 << endl;}return 0;
}

求和

解法：dfs

画出决策树进行枚举求解

#include <iostream>
#include <vector>
using namespace std;int n, m, sum;
vector<vector<int>> ret;
vector<int> path;
bool vis[20];void dfs(int pos)
{if (sum > m)return;if (sum == m){ret.push_back(path);return;}for (int i = pos; i <= n; i++){vis[i] = true;sum += i;path.push_back(i);dfs(i + 1);path.pop_back();sum -= i;vis[i] = false;}
}int main()
{cin >> n >> m;dfs(1);for (auto &e : ret){for (auto &c : e)cout << c << ' ';cout << endl;}return 0;
}

计算字符串的编辑距离

解法：动态规划

两个字符串的dp问题：

a状态表示

dp [i][j]表示s1[0,i]区间与s2[0,j]区间内的最少的编辑距离

b状态转移方程

当 s1[i] 与 s2[j]相等时，dp [i][j] = dp [i-1][j-1]

当 s1[i] 与 s2[j]不相等时，有三种情况：

        选择把s1[i] 替换成s2[j] ，则 dp [i][j] = dp [i-1][j-1] +1

        选择s1后插入s2[j]，则 dp [i][j] = dp [i][j-1] +1

        选择s1[i]删除，则 dp[i][j] = dp [i-1][j] + 1

取最小的情况min即可

c初始化

s1 = ‘ ’ + s1   s2 = ' ' + s2 （不用担心映射操作）

多开一行一列防止越界，根据实际情况对多开的空间进行初始化(不能上来就INT_MAX！)，比较 dp[0][1]表示s1为空，需要进行一次编辑操作(插入字符)...

d填表顺序

从左往右，从上到下

e返回值 

dp[n][m]

#include <iostream>
#include <string>
using namespace std;string s1, s2;
int dp[1010][1010], n, m;int main()
{cin >> s1 >> s2;s1 = ' ' + s1, s2 = ' ' + s2;n = s1.size(), m = s2.size();// memset(dp, INT_MAX, sizeof(dp));for (int i = 0; i <= n; i++)dp[i][0] = i;for (int j = 0; j <= m; j++)dp[0][j] = j;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (s1[i] == s2[j])dp[i][j] = dp[i - 1][j - 1];else{dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;// if(i==j) dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;}}}cout << dp[n][m] << endl;return 0;
}

以上便是全部内容，有问题欢迎在评论区指正，感谢观看！