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

一、小易的升级之路

题目解析

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

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

算法思路

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

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

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

代码实现

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

#include <iostream>
using namespace std;

int min_y(int x, int y) {
    int tmp = x % y;
    while (tmp) {
        x = y;
        y = tmp;
        tmp = x % y;
    }
    return y;
}
int main() {
    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;
    }
    return 0;
}

二、礼物的最大价值

题目解析

题目给了一个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)中的。

class Solution {
public:
    int dp[201][201] = {0};
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        int 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>
using namespace std;

bool func(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;
}
int main()
{
    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;
    }
    return 0;
}