Tag Archives: Easy

Leetcode

13. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol



Value


I             1
V             5
X             10
L             50
C             100
D             500
M             1000


For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.


Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:


    

  • I can be placed before V (5) and X (10) to make 4 and 9.
    • 

  • X can be placed before L (50) and C (100) to make 40 and 90.
    • 

  • C can be placed before D (500) and M (1000) to make 400 and 900.
    • 



Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.


Example 1:


Input:


 "III"



Output:


 3


Example 2:


Input:


 "IV"



Output:


 4


Example 3:


Input:


 "IX"



Output:


 9


Example 4:


Input:


 "LVIII"



Output:


 58



Explanation:


 L = 50, V= 5, III = 3.



Example 5:


Input:


 "MCMXCIV"



Output:


 1994



Explanation:


 M = 1000, CM = 900, XC = 90 and IV = 4.












class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function romanToInt($s) {
        $i= 0;
        $p = ["I"=>1, "V"=>5, "X"=>10, "L"=>50, "C"=> 100, "D"=>500, "M"=>1000];
        $result = 0;
        $increment = INF;
        while($i < strlen($s)){
            $new_increment =  $p[$s[$i]];
            if($increment < $new_increment){
                $result -= (2 * $increment);
            }
            $increment = $new_increment;
            $result += $increment;
            $i ++;
        }
        return $result;
    }
}


The solution is based on the fact that the input is valid, otherwise won’t work





	

	
	




	
	

				

			Leetcode
		

			
1020. Partition Array Into Three Parts With Equal Sum

		

			 		

	


		

		




Given an array A of integers, return true if and only if we can partition the array into three non-empty parts with equal sums.


Formally, we can partition the array if we can find indexes i+1 < j with (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])


 


Example 1:


Input: 


[0,2,1,-6,6,-7,9,1,2,0,1]



Output: 


true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1





Example 2:


Input: 


[0,2,1,-6,6,7,9,-1,2,0,1]



Output: 


false





Example 3:


Input: 


[3,3,6,5,-2,2,5,1,-9,4]



Output: 


true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4







 


Note:


    

  1. 3 <= A.length <= 50000
    2. 

  2. -10000 <= A[i] <= 10000
    3. 











class Solution {

    /**
     * @param Integer[] $A
     * @return Boolean
     */
    function canThreePartsEqualSum($A) {
        $mean = array_sum($A) / 3;
        if (floor($mean) != $mean){
            return false;
        }
        
        $count  = 0;
        $sum = 0;
        $i = 0;
        while ($i < count($A)){    
            $sum += $A[$i];
            $i ++;
            if($sum == $mean){
                $count ++;
                $sum = 0;
            }
        }
        return $count == 3;
    }
}


 







	

	
	




	
	

				

			Leetcode
		

			
181. Employees Earning More Than Their Managers

		

			 		

	


		

		




The Employee table holds all employees including their managers. Every employee has an Id, and there is also a column for the manager Id.




+----+-------+--------+-----------+
| Id | Name  | Salary | ManagerId |
+----+-------+--------+-----------+
| 1  | Joe   | 70000  | 3         |
| 2  | Henry | 80000  | 4         |
| 3  | Sam   | 60000  | NULL      |
| 4  | Max   | 90000  | NULL      |
+----+-------+--------+-----------+



Given the Employee table, write a SQL query that finds out employees who earn more than their managers. For the above table, Joe is the only employee who earns more than his manager.


+----------+
| Employee |
+----------+
| Joe      |
+----------+















Thoughts:


Self  Join, nothing special














# Write your MySQL query statement below
SELECT e1.Name as Employee FROM Employee e1  LEFT JOIN Employee e2 on e2.id =  e1.ManagerId WHERE e2.Salary < e1.Salary;


 



	

	
	




	
	

				

			Leetcode
		

			
104. Maximum Depth of Binary Tree

		

			 		

	


		

		
Given a binary tree, find its maximum depth.


The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.


Note: A leaf is a node with no children.


Example:


Given binary tree [3,9,20,null,null,15,7],


    3
   / \
  9  20
    /  \
   15   7


return its depth = 3.




Thought:


Nothing special but..


I’m using Java this time..




 


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return maxDepthHelper(root, 0);
    }
     public int maxDepthHelper(TreeNode node, int depth) {
        if(node != null){
            return Math.max(maxDepthHelper(node.left, depth+1)
                       , maxDepthHelper(node.right, depth+1));
        }
         return depth;
    }
}


 

	

	
	




	
	

				

			Leetcode
		

			
859. Buddy Strings

		

			 		

	


		

		




Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.


 


Example 1:




Input: 


A = "ab", B = "ba"



Output: 


true





Example 2:


Input: 


A = "ab", B = "ab"



Output: 


false





Example 3:


Input: 


A = "aa", B = "aa"



Output: 


true





Example 4:


Input: 


A = "aaaaaaabc", B = "aaaaaaacb"



Output: 


true





Example 5:


Input: 


A = "", B = "aa"



Output: 


false



 


Note:


    

  1. 0 <= A.length <= 20000
    2. 

  2. 0 <= B.length <= 20000
    3. 

  3. A and B consist only of lowercase letters.
    4. 



















Two cases:


    

  1. Exactly two chars are different, and two strings are same with these chars swapped
    2. 

  2. Two strings are exactly same, the string has duplicate char, so we can pretend to have a swap.
    3. 



 




class Solution {

    /**
     * @param String $A
     * @param String $B
     * @return Boolean
     */
    function buddyStrings($A, $B) {
        if(empty($A) || empty($B) || count($A) !== count($B)){
            return false;
        }
        
        if($A == $B){
            if(strlen(count_chars($A, 3)) != strlen($A)){
                // Check is there're duplicate chars
                return true;
            }
        }
        
        $diff_a = [];
        $diff_b = [];
        
        
        for($i = 0; $i < strlen($A); $i ++){
            if($A[$i] !== $B[$i]){
                $diff_a[] = $A[$i];
                $diff_b[] = $B[$i];
            }
        }

        return  count($diff_b) == 2
            && $diff_a[1] == $diff_b[0] 
            && $diff_a[0] == $diff_b[1]; 
    }
}


 



	

	
	




	
	

				

			Leetcode
		

			
884. Uncommon Words from Two Sentences

		

			 		

	


		

		
We are given two sentences A and B.  (A sentence is a string of space separated words.  Each word consists only of lowercase letters.)


A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.


Return a list of all uncommon words.


You may return the list in any order.


 




Example 1:


Input: A = "this apple is sweet", B = "this apple is sour"
Output: ["sweet","sour"]





Example 2:


Input: A = "apple apple", B = "banana"
Output: ["banana"]



 


Note:


    

  1. 0 <= A.length <= 200
    2. 

  2. 0 <= B.length <= 200
    3. 

  3. A and B both contain only spaces and lowercase letters.
    4. 



Runtime: 8 ms


Memory Usage: 14.9 MB






class Solution {

    /**
     * @param String $A
     * @param String $B
     * @return String[]
     */
    function uncommonFromSentences($A, $B) {
        $x = []; $y = [];
        foreach(explode(' ',$A) as $aa) {
            $this->add($x, $aa);
        }
        foreach(explode(' ',$B) as $bb) {
            $this->add($y, $bb);
        }
        $this->rmCommon($x, $y);
        $x = array_keys($x);
        $y = array_keys($y);
        return array_merge(array_diff($x,$y), array_diff($y, $x));
    }
    
    function add(&$arr, $v){
        if(isset($arr[$v])){
            $arr[$v] ++;
        } else {
            $arr[$v] = 1;
        }
    }
                
    function rmCommon(&$a,&$b){
        foreach($a as $k => $v){
            if ($v > 1){
                unset ($a[$k]);
                unset ($b[$k]);
            }
        }
        foreach($b as $k => $v){
            if ($v > 1){
                unset ($b[$k]);
                unset ($a[$k]);
            }
        }
    }
}


 


 

	

	
	




	
	

				

			Leetcode
		

			
994. Rotting Oranges

		

			 		

	


		

		
In a given grid, each cell can have one of three values:
the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.
Example 1:
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Note:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.


24 ms 38.6 MB


class Solution {
    public int orangesRotting(int[][] grid) {
        if(this.nothing(grid)){
            return 0;
        }
        if(this.neverR(grid)){
            return -1;
        }
        
        int count = 0;
        while(!this.isAllR(grid)){
            grid = this.infect(grid);

            count ++;
            if(count > grid.length * grid[0].length){
                return -1;
            }
        }
        return count;
    }
    
    public int[][] infect(int[][] grid){
        int[][] next = new int[grid.length][grid[0].length];
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){
                next[x][y] = grid[x][y];
            }
        }
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){
                if(grid[x][y] == 2){
                    if(x>0 && next[x-1][y] > 0){
                        next[x-1][y] = 2;
                    }
                    if(y>0 && next[x][y-1] > 0){
                        next[x][y-1] = 2;
                    }
                    if(x< grid.length-1 && next[x+1][y] > 0){
                        next[x+1][y] = 2;
                    }
                    if(y < grid[0].length - 1 && next[x][y+1] > 0){
                        next[x][y+1] = 2;
                    }
                }
            }
        }
        return next;
    }
    
    public boolean isAllR(int[][] grid){
        boolean allR = true;
        for (int[] col : grid){
            for (int c : col){
                if(c == 1){
                    allR = false;
                }
            }
        }
        return allR;
    }
    
    public boolean neverR(int[][] grid){
        boolean allFresh = true;
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){

                if(grid[x][y] == 2){
                    allFresh = false;
                }
                
                if(grid[x][y] == 1){
                    
                    boolean alone = true;
                    if(x>0 && grid[x-1][y] != 0){
                        alone = false;
                    }
                    if(y>0 && grid[x][y-1] != 0){
                        alone = false;
                    }
                    if(x< grid.length-1 && grid[x+1][y] != 0){
                        alone = false;
                    }
                    if(y < grid[0].length - 1 && grid[x][y+1] != 0){
                        alone = false;
                    }
                    System.out.println(alone);
                    if(alone){
                        return true;
                    }
                }
            }
        }
        return allFresh;
    }
    
    
    public boolean nothing(int[][] grid){
        boolean nothing = true;
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){

                if(grid[x][y] > 0){
                    nothing = false;
                }

            }
        }
        return nothing;
    }
}