Leetcode第190次周赛解题报告

这次周赛总体而言还是很简单的，加上灵光闪现，速度AK。
模拟赛成功拿到19/3300名次，动态规划还是要加强练习。

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

模拟题，上来照题意对拍即可，因为他没有要求做模式匹配，也没有要求更高级的算法
前缀匹配直接暴力匹配即可
求解顺序：

• 将输入内容按空格分割
• 遍历每一个单词，假如匹配则返回下标+1
• 假如没有任何一个匹配成功则返回-1

/**
 * @param {string} sentence
 * @param {string} searchWord
 * @return {number}
 */
var isPrefixOfWord = function(sentence, searchWord) {
    const match = (a,b)=>{
        const [lenA,lenB] = [a.length,b.length]
        if(lenA < lenB) return false
        for(let i = 0;i < lenB;i++) {
            if(a[i]!==b[i]) return false
        }
        return true
    }
    const words = sentence.split(" ")
    for(let i = 0;i < words.length;i++) {
        if(match(words[i], searchWord)) return i+1
    }
    return -1
};

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

根据题意知该题目是滑动窗口，也就是说给定一个大小为K的窗口，询问该窗口内出现过的元音音节最多是多少个。
求解顺序：

• 维护一个ans计数器用于记录最多的次数，维护now用于记录当前出现次数
• 扩展窗口：查看当前窗口边界下一个是否为元音，假如是则now+1
• 缩小窗口：查看以前窗口边界是否为元音，假如是则now-1，直到窗口大小为K位置
• 维护答案：假如now比ans大，则将答案更新为now

class Solution {
public:
    bool ok(char n) {
        return n=='a'||n=='e'||n=='i'||n=='o'||n=='u';
    }
    int maxVowels(string s, int k) {
        int ans = 0;
        int left = 0;
        int now = 0;
        for(int i = 0;i < s.size();i++) {
            if(ok(s[i])) now++;
            while(i-left+1 > k) {
                if(ok(s[left])) now--;
                left++;
            }
            ans = max(ans,now);
        }
        return ans;
    }
};

1457.二叉树中的伪回文路径

该题目我认为主要考察归纳方法，题意归纳起来即：在叶子节点时，所走路径是否满足回文串条件。
回文串条件：对于一串字符串，只有0个或1个字母是只出现过奇数次的，其他字母出现过偶数次。
为了到达子节点，使用深度搜索。
求解顺序：

• 对树进行深度搜索，路径中维护计数器count。
• 假如是叶子节点，那么开始判断当前所走的这条路径是否是伪回文路径，是则计数器ans+1
• 返回计数器

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int count[11]={0};
    int ans = 0;
public:
    bool ok() {
        int cnt = 0;
        int cntSingle = 0;
        for(int i = 0;i < 11;i++) {
            if(count[i]>0) cnt++;
            if(count[i]%2==1) cntSingle++;
        }
        return cnt > 0 && cntSingle <= 1;
    }
    int pseudoPalindromicPaths (TreeNode* root) {
        count[root->val]++;
        if(root->left!=0) pseudoPalindromicPaths(root->left);
        if(root->right!=0) pseudoPalindromicPaths(root->right);
        if(root->right==0&&root->left==0) {
            if(ok()) ans++;
        }
        count[root->val]--;
        return ans;
    }
};

1458. 两个子序列的最大点积

对于dp[i][j]，令其维护截至nums1[i]与nums2[j]的最大点积
因此状态转移是如下的，对于每一对i,j：

• 若选(i,j)，则需要在dp[i-1][j-1]的基础上增加nums1[i] * nums[2]
• 若不选，则比较dp[i][j]和dp[i-1][j]、dp[i][j-1]的大小，因为已经默认(i,j)有一个有可能已经被选过了，不能再选

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxDotProduct = function(nums1, nums2) {
        const dp = []
        const [n,m] = [nums1.length,nums2.length]
        for(let i = 0;i < n;i++) {
            const arr = []
            for(let j = 0; j < m;j++){
                arr.push(0)
            }
            dp.push(arr)
        }
        for(let i = 0;i < n;i++) {
            for(let j = 0; j < m;j++){
                const nowS = nums1[i] * nums2[j]
                dp[i][j] = nowS
                if(i > 0) dp[i][j] = Math.max(dp[i][j],dp[i-1][j])
                if(j > 0) dp[i][j] = Math.max(dp[i][j],dp[i][j-1])
                if(i > 0 && j > 0) dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+nowS)
            }
        }
        return dp[n-1][m-1]
};