BobbyChow

https://leetcode.com/problems/search-in-rotated-sorted-array/ 首先題目要求log(n) time ，所以用binary search方法做。 拿這個testcase為例 Input: nums = [3,4,5,6,0,1,2], 這題最重要的地方是你要分清楚mid到底在左邊4567 還是右邊012， 這題的mid是index 3 (6)，我們可以透過nums[left] <= nums[mid]，我們知道idx1(4) <= mid (6)，代表我們在4567這邊，如果mid 是1的話，nums[left] 是會大於nums[mid] ，這時我們便知道我們在0,1,2 這邊 如果我們在4567 左手邊這區的做法:  現在假設我們mid 是idx2 (6) target 是idx3(7)，target > nums[mid]，我們知道binary search會將left = mid +1;  但如果target < nums[mid]，target 是 idx5 (1) 的話，我們會發現4,5 / 0, 1, 2都可以是小於mid (6)，這個時候我們要如何做呢? 我們可以把target (1) < nums[l] (4) ， 如果target 小於 最左邊的話，代表我們要搜尋的位置是右邊這區，亦即是0,1,2這部份，而由於mid是idx 3 (6 ) ，所以是mid +1，7,0,1,2。 假如 target < nums[mid] 又 target > nums[l]，這個情況只有target 是idx0, 1 (4,5) 才會出現 ，所以這時會將right = mid -1; 向左邊搜尋。 如果我們在 012，右手邊這區的做法:  假設mid是 idx5 (1) ，target 是idx4 (0) ，透過nums[left] <= nums[mid] 分左邊右邊，由於left (3 ) > mid (1) ，我們在右手，這時我們就可以查，如果target (0) < mid (1) ，我們可以將向左搜尋，亦即是right = mid -1;  但這時會有個edge case，假設我們tar...

 given a complete binary tree, count how many node inside the tree; 普通方法可以用BFS, DFS 去得出一條array list, 然後count array.length 就得出答案 但係以上方法係 O(N) TIME & O(N) SPACE; 而呢條既要求係 細過O(N)，所以我地要用其他方法去計 首先一個complete binary tree ，除左最下面一行既node 係有機會係null，以及有node既話，都會係出現係left side先之外，上面既node全部都會係填滿左node. 所以我地可以先搵出binary tree 既height, 再透過Math.pow(2, height) -1 得出除最後一行以上既tree既node總和, 亦即是upperCount; 然後我地就要諗方法計算最下面一行既node，而計算之前，我地知道最下一行總共最多可以有既node數量，就是 Math.pow(2, height); 假設有4層，減除root不計算外，就是3層，2 pow 3 = 8; 然後我們現在既問題係，點樣知道最下一層到底係有node還是null，所以我們需要一個function 去查看到底有沒有node，而已知compelete binary tree 只有左邊有node，所以我們只要查看node的右邊，一但node.right 有node出現，我們就知道node.left 也一定有node，所以我們只需要查看node.right，直至node.right由null 變成有node, 便知道最下面一行有多個個node. 用nodeExist 以 binary search 方法查看到底最下面一行的mid range 有沒有node，有就left = mid +1, 沒有就right = mid-1 重新運算 function getTreeHeight ( root ) {     let height = 0 ;     while (root . left !== null ) {         root = root . left ;     ...

 簡單方法 const findCycle = function ( head ) {     const seenNodes = new Set () ;     let currentNode = head ;         while ( ! seenNodes . has (currentNode)) {       if (currentNode . next === null ) {         return false ;       }         seenNodes . add (currentNode) ;         currentNode = currentNode . next ;     }       return currentNode ;   } Floyd's algorithm (龜兔賽跑方法) const findCycle = function ( head ) {     if ( ! head) return null ;         let tortoise = head , hare = head ;         while ( true ) {       tortoise = tortoise . next ;       hare = hare . next ;             if (hare === null || hare . next === null ) {         return null ;     ...

呢條題目難既地方係要釐清唔同既varivable 點樣連 首先睇左張pic去理解我地點樣connect linkedlist 係呢張pic睇到，20 至50係我地要reverse 既linkedlist reverse 完個樣係 50 - 40 -30 -20 -null 所以我地要將10 連去50, 20 連去60 當初我理解下面code既難處係我唔明tail同currentNode個實際value係咩 start = 10,  tail = 20 (after第一個while loop ，我地set左佢做currentNode, 當時既currentNode 係20) ,   currentNode =60 ( 係第2個while loop入面, 我地set左佢做currentNode.next , which is 50.next ,所以係60),  newList = 50 ( 係第2個while loop入面, 我地set左佢做 currentNode, 當時currentNode = 50) 所以  start.next = newList;           即係 10.next to 50 tail.next = currentNode;      即係 20.next = 60 個tail同start太confused, 因為直覺會以為start 就係頭,tail 就係尾，未reverse既情況下，tail 的確睇落以為係頭，因為佢係represent Node20，但實際經過reverse 之後，雖然佢都係Node20，但佢已經變左尾，而我地要做既就係將tail (Node20) 連去60, 最後就變成 10(start) > 50 (newList) > 40 > 30 > 20 (tail) > 60 (currentNode) var reverseBetween = function ( head , m , n ) {   let currentPos = 1 , currentNode = head ;   let start...

  function merge ( arr1 , arr2 ) {     let result = [] ;     let i = 0 ;     let j = 0 ;     while (i < arr1 . length && j < arr2 . length) {         if (arr2[j] > arr1[i]) {             result . push (arr1[i]) ;             i ++         } else {             result . push (arr2[j]) ;             j ++         }     }     while (i < arr1 . length ) {         result . push (arr1[i]) ;         i ++ ;     }     while (j < arr2 . length ) {         result . push (arr2[j]) ;         j ++     }     return result ; } function mergeSort ( arr ) {     if (arr . length <= 1 ) return...

function naiveStringSearch ( long , short ) {     let count = 0 ;     for ( let i = 0 ; i < long . length ; i ++ ) {         for ( let j = 0 ; j < short . length ; j ++ ) {             if (long[i + j] !== short[j] ) {                 break ;             }             if (j === short . length - 1 ) {                 count ++ ;             }         }     }     return count ; } naiveStringSearch ( " lorie loled " , " lol " ) ; given a long string and short string, find how many times short string shown in long string, return -1 if short string is not found. This is quite a easy question, however, there is a trickly part to understand in order to solve it. the trickly part is that you n...