leetcodeWk190

写在前面

这次的周赛是真的简单

第 190 场周赛

题目

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

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

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

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

提示:

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

每啥好说的,直接模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int isPrefixOfWord(String sentence, String searchWord) {
String []strs=sentence.split(" ");
int d=0;
for(String str : strs){
d++;
char[] a=str.toCharArray();
char[] b=searchWord.toCharArray();
if(a.length < b.length) continue;
int j=0;
for(j=0;j<b.length;j++){
if(a[j]!=b[j]) break;
}
if(j==b.length) return d;
}
return -1;
}
}

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

给你字符串 s 和整数 k

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

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

提示:

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

维护一段区间的元音字母个数即可,每一段可由增加一个减少一个得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private int check(char c){
if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u') return 1;
return 0;
}
public int maxVowels(String s, int k) {
int ans=0;
int cur=0;
char []str=s.toCharArray();
for(int i=0;i<k;i++){
cur+=check(str[i]);
}
ans=cur;
for(int i=k;i<str.length;i++){
cur = cur-check(str[i-k])+check(str[i]);
ans=Math.max(cur,ans);
}
return ans;
}
}

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

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

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

示例 1:

img

1
2
3
4
输入: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:

img

1
2
3
4
输入: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:

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

提示:

  • 给定二叉树的节点数目在 110^5 之间。
  • 节点值在 19 之间。

按题意枚举所有的路径,再统计一下即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
int ans=0;
void DFS(TreeNode cur,int [] arr){
if(cur==null) return;
arr[cur.val-1]++;
if(cur.left==null&&cur.right==null){
int d=0;
for(int i=0;i<9;i++){
d+=(arr[i]%2);
}
ans+= (d<=1) ? 1:0;
}
DFS(cur.left,arr);
DFS(cur.right,arr);
arr[cur.val-1]--;
}
public int pseudoPalindromicPaths (TreeNode root) {
int [] arr=new int[9];
ans=0;
DFS(root,arr);
return ans;
}
}

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

给你两个数组 nums1nums2

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

点积:

1
2
3
4
5
定义 a = [a1, a2,…, an] 和 b = [b1, b2,…, bn] 的点积为:



这里的 Σ 指示总和符号。

考虑$dp[i][j]$表示考虑前$i$个$a$元素和前$j$个$b$元素.

转移很容易得出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int maxDotProduct(int[] nums1, int[] nums2) {
int n=nums1.length;
int m=nums2.length;
int ans=-1000*1000;
int [][]dp=new int[n+1][m+1];
dp[0][0]=-10000000;
for(int i=0;i<=n;i++){dp[i][0]=dp[0][0];}
for(int j=0;j<=m;j++){dp[0][j]=dp[0][0];}
for(int i=1;i<=n;i++){
int x=nums1[i-1];
for(int j=1;j<=m;j++){
int y=nums2[j-1];
dp[i][j]=Math.max(dp[i-1][j-1]+x*y,Math.max(x*y,dp[i-1][j-1]));
dp[i][j]=Math.max(Math.max(dp[i-1][j],dp[i][j-1]),dp[i][j]);
ans=Math.max(ans,dp[i][j]);
}
}
return ans;
}
}

总结

自己还是太憨了