On the shoulders of giants.

weekly-contest-190

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

给你一个字符串 sentence 作为句子并指定检索词为 searchWord ,其中句子由若干用 单个空格 分隔的单词组成。

请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。

  • 如果 searchWord 是某一个单词的前缀,则返回句子 sentence 中该单词所对应的下标(下标从 1 开始)。
  • 如果 searchWord 是多个单词的前缀,则返回匹配的第一个单词的下标(最小下标)。
  • 如果 searchWord 不是任何单词的前缀,则返回 -1

字符串 S 的 「前缀」是 S 的任何前导连续子字符串。

示例 1:

输入:sentence = "i love eating burger", searchWord = "burg"
输出:4
解释:"burg" 是 "burger" 的前缀,而 "burger" 是句子中第 4 个单词。

示例 2:

输入:sentence = "this problem is an easy problem", searchWord = "pro"
输出:2
解释:"pro" 是 "problem" 的前缀,而 "problem" 是句子中第 2 个也是第 6 个单词,但是应该返回最小下标 2 。

示例 3:

输入:sentence = "i am tired", searchWord = "you"
输出:-1
解释:"you" 不是句子中任何单词的前缀。

示例 4:

输入:sentence = "i use triple pillow", searchWord = "pill"
输出:4

示例 5:

输入:sentence = "hello from the other side", searchWord = "they"
输出:-1

提示:

  • 1 <= sentence.length <= 100
  • 1 <= searchWord.length <= 10
  • sentence 由小写英文字母和空格组成。
  • searchWord 由小写英文字母组成。
  • 前缀就是紧密附着于词根的语素,中间不能插入其它成分,并且它的位置是固定的——-位于词根之前。(引用自 前缀_百度百科
题解

分解出每一个单词,判断是否为前缀。

时间复杂度:\(O(n)\)

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        int n = sentence.length(), m = searchWord.length(), index = 0;
        for(int i = 0; i < n; i++) {
            while(i < n && sentence[i] == ' ') i++;
            if(i == n) break;
            index++;
            if(sentence.substr(i, m) == searchWord) {
                return index;
            }
            while(i < n && sentence[i] != ' ') i++;
        }
        return -1;
    }
};

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

给你字符串 s 和整数 k

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为(a, e, i, o, u)。

示例 1:

输入:s = "abciiidef", k = 3
输出:3
解释:子字符串 "iii" 包含 3 个元音字母。

示例 2:

输入:s = "aeiou", k = 2
输出:2
解释:任意长度为 2 的子字符串都包含 2 个元音字母。

示例 3:

输入:s = "leetcode", k = 3
输出:2
解释:"lee"、"eet" 和 "ode" 都包含 2 个元音字母。

示例 4:

输入:s = "rhythms", k = 4
输出:0
解释:字符串 s 中不含任何元音字母。

示例 5:

输入:s = "tryhard", k = 4
输出:1

提示:

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成
  • 1 <= k <= s.length
题解

移动区间统计个数即可。

时间复杂度:\(O(n)\)

class Solution {
public:
    bool check(char c) {
        if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
            return true;
        else return false;
    }
    int maxVowels(string s, int k) {
        int n = s.length(), lef = 0, rig = -1, count = 0, result = 0;
        for(int i = 0; i < k; i++) {
            if(check(s[++rig])) count++;
        }
        result = max(result, count);
        for(int i = k; i < n; i++) {
            if(check(s[lef++])) count--;
            if(check(s[++rig])) count++;
            result = max(result, count);
        }
        return result;
    }
};

二叉树中的伪回文路径

给你一棵二叉树,每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的,当它满足:路径经过的所有节点值的排列中,存在一个回文序列。

请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。

示例 1:

输入:root = [2,3,1,3,1,null,1]
输出:2 
解释:上图为给定的二叉树。总共有 3 条从根到叶子的路径:红色路径 [2,3,3] ,绿色路径 [2,1,1] 和路径 [2,3,1] 。
     在这些路径中,只有红色和绿色的路径是伪回文路径,因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ,绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。

示例 2:

输入:root = [2,1,1,1,3,null,null,null,null,null,1]
输出:1 
解释:上图为给定二叉树。总共有 3 条从根到叶子的路径:绿色路径 [2,1,1] ,路径 [2,1,3,1] 和路径 [2,1] 。
     这些路径中只有绿色路径是伪回文路径,因为 [2,1,1] 存在回文排列 [1,2,1] 。

示例 3:

输入:root = [9]
输出:1

提示:

  • 给定二叉树的节点数目在 1 到 10^5 之间。
  • 节点值在 1 到 9 之间。
题解

遍历二叉树,在叶子节点中判断序列中出现奇数的次数。如果该次数 ≤1,那么存在回文序列,否者不存在。

时间复杂度:\(O(n)\)

/**
 * 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 {
public:
    vector<int> count;
    int result = 0;
    bool check() {
        int sum = 0;
        for(int i = 1; i <= 9; i++) {
            if(count[i] & 1) sum++;
        }
        return sum <= 1;
    }
    void search(TreeNode* root) {
        if(root == NULL) return;
        count[root->val]++;
        if(root->left == NULL && root->right == NULL) {
            if(check()) result++;
        } else {
            search(root->left);
            search(root->right);
        }
        count[root->val]--;
    }
    int pseudoPalindromicPaths (TreeNode* root) {
        count = vector<int> (10, 0);
        search(root);
        return result;
    }
};

两个子序列的最大点积

给你两个数组 nums1 和 nums2 。

请你返回 nums1nums2 中两个长度相同的 非空 子序列的最大点积。

数组的非空子序列是通过删除原数组中某些元素(可能一个也不删除)后剩余数字组成的序列,但不能改变数字间相对顺序。比方说,[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。

示例 1:

输入:nums1 = [2,1,-2,5], nums2 = [3,0,-6]
输出:18
解释:从 nums1 中得到子序列 [2,-2] ,从 nums2 中得到子序列 [3,-6] 。
它们的点积为 (2*3 + (-2)*(-6)) = 18 。

示例 2:

输入:nums1 = [3,-2], nums2 = [2,-6,7]
输出:21
解释:从 nums1 中得到子序列 [3] ,从 nums2 中得到子序列 [7] 。
它们的点积为 (3*7) = 21 。

示例 3:

输入:nums1 = [-1,-1], nums2 = [1,1]
输出:-1
解释:从 nums1 中得到子序列 [-1] ,从 nums2 中得到子序列 [1] 。
它们的点积为 -1 。

提示:

  • 1 <= nums1.length, nums2.length <= 500
  • -1000 <= nums1[i], nums2[i] <= 100

点积:

定义 a = [a1a2,…, an] b = [b1b2,…, bn] 的点积为:
这里的 Σ 指示总和符号。
题解

动态规划,设:\(dp_{x,y}\) 为 a 数组中取前 x 个,b 数组中取前 y 个的最大点积。

有动态转移方程:\(dp_{x,y}=\max (dp_{x-1,y-1}+a_x\cdot b_y,dp_{x-1,y},dp_{x,y-1},a_x\cdot b_y)\)

时间复杂度:\(O(nm)\)

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

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注