14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input:

["flower","flow","flight"]

Output:

 "fl"

Example 2:

Input:

["dog","racecar","car"]

Output:

 ""

Explanation:

 There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

 


class Solution {

    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        if(empty($strs)){
            return "";
        }
        $result = "";
        for($i = 0; $i < strlen($strs[0]); $i ++){
            $cur = $strs[0][$i];
            foreach ($strs as $s){
                if($s[$i] != $cur){
                    return $result;
                }
            }
            $result.= $cur;
        }
        return $result;
        
    }
}

 

13. Roman to Integer

Roman numerals are represented by seven different symbols: IVXLCD 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

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. -10000 <= A[i] <= 10000
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;
    }
}

 

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;

 

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

 

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. 0 <= B.length <= 20000
  3. A and B consist only of lowercase letters.

Two cases:

  1. Exactly two chars are different, and two strings are same with these chars swapped
  2. Two strings are exactly same, the string has duplicate char, so we can pretend to have a swap.

 

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

 

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. 0 <= B.length <= 200
  3. A and B both contain only spaces and lowercase letters.
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]);
            }
        }
    }
}

 

 

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