LeetCode第 190 场周赛

暴力完事

---

class Solution:
    def isPrefixOfWord(self, sentence: str, a: str) -> int:
        ans = -1
        word = sentence.split(" ")
        # print(word)
        beg = 1
        for w in word:
            if len(a)<=len(w) and a==w[0:len(a)]:
                return beg
            beg += 1
        return ans

一波前缀和完事

---

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        a = [0]*(len(s)+3)
        word = ['a', 'e','i','o','u']
        for i,w in enumerate(s):
            if w in word:
                a[i+1]=1
        for i in range(0,len(s)):
            a[i+1] += a[i]
        ans = 0
        for i in range(k,len(s)+2):
            ans = max(ans,a[i]-a[i-k])
        return ans

---

dfs回溯，记录每个数字的出现次数，在叶节点判断

---

class Solution {
public:
    int pseudoPalindromicPaths (TreeNode* root) {
        ans = 0;
        memset(num,0, sizeof num);
        dfs(root);
        return ans;
    }
    void dfs(TreeNode* root){
        num[root->val]++;
        if(root->left||root->right){
            if(root->left)
                dfs(root->left);
            if(root->right)
                dfs(root->right);
        }
        else if(judge())
            ans++;
        num[root->val]--;
    }
    inline bool judge(){
        int cnt=0;
        for(int i=1; i<10; i++)
            if(num[i]&1)
                cnt++;
        return cnt<=1;
    }
    int ans=0;
    int num[10];//分别表示0到9的数量就行
};

---

二维dp，经典好题

---

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        
        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                dp[i][j] = nums1[i-1]*nums2[j-1];
                dp[i][j] = max(dp[i][j],nums1[i-1]*nums2[j-1] + dp[i-1][j-1]);
                if(i > 1) dp[i][j] = max(dp[i][j],dp[i-1][j]);
                if(j > 1) dp[i][j] = max(dp[i][j],dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};