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

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

image.png

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

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

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
展开全部 31 讨论