翻書問題或者走臺階問題罩锐。

問：共有n個臺階奉狈，每次只能上1個臺階或者2個臺階，共有多少種方法爬完臺階涩惑？共有n頁書仁期，每次只能翻1頁或者2頁書，共有多少種方法翻完全書竭恬？
ps：本質(zhì)上是斐波那契數(shù)列問題跛蛋。假設(shè)只有一個臺階，則只有一種跳法痊硕，f(1)=1赊级；如果兩個臺階，那么有兩種跳法：1,一次跳一級岔绸，2,一次跳兩級理逊，f(2) = 2。如果大于2的n級臺階盒揉，那么一次跳一級臺階晋被，剩下還有n-1級臺階，有f(n-1)種跳法刚盈。假如一次跳2級臺階墨微，剩下n-2級臺階，有f(n-2)中跳法扁掸。這就表示f(n) = f(n-1)+f(n-2)翘县。

function fibonacci(n) {
    if (n === 1 || n === 2) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2)
    }
}
// 一個記憶化的斐波那契數(shù)列
let tem = [0, 1]
function fibonacci(n) {
   let result = tem[n]
   if(typeof result !== 'number') {
        result = fibonacci(n-1)+fibonacci(n-2)
        tem[n] = result   // 將每次 fibonacci(n) 的值都緩存下來
   }
   return result
}
// 動態(tài)規(guī)劃：從底部開始解決問題， 將所有小問題解決掉谴分， 然后合并成一個整體解決方案锈麸， 從而解決掉整個大問題 。
function fibonacci(n) {
    let last = 1;
    let nextLast = 1;
    let result = 1;
    for (let i = 2; i < n; ++i) {
        result = last + nextLast;
        nextLast = last;
        last = result;
    }
    return result;
}

二分查找牺蹄。

數(shù)組array包含了順序的元素忘伞，[1,2,3,...,10]，查找目標(biāo)元素t是否在數(shù)組中。
我們已經(jīng)提前知道數(shù)組是順序排列的氓奈，比如遞增順序翘魄。
時間復(fù)雜度為O(logN)
遞推公式：
f(N) = f(N/2) + O(1) = f(N/4) + 2 * O(1)
假設(shè) N = 2 ^ M
最后可以推出
f(N) = O(logN)

let list = [1,2,3,4,5,6,7,8,9,10]
function binarySearch(array, t) {
    let left = 0, right = array.length - 1;
    while(left <= right) {
        let mid = parseInt((right + left)/2)
        if(array[mid] < t) {
            left = mid + 1
        } else if(array[mid] > t) {
            right = mid - 1
        } else {
            return true
        }
    }
    return false
}
// 遞歸寫法
function binarySearch2(array, t, left, right) {
    if(left > right) return -1
    let mid = parseInt((right - left)/2) + left
    if(array[mid] === t) {
        return mid
    }else if(array[mid] < t){
        return binarySearch2(array, t, mid + 1, right)
    }else if(array[mid] > t){
        return binarySearch2(array, t, left, mid - 1)
    }
}
let test1 = binarySearch(list, 5)
let test2 = binarySearch2(list, 5, 0, list.length-1)
console.log(test1, test2)

貪心算法--最少硬幣找零問題

所謂貪心，就是先選擇當(dāng)前階段的最優(yōu)解舀奶，不去考慮這次的選擇會不會對未來造成影響暑竟，想要通過每個階段的局部最優(yōu)解，達(dá)到全局最優(yōu)解育勺。

假設(shè)你為一家自動售貨機廠家編程序但荤，自動售貨機要每次找給顧客最少數(shù)量硬幣，美國有以下面額的硬幣：1美分涧至、5美分腹躁、10美分、25美分南蓬。比如說要找36美分的零錢纺非，我們可以用1個25美分、1個10美分和一個1美分赘方。
(ps：找零問題铐炫，先找大額的硬幣25分，依次遞減)

function minCoinChange(amount, coins) {
    let minCoin = amount
    let count = 0
    for(let i = 0, l = coins.length; i < l; i++) {
        if (coins[i] <= minCoin) {
            count += Math.floor(minCoin / coins[i])
            console.log(coins[i] + '*' + Math.floor(minCoin / coins[i]))
            minCoin = minCoin % coins[i]
        }
    }
    return count
}
let counts = minCoinChange(61, [25, 10, 5, 1])
console.log(counts)

動態(tài)規(guī)劃--01背包問題

image.png

function main(volume, value, c){
    let tArray = []
    let useGoodsNo = []
    for(let i = 0, l = volume.length; i <= l; i++) {
        tArray[i] = []
        useGoodsNo[i] = 0
        for(let j = 0; j <= c; j++) {
            if(i == 0 || j == 0){
                tArray[i][j] = 0
            }
        }
    }

    volume.unshift(0)  //讓i = 1的時候?qū)?yīng)的是1號物品
    value.unshift(0)
    
    for(let i = 1, l = volume.length; i < l; i++) {  // i從1開始 tArray[0][j]已經(jīng)填滿
        for(let j = 1; j <= c; j++) {
            if(j < volume[i]){
                tArray[i][j] = tArray[i-1][j]
            } else {
                //如果裝了剩下的體積
                let leftVolume = j - volume[i]
                // 當(dāng)前物品的價值
                let curValue = value[i]
                // 剩下的體積的價值是 （tArray[i - 1]因為0 1背包蒜焊，不能重復(fù)放同個物品）
                let leftValue = tArray[i - 1][leftVolume]

                tArray[i][j] = Math.max(tArray[i-1][j], curValue+leftValue)
            }
        }
    }
    // 填滿表格
    console.table(tArray)
    // 逆向獲取物品
    let C = c
    for(let i = value.length-1; i > 0; i--){
        if(tArray[i][C] > tArray[i-1][C]){
            useGoodsNo[i] = 1
            C = C - volume[i]
        }
    }
    console.table(useGoodsNo)  // 所選的物品
    console.log(tArray[value.length-1][c])  // 最大價值
}
main([2,3,4,5], [3,4,5,6], 8)

展平數(shù)組

// 展平數(shù)組 [[1, 2], 3, [[[4], 5]]] => [1, 2, 3, 4, 5]
function flatten(arr) {
    return [].concat(
        ...arr.map(x => Array.isArray(x) ? flatten(x) : x)
    )
}

隨機打亂數(shù)組

function shuffle(arr) {
    for(let i = 0; i < arr.length-1; i++){
        const j = i + Math.floor(Math.random() * (arr.length - i))
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
}

函數(shù)節(jié)流倒信，防抖

// 函數(shù)節(jié)流
function throttle(func, delay = 60) {
    let lock = false
    return (...args) => {
        if(lock) return
        func(...args)
        lock = true
        setTimeout(()=> {
            lock = false
        }, delay)
    }
}
// 防抖函數(shù)
function debounce (fn, delay = 60) {
        let timer
        return (...arg) => {
            clearTimeout(timer)
            timer = setTimeout(()=>{
                fn(...arg)
            }, delay)
        }
    }

深拷貝

let obj = {
        a: 100,
        b: [10, 20, 30],
        c: {
            x: 10
        },
        d: /^\d+$/
}
function deepClone(obj) {
    if(obj === null) return null
    if(typeof obj != 'object') return obj
    if(obj instanceof RegExp) { return new RegExp(obj) }
    if(obj instanceof Date) { return new Date(obj) }
        
    let newObj = new obj.constructor // 不直接創(chuàng)建空對象，克隆的結(jié)果和之前保持相同的所屬類
    for(let key in obj){
        if(obj.hasOwnProperty(key)) {
            newObj[key] = deepClone(obj[key])
        }
    }
    return newObj
}

柯里化

對于curry(foo),g函數(shù)參數(shù)足夠4個泳梆，就調(diào)用foo(a,b,c,d),如果小于4就返回一個可以繼續(xù)積累參數(shù)的函數(shù)
const curry = func => {
    const g = (...allArgs) => allArgs.length >= func.length ?
    func(...allArgs) : (...args) => g(...allArgs, ...args)
    return g
} 
const foo = curry((a, b, c, d) =>{
    console.log(a, b, c, d)
})
foo(1)(2)(3)(4) // 1 2 3 4
foo(1)(2)(3)  // 不返回
const f = foo(1)(2)(3)
f(4) // 1 2 3 4 5

滑動窗口

image.png

力扣1343題鳖悠，求大小為 K 且平均值大于等于threshold的子數(shù)組數(shù)目，和所有子數(shù)組优妙？
var arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
var numOfSubarrays = function(arr, k, threshold) {
    let sums = 0  // 子數(shù)組的和
    let nums = 0  // 結(jié)果數(shù)目
    let target = k * threshold
    let result = []  // 結(jié)果子數(shù)組
    let sub = []  

    if (arr.length < k) return 0

    // 初始化子數(shù)組
    for(let i = 0; i < k; i++) {
        sums += arr[i]
        sub.push(arr[i])
    }
    if (sums >= target){
        result.push(sub.join(','))
        nums++
    }

    // 滑動窗口
    for(let i = k, l = arr.length; i < l; i++) {
        sums = sums - arr[i - k]
        sums = sums + arr[i]

        sub.shift()
        sub.push(arr[i])

        if (sums >= target) {
            result.push(sub.join(','))
            nums++
        }
    }

    return {
        nums,
        result
    }
}

let result = numOfSubarrays2(arr, k,threshold)
console.log(result)

Y組合子

const y = function(le) {
    return function (f) {
        return f(f)
    }(function (f) {
        return le(
            function(...x) {
                return (f(f))(...x)
            }
        )
    })
}
const curryY = func => y(g => {
        (...allArgs) => {
            allArgs.length >= func.length ? func(...allArgs) : (...args) =>g(...allArgs, ...args)
        }
    }
)
const foo = curryY((a, b, c, d) => {
    console.log(a, b, c, d)
})
foo(1)(2)(3)(4)

鏈表

鏈表中最簡單的一種是單向鏈表乘综，它包含兩個域，一個信息域和一個指針域套硼。這個鏈接指向列表中的下一個節(jié)點卡辰，而最后一個節(jié)點則指向一個空值。

function ListNode(val) {
    this.val = val
    this.next = null
}
let node1 = new ListNode(1)
let node2 = new ListNode(2)
let node3 = new ListNode(3)
node1.next = node2
node2.next = node3
console.log(node1)

function recursiveTraverse(head) {
    if(head != null) {
        console.log(head.val)
        recursiveTraverse(head.next)
    }
}
recursiveTraverse(node1)

// 翻轉(zhuǎn)一條單向鏈表
// 輸入 1 -> 2 -> 3 -> null
// 輸出 3 -> 2 -> 1 -> null
function reverseLinkedList(head){
    let dummy = head
    let tem = dummy
    while(head != null && head.next != null){
        dummy = head.next
        head.next = dummy.next
        dummy.next = tem
        tem = dummy
    }
    return dummy
}
let reverseLink = reverseLinkedList(node1)
console.log(reverseLink)

二叉樹

function TreeNode(val) {
    this.val = val
    this.left = null
    this.right = null
}
let root = new TreeNode(2)
root.left = new TreeNode(1)
root.right = new TreeNode(3)
console.log(root)
/*
*     2
*   /   \
*  1     3
*/

/*
    中序遍歷：(
        定義：
        1邪意，中序遍歷左子樹
        2九妈，遍歷根節(jié)點
        3，中序遍歷右子樹
    )
    前序遍歷：(
        定義：
          1雾鬼，遍歷根節(jié)點
          2萌朱，前序遍歷左子樹
          3，前序遍歷右子樹
    )
    后序遍歷：(
        定義：
          1策菜，后序遍歷左子樹
          2晶疼，后序遍歷右子樹
          3酒贬，遍歷根節(jié)點
    )
*/

function inOrder(root) {
    if(root) {
        console.log('前',root.val)  // 2 1 3
        inOrder(root.left)
        console.log('中',root.val)  // 1 2 3
        inOrder(root.right)
        console.log('后',root.val)  //  1 3 2
    }
}
inOrder(root)

/*
    二叉查找樹/二叉搜索樹：(
        定義：
        左子樹的所有節(jié)點的值小于根節(jié)點
        右子樹的所有節(jié)點的值大于根節(jié)點
        左子樹和右子樹都是二叉查找樹
    )
    二叉搜索樹的中序遍歷就是排好序的元素。
*/
function binarySearchTreeFind(root, target) {
    if(!root) return false
    if(root.val === target) {
        return true
    } else if(root.val < target){
        return binarySearchTreeFind(root.right, target)
    } else if(root.val > target) {
        return binarySearchTreeFind(root.left, target)
    }
}
console.log(binarySearchTreeFind(root, 1))

棧

First In Last Out（FILO）
先進后出翠霍，后進先出

function Stack(){
    this.stack = []

    this.isEmpth = function(){
        return this.size() === 0
    }
    this.size = function() {
        return this.stack.length
    }
    // 出棧
    this.pop = function(){
        if(this.isEmpth()){
            return null
        } else {
            return this.stack.pop()
        }
    }
    // 進棧
    this.push = function (val){
        return this.stack.push(val)
    }
        // 返回棧頂元素
    this.peak= function(){
        if(this.isEmpth()) {
            return null
        } else {
            return this.stack[this.stack.length - 1]
        }
    }
}

let test = new Stack()
test.push(1)
console.log(test.peak())
console.log(test.isEmpth())
test.pop()
console.log(test.peak())

隊列

First In First Out(FIFO)
先進先出

function Queue() {
    this.queue = []

    this.size = function() {
        return this.queue.length
    }
    this.isEmpty = function(){
        return this.size() === 0
    }
    // 入隊列
    this.enqueue = function (val){
        this.queue.unshift(val)
    } 
    // 出隊列
    this.dequeue = function(){
        if(this.isEmpty()){
            return null
        } else {
            return this.queue.pop()
        }
    }
}
let test = new Queue()
test.enqueue(1)
test.enqueue(2)
console.log(test.queue)
test.dequeue()
console.log(test.queue)