1. Linear Search (Sequential Search)

目的：有一個未知長度的陣列，要在這串陣列中找尋某個數字，如果他存在的話他的 index 是多少 ?

1. It's an algorithm that sequentially checks(一步一步地) each element of the list until a match is found or the whole list has been searched.
2. Probably the easily algorithm we'll learn in the course.
3. In our coding practice, we'll try to find a number inside an array. If the number could be found, then return the index. If not, then return -1.

Pseudocode for Linear Search

Linear_Search(array, n) :
  for i from 0 to array.length-1:
    if (array[i] === n):
      return i
  return -1

Code for Linear Search

function linearSearch(arr, n) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === n) {
      console.log("Found number " + n + " at index " + i)
      return i
    }
  }
  console.log('can not find' + n)
  return -1
}

linearSearch(numbers, 33)

Overview of Linear Search

1. Worst case performance：O(n) -> 要找的在陣列的最後一個位置 ie index = arr.length-1
2. Best case performance：O(1) -> 要找的在陣列的第一個位置，ie index = 0
3. Average performance：O(n/2)

2. Binary Search

對於 sorted array，更好的找法是將這個 array 拆成一半，一半裡面再去比較要找的數字在左半邊還是右半邊。

1. Binary search is a search algorithm that finds the position of a target value within a sorted array.
2. More efficient than linear search, but only works with sorted data set.
3. In our coding practice, we'll have a sorted array, and one number we want to find inside the sorted array. If the number could be found, then return the index. If not, then return -1.

Pseudocode for Binary Search

先去抓出這個 sorted array 的第一格(min)與最後一格(max)。

Binary_Search(array, n) :
  min = 0
  max = array.length - 1
  while min < = max :
    middle = (min + max) /2
    if num > array[middle]
      min = middle + 1
    else if num < array[middle]
      max = middle - 1
    else 
      return middle
  return -1

Code for Binary Search

最多需要步數：log 以 2 為底，指數是陣列的長度

function binarySearch(array, number) {
  let min = 0
  let max = array.length - 1
  let step = 0
  while(min <= max) {
    step ++
    let middle = Math.floor((min + max)/2)
    if (array[middle] < number) {
      min = middle + 1
    } else if (array[middle] > number) {
      max = middle -1
    } else if (array[middle] === number) {
      console.log(`Found it after ${step} steps.`)
      console.log(`Found number ${number} at position ${middle}`)
      return middle
    }
  }
  console.log(`Not found number ${number} in the sorted array`)
  return -1
}

Overview of Binary Search

1. Worst case performance：O(log(n)) -> f(n) = log 以 2 為底，指數是 n，又 big O 不在意底數，所以就會變成 O(log(n))
2. Best case performance：O(1) -> 要找的在陣列的中央
3. Average performance：O(log(n)) -> 絕大多數情況下都是 log 以 2 為底，指數是 n

3. General guides to algorithm Design

Implement some human thinking in algorithms.
Don't make the computers do dumb calculations or stupid things just because computers can do it.
用人腦的方式想想，先不要用複雜的迴圈解。

Intersection Problem

外層有迴圈(長度 n)、內層也有迴圈(長度 m)，所以 intersection 的演算法他的 big O 是 n * m

function intersection(arr1, arr2) {
  let result = []
  for (let i=0; i<arr1.length; i++) {
    for (let j=0; j<arr2.length; j++) {
      if (arr1[i] === arr2[j]) {
        result.push(arr1[i])
      }
    }
  }
  console.log('result', result)
  return result
}

Counter

1. This is a general skill when doing algorithm design. Counter is not a formal name. Name is different everywhere but the idea is the same.
2. Using the counter object will reduce the complexity of algorithms.

以 Intersection Problem 為例子
時間複雜度：Ｏ(n + m)

function intersection(arr1, arr2) {
  let result = []
  let arr3 = arr1.concat(arr2)
  let counter = {}

  for (let i = 0; i < arr3.length; i++) {
    // 計分板無法找到 arr[i] 的值
    if (!counter[arr3[i]]) {
      counter[arr3[i]] = 1
    } else { // 計分板可以找到 arr[i]
      counter[arr3[i]] ++
    }
  }
  console.log(counter)
  // loop over the counter
  for (let property in counter) {
    if (counter[property] >=2 ) {
      result.push(property)
    }
  }
  console.log('result', result)
  return result
}

intersection([15, 3, 6, 8, 24, 16], [11, 3, 9, 6, 15, 8])

Frequency Problem

先將 array 換成 string => arr.split('')

• 在 counter1 裡面的每個 property，如果在 counter2 裡面不存在 -> return false
• counter1 property 的值與 counter2 property s的值不一樣 -> return false
• 通過上述 property test -> return true

function sameFrequency(str1, str2) {
  let arr1 = str1.split('')
  let arr2 = str2.split('')
  let counter1 = {}
  let counter2 = {}
  if (arr1.length !== arr2.length) return false
  for (let i=0; i<arr1.length; i++) {
    if (!counter1[arr1[i]]) {
      counter1[arr1[i]] = 1
    } else {
      counter1[arr1[i]] ++
    }
  }
  for (let i=0; i<arr2.length; i++) {
    if (!counter2[arr2[i]]) {
      counter2[arr2[i]] = 1
    } else {
      counter2[arr2[i]] ++
    }
  }
  for (let property in counter1) {
    if (!counter2[property]) {
      return false
    }
    if (counter2[property] !== counter1[property]) {
      return false
    }
  }
  return true
}

Average Pair

時間複雜度：Ｏ(n^2) -> 因為 nested array
接著會學習 pointer 幫我們將 Ｏ(n^2) -> Ｏ(n)

function averagePair(arr, avg) {
  let result = []
  for (let i=0; i<arr.length-1; i++) {
    for (let j=i+1; j<arr.length; j++) {
      if ((arr[i] + arr[j])/2 === avg) {
        result.push([arr[i], arr[j]])
      }
    }
  }
  console.log(result)
  return result
}

Pointer

1. This is a general skill when doing algorithm design. Pointer is not a formal name. Name is different everywhere but the idea is the same.
2. It helps reduce the complexity of algorithms.
   時間複雜度：Ｏ(n)
   

function averagePair(arr, avg) {
  let left = 0
  let right = arr.length - 1
  let result = []
  while(right > left) {
    let tempAvg = (arr[left] + arr[right])/2
    if (tempAvg > avg) {
      right --
    } else if (tempAvg < avg) {
      left ++
    } else {
      result.push([arr[left], arr[right]])
      right --
      left ++
    }
  }
  return result
}

Palindrome

function isPalindrome(str) {
  let left = 0
  let right = str.length -1
  while (left <= right) {
    if (str[left] !== str[right]) {
      return false
    }
    left ++
    right --
  }
  return true
}

Subsequence Problem (⚝⚝⚝)

function isSubsequence(str1, str2) {
  if (str1.length === 0) return true
  let pointer1 = 0
  let pointer2 = 0
  while (pointer2 < str2.length) {
    if (str1[pointer1] === str2[pointer2]) {
      pointer1 ++
    }
    if (pointer1 >= str1.length) {
      return true
    }
    pointer2 ++
  }
  return false
}

Sliding Window (⚝)

window 的 size 也可以不固定

怎麼找 index number 的終點 ? 從最後一格開始看，最末格的 index = arr.length - 1，若 size 是 n 就往前推 n - 1 格，所以 index = arr.length - n

function maxSum(arr, size) {
  let maxValue = -Infinity
  if (size > arr.length) return null
  for (let i = 0; i <= arr.length - size; i++) { // i 是 Sliding Window 第一個 pointer
    let attempt = 0
    for (let j = i; j < i + size; j++) { // j 表示 arr 的 index number
     attempt += arr[j]
    }
    if (attempt > maxValue) {
      maxValue = attempt
    }
  }
  return maxValue
}

function minSum(arr, size) {
  let minValue = Infinity
  if (size > arr.length) {
    return null
  }
  for (let i = 0; i <= arr.length - size; i++) {
    let temp = 0
    for (let j = i; j < i + size; j++) {
      temp += arr[j]
    }
    if (temp < minValue) {
      minValue = temp
    }
  }
  return minValue
}

各自算每個 window 的總和並不是個好方法。
第一個 window 與 第二個 window 的差別在於第一個值與最後一個值，中間 7, 3 都是重複的。

Improved Maxsum

function maxSum(arr, size) {
  let maxValue = 0
  if (size > arr.length) {
    return null
  }
  // 先拿第一個 sliding window 的總和
  for (let i = 0; i < size; i++) {
    maxValue += arr[i]
  }
  let tempValue = maxValue
  for (let j = size; j < arr.length; j++) {
    tempValue = tempValue + arr[j] - arr[j - size]
    if (tempValue > maxValue) {
      maxValue = tempValue
    }
  }
  return maxValue
}

Improved Minsum

function minSum(arr, size) {
  let minSum = 0
  if (size > arr.length) {
    return null
  }
  for (let i = 0; i < size; i++) {
    minSum += arr[i]
  }
  let temp = minSum
  for (let i = size; i < arr.length; i++) {
    temp += arr[i] - arr[i - size]
    if (temp < minSum) {
      minSum = temp
    }
  }
  return minSum
}

Coding Practice - Min Sub Array (⚝)

提示：sliding window、pointer

1. start、end 這兩個 pointer 都指向第一個數字
2. 若沒有大於 sum，就將 end 往後移動一格，直到各數字加總大於 sum -> 找到第一個 sub array -> 算出它的長度
3. 降低這個 sub array 的長度 -> 將 start 往後移一格，若 start 到 end 的各數字加總小於 sum -> end 就再往後移動一格

function minSubArray(arr, sum) {
  let start = 0
  let end = 0
  let total = 0
  let minLength = Infinity
  while(start < arr.length) {
    if (total < sum && end < arr.length) {
      total += arr[end]
      end ++
    } else if (total >= sum) {
      let currentLength = end - start
      if (minLength > currentLength) {
        minLength = currentLength
      }
      total -= arr[start]
      start ++
    } else if (end >= arr.length) {
      break
    }
  }
  if (minLength === Infinity) {
    console.log('can not find subarray that can sum up to the given number')
    return -1
  } else {
    console.log(minLength)
    return minLength
  }
}

Unique Letter Substring (⚝⚝⚝)

提示：sliding window、counter

針對這串字 thisishowwedoit

1. 準備 start, end 兩個 pointer 與 counter
2. 若沒有重複，end 就會繼續指向下一格
3. 若 counter 裡面有重複，移動 start，若 counter 裡面還有重複 start 就繼續往後移一格

function uniqueLetterString(str) {
  let start = 0
  let end = 0
  let counter = {}
  let maxLength = -Infinity

  while(end < str.length) {
    if (counter[str[end]]) {
      counter[str[start]] --
      start ++
    } else {
      counter[str[end]] = 1
      end ++
      if ((end - start) > maxLength) {
        maxLength = end - start
      }

    }
  }
  if (maxLength === -Infinity) {
    console.log('cant not find unique letter sub string')
    return null
  }
  console.log('maxLength', maxLength)
  return maxLength
}

Largest Product (⚝)

提示：sliding window、pointer

function largestProduction(n) {
  let currentProduct
  let maxProduct = -Infinity
  let left = 0
  let right = n - 1

  while (right < thousandDigits.length) {
    currentProduct = 1
    for (let i = left; i <= right; i++) {
      currentProduct *= thousandDigits[i]
    }
    if (currentProduct > maxProduct) {
      maxProduct = currentProduct
    }
    right ++
    left ++
  }
  return maxProduct
}

Recursion

學習動機：排列的演算法會大量使用遞迴

1. Def：a function that calls itself.
2. Recursion is using a data structure called stack. When we're calling a function inside another function, we're on the call stack.
3. Recursion is also a mathematical relation in sequences. 遞迴是數列的一種關係

function rs(n) {
  console.log(`inside function rs(${n})`)
  if (n === 1) {
    return 10
  } else {
    return rs(n - 1) + 15
  }
}

(⚝) console.log(rs(3)) 執行流程

1. rs(3) 因為 3 不等於 1 所以會執行 return -> rs(2) + 15 -> + 15 還沒做，rs(2) 就被執行了
2. 同理，rs(2) -> rs(1) + 15 -> + 15 還沒做，rs(1) 就被執行了
3. rs(1) return 10
4. 回到 rs(2) -> rs(1) + 15 = 10 + 15 = 25
5. 回到 rs(3) -> rs(2) + 15 = 25 + 15 = 40

Fibonacci Sequence

function fs(n) {
  if (n === 0) return 0
  if (n === 1) return 1
  return fs(n-1) + fs(n-2)
}

Array of Arrays (⚝⚝⚝)

let result = []
function collector(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      collector(arr[i])
    } else {
      result.push(arr[i])
    }
  }
  return result
}

let arrs = [[[["a", [["b", ["c"]], ["d"]]], [["e"]], [[["f", "g", "h"]]]]]];

function collector(arr1) {
  let result = []
  helper(arr1)
  return result
  function helper(arr2) {
    for (let i = 0; i < arr2.length; i++) {
      if (Array.isArray(arr2[i])) {
        helper(arr2[i])
      } else {
        result.push(arr2[i])
      }
    }
  }
}