Weekly Contest 405

日期 2024/07/07
這次題目水水的，很快就做出第一、二、三題目，第四題是一個 DP + Trie 變形題目，當下沒做出來。

• Find the Encrypted String
• Generate Binary Strings Without Adjacent Zeros
• Count Submatrices With Equal Frequency of X and Y
• Construct String with Minimum Cost

第一題

string getEncryptedString(string s, int k) {
    const int n = s.size();
    string t = s;
    for(int i = 0; i < n; i++) {
        int c = s[(i + k) % n];
        t[i] = c;
    }
    return t;
}

第二題

vector<string> validStrings(int n) {
    if(n == 1)
        return {"0", "1"};

    vector<string> xx = validStrings(n - 1);
    unordered_set<string> ret;
    for(int i = 0; i < xx.size(); i++) {
        if(xx[i].back() == '0') {
            ret.insert(xx[i] + '1');
        }else{
            ret.insert(xx[i] + '1');
            ret.insert(xx[i] + '0');
        }
    }
    return vector<string>(ret.begin(), ret.end());
}

第三題

這次第三題蠻水的

Area:
1 2
3 4

(i - 1, j - 1)  (i - 1, j)
(i,     j - 1)  (i,     j)

int numberOfSubmatrices(vector<vector<char>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<int>> x1(m, vector<int>(n, 0));
    vector<vector<int>> y1(m, vector<int>(n, 0));
    x1[0][0] = grid[0][0] == 'X';
    y1[0][0] = grid[0][0] == 'Y';

    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            int area1, area2, area3;

            if(i == 0 && j == 0) {
                continue;
            }

//                 X
            if(i == 0) {
                area1 = 0;
                area2 = 0;
                area3 = x1[i][j - 1];
            }else if(j == 0) {
                area1 = 0;
                area2 = x1[i - 1][j];
                area3 = 0;
            }else{
                area1 = x1[i - 1][j - 1];
                area2 = x1[i - 1][j];
                area3 = x1[i][j - 1];
            }
            x1[i][j] = (grid[i][j] == 'X') + area2 + area3 - area1;
//                 Y

            if(i == 0) {
                area1 = 0;
                area2 = 0;
                area3 = y1[i][j - 1];
            }else if(j == 0) {
                area1 = 0;
                area2 = y1[i - 1][j];
                area3 = 0;
            }else{
                area1 = y1[i - 1][j - 1];
                area2 = y1[i - 1][j];
                area3 = y1[i][j - 1];
            }
            y1[i][j] = (grid[i][j] == 'Y') + area2 + area3 - area1;
        }
    }

    int ret = 0;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {

            ret += (x1[i][j] == y1[i][j]) && (x1[i][j] >= 1);
        }
    }

    return ret;
}

第四題

參考討論區解答
我當下第一次寫混合的方法，Trie 跟 DP table 定義都不熟，都沒做出來。

struct TrieNode {
    TrieNode *children[26];
    int cost;
    TrieNode()
    {
        fill(begin(children), end(children), nullptr);
        cost = INT_MAX;
    }
};

struct Trie {
    TrieNode *root;
    Trie() { root = new TrieNode(); }

    void insert(string &word, int cost)
    {
        TrieNode *node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index])
                node->children[index] = new TrieNode();
            node = node->children[index];
        }
        node->cost = min(node->cost, cost);
    }

    int search(string &prefix)
    {
        TrieNode *node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (!node->children[index])
                return INT_MAX;
            node = node->children[index];
        }
        return node->cost;
    }
};
class Solution
{
public:
    int minimumCost(string target, vector<string> &words, vector<int> &costs)
    {
        const int n = target.size();
        Trie trie;
        for (int i = 0; i < words.size(); i++) {
            trie.insert(words[i], costs[i]);
        }

        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == INT_MAX)
                continue;
            TrieNode *node = trie.root;
            for (int j = i; j < n; j++) {
                int index = target[j] - 'a';
                if (!node->children[index])
                    break;
                node = node->children[index];
                if (node->cost != INT_MAX)
                    dp[j + 1] = min(dp[j + 1], dp[i] + node->cost);
            }
        }

        if (dp[n] == INT_MAX)
            return -1;
        return dp[n];
    }
};