力扣第 415 场周赛

A

模拟+哈希。

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        vector<int>ans;
        unordered_map<int,int>mp;
        for(auto a:nums)
        {
            mp[a]++;
            if(mp[a]==2)
            {
                ans.push_back(a);
            }
        }
        return ans;
    }
};

B

dp，定义为前i个数字里面用了j个。

using ll=long long;
class Solution {
public:
    long long maxScore(vector<int>& a, vector<int>& b) {
        int n=b.size();
        vector<array<ll,5>>dp(n+1);
        ll MINF=-1e18;
        for(int j=1;j<5;j++)
        {
            dp[0][j]=MINF;
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<4;j++)
            {
                dp[i+1][j+1]=max(dp[i][j+1],dp[i][j]+(ll)a[j]*b[i]);
            }
        }
return dp[n][4];
    }
};

C

//定义Trie和查询最长前缀操作
struct TrieNode {
    TrieNode* chil[26] = {nullptr};
};
class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->chil[index] == nullptr) {
                node->chil[index] = new TrieNode();
            }
            node = node->chil[index];
        }
    }
    vector<int> search(const string& target, int pos) {
        TrieNode* node = root;
        vector<int> pres;
        for (int i = pos; i < target.size(); ++i) {
            int index = target[i] - 'a';
            if (node->chil[index] == nullptr) {
                break;
            }
            node = node->chil[index];
            pres.push_back(i - pos + 1);
        }
        return pres;
    }
};

//接下来愉快写主代码！
class Solution {
public:
    int minValidStrings(vector<string>& words, string target) {
        Trie trie;
        int n = target.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        //将所有单词插入前缀树
        for (const string& word : words) {
            trie.insert(word);
        }
        for (int i = 0; i < n; ++i) {
            if (dp[i] == INT_MAX)//根本到不了这里
                continue;
            vector<int> pres = trie.search(target, i);
            for (int len : pres) {//1～最长前缀都是可行的长度
                dp[i + len] = min(dp[i + len], dp[i] + 1);
            }
        }
        return dp[n] == INT_MAX ? -1 : dp[n];
    }
};

代码解释

1. 定义 Trie 和查询最长前缀操作

struct TrieNode {
    TrieNode* chil[26] = {nullptr};
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }
    
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->chil[index] == nullptr) {
                node->chil[index] = new TrieNode();
            }
            node = node->chil[index];
        }
    }
    
    vector<int> search(const string& target, int pos) {
        TrieNode* node = root;
        vector<int> pres;
        for (int i = pos; i < target.size(); ++i) {
            int index = target[i] - 'a';
            if (node->chil[index] == nullptr) {
                break;
            }
            node = node->chil[index];
            pres.push_back(i - pos + 1);
        }
        return pres;
    }
};

• TrieNode 结构体表示前缀树的一个节点，包含 26 个子节点指针（对应字母 a-z）。
• Trie 类：包含插入单词和搜索最长前缀的功能。
  • insert 方法：将单词插入前缀树。
  • search 方法：从 target 字符串的指定位置 pos 开始，查找从当前位置开始的所有可能有效前缀的长度。

2. 主代码实现

class Solution {
public:
    int minValidStrings(vector<string>& words, string target) {
        Trie trie;
        int n = target.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        // 将所有单词插入前缀树
        for (const string& word : words) {
            trie.insert(word);
        }
        
        for (int i = 0; i < n; ++i) {
            if (dp[i] == INT_MAX) // 根本到不了这里
                continue;
            vector<int> pres = trie.search(target, i);
            for (int len : pres) { // 1～最长前缀都是可行的长度
                dp[i + len] = min(dp[i + len], dp[i] + 1);
            }
        }
        
        return dp[n] == INT_MAX ? -1 : dp[n];
    }
};

• minValidStrings 方法：
  • 初始化：
    • 创建一个 Trie 对象。
    • 初始化一个动态规划数组 dp，大小为 n+1（其中 n 是目标字符串 target 的长度）。dp[i] 表示形成 target 的前 i 个字符所需的最小字符串数量，初始值为 INT_MAX，表示不可达，dp[0] = 0 表示从空字符串开始不需要任何字符串。
  • 构建前缀树：
    • 遍历所有的单词，将它们插入到前缀树中。
  • 动态规划更新：
    • 遍历每个位置 i，如果 dp[i] 不是 INT_MAX（即可以到达位置 i），则从位置 i 开始，利用前缀树查找所有可以匹配的有效前缀的长度。
    • 对于每个有效前缀长度 len，更新 dp[i + len]，即从 i 到 i + len 形成的字符串的最小数量。这里 dp[i + len] = min(dp[i + len], dp[i] + 1) 表示选择最小的字符串数量。
  • 返回结果：
    • 如果 dp[n] 仍然是 INT_MAX，表示无法形成目标字符串，返回 -1。
    • 否则，返回 dp[n]，即形成目标字符串所需的最小字符串数量。

示例解释

• 示例 1：words = ["abc","aaaaa","bcdef"] 和 target = "aabcdabc"，根据给定单词可以形成目标字符串所需的最少字符串数量为 3（"aa" + "bcd" + "abc"）。

• 示例 2：words = ["abababab","ab"] 和 target = "ababaababa"，可以通过两个 "ababa" 形成目标字符串。

• 示例 3：words = ["abcdef"] 和 target = "xyz"，目标字符串无法由任何前缀形成，返回 -1。