dustfree's blog
0%

Weekly Contest 190

Posted on In ,

Question

  1. Check If a Word Occurs As a Prefix of Any Word in a Sentence

    Given a sentence that consists of some words separated by a single space, and a searchWord.You have to check if searchWord is a prefix of any word in sentence.

    Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).

    If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

    A prefix of a string S is any leading contiguous substring of S.

    Example 1:
    Input: sentence = “i love eating burger”, searchWord = “burg”
    Output: 4
    Explanation: “burg” is prefix of “burger” which is the 4th word in the sentence.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int isPrefixOfWord(String sentence, String searchWord) {
    if (sentence.length() < searchWord.length()) {
        return -1;
    }
    
    String[] str = sentence.split(" ",0);
    for (int i = 0; i < str.length; i++) {            
        int j = 0;
        while (j < searchWord.length()) {
            if (j == str[i].length()) {
                break;    
            }if (j < str[i].length() && str[i].charAt(j) != searchWord.charAt(j)) {
                break;
            }else {
                j++;
            }
        }
        if (j == searchWord.length()) {
            return i+1;
        }
    }
    return -1;
}

Question

  1. Maximum Number of Vowels in a Substring of Given Length

    Given a string s and an integer k.

    Return the maximum number of vowel letters in any substring of s with length k.

    Vowel letters in English are (a, e, i, o, u).

    Example 1:

    Input: s = “abciiidef”, k = 3
    Output: 3
    Explanation: The substring “iii” contains 3 vowel letters.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public int maxVowels(String s, int k) {
    if (s.length() <= 0 || k == 0 || s.length() < k) {
        return 0;
    }
    
    int count = 0;
    int max = 0;
    for (int i = 0, j = 0; i < s.length() && j < s.length(); j++) {
        char c = s.charAt(j);
        if (j < i+k) {
            if (valid(c)) {
                count++;
            }                
            max = Math.max(max, count);
            continue;
        }
        if (valid(c)) {
            count++;
        }
        if (valid(s.charAt(i))) {
            count--;
            
        }       
        i++;
        max = Math.max(max, count);
    }
            
    return max;
}

public boolean valid(char c) {
    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ) {
        return true;   
    }
    return false;
}

Question

  1. Pseudo-Palindromic Paths in a Binary Tree

    Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

    Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

    Example 1:
    Input: root = [2,3,1,3,1,null,1]
    Output: 2

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
Algorithm: dfs + backtracking
*/
int res = 0;
public int pseudoPalindromicPaths (TreeNode root) {
    if (root == null) {
        return 0;
    }
    int[] num = new int[10];
    dfs(root, num, 0);
    return res;
    
}
public void dfs(TreeNode root, int[] num, int count) {
    if (root == null) {
        return;
    }
    num[root.val]++;
    if (num[root.val]%2 == 0) {
        count--;
    }else {
        count++;
    }
    if (root.left == null && root.right == null) {
        if (count < 2) {
            res++;
        }
    }else {
        if (root.left != null) {
            dfs(root.left, num, count);                          
        }
        if (root.right != null) {
            dfs(root.right, num, count);
        }
    }
    num[root.val]--;
}

Question

  1. Max Dot Product of Two Subsequences

    Given two arrays nums1 and nums2.

    Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.

    A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).

    Example 1:

    Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
    Output: 18
    Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
    Their dot product is (23 + (-2)(-6)) = 18.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*        
Algorithm：这题一看应该能反应出是dp，题目类似于1143. Longest Common Subsequence。处理subsequence的解法
状态转移方程 设p = nums1[i] * nums2[j]，p > 0, 则状态转移方程dp[i][j] = Max(dp[i-1][j-1]+p, dp[i-1][j], dp[i][j-1], p);
p < 0 则状态转移方程 dp[i][j] = Max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1], p);
*/
public int maxDotProduct(int[] nums1, int[] nums2) {
    int l1 = nums1.length;
    int l2 = nums2.length;
    if (nums1.length == 0 || nums2.length == 0) {
        return 0;
    }
    
    int[][] dp = new int[l1][l2];
    
    dp[0][0] = nums1[0] * nums2[0];
    for (int i = 1; i < l1; i++) {
        int p = nums1[i] * nums2[0];
        dp[i][0] = Math.max(dp[i-1][0], p);
    }
    
    for (int j = 1; j < l2; j++) {
        int p = nums2[j] * nums1[0];
        dp[0][j] = Math.max(dp[0][j-1],p);
    }
            
    for (int i = 1; i < l1; i++) {
        for (int j = 1; j < l2; j++) {
            int p = nums1[i] * nums2[j];
            if (p > 0) {
                if (dp[i-1][j-1] > 0) {
                    dp[i][j] = dp[i-1][j-1] + p;                        
                }else {
                    dp[i][j] = p;
                }
            }else {
                dp[i][j] = Math.max(dp[i-1][j-1], p);
            }
            
            dp[i][j] = Math.max(dp[i][j], Math.max(dp[i-1][j],dp[i][j-1]));
            
        }
    }
    return dp[l1-1][l2-1];
}