翻转链表

---

#链表 这道题有点烦，因为js没有指针这种说法，实现起来也有点奇怪

let head = [1, 2, 3, 4, 5]

function ListNode(val, next) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
}
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    let pre = null,
        cur = head
    while (cur) {
        const nxt = cur.next
        cur.next = pre // 把 cur 插在 pre 链表的前面（头插法）
        pre = cur // 将头转换为刚插入的结点
        cur = nxt
    }
    return pre
}

console.log('result:', reverseList(head))

爬楼梯

---

#动态规划

/**
 * @param {number} n
 * @return {number}
 */

// 使用额外的空间来减少同样的计算
const map = new Map()
var climbStairs = function (n) {
    if (n === 0 || n === 1) {
        return 1
    } else if (n === 2) {
        return 2
    }

    if (map.has(n)) {
        console.log('has', map.get(n))

        return map.get(n)
    } else {
        const temp = climbStairs(n - 1) + climbStairs(n - 2)
        map.set(n, temp)
        return temp
    }
}

console.log(climbStairs(10))
// has 3
// has 5
// has 8
// has 13
// has 21
// has

杨慧三角

---

这个使用通项公式的思路的问题就是：在计算阶乘时，即使使用了缓存，对于较大的n（比如30），阶乘值已经非常大，Number超出了安全整数范围，所以会出现精度丢失（如：377.99999999999994。

// 阶乘函数
const map1 = new Map()
function factorial(n) {
    if (n < 0) return NaN
    if (n === 0 || n === 1) return 1

    if (map1.has(n)) {
        return map1.get(n)
    } else {
        let result = 1
        for (let i = 2; i <= n; i++) {
            result *= i
        }
        map1.set(n.result)
        return result
    }
}

// 杨辉三角通项公式
function yanghuiTerm(n, k) {
    return factorial(n) / (factorial(k) * factorial(n - k))
}

// 生成杨辉三角的某一行
function generateYanghuiRow(rowIndex) {
    const row = []
    for (let k = 0; k <= rowIndex; k++) {
        row.push(yanghuiTerm(rowIndex, k))
    }
    return row
}

var generate = function (numRows) {
    const result = []
    for (let index = 0; index < numRows; index++) {
        result.push(generateYanghuiRow(index))
    }
    return result
}

console.log(generate(23))
// [ [ 1 ], [ 1, 1 ], [ 1, 2, 1 ], [ 1, 3, 3, 1 ], [ 1, 4, 6, 4, 1 ] ]

灵神的这个思路我最开始也是这样想的，但感觉通项会快

var generate = function(numRows) {
    const c = Array(numRows);
    for (let i = 0; i < numRows; i++) {
        c[i] = Array(i + 1);
        c[i][0] = c[i][i] = 1;
        for (let j = 1; j < i; j++) {
            // 左上方的数 + 正上方的数
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
    return c;
};

打家劫舍

---

#动态规划 从问题规模最小的时候考虑，一般是最后一个或开始的时候。如果做后一个n没有偷，那么n- 就要偷了，n偷了，n-2就偷dfs(i) = Math.max(dfs(i - 1), dfs(i - 2) + nums[i])

 /**
 * @param {number[]} nums
 * @return {number}
 */

var rob = function (nums) {
    const len = nums.length
    
	// 使用缓存减少重复的计算
    const map = new Map()

    function dfs(i) {
        if (i < 0) {
            return 0
        }
        if (map.has(i)) {
            return map.get(i)
        } else {
            const t = Math.max(dfs(i - 1), dfs(i - 2) + nums[i])
            map.set(i, t)
            return t
        }
    }
    return dfs(len - 1)
}