1170. Compare Strings by Frequency of the Smallest Character

2019/12/14 shiji

Let’s define a function f(s) over a non-empty string s, which calculates the frequency of the smallest character in s. For example, if s = "dcce" then f(s) = 2 because the smallest character is "c" and its frequency is 2.

Now, given string arrays queries and words, return an integer array answer, where each answer[i] is the number of words such that f(queries[i]) < f(W), where W is a word in words.

Example 1:

Input:

 queries = ["cbd"], words = ["zaaaz"]

Output:

[1]

Explanation:

 On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").

Example 2:

Input:

 queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]

Output:

 [1,2]

Explanation:

 On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").

Constraints:

1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j], words[i][j] are English lowercase letters.

Straight forward solution O(q * w)

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] result = new int[queries.length];
        for (int i = 0 ; i < queries.length; i ++){
            int score = s(queries[i]);
            
            for (String w : words){
                if (s(w) > score){
                    result[i] ++;
                }
            }
        }
        return result;
    }
    
    public static int s(String s) {
        char min = 'z';
        char[] ca = s.toCharArray();
        for(char c : ca){
            if (c < min){
                min = c;
            }
            if (c == 'a'){
                break;
            }
        }
        int r = 0;
        for(char c : ca){
            if (c == min)
                r ++;
        }
        return r;
    }
}

Optimized solution O (q + w)

since we have 1 <= queries[i].length, words[i].length <= 10

which means query will have only 10 possible values (limited), so for the result.

so we can use counting.

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        
		int[] freqCounter = new int[11];
		int[] result = new int[queries.length];
		for (int i = 0; i < words.length; i++) {
			int freq = s(words[i]);
			freqCounter[freq]++;
		}

		for (int i = 1; i < freqCounter.length; i++) {
			freqCounter[i] += freqCounter[i - 1];
		}
		for (int i = 0; i < queries.length; i++) {
			int freq = s(queries[i]);
			result[i] = words.length - freqCounter[freq];
		}
        
        return result;
    }
    
    public static int s(String s) {
        char min = 'z';
        int r = 0;
        char[] ca = s.toCharArray();
        for(char c : ca){
            if (c < min){
                r = 1;
                min = c;
            } else if(c == min) {
                r ++;
            }

        }
        return r;
    }
    
}

Leetcode

1278. Palindrome Partitioning III

2019/12/01 shiji

You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters.
Then divide s into k non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input:

 s = "abc", k = 2

Output:

Explanation:

 You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

Example 2:

Input:

 s = "aabbc", k = 3

Output:

Explanation:

 You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input:

 s = "leetcode", k = 8

Output:

Constraints:

1 <= k <= s.length <= 100.
s only contains lowercase English letters.

Failed to build the dp during the contest : ( . it was quite close

class Solution {
    public int palindromePartition(String s, int k) {
        if (k == s.length()){
            return 0;
        }
        
        int[][] dp = new int[s.length()+1][k+1];
        
        
        for (int i = 0; i <= s.length(); i++)
            for (int j = 0; j <= k; j++)
                dp[i][j] = s.length();
        
        dp[0][0] = 0;
        for (int i = 0; i < s.length(); i ++){
          
            for (int j = 0; j < k; j ++){
                
                for (int len = 1; i + len <= s.length(); len++) {
                    int cost = 0;

                    for (int a = i, b = i + len - 1; a < b; a++, b--){
                        if (s.charAt(a) != s.charAt(b)){
                            cost ++;
                        }
                    }
    

                    dp[i + len][j + 1] = Math.min(dp[i + len][j + 1], dp[i][j] + cost);
                }
            }
        }
        
        return dp[s.length()][k];
    }
    

}

Few things to point out:

I initialize each value of dp with s.length(), since it can’t be worse than replacing every chars. Integer.MAX_VALUE will cause an integer overflow while building the dp

Leetcode

1277. Count Square Submatrices with All Ones

2019/12/01 shiji

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input:

 matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]

Output:

Explanation:

 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is one square of side 3.
Total number of squares = 10 + 4 + 1 = 15

Example 2:

Input:

 matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]

Output:

Explanation:

 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7

Constraints:

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

Example:

[0,1,1,1],
[1,1,1,1],
[0,1,1,1]

count single ones
count 2×2
count 3×3
……

Goal: reduce n x n to (n-1)x(n-1) … to 2×2

Now scan 2×2 block, for each position(i,j) scan (i+1,j) (i,j+1) (i+1, j+1)
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]

if the 2×2 scanning block contains 0, update (i,j) to 0
[0,1,1,1],
[0,1,1,1],
[0,1,1,1]

then we can reduce it by removing (ignoring) the last row and column.

[0,1,1],
[0,1,1]

Then walk through with the 2×2 scanning block again.

the counter could be updated when the whole 2×2 block is 1, OR count number of ones in the next round.

Version A, update counter during 2×2 scan

class Solution {
    public int countSquares(int[][] matrix) {
        int c = 0;
        
        int m  = matrix.length;
        int n  = matrix[0].length;
        
        for (int i = 0; i < m; i ++){
            for (int j = 0; j < n; j ++){
                if (matrix[i][j] == 1){
                    c++;
                } 
            }
        }
        
        
        while (m > 1 && n > 1){
            for (int i = 0; i < m-1; i ++){
                for (int j = 0; j < n-1; j ++){
                    if (  matrix[i][j]     == 0 
                       || matrix[i+1][j]   == 0
                       || matrix[i][j+1]   == 0
                       || matrix[i+1][j+1] == 0)
                    {
                        matrix[i][j] = 0;
                    }  else {
                        c++;
                    }
                }
            }
            // lower m and n (ignoring last row and column)
            m --;
            n --;
        }
        return c;
        
    }
}

B, a more compact version, update counter next round, count number of ones.
slightly slower for more loops

class Solution {
    public int countSquares(int[][] matrix) {
        int c = 0;
        
        int m  = matrix.length;
        int n  = matrix[0].length;
        
        
        
        while (m > 0 && n > 0){
            
            for (int i = 0; i < m; i ++){
                for (int j = 0; j < n; j ++){
                    if (matrix[i][j] == 1){
                        c++;
                    } 
                }
            }
            
            
            for (int i = 0; i < m-1; i ++){
                for (int j = 0; j < n-1; j ++){
                    if (matrix[i][j] == 0 
                       || matrix[i+1][j] == 0
                       || matrix[i][j+1] == 0
                       || matrix[i+1][j+1] == 0){
                        matrix[i][j] = 0;
                    }
                }
            }
            // lower m and n (ignoring last row and column)
            m --;
            n --;
        }
        return c;
        
    }
}

A: 86-110 ms
B: 160-170 ms

Leetcode

1276. Number of Burgers with No Waste of Ingredients

2019/12/01 shiji

Given two integers tomatoSlices and cheeseSlices. The ingredients of different burgers are as follows:

Jumbo Burger: 4 tomato slices and 1 cheese slice.
Small Burger: 2 Tomato slices and 1 cheese slice.

Return [total_jumbo, total_small] so that the number of remaining tomatoSlices equal to 0 and the number of remaining cheeseSlices equal to 0. If it is not possible to make the remaining tomatoSlices and cheeseSlices equal to 0 return [].

Example 1:

Input:

 tomatoSlices = 16, cheeseSlices = 7

Output:

 [1,6]

Explantion:

 To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese. There will be no remaining ingredients.

Example 2:

Input:

 tomatoSlices = 17, cheeseSlices = 4

Output:

[]

Explantion:

 There will be no way to use all ingredients to make small and jumbo burgers.

Example 3:

Input:

 tomatoSlices = 4, cheeseSlices = 17

Output:

[]

Explantion:

 Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.

Example 4:

Input:

 tomatoSlices = 0, cheeseSlices = 0

Output:

 [0,0]

Example 5:

Input:

 tomatoSlices = 2, cheeseSlices = 1

Output:

 [0,1]

Constraints:

0 <= tomatoSlices <= 10^7
0 <= cheeseSlices <= 10^7

Should be an easy question..

class Solution {
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        
        List<Integer> result = new ArrayList<>();
        
        if (tomatoSlices % 2 ==1 || cheeseSlices * 4 < tomatoSlices || cheeseSlices * 2 > tomatoSlices){
            return result;
        }
        
        int x = (tomatoSlices - cheeseSlices*2)/2;
        result.add(x);
        result.add(cheeseSlices-x);
        
        return result;
    }
}

Leetcode

1275. Find Winner on a Tic Tac Toe Game

2019/12/01 shiji

Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares (” “).
The first player A always places “X” characters, while the second player B always places “O” characters.
“X” and “O” characters are always placed into empty squares, never on filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return “Draw”, if there are still movements to play return “Pending”.

You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example 1:

Input:

 moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]

Output:

"A"

Explanation:

 "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "

  "
"   " -> "   " -> " X " -> " X " -> "

 "
"   "    "O  "    "O  "    "OO "    "OO

Example 2:

Input:

 moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]

Output:

"B"

Explanation:

 "B" wins.
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XX

"
"   " -> " O " -> " O " -> " O " -> "XO " -> "X

 " 
"   "    "   "    "   "    "   "    "   "    "

Example 3:

Input:

 moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]

Output:

 "Draw"

Explanation:

 The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"

Example 4:

Input:

 moves = [[0,0],[1,1]]

Output:

 "Pending"

Explanation:

 The game has not finished yet.
"X  "
" O "
"   "

Constraints:

1 <= moves.length <= 9
moves[i].length == 2
0 <= moves[i][j] <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.

class Solution {
    public String tictactoe(int[][] moves) {
        
        
        for (int a = 0; a <= 1; a++ ){
            int[] x = new int[3];
            int[] y = new int[3];
            int[] v = new int[2];
            
            for (int i = a ; i < moves.length; i += 2){
                x[moves[i][0]] ++;
                y[moves[i][1]] ++;
                if (moves[i][0] == moves[i][1]){
                    v[0] ++;
                }
                if (moves[i][0] == 2 - moves[i][1]) {
                    v[1] ++;
                }
            }

            if (x[0] == 3 || x[1] == 3 ||x[2] == 3 || y [0] == 3 || y [1] == 3|| y [2] == 3 || v[0] == 3 || v[1] == 3){
                return a==0? "A":"B";
            }
        }
    
        return moves.length == 9? "Draw":"Pending";
    }
}

Leetcode

1269. Number of Ways to Stay in the Same Place After Some Steps

2019/11/23 shiji

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input:

 steps = 3, arrLen = 2

Output:

Explanation:

There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:

Input:

 steps = 2, arrLen = 4

Output:

Explanation:

 There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:

Input:

 steps = 4, arrLen = 2

Output:

Constraints:

1 <= steps <= 500
1 <= arrLen <= 10^6

class Solution {
    public int numWays(int steps, int arrLen) {
        int end = Math.min(steps, arrLen);
        
        int mod = 1000000000 + 7;
        long[][] dp = new long[steps+1][end+5];
        
        dp[0][0] = 1;
        
        for (int i = 0; i < steps; i++) {
            dp[i+1][0] = (dp[i][0] + dp[i][1]) % mod;
            for (int j = 1; j < end; j++) {
                dp[i+1][j] = (dp[i][j-1] + dp[i][j] + dp[i][j+1]) % mod;
            }
        }
        return (int) (dp[steps][0]);
    }
}

Leetcode

1268. Search Suggestions System

2019/11/23 shiji

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input:

 products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

Output:

 [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]

Explanation:

 products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

Example 2:

Input:

 products = ["havana"], searchWord = "havana"

Output:

 [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:

Input:

 products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"

Output:

 [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input:

 products = ["havana"], searchWord = "tatiana"

Output:

 [[],[],[],[],[],[],[]]

Constraints:

1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
All characters of products[i] are lower-case English letters.
1 <= searchWord.length <= 1000
All characters of searchWord are lower-case English letters.

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        
        List<List<String>> r = new ArrayList<>();
        Arrays.sort(products);

        for (int i = 0; i < searchWord.length(); i ++){
            List<String> rr = new ArrayList<>();
            String prefix = searchWord.substring(0,i+1);

            for (int j = 0; j < products.length && rr.size() < 3; j ++){
                if(products[j].startsWith(prefix)){
                    rr.add(products[j]);
                }
            }

            r.add (rr);
        }
        return r;
    }
}

Yes, we can introduce trie for more results. 3 is fairly small here

Leetcode

1267. Count Servers that Communicate

2019/11/23 shiji

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Example 1:

Input:

 grid = [[1,0],[0,1]]

Output:

 0
Explanation: No servers can communicate with others.

Example 2:

Input:

 grid = [[1,0],[1,1]]

Output:

 3
Explanation: All three servers can communicate with at least one other server.

Example 3:

Input:

 grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]

Output:

 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1

class Solution {
    public int countServers(int[][] grid) {
        int result = 0 ;
        int[] a = new int[grid.length];
        int[] b = new int[grid[0].length];
        
        for (int i = 0; i < grid.length; i ++){
            for (int j = 0; j < grid[0].length; j ++){
                if (grid[i][j] == 1){
                    a[i] ++;
                    b[j] ++;
                    result ++;
                }
            }
        }
        
        for (int i = 0; i < grid.length; i ++){
            for (int j = 0; j < grid[0].length; j ++){
                if (a[i] == 1 && b[j] == 1 && grid[i][j] == 1){
                    result --;
                }
            }
        }
        
        return result;
    }
    
}