讨论/题目交流/🏆 第 190 场力扣周赛/
🏆 第 190 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 检查单词是否为句中其他单词的前缀
4 分 - 定长子串中元音的最大数目
5 分 - 二叉树中的伪回文路径
6 分 - 两个子序列的最大点积

展开讨论
力扣 (LeetCode)发起于 2020-05-24

检查单词是否为句中其他单词的前缀

思路

  1. 就按照要求模拟

答题

    int isPrefixOfWord(string sentence, string searchWord) {
        int ans = -1;
        int i = 0;
        stringstream ss(sentence);
        string word;
        while (ss >> word) {
            if (word.size() >= searchWord.size()) {
                bool flag = true;
                for (int j = 0; j < searchWord.size(); j++) {
                    if (word[j] != searchWord[j]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    ans = i;
                    break;
                }
            }
            i++;
        }
        return ans == -1 ? ans : ans + 1;
    }

定长子串中元音的最大数目

思路

  1. 滑动窗口

答题

    int maxVowels(string s, int k) {
        unordered_set<char> us({ 'a', 'e', 'i', 'o', 'u' });
        
        int ans = 0;
        int i = 0;
        int j = 0;
        int cnt = 0;
        while (j < s.size()) {
            while (j < s.size() && j - i < k) {
                cnt += (us.count(s[j]) != 0);
                j++;
            }
            ans = max(ans, cnt);

            while (true) {
                cnt -= (us.count(s[i]) != 0);
                i++;
                if (i == j || us.count(s[i]) != 0) break;
            }
        }
        return ans;
    }

二叉树中的伪回文路径

思路

  1. 题目所说的路径指的是从根节点到叶子节点,英文:Return the number of pseudo-palindromic paths going from the root node to leaf nodes.
  2. 所以只需要在到叶子节点的时候进行计算
  3. 使用 dfs + 回溯,可以将一路上走过节点的 val 保存起来
  4. 伪回文的判断只需要确定出现的字符个数,保证数值中只有一个奇数个,其他数值都是偶数个
  5. 因此保存 val 时可以使用 unordered_map
    41. 或者因为数值范围 1-9 ,可以使用数组标记

答题

class Solution {
public:
    int pseudoPalindromicPaths(TreeNode* root) {
        unordered_map<int, int> vals;
        int ans = 0;
        dfs(root, vals, ans);
        return ans;
    }

    void dfs(TreeNode* root, unordered_map<int, int>& vals, int& ans) {
        if (root == nullptr) return;
        vals[root->val]++;

        if (root->left == nullptr && root->right == nullptr) {
            ans += check(vals);
        }
        dfs(root->left, vals, ans);
        dfs(root->right, vals, ans);

        vals[root->val]--;
    }

    bool check(unordered_map<int, int>& vals) {
        bool singleFlag = false;
        for (auto it = vals.begin(); it != vals.end(); it++) {
            if (it->second % 2 == 0) continue;
            if (singleFlag) return false;
            singleFlag = true;
        }
        return true;
    }
};

两个子序列的最大点积

思路

  1. dp[i][j] ,到 nums1[i - 1]nums2[j - 1] 为止的子序列的最大点积
  2. 转移,最大点积在以下几种情况中产生
    21. 选 nums1[i - 1] * nums2[j - 1] ,不选 dp[i-1][j-1]
    22. 选 nums1[i - 1] * nums2[j - 1] ,并且加上 dp[i-1][j-1]
    23. 不选 nums1[i - 1] * nums2[j - 1] ,选择 dp[i - 1][j]
    24. 不选 nums1[i - 1] * nums2[j - 1] ,选择 dp[i][j - 1]

答题

    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, INT_MIN));

        for (int i = 1; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); j++) {
                dp[i][j] = max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1];
                dp[i][j] = max({ dp[i][j], dp[i - 1][j], dp[i][j - 1] });
            }
        }

        return dp.back().back();
    }

致谢

好久没有做完周赛了,虽然排名垫底,我也要发一下~~~~

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

如果感觉还不错就点个赞吧~

这是 我的leetcode ,帮助我收集整理题目,可以方便的 visual studio 调试,欢迎关注,star

2
展开全部 31 讨论