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

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

image.png

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

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

谢谢开发人员以及 PM,填样例终于安排上了

18

前三题白给 第四题不会。。。

12

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

python 友好的题目,直接 split 然后 startswith

class Solution(object):
    def isPrefixOfWord(self, sentence, searchWord): 
        parts = sentence.split(" ")
        ans = -1
        n = len(parts)
        for i in xrange(0, n):
            if parts[i].startswith(searchWord):
                ans = i+1
                break
        return ans
        

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

  1. 计算前缀和:presum[k] 表示 substr[0, k] 内元音字符的个数,O(n)
  2. 求区间 [x, y] 内的元音个数:presum[y] - presum[x-1],O(1)
  3. 区间长度固定是 k,枚举左端点 l(右端点 l+k-1),O(n)
class Solution {
public:
    const static inline std::string target = "aeiou";
    int maxVowels(string s, int k) {
        vector<int> presum;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int val = 0;
            auto pos = target.find(s[i]);
            if (pos != std::string::npos) val = 1;
            
            if (!i) presum.push_back(val);
            else presum.push_back(presum.back()+val);
        }
        
        int ret = 0;
        for (int i = 0; i + k <= n; ++i) {
            int sum = 0;
            if (!i) sum = presum[i+k-1];
            else sum = presum[i+k-1] - presum[i-1];
            ret = max(ret, sum);
        }
        return ret;
    }
};

C: 二叉树中的伪回文路径

  1. 节点的值只有 [1, 9],用一个计数数组记录路径中每种值出现的个数
  2. 从 root 一直遍历至叶子,再判断这条路径上每种值的个数;数量为单数的值最多只能有 1 种,则能构造成回文串
class Solution {
public:
    int ret = 0;
    vector<int> cnt;
    
    void dfs(TreeNode* root) {
        if (!root) return;
        int scnt = 0;
        cnt[root->val]++;
        if (root->left) {
            scnt++;
            dfs(root->left);
        }
        if (root->right) {
            scnt++;
            dfs(root->right);
        }
        if (!scnt) {
            int odd = 0;
            for (int i = 0; i < 10; ++i)
                if (cnt[i] & 1) odd++;
            if (odd <= 1) ret++;
        }
        cnt[root->val]--;
    }
    
    int pseudoPalindromicPaths (TreeNode* root) {
        ret = 0;
        cnt.assign(10, 0);
        dfs(root);
        return ret;
    }
};

D:两个子序列的最大点积

把两个字符串分别称为 a 串,b 串;长度分别为 n,m;下标从 0 开始

  1. dp(i, j) 表示 a 串的 [i, n-1] 子串 和 b 串的 [j, m-1] 子串中选择出来的最大值
  2. 初始化 dp(n-1, m-1) = a[n-1] * b[m-1];因为本题要求至少必选一项
  3. 状态从右往左推;考虑转移方程
    • 不考虑 a[i],考虑 b[j],相当于从 (i+1, j) 状态直接继承过来: dp(i+1, j) -> dp(i, j)
    • 不考虑 a[i],也不考虑 b[j],相当于从 (i+1, j+1) 状态直接继承过来:dp(i+1, j+1) -> dp(i, j)
    • 选择 a[i],不考虑 b[j],相当于从 (i, j+1) 状态直接继承过来:dp(i, j+1) -> dp(i, j)
    • 仅选择 a[i] 和 b[j]:a[i] * b[j] -> dp(i, j)
    • 选择 a[i] 和 b[j],再加上 (i+1, j+1) 状态的值:a[i] * b[j] + dp(i+1, j+1) -> dp(i, j)
const int INF = 1e9;
int dp[505][505];

class Solution {
public:
    int maxDotProduct(vector<int>& a, vector<int>& b) {
        int n = a.size();
        int m = b.size();
        for (int i = 0; i < 505; ++i)
            for (int j = 0; j < 505; ++j)
                dp[i][j] = -INF;
        
        dp[n-1][m-1] = a[n-1] * b[m-1];
        for (int i = n-1; i >= 0; --i) {
            for (int j = m-1; j >= 0; --j) {
                if (i == n-1 && j == m-1) continue;
                int& ret = dp[i][j];
                
                ret = max(ret, dp[i][j+1]);
                ret = max(ret, dp[i+1][j]);
                ret = max(ret, a[i] * b[j]);
                ret = max(ret, a[i] * b[j] + dp[i+1][j+1]);
            }
        }
        return dp[0][0];
    }
};
10

前三题给了我这次能做完的错觉。。。

6

第三题使用 JavaScript 和 TypeScript 会一直超时. 看图

image.png

4

填了样例样例没过也是绿色的成功运行 有误导性。 第一题标题说是否 结果不是返回true/false,也有点误导。

2

这周有点过于水了

2

今天的简单。第一次ac

2

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

思路

  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

这周是水题娱乐局,给个四题Rust代码吧:

impl Solution {
    pub fn max_dot_product(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n = nums1.len();
        let m = nums2.len();
        if n == 1 && m == 1 {
            return nums1[0]*nums2[0];
        }
        let mut f = vec![vec![std::i32::MIN; m+1]; n+1];
        for i in 0..=m {
            f[0][i] = 0;
        }
        for i in 0..=n {
            f[i][0] = 0;
        }
        let mut ans = std::i32::MIN;
        for i in 1..=n {
            for j in 1..=m {
                f[i][j] = f[i-1][j-1] + nums1[i-1]*nums2[j-1];
                ans = ans.max(f[i][j]); // 答案必须至少乘一次,所以ans在这里更新
                f[i][j] = f[i][j].max(f[i-1][j]);
                f[i][j] = f[i][j].max(f[i][j-1]);
            }
        }
        ans
    }
}
1