1170. Compare Strings by Frequency of the Smallest Character

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;
    }
    
}

 

1275. Find Winner on a Tic Tac Toe Game

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 " -> " X " -> "

X

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

X

"

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 " -> " O " -> "XO " -> "X

O

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

O

  "

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";
    }
}

 

1266. Minimum Time Visiting All Points

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

  • In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
  • You have to visit the points in the same order as they appear in the array.

 

Example 1:

Input:

 points = [[1,1],[3,4],[-1,0]]

Output:

 7

Explanation:

One optimal path is

[1,1]

 -> [2,2] -> [3,3] ->

[3,4]

-> [2,3] -> [1,2] -> [0,1] ->

[-1,0]

   
Time from [1,1] to [3,4] = 3 seconds 
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds

Example 2:

Input:

 points = [[3,2],[-2,2]]

Output:

 5

 

Constraints:

  • points.length == n
  • 1 <= n <= 100
  • points[i].length == 2
  • -1000 <= points[i][0], points[i][1] <= 1000

 

class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int result = 0;
        int prev_x = points[0][0];
        int prev_y = points[0][1];
        for (int i = 1; i < points.length; i ++){
            int x = points[i][0];
            int y = points[i][1];
            
            int diff_x = Math.abs(x - prev_x);
            int diff_y = Math.abs(y - prev_y);
            
            result += Math.min(diff_x,diff_y)+Math.abs(diff_x-diff_y);
            
            prev_x = x;
            prev_y = y;
        }
        return result;
    }
}

 

189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input:

[1,2,3,4,5,6,7] and

k

 = 3

Output:

[5,6,7,1,2,3,4]

Explanation:

rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input:

[-1,-100,3,99] and

k

 = 2

Output:

 [3,99,-1,-100]

Explanation:

 rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Note:

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

 

In place rotate

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return NULL
     */
    function rotate(&$nums, $k) {
        $c = count($nums);
        $steps = 0;
        $start = 0;
        
        while($steps < $c){  
            $i = $start;
            $prev = $nums[$i];
            do{         
                $next = ($i+$k)%$c;
                $temp = $nums[$next];
                $nums[$next] = $prev;
                $prev = $temp;
                $i += $k;
                $i = $i % $c;
                $steps++;
            }while($start != $i);
            $start ++;
            
        }
    
    }
}

 

917. Reverse Only Letters

Given a string S, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

 

Example 1:

Input:

"ab-cd"

Output:

"dc-ba"

Example 2:

Input:

"a-bC-dEf-ghIj"

Output:

"j-Ih-gfE-dCba"

Example 3:

Input:

"Test1ng-Leet=code-Q!"

Output:

"Qedo1ct-eeLg=ntse-T!"

 

Note:

  1. S.length <= 100
  2. 33 <= S[i].ASCIIcode <= 122
  3. S doesn’t contain \ or "

 

Straightforward solution. 

  1. collect letters in reverse order.
  2. go through string from beginning, if it’s letter, replace with letter from reverse string, else keep special chars and adjust pointer accordingly
  3. of course there’s space for improvement, but not necessary
<?php
class Solution {

    /**
     * @param String $S
     * @return String
     */
    function reverseOnlyLetters($S) {
        $x = '';
        $y = '';
        for($i = strlen($S)-1; $i >=0; $i -- ){
            if(ctype_alpha($S[$i])){
                $x .= $S[$i];
            }
        }
        $xi = 0;
        for($i = 0; $i < strlen($S); $i ++){
            if(!ctype_alpha($S[$i])){
                $y .= $S[$i];
            } else {
                $y .= $x[$xi];
                $xi ++;
            }
             
        }
        
        return $y;
    }
}

?>

 

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input:

 123

Output:

 321

Example 2:

Input:

 -123

Output:

 -321

Example 3:

Input:

 120

Output:

 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

class Solution {

    /**
     * @param Integer $x
     * @return Integer
     */
    function reverse($x) {
        
        $r =  (int) (strrev(trim($x,"+-")) * ($x>0?1:-1));
        
        if($r >  pow(2,31)-1 || $r < -pow(2,31)){
            return 0;
        }
        return $r;
    }
}

 

9. Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input:

 121

Output:

 true

Example 2:

Input:

 -121

Output:

 false

Explanation:

 From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input:

 10

Output:

 false

Explanation:

 Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

 

class Solution {

    /**
     * @param Integer $x
     * @return Boolean
     */
    function isPalindrome($x) {
        if($x < 0){
            return false;
        }
        return strrev($x) == $x;
    }
}

For the followup

not converting to string? Create a  stack of integers instead (like a push down automata)

26. Remove Duplicates from Sorted Array


Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn’t matter what you leave beyond the returned length.
Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn’t matter what values are set beyond the returned length.
Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}


class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums) {
        if(empty($nums)){
            return 0;
        }
        $i = 0;
        $r = 1;
        while($i < count($nums)-1){
            if($nums[$i] != $nums[$i+1]){
                $nums[$r] = $nums[$i+1];
                $r ++;
                
            }
            $i ++;
        }
        return $r;
    }
}