Leetcode

Tree traverse, DFS, BFS (BinaryTree traverse, preorder, inorder, postorder, bfs, bfs storing level)

Problems by type

DFS (Visit friends, numIslands, Valid binary search tree)

Sliding Window (minWindow, lengthOfLongestSubstring, checkInclusion)

BackTracking (subsets, combinationSum, permutations)

Dynamic (longestPalindrome, maxProfit, maxSubArray)

Tree traverse, DFS, BFS

DFS (Depth First Search): Pre, in and postorder are variations of DFS

Binary tree traverse

class BinaryNode1 {  
 
  public $data;  
  public $left;  
  public $right;  
 
  public function __construct(string $data = NULL) {  
	  $this->data = $data;  
	  $this->left = NULL;  
	  $this->right = NULL;  
  }  
 
  public function addChildren(BinaryNode1 $left, BinaryNode1 $right) {  
	  $this->left = $left;  
	  $this->right = $right;  
  }  
}  
 
class BinaryTree {  
 
  public $root = NULL;  
 
  public function __construct(BinaryNode1 $node) {  
  $this->root = $node;  
  }  
 
  public function traverse(BinaryNode1 $node, int $level = 0) 
  {  
  	  if ($node) {  
		  echo str_repeat("-", $level);  
		  echo $node->data . "\n";  
 
		  if ($node->left)  
		  $this->traverse($node->left, $level + 1);  
 
		  if ($node->right)  
		  $this->traverse($node->right, $level + 1);  
	  }  
 }  
}  

Binary tree DFS (pro, in, post)

DFS using stack:

1. $stack[] = $root;
2. $node = $stack->pop();
3. Fetch its unvisited neighbours $stack->push($current->right);
   $stack->push($current->left);
4. Repeat 2,3 until stack empty.

 class BinaryNode
 {
        public $value;
        public $left;
        public $right;
 
        public function __construct($item) {
            $this->value = $item;
            $this->left = null;
            $this->right = null;
        }
        public function isEmpty() {}
        public function insert($item) {}
        protected function insertNode($node, &$subtree) {}      
}
 
class TraversalBT {
 
        public function preOrderTraversal(BinaryNode $root) 
        {
            $preOrder = [];
            $nodes = new SplStack();
            if ($root == null) { return $preOrder;}
 
            while ($root !== null || !$nodes->isEmpty()) {
                while ($root !== null) {
                    $preOrder[] = $root->value;
                    $nodes->push($root);
                    $root = $root->left;
                }
                $root = $nodes->pop();
                $root = $root->right;
            }
            return $preOrder;
        }
 
        public function inorderTraversal(BinaryNode $root) 
        {
            $inorder = [];
            $nodes = new SplStack();
            if ($root == null) {return $inorder;}
 
            while ($root !== null || !$nodes->isEmpty()) {
                while ($root !== null) {
                    $nodes->push($root);
                    $root = $root->left;
                }
                $root = $nodes->pop();
                $inorder[] = $root->value;
                $root = $root->right;
            }
            return $inorder;
        }
 
        public function postOrderTraversal(BinaryNode $root) 
        {
            $postOrder, $visited = [];
            $nodes = new SplStack();
            if ($root == null) { return $postOrder; }
 
            while ($root !== null || !$nodes->isEmpty()) {
                while ($root !== null) {
                    $nodes->push($root);
                    $root = $root->left;
                }
 
                $root = $nodes->pop();
 
                if ($root->right !== null && !in_array($root, $visited)) {
                    $nodes->push($root);
                    $visited[] =  $root;
                    $root = $root->right;
                    continue;
                }
 
                if (!in_array($root->value, $postOrder)) {
                    $inorder[] = $root->value;
                }
 
                $root = $root->right;
            }
 
            return $postOrder;
        }
 
    }

BFS traversal

class TreeNode {
 
        public $data = NULL;
        public $children = [];
 
        public function __construct(string $data = NULL) {
            $this->data = $data;
        }
 
        /** 
         * traverse tree and return path 
         */
        public function BFSTree(TreeNode $node): SplQueue {
 
            $queue = new SplQueue;
            $visited = new SplQueue;
 
            $queue->enqueue($node);
 
            while (!$queue->isEmpty()) {
                $current = $queue->dequeue();
                $visited->enqueue($current);
 
                foreach ($current->children as $child) {
                    $queue->enqueue($child);
                }
            }
            return $visited;
        }
 
        public function BFSGraph(array &$graph, int $start, array $visited): SplQueue {
            $queue = new SplQueue;
            $path = new SplQueue;
 
            $queue->enqueue($start);
            $visited[$start] = 1;
 
            while (!$queue->isEmpty()) {
                $node = $queue->dequeue();
                $path->enqueue($node);
                foreach ($graph[$node] as $key => $vertex) {
                    if (!$visited[$key] && $vertex == 1) {
                        $visited[$key] = 1;
                        $queue->enqueue($key);
                    }
                }
            }
 
            return $path;
        }
 
	    public function bfsStoringPerLevel($root) {
 
			$result, $queue = [];	    
	        if(empty($root)){return [];}
	        array_push($queue,$root);
 
	        while(!empty($queue)){
	            $count = count($queue);
	            $leveQueue = [];
	            for($i=0;$i<$count;$i++){
	                $node = array_shift($queue);
	                array_push($leveQueue,$node->val);
	                if($node->left) array_push($queue,$node->left);
	                if($node->right) array_push($queue,$node->right);
	            }
	            array_push($result,$leveQueue);
	        }
	        return $result;
	    }
    }

DFS

/**
There are  **N**  students in a class. Some of them are friends, while some are not. Their friendship 
is transitive in nature. For example, if A is a  **direct**  friend of 
B, and B is a  **direct**  friend of C, then A is an  **indirect**  friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
 
Given a  **N*N**  matrix  **M**  representing the friend relationship between students in the class. 
If M[i][j] = 1, then the ith  and jth  students are  **direct**friends with each other, otherwise not. 
And you have to output the total number of friend circles among all the students.
*/
class Solution {
    function visitFriends(&$M, &$visited, $m, $n)
    {
        if($m<0 || $m > count($M) || $n<0 || $n> count($M)) {
            return ;
        }
 
        $visited[$m][$n] = 1;
        $visited[$n][$m] = 1;
 
        for ($i = 0; $i < count($M[0]); $i++) {
            if ($M[$n][$i] == 1 && $visited[$n][$i]==0) {
                $this->visitFriends($M, $visited, $n, $i);
            }
        }
    }
 
    /**
     * @param Integer[][] $M
     * @return Integer
     */
    function findCircleNum($M) {
 
        $visited = [];
 
        foreach ($M as $key1 => $item1) {
            foreach ($item1 as $key2 => $item2) {
                $visited[$key1][$key2] = 0;
            }
        }
 
        $count = 0;
 
        for ($i = 0; $i < count($M); $i++) {
            for ($j = 0; $j < count($M[0]); $j++) {
                if ($visited[$i][$j]===0 && $M[$i][$j] == 1) {
                    $this->visitFriends($M, $visited, $i, $j);
                    $count++;
                }
            }
        }
        return $count;
    }
}
 
/**
Given a 2d grid map of  `'1'`s (land) and  `'0'`s (water), count the number of islands. 
An island is surrounded by water and is formed by connecting adjacent lands horizontally 
or vertically. You may assume all four edges of the grid are all surrounded by water.
 
**Example 1:**
 
**Input:**
11110
11010
11000
00000
 
**Output:** 1
*/
class Solution {  
 
   /**  
    * @param String[][] $grid  
    * @return Integer  
    */  
    function numIslands($grid) 
    {  
           $islands = 0;  
           foreach ($grid as $i => $row) {  
               foreach ($row as $j => $column) {  
                   if ($grid[$i][$j] == '1') {  
                       $islands++;  
                       $this->dfs($grid, $i, $j);  
                   }  
               }  
           }  
           return $islands;  
       }  
 
       public function dfs(&$grid, $i, $j)  
       {  
           if ($i < 0 || $i >= count($grid) ||  
               $j < 0 || $j >= count($grid[0])) {  
               return;  
           }  
 
           if ( isset($grid[$i]) && isset($grid[$i][$j]) && $grid[$i][$j] !== '1') {  
               return;  
           }  
 
           $grid[$i][$j] = '*';  
 
           $this->dfs($grid, $i+1, $j);  
           $this->dfs($grid, $i-1, $j);  
           $this->dfs($grid, $i, $j+1);  
           $this->dfs($grid, $i, $j-1);  
       }  
}
 
/**
Given a binary tree, determine if it is a valid binary search tree (BST).
 
Assume a BST is defined as follows:
 
-   The left subtree of a node contains only nodes with keys  **less than**  the node's key.
-   The right subtree of a node contains only nodes with keys  **greater than**  the node's key.
-   Both the left and right subtrees must also be binary search trees.
 */
class Solution {
 
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isValidBST($root) {
 
            $stack = new SplStack();
            $inorder = PHP_INT_MIN;
 
            while (!$stack->isEmpty() || $root != null) {
                while ($root != null) {
                    $stack->push($root);
                    $root = $root->left;
                }
                $root = $stack->pop();
                // If next element in inorder traversal  is smaller than the previous one
                // that's not BST.
                if ($root->val <= $inorder) {
                    return false;
                }
                $inorder = $root->val;
                $root = $root->right;
            }
            return true;
 
    }
}

Sliding Window

/**
Given a string S and a string T, find the minimum window in S which will contain all the 
characters in T in complexity O(n).
 
**Example:**
 
**Input: S** = "ADOBECODEBANC", **T** = "ABC"
**Output:** "BANC"
*/
class Solution {
 
    public function minWindow(string $string1, string $string2)
    {
            $string1 = str_split($string1);
            $string2 = str_split($string2);
 
            if (count($string2)>count($string1)) {
                return '';
            }
 
            if ($string1 === $string2) {
                return implode($string1);
            }
 
            $frequencyArray = $this->getFrequencyArray($string2);
 
            $begin = 0;
            $end = 0;
            $len = PHP_INT_MAX;
            $counter = count($frequencyArray);
            $result = [];
 
//            var_dump($frequencyArray);die;
 
            while ($end < count($string1)) {
 
                $endChar = $string1[$end];
 
                // if current char found in table, decrement count
                if (array_key_exists($endChar, $frequencyArray)) {
                    $frequencyArray[$endChar]--;
                    if ($frequencyArray[$endChar] === 0) {
                        $counter--;
                    }
                }
 
                $end++;
 
                // if counter == 0, means we found an answer, now try to trim that window by 
                // sliding begin to right.
                while ($counter === 0) {
 
                    // store new answer if smaller than previously best
                    if ( $end - $begin < $len) {
                        $len = $end - $begin;
                        $result = array_slice($string1, $begin, $end - $begin);
                    }
 
                    $startChar = $string1[$begin];
 
                    // startChar could be in frequencyArray, if not then it was a wasteful char and we shortened the prev substring.
 
                    // if found in frequencyArray increment count in table, as we are leaving it out of window and moving ahead,
                    // so it would no longer be a part of the substring marked by begin-end window
                    // frequencyArray only has count of chars required to make the present 
                    //substring a valid candidate
                    // if the count goes above zero means that the current window is missing one char 
                    // to be an answer candidate
 
                    if ($this->countNumberOfElements($frequencyArray, $startChar) == 1) {
                        $frequencyArray[$startChar]++;
                        if ($frequencyArray[$startChar] > 0) {
                            $counter++;
                        }
                    }
 
                    $begin++;
 
                }
 
            }
 
            return implode('', $result);
 
        }
 
        public function getFrequencyArray($string2)
        {
            $frequencyArray = [];
 
            foreach ($string2 as $item) {
 
                if (isset($frequencyArray[$item])) {
                    $frequencyArray[$item]++;
                } else {
                    $frequencyArray[$item] = 1;
                }
            }
 
            return $frequencyArray;
        }
 
        public function countNumberOfElements($frequencyArray, $startChar)
        {
            $count = 0;
 
            foreach ($frequencyArray as $key => $item) {
                if ($startChar == $key) {
                    $count++;
                }
            }
 
            return $count;
        }
}
/** Given a string, find the length of the  **longest substring**  without repeating characters.*/
    class lengthOfLongestSubstringClass {
        /**
         * @param String $s
         * @return Integer
         */
        function lengthOfLongestSubstring($s)
        {
            if ($s=="") { return 0;}
            $s = str_split($s);
            $n = count($s);
            $set = [];
            $ans = 0;
            $i = 0;
            $j = 0;
 
            while ($i < $n && $j < $n) {
                if (!in_array($s[$j], $set)){
                    $set[$s[$j]] = $s[$j];
                    $j++;
                    $ans = max($ans,$j-$i);
                } else {
                    unset($set[$s[$i]]);
                    $i++;
                }
            }
            return $ans;
        }
    }
/**
Given two strings  **s1**  and  **s2**, write a function to return true if  **s2**  contains the permutation 
of  **s1**. In other words, one of the first string's permutations is the  **substring**  of the second 
string.
 
**Example 1:**
 
**Input:** s1 = "ab" s2 = "eidbaooo"
**Output:** True
**Explanation:** s2 contains one permutation of s1 ("ba").
*/
 
class Solution {
    function checkInclusion($s1, $s2) {
        $string1 = str_split($s2);
            $string2 = str_split($s1);
 
            $frequencyArray = [];
 
            foreach ($string2 as $item) {
                if (isset($frequencyArray[$item])) {
                    $frequencyArray[$item]++;
                } else {
                    $frequencyArray[$item] = 1;
                }
            }
 
            $counter = count($frequencyArray);
            $end = 0;
            $begin = 0;
 
            while ($end < count($string1)) {
 
                $endChar = $string1[$end];
 
                if (array_key_exists($endChar, $frequencyArray)) {
                    $frequencyArray[$endChar]--;
                    if ($frequencyArray[$endChar]==0)
                    {
                        $counter--;
                    }
                }
 
                $end++;
 
                while ($counter == 0) {
 
                    $beginChar = $string1[$begin];
 
                    if (array_key_exists($beginChar, $frequencyArray)) {
 
                        $frequencyArray[$beginChar]++;
 
                        if ($frequencyArray[$beginChar] > 0) {
                            $counter++;
                        }
                    }
 
                    if ($end - $begin == count($string2)) {
                        return true;
                    }
 
                    $begin++;
                }
            }
 
            return false;
    }
}

BackTracking

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step,

class subsetsClass {
 
        private $powerset = [];
        private $subset = [];
 
        public function subsets(array &$nums): array
        {
            $this->backTrack($nums, 0);
            return $this->powerset;
        }
 
        public function backTrack(array &$nums, int $start): void
        {
            $this->powerset[] = $this->subset;
            $size = count($nums);
 
            for ($i = $start; $i < $size; $i++) {
                $this->subset[] = $nums[$i];
                $this->backTrack($nums, $i+1);
                array_pop($this->subset);
            }
        }
    }
 
/**
***Input:** candidates = [2,3,5]`,` target = 8,
**A solution set is:**
* [
*  [2,2,2,2],
*  [2,3,3],
*  [3,5]
* ]
*/
class combinationSumClass {
 
        private $result, $subset = [];
        private $target;
 
        function combinationSum($candidates, $target) {
            $this->target = $target;
            $this->combinationSumRec($candidates);
            return $this->result;
        }
 
        public function combinationSumRec(array &$candidates): void
        {
            if (array_sum($this->subset) <= $this->target) {
                if (array_sum($this->subset) === $this->target) {
                    sort($this->subset);
                    if (!in_array($this->subset, $this->result)) {
                        $this->result[] = $this->subset;
                    }
                }
 
                $size = count($candidates);
 
                for ($i = 0; $i < $size; $i++) {
                    $this->subset[] = $candidates[$i];
                    $this->combinationSumRec($candidates);
                    array_pop($this->subset);
                }
            }
        }
    }
 
// Given a collection of  **distinct**  integers, return all possible permutations.
/**
 
*/
class Solution {
 
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permute($nums) {
        $result = array();
        $this->backTracking($nums, count($nums), 0, array(), $result);
        return $result;
    }
 
    function backTracking($nums, $numsLength, $startIndex, $permutation, &$result) 
    {
        if (count($permutation) == $numsLength) {
            array_push($result, $permutation);
            return;
        }
 
        for($i = $startIndex; $i < $numsLength; $i++) {
            if (!in_array($nums[$i], $permutation)) {
                array_push($permutation, $nums[$i]);
                $this->backTracking($nums, $numsLength, 0, $permutation, $result);
                array_pop($permutation);
            }
        }
    }
 
}
 
 
    class gardenNoAdjClass3
    {
 
        public $paths;
        public $numberOfGardens;
 
        public function gardenNoAdj($numberOfGardens, $paths)
        {
            $this->paths = $paths;
            $this->numberOfGardens = $numberOfGardens;
            $solution = array_fill(1, $numberOfGardens, null);
            $this->solve($solution, 1);
            return $solution;
        }
 
        public function solve(&$solution, $position)
        {
            if ($position > count($solution)) {
                return true;
            }
 
            for($i = 1; $i <= 4; $i++) {
                $solution[$position] = $i;
                if ($this->correctUntilHere($solution)) {
                    if ($this->solve($solution, $position+1)) {
                        return true;
                    }
                }
                $solution[$position] = null;
            }
        }
 
        public function correctUntilHere($solution)
        {
            foreach ($this->paths as $path) {
                if ($solution[$path[0]] == $solution[$path[1]] && $solution[$path[0]]!==null) {
                    return false;
                }
            }
 
            return true;
        }
    }

Dynamic Programming

/**
Given a string  **s**, find the longest palindromic substring in  **s**. You may assume that the maximum length of  **s**  is 1000.
 
**Example 1:**
 
**Input:** "babad"
**Output:** "bab"
**Note:** "aba" is also a valid answer.
*/
class Solution {
 
    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        $a = str_split($s);
        $maxLength = 0;
        $maxArray = [];
        for ($i = 0; $i < count($a); $i++){
            for ($j = 1; $j < count($a); $j++) {
 
                if (isset($a[$i-$j])) {
                    $bottom = $a[$i-$j];
                } else {
                    break;
                }
 
                if (isset($a[$i+$j])) {
                    $top = $a[$i+$j];
                } else {
                    break;
                }
 
                if ($bottom == $top) {
                    $length = $j+1;
 
                    if ($length > $maxLength) {
                        $maxLength = $length;
                        $maxArray = array_slice($a,$i-$j, $length+$j);
                    }
                } else {
                    break;
                }
            }
        }
 
        return implode($maxArray);
    }
}
 
/**
Say you have an array for which the  _i_th  element is the price of a given stock on day  _i_.
 
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
 
Note that you cannot sell a stock before you buy one.
 
**Example 1:**
 
**Input:** [7,1,5,3,6,4]
**Output:** 5
*/
 
class Solution {
 
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $minValue = max($prices);
        $maxProfit = 0;
 
        for($i=0;$i<count($prices);$i++){
            if($prices[$i]<$minValue){
                $minValue = $prices[$i];
                continue;
            }
 
            if($prices[$i]-$minValue > $maxProfit){
                $maxProfit = $prices[$i]-$minValue;
            }
        }
        return $maxProfit;
    }
}
/**
Given an integer array  `nums`, find the contiguous subarray (containing at least one number) which 
has the largest sum and return its sum.
 
**Example:**
 
**Input:** [-2,1,-3,4,-1,2,1,-5,4],
**Output:** 6
**Explanation:** [4,-1,2,1] has the largest sum = 6.
*/
class Solution {
 
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxSubArray($nums) {
 
          $cur=$nums[0];
          $res=$nums[0];
 
            for($i=1;$i<count($nums);$i++){
                if($cur<0){
                    $cur=$nums[$i];
 
                }else{
                    $cur +=$nums[$i];
                }
                $res=max($res,$cur);
            }
            return $res;
    }
}

Problems

1 Two Sum Ok

2 Add Two Numbers Ok

146 LRU Cache Ok

5 Longest Palindromic Substring Ok

4 Median of two sorted Arrays Ok

42 Trapping Rain Water Ok

200 Number of Islands Ok - DFS

3 Longest Subst wihout rep char Ok

15 3Sum Ok 23 Merge K Sorted Lists Ok

238 Product array execpt self Ok

76 MinWindow Substring OK - MWS

973 K Closest Points to Origin Ok - MinHeap y array

273 Integer to English Words Ok

301 Remove Invalid Parentheses Ok - Queue

289 Game of Life Ok - now in place

297 Serialize and Deserialize Binary T Ok - Queue y For

121 Best Time To Buy and Sell stock Ok

33 Search in rotated sorted Array Ok

253 Meeting Rooms Ok - Min Heap

22 Generate Parentheses Ok - Recursive

11 Container with most water Ok

49 Group Anagrams Ok

560 SubArray Sum Equals K Ok

380 Insert Delete GetRandom Ok

54 Spiral Matrix Ok

88 Merge Sorted Array Ok

56 Merge Intervals ¿? - Mejorar