C++ 笔试刷题：模拟、动态规划与回文判断

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int dp[201][201] = {0};
    int maxValue(vector<vector<int>>& grid) {
        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 个字符串，从每个字符串取一个字符组成新字符串，判断是否可能构成回文字符串。

算法思路

双指针 + 哈希表。定义 l 和 r 分别从两边遍历字符串数组，判断 arr[l] 和 arr[r] 是否存在相同字符。若存在，则继续向中间移动；否则无法构成回文。

代码实现

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

bool func(string& str1, string& str2) {
    unordered_set<char> hash;
    for (char c : str1) hash.insert(c);
    for (char c : str2) {
        if (hash.count(c)) return true;
    }
    return false;
}

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 <= r) {
            if (!func(arr[l], arr[r])) {
                ret = false;
                break;
            }
            l++;
            r--;
        }
        if (ret) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}