[算法]LeetCode第190场周赛20200524

本文主要是介绍[算法]LeetCode第190场周赛20200524，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第190场周赛20200524

20200524

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

题目描述1

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

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

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

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

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

解答1

class Solution {public int isPrefixOfWord(String sentence, String searchWord) {String[] sentenceArray = sentence.split(" ");int i = 0, j;int len = sentenceArray.length;String temp = "";boolean flag = false;Set<String> searchSet = new HashSet<>();searchSet.add(searchWord);while(i < len){temp = sentenceArray[i];i++;if(temp.length() < searchWord.length()){continue;}if(searchSet.contains(temp.substring(0,searchWord.length()))){return i;}}return -1;}
}

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

题目描述2

给你字符串 s 和整数 k 。

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

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

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

解答2

class Solution {public int maxVowels(String s, int k) {int res = 0;int temp = 0;char[] c = s.toCharArray();// slide windowsint left = 0, right = 0;while(right < k){switch(c[right]){case 'a':;case 'e':;case 'i':;case 'o':;case 'u':temp++;res = Math.max(res, temp);// System.out.println("rr< res++");break;default:break;}right++;}while(right < c.length){if(res == k){break;}switch(c[left]){case 'a':;case 'e':;case 'i':;case 'o':;case 'u':temp--;res = Math.max(res, temp);// System.out.println("res--");break;default:break;}left++;switch(c[right]){case 'a':;case 'e':;case 'i':;case 'o':;case 'u':temp++;res = Math.max(res, temp);// System.out.println("res++");break;default:break;}right++;}return res;}
}

1457 二叉树中的伪回文路径

题目描述3

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

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

输入：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] 。

解答3

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int res;public int pseudoPalindromicPaths (TreeNode root) {res = 0;int[] path = new int[10];Arrays.fill(path, 0);recur(root, path);return res;}public void recur(TreeNode root, int[] path){if(root == null){return;}path[root.val] ^= 1;if(root.left == null && root.right == null){int sum = 0;for(int i = 1; i < 10; i++){sum = sum + path[i];}if(sum <= 1){res++;}}recur(root.left, path);recur(root.right, path);path[root.val] ^=1;}
}

优化,用一整个变量来异或，就省去了求和步骤。

if (x->left) dfs(x->left, s^(1<<x->left->val));
if (x->right) dfs(x->right, s^(1<<x->right->val));

1458 两个子序列的最大点积

题目描述4

给你两个数组 nums1 和 nums2 。

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

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

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

解答4

动态规划，有点像72编辑距离的题目

class Solution {public int maxDotProduct(int[] nums1, int[] nums2) {int len1 = nums1.length, len2 = nums2.length;int[][] dp = new int[len1 + 1][len2 + 1];int min = -1000*1000*5000;for(int i = 0; i < len1 + 1; i++){for(int j = 0; j < len2 + 1; j++){dp[i][j] = min;}}for(int i = 1; i < len1 + 1; i++){for(int j = 1; j < len2 + 1; j++){int a = nums1[i-1];int b = nums2[j-1];dp[i][j] = Math.max(dp[i][j], a*b);dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + a*b);// dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]);已经被另外两种情况包含了dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);// dp[i][j] = Math.max(Math.max(nums1[i - 1]*nums2[j - 1],nums1[i - 1]*nums2[j - 1] + dp[i - 1][j - 1]),Math.max(dp[i][j - 1], dp[i - 1][j]));}}return dp[len1][len2];}
}

72. 编辑距离–动态规划扩展

题目描述5

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

解答5

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length(), len2 = word2.length();if(len1 * len2 == 0){return len1 + len2;}int[][] dp = new int[len1 + 1][len2 + 1];//边界for (int i = 0; i < len1 + 1; i++) {dp[i][0] = i;}for (int j = 0; j < len2 + 1; j++) {dp[0][j] = j;}for(int i = 1; i < len1 + 1; i++){for(int j = 1; j < len2 + 1; j++){int dp1 = dp[i - 1][j] + 1;int dp2 = dp[i][j - 1] + 1;int dp3 = dp[i - 1][j - 1];if(word1.charAt(i - 1) != word2.charAt(j - 1)){dp3 += 1;}dp[i][j] = Math.min(Math.min(dp1, dp2), dp3);}}return dp[len1][len2];}
}