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

 

807. Max Increase to Keep City Skyline

In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.

At the end, the “skyline” when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city’s skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.

What is the maximum total sum that the height of the buildings can be increased?

Example:


Input:

 grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

Output:

 35

Explanation:

 
The grid is:
[ [3, 0, 8, 4], 
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

Notes:

  • 1 < grid.length = grid[0].length <= 50.
  • All heights grid[i][j] are in the range [0, 100].
  • All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

Thoughts;

  1. Vertical & Horizontal  scan, generate skyline view array
  2. Max increment = min(vertical, horizontal).
  3. Result = Sum (each max increment)

class Solution {

    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    function maxIncreaseKeepingSkyline($grid) {
        if(empty($grid)){
            return 0;
        }
        $result = 0;
        $h = array_fill(0,count($grid), 0);
        $v = array_fill(0,count($grid[0]), 0);
        
        for($i = 0; $i < count($grid); $i ++){
            $h[$i] = max($grid[$i]);
            for($j = 0; $j < count($grid[0]); $j ++){
                if($grid[$i][$j] > $v[$j]){
                    $v[$j] = $grid[$i][$j];
                }
            }
        }
        
        for($i = 0; $i < count($grid); $i ++){
            for($j = 0; $j < count($grid[0]); $j ++){
                $max = min($h[$i], $v[$j]);
                $result += $max - $grid[$i][$j];
            }
        }
        return $result;
    }
}

 

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

 

987. Vertical Order Traversal of a Binary Tree

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report “[1,5,6]”, the node value of 5 comes first since 5 is smaller than 6.

Note:

The tree will have between 1 and 1000 nodes.
Each node’s value will be between 0 and 1000.

My notes.

Mind the case.

[0,8,1,null,null,3,2,null,4,5,null,null,7,6]

          0
     8         1
          3         2
              4,5
          6         7

Rendered by Leetcode, with my lines added

Screen Shot 2019-02-18 at 15.10.02

My Solution

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this-&gt;val = $value; }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function verticalTraversal($root) {
        $result = [];
        $this-&gt;traversalHelper($root,0,0,$result);
        // Sort by col, from left to right
        ksort($result);
        foreach($result as &amp;$rs){
            $new_sub = [];
            // foreach col, sort by depth from top to bottom
            ksort($rs);
            foreach($rs as &amp;$r){
                // Same depth, sort by value asc, according to spec
                asort($r);
                $new_sub = array_merge($new_sub,$r);
            }
            $rs = $new_sub;
        }
        return $result;
    }
    
    // Recursion, go through the tree
    function traversalHelper($root, $pos,$depth, &amp;$result) {
        if($root !== null){
            if(!isset($result[$pos])){
                $result[$pos] = [];
            } 
            if(!isset($result[$pos][$depth])){
                $result[$pos][$depth] = [];
            }
            $result[$pos][$depth][] = $root-&gt;val;
            
            $this-&gt;traversalHelper($root-&gt;left, $pos - 1,$depth+1, $result);
            $this-&gt;traversalHelper($root-&gt;right, $pos + 1,$depth+1, $result);
        }
    }
}

 

991. Broken Calculator

On a broken calculator that has a number showing on its display, we can perform two operations:

Double: Multiply the number on the display by 2, or;
Decrement: Subtract 1 from the number on the display.
Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2

Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3

Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023

Explanation: Use decrement operations 1023 times.

Note:

1 <= X <= 109
1 <= Y <= 109

class Solution {

    /**
     * @param Integer $x
     * @param Integer $y
     * @return Integer
     */
    function brokenCalc($x, $y) {
        $c = 0;
        while($x < $y){
           if($y % 2 == 0){
                $y /= 2;
            } else {
                $y ++;
           } 
            $c ++;
        }
        return $c + $x - $y;
    }
}

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

 

996. Number of Squareful Arrays

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1:

Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: [2,2,2]
Output: 1

Note:

1 <= A.length <= 12
0 <= A[i] <= 1e9

Solved this with PHP.

  1. Go through the input and construct array ‘peers’
    1. peers holds an array of pointers pointing to all possible ‘partners’ in the input.
    2. For example, [1 => [8=>ref(8)], 8 => [1=>ref(1), 17=>ref(17)], 17 => [8=>ref(8)]]
  2. Meanwhile, another array stat collect all numbers and its occurrence.
  3. Then peers is recursive. so it’s like a tree, with infinite depth.
  4. Starting from the root of peers, if found any number in ‘stat’, update (-1) stat, and move on to peers’ children
    1. if cannot find any match at some points, break;
    2. since stat is finite, the recursive func will run forever
  5. Calculate the sum.

Works well with even larger input length.

16ms runtime w/ 14.7M RAM

Class Solution {

    /**
     * @param Integer[] $ls
     * @return Integer
     */
    function numSquarefulPerms($ls) {
        
        if(count($ls) <= 1){
            return 0;
        }
        
        $peers = [];
        $stat = [];
        
        for($i = 0; $i < count($ls); $i++){
            // Insert/Update stat
            if(!isset($stat[$ls[$i]])){
                $stat[$ls[$i]] = 1;
            } else {
                $stat[$ls[$i]] ++;
            }
            
            for($j = $i + 1; $j < count($ls); $j++){

                $value_i = $ls[$i];
                $value_j = $ls[$j];
                
                if(!isset($peers[$value_i])){
                    $peers[$value_i] = [];
                }
                if(!isset($peers[$value_j])){
                    $peers[$value_j] = [];
                }
                if($this -> isPerfectSquare($ls[$i] + $ls[$j])){
                    $peers[$value_i][$value_j] = &$peers[$value_j];
                    if($ls[$j] !== $ls[$i]){
                        $peers[$value_j][$value_i] = &$peers[$value_i];
                    }
                }
            }
        }
        // If any number has no partner
        foreach($peers as $p){
            if($p === []){
                return 0;
            }
        }
        return $this->traversal($stat, $peers, count($ls));
    }
    
    // Check if number is perfect square w/ small optimization
    function isPerfectSquare($num){
        $last_digit = $num % 10;
        if($last_digit == 2 ||
            $last_digit == 3 ||
            $last_digit == 7 ||
            $last_digit == 8 
          ) 
            return false;
        
        $sqrt = sqrt($num);
        return $sqrt == floor($sqrt);
    }
    
    function traversal($nums, &$tree, $max){
        $count = 0;
        var_dump($nums);
        if(empty($nums)){
            echo "Add\r\n";
            return 1;
        }
        foreach($tree as $k => $v){
            // Make a copy
            $nums_copy = $nums;
            if(isset($nums_copy[$k])){
                // If exist decrease, if last remove
                if($nums[$k] > 1){
                    $nums_copy[$k] --;
                } else {
                    unset($nums_copy[$k]);
                }
                // move on to children
                $count += $this -> traversal($nums_copy, $v, $max - 1); 
            }     
        }
        return $count;
    }
}