讨论/题目交流/🏆 第 190 场力扣周赛/
🏆 第 190 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 检查单词是否为句中其他单词的前缀
4 分 - 定长子串中元音的最大数目
5 分 - 二叉树中的伪回文路径
6 分 - 两个子序列的最大点积

展开讨论
力扣 (LeetCode)发起于 2020-05-24

这次终于能自动填样例了!好评!
这周的题还是比较简单的。
检查单词是否为句中其他单词的前缀
思路很简单,分词,然后一个个比较,如果是前缀则输出下标。

class Solution {
    public int isPrefixOfWord(String sentence, String searchWord) {
        String[] str=sentence.split(" "); //分词,
        for(int i=0;i<str.length;i++){ //按顺序对每个词判断,
            if(str[i].startsWith(searchWord)) //是前缀,
                return i+1; //输出下标。由于输出下标从1开始,所以注意此处+1。
        }
        return -1; //不是前缀,返回-1。
    }
}

定长子串中元音的最大数目
思路也很简单,只要从头到尾遍历一遍,同时维护连续k个字符中的元音数量即可。可以通过类似队列边进边出来判断。

class Solution {
    public int maxVowels(String s, int k) {
        int max=0;
        int count=0;
        int length=s.length();
        for(int i=0;i<length;i++){ //从头到尾遍历,
            char c=s.charAt(i);
            if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u') //如果是元音字母,
                count++; //数量+1。
            if(i-k>=0){ //同时判断要出去的字母,
                c=s.charAt(i-k);
                if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u') //如果是元音字母,
                    count--; //数量-1。
            }
            if(count>max)
                max=count; //记录最大值。
        }
        return max; //返回最大值。
    }
}

二叉树中的伪回文路径
注意到,一个序列是伪回文序列,当且仅当其至多只有一个元素出现奇数次。比如111223344由于只有1出现了奇数次,所以其是伪回文序列。
如果用c1,c2,...,c9来表示1到9的个数,那么,当c1%2+c2%2+...+c9%2<=1时,序列才是伪回文的。
因此,我们只要能记录下路径中1到9的个数,即可利用这点来判断。

class Solution {
    public int count(TreeNode node,int c1,int c2,int c3,int c4,int c5,int c6,int c7,int c8,int c9){
        if(node==null)return 0; //如果节点为空,则直接返回0。
        switch(node.val){ //根据节点的值,进行计数。
            case 1: c1++;break;
            case 2: c2++;break;
            case 3: c3++;break;
            case 4: c4++;break;
            case 5: c5++;break;
            case 6: c6++;break;
            case 7: c7++;break;
            case 8: c8++;break;
            case 9: c9++;break;
        }
        if(node.left==null&&node.right==null){ //如果是叶子节点,则进行判断,
            if(c1%2+c2%2+c3%2+c4%2+c5%2+c6%2+c7%2+c8%2+c9%2<=1) //是回文
                return 1; //则返回1条路径数量。
            return 0; //不是回文则返回0条。
        }
        return count(node.left,c1,c2,c3,c4,c5,c6,c7,c8,c9)+count(node.right,c1,c2,c3,c4,c5,c6,c7,c8,c9); //不是叶子节点,则递归遍历左右节点。
    }
    public int pseudoPalindromicPaths (TreeNode root) {
        return count(root,0,0,0,0,0,0,0,0,0); //计数初始化为0。
    }
}

两个子序列的最大点积
这种题目,最暴力的方法就是列举所有可能并计算,但其复杂度为指数级别的,显然不现实,因此我们可以考虑用动态规划来解决这题。
我们设立dp[i][j]来表示以nums1[i]和nums2[j]结尾的向量的最大点积。
那么,dp[i][j]=nums1[i]*nums2[j]+某个最大值。因为要求非空,所以这个最大值至少为0,此外,既然nums1[i]和nums2[j]都是结尾元素了,那么,只要找nums1[i-1]和nums2[j-1]之前的最大值即可,也就是说,dp[i][j]=nums1[i]*nums2[j]+max(0,dp[0,...,i-1][0,...,j-1])。然而,这么一来,时间复杂度就是O(nums1.length^2*nums2.length^2),显然会超时。
此时,我们可以考虑去存下dp[0,...,i-1][0,...,j-1]的最大值,我们可以用dpmax[i-1][j-1]来记录它。
因此,只要一边更新dp[i][j],一边更新dpmax[i][j],即可实现时间复杂度为O(nums1.length*nums2.length)的算法。最终,只要返回dpmax[nums1.length-1][nums2.length-1]即可。

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int l1=nums1.length;
        int l2=nums2.length;
        int[][]dp=new int[l1][l2];
        int[][]dpmax=new int[l1][l2];
        for(int i=0;i<l1;i++){
            for(int j=0;j<l2;j++){
                if(i==0&&j==0){ //dp[0][0]=nums1[0]*nums2[0]。
                    dp[i][j]=nums1[i]*nums2[j];
                    dpmax[i][j]=dp[i][j];
                    continue;
                }
                int max=0; //由于最大值至少是0,所以此处先取0。
                if(i>0&&j>0&&dpmax[i-1][j-1]>max) //如果dpmax[i-1][j-1]比0大了,就用它。
                    max=dpmax[i-1][j-1];
                dp[i][j]=nums1[i]*nums2[j]+max; //利用递推公式更新dp数组。
                max=dp[i][j]; //将dp[i][j]的值,
                if(i>0&&dpmax[i-1][j]>max)max=dpmax[i-1][j]; //和上边比较,
                if(j>0&&dpmax[i][j-1]>max)max=dpmax[i][j-1]; //和左边比较,
                dpmax[i][j]=max; //确定出最大值,即为dpmax[i][j]的值。
            }
        }
        return dpmax[l1-1][l2-1]; //返回dpmax的右下角,即为正确答案。
    }
}
1
展开全部 31 讨论