Don't LeetCode Yet - 9 - Data Structure Intro

Importance of Data Structure

How important is Data Structure? VERY IMPORTANT!
Different scinario needs different data structure.

Array in JavaScript is more than array.
JavaScript just made it too convinent with array, object…etc.
Like: .push, .pop, .shift, .unshift… method in array.
It behaves more like queue or stack (STEAK XD)

Object in JavaScript can be used as map.

Some common data structures:

• Linked list
• Queue
• Stack
• Hash Table
• Tree

Take SET [] as example

1. push
2. remove
3. isExist

Definition of SET data structure: One element can only appear once.(unique values)
Throw 1 1 2 2 3 3 4 into a SET, we can get 1 2 3 4

Queue VS Array

queue.enqueue
queue.front
queue.dequeue

Algorithm

different Sorting Algorithm

Bubble sort, Merge sort, Selection sort, Insertion sort,

Lidemy-排序方式簡介
VISUALGO: Nice visualising site.

LIOJ 1035

Since the range is numbers from 1 to 100, we can make an array of 100 0s (index[0]- index[99])
And +1 on that index every times a number has been found.
Array = [1,4,4,3,4] > zeroArray = [0,0,0,0,0,0,0…..]
zeroArray = [1, 0, 1, 3, 0, 0, 0, 0…..]
output = [1, 3, 4, 4, 4,]

Counting sort

LIOJ 1047

binary search

let L = 0
let R = arr.length-1
let M = Math.floor(arr.length/2)
if(q > arr[R] || q < arr[L]){
    return -1
}
while(end - start > 1){
    if(q==arr[L]){
        return L
    } else if (q== arr[R]){
        return R
    } else {
        if(q==arr[M]){
            return M
        } else if (q < arr[M]){
            R = M
            M = Math.floor((L+M)/2)
        } else {
            L = M
            M = Math.floor((M+R)/2)
        }
    }
}
return -1

LIOJ 1048

If all numbers are positive there will not be any problem.
Here we can just loop thorugh the array, add all the numbers already passed.
If the sum of X ~ (Y-1) is smaller than Y, then we can ditch the sum of X ~ Y-1.
It actually means if X add to Y-1 is negative…
Rather than writing this:

if (arr[i]+currentSum > arr[i]){
    currentSum += arr[i]
} else {
    currentSum = arr[i]
}

This might be easier to understand?

if(currentSum < 0){
    currentSum = arr[i]
} else {
    currentSum += arr[i]
}

• Algorithm
• JavaScript
• Lidemy