【C++】 —— 笔试刷题day_19

一、小易的升级之路

题目解析

小易现在要打游戏，现在游戏角色的初始能力值为a，我们会遇到n个怪，这些怪物的防御值为b1、b2、b3...，如果我们的能力值要高于或者等于怪物的防御值，那我们的能力值就会加bi；如果不大于怪物的防御值，我们的能力值就加当前能力值和bi的最大公约数。

我们要求出来小易的最终能力值。

算法思路

这道题，也是一道很简单的模拟题目了，直接模拟整个过程即可。

当前能力值为c，如果c>=bi，那能力值就加上bi；

如果c<bi，那能力值就加上c和bi的最大公约数。

代码实现

这里要注意的是：题目是多组输入，我们这里要用while(cin>>n>>c)来进行多组输入

#include<iostream>usingnamespace std;intmin_y(int x,int y){int tmp = x % y;while(tmp){ x = y; y = tmp; tmp = x % y;}return y;}intmain(){int c, n;while(cin >> n >> c){for(int i =0; i < n; i++){int x; cin >> x;if(c >= x) c += x;else c +=min_y(x, c);} cout << c << endl;}return0;}

二、礼物的最大价值

题目解析

题目给了一个m*n的棋盘，每一个格子里面都放着一个礼物，每一个礼物都有一定价值；现在我们从左上角开始拿礼物，我们只能向右或者向下移动一格，直到棋盘的右下角；我们要计算最多可以拿到多少价值的礼物。

给定一个二维数组，每一个位置的值就表示该位置礼物的价值，我们从(1,1)位置开始，向右或者向下走，直到(m,n)位置，求最多可以拿到多少价值的礼物。

算法思路

这道题呢，算是一道路径问题，解法呢就是动态规划

题目中说，我们可以向右和向下走，也就是从[i,j]位置移动到[i][j+1]位置和[i+1][j]位置（我们反过来理解就是，要走到[i,j]位置，只能从[i][j-1]和[i-1][j]两个位置走过去，那走到[i,j]位置能拿到礼物的最大价值就等于，走到[i,j-1]和[i-1][j]位置能拿到礼物的最大价值的最大值再加上[i,j]位置礼物的价值。

动态规划思路：

状态表示：dp[i][j]表示走到[i,j]位置能拿到礼物的最大价值。

状态转移方程：dp[i][j] = max(dp[i][j-1] , dp[i-1][j]) + arr[i][j]。

代码实现

这里要注意

下标对应，题目给的数组grid下标是从(0,0)开始的，而我们的dp表为了方便初始化，下标是从(1,1)开始的。

所以对于(i,j)位置，该位置礼物的价值是存在(i-1,j-1)中的。

classSolution{public:int dp[201][201]={0};intmaxValue(vector<vector<int>>& grid){// write code hereint m = grid.size();int n = grid[0].size();for(int i =1;i<=m;i++){for(int j =1;j<=n;j++){ dp[i][j]=max(dp[i][j-1], dp[i-1][j])+ grid[i-1][j-1];}}return dp[m][n];}};

三、对称之美

题目解析

这里，题目给出n个字符串，让第1个字符到第n个字符，每一个字符取出一个字符，这样组成一个新的字符串，让我们判断这个新的字符串是否可能是一个回文字符串；如果也可能输出Yes，否则就输出No。

题目有t组数据，对于每一组数据，我们都要进行判断并输出结果。

算法思路

这道题初看可能有一点思路，但不多；

对于n个字符串，每一个字符串取一个字符组成的新字符串，能否构成回文字符串；（对于回文字符串，我们知道，第1哥和第n个、第2个和第n-1个…这些字符都是相同的）

我们就非常好判断了，定义l和r分别从两边开始遍历字符数组，我们只需要判断l位置字符串和r位置字符串是否存在相同的字符就OK了。

思路：双指针 + 判断两个字符串是否存在相同的字符。

那么现在问题就变成了：如何判断两个字符串存在相同的字符？

那判断两个字符串中是否存在相同的字符，方法就很简单了：使用hash表计数。

首先遍历第一个字符串，将所有出现的字符放到hash表中，让遍历第二个字符串判断是否存在相同的字符即可。

代码实现

#include<iostream>#include<vector>#include<unordered_set>usingnamespace std;boolfunc(string& str1, string& str2){ unordered_set<char> hash;for(int i =0;i<str1.size();i++){ hash.insert(str1[i]);}bool b =false;for(int i =0;i<str2.size();i++){if(hash.count(str2[i])){ b =true;break;}}return b;}intmain(){int n; cin>>n;while(n--){int k; cin>>k; vector<string>arr(k);for(int i =0;i<k;i++){ cin>>arr[i];}int l =0,r = k-1;//判断两个字符串中是否存在相同的字符bool ret =true;while(l<k){if(func(arr[l],arr[r])==false){ ret =false;break;} l++; r--;}if(ret) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return0;}