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

★解题思路

使用 String.split() 对字符串按照单词分割, 然后使用 String.startsWith() 判断是否前缀.

代码展示

class Solution {   public int isPrefixOfWord(String sentence, String searchWord) {       String[] words = sentence.split(" ");       for (int i = 0; i < words.length; i++) {           if (words[i].startsWith(searchWord)) {               return i + 1;           }       }       return -1;   } }

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

★解题思路

类似于滑动窗口, 维护当前元素之前的 k 个元素中的元音字母数量即可.

代码展示

class Solution {   public int maxVowels(String s, int k) {       int res = 0;       int cnt = 0;       char[] str = s.toCharArray();       // 前 k - 1 个       for (int i = 0; i < k - 1; i++) {           cnt += isVowel(str[i]) ? 1 : 0;       }       // 每次循环统计 (i - k, i] 这 k 个字符的元音数量       for (int i = k - 1; i < str.length; i++) {           cnt += isVowel(str[i]) ? 1 : 0;           res = Math.max(res, cnt);           cnt -= isVowel(str[i - k + 1]) ? 1 : 0;       }       return res;   }   private boolean isVowel(char c) {       return c == 'a' || c == 'e' || c == 'i' ||               c == 'o' || c == 'u';   } }

No.3 二叉树中的伪回文路径

★解题思路

判断伪回文路径实际比回文路径简单, 我们只需要判断每种字符的数量是否偶数即可.

最多允许一种字符的数量为奇数, 否则这些字符就无法构成回文串.

代码展示

class Solution {   public int pseudoPalindromicPaths (TreeNode root) {       Map<Integer,Integer> valCount = new HashMap<>();       return dfs(root, valCount);   }   private int dfs(TreeNode cur, Map<Integer,Integer> valCount) {       if (cur == null) {           return 0;       }       int res = 0;       valCount.put(cur.val, valCount.getOrDefault(cur.val, 0) + 1);       if (cur.left == null && cur.right == null) {           int odd = 0;           for (var e : valCount.entrySet()) {               odd += e.getValue() % 2;           }           res += odd <= 1 ? 1 : 0;       } else {           res += dfs(cur.left, valCount);           res += dfs(cur.right, valCount);       }       valCount.put(cur.val, valCount.get(cur.val) - 1);       return res;   } }

No.4 两个子序列的最大点积

★解题思路

动态规划:

i.定义状态: f[i][j] 表示 nums1 的前 i 个元素与 nums2 的前 j 个元素的非空子序列的最大点积

ii.状态转移: 选 nums1[i - 1] * nums2[j - 1] (第 i 个和第 j 个元素的乘积), 或者不选; 具体转移见代码注释

iii.边界状态: 因为至少要选一次, 即不允许出现空子序列的情况, 所以 f[0][j] 或 f[i][0] 皆为非法状态, 应设为负无穷

对称地, 圆心还有一种情况, 就是在上面. 即任意一对点都可以确定两个圆心. 我们枚举每一对点, 然后对于确定的圆心计算这个圆可以圈出多少个点, 最后取最大即可.

代码展示

class Solution {   public int maxDotProduct(int[] nums1, int[] nums2) {       int n = nums1.length;       int m = nums2.length;       int[][] f = new int[n + 1][m + 1];       for (int i = 0; i <= n; i++) {           Arrays.fill(f[i], -0x3f3f3f3f);       }       for (int i = 1; i <= n; i++) {           for (int j = 1; j <= m; j++) {               // 转移一: 选 nums1 的第 i 个元素和 nums2 的第 j 个元素               // 因为 f[i][j] 至少选一组, 所以 f[i - 1][j - 1] 可能小于 0               // 既然选了 nums1[i - 1] * nums2[j - 1]               // 所以前 i - 1 个和 j - 1 个可以都不选               f[i][j] = Math.max(0, f[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1];               // 转移二: 不选当前的乘积               f[i][j] = Math.max(f[i][j], f[i - 1][j]);               f[i][j] = Math.max(f[i][j], f[i][j - 1]);           }       }       return f[n][m];   } }

杭州上岸算法网络科技有限公司

上岸科技是一家【死磕100%上岸率】的小公司。

核心团队和老师均来自于行业内知名公司，我们坚持采用小班课形式，并结合大量”面试式“和”白板“的教学和交流形式，最终做到摆渡【每个人】成功上岸的承诺。

我们对每个人负责，上岸，一个都不能少！

扫码关注公众号，获取最新刷题动态