算法

链表及数组

反转链表

leetcode-cn.com/problems/re…

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const reverseList = function(head) {
  if (head === null) return head;
  if (head.next === null) return head;

  let prev = null;
  let cur = head;
  let tmp = cur.next;

  while (cur) {
    cur.next = prev
    prev = cur;
    cur = tmp;
    tmp = cur ? cur.next : cur;
  }

  return prev;
};
复制代码

解题思路:

• 从 1->2->3->4->null 反转为 null<-1<-2<-3<-4
• 三个指针 prev, cur, tmp 分别指向前中后三个结点
• 开始反转
  • cur.next 指向 prev (反指)
  • prev 指向 cur (挪位置)
  • cur 指向 tmp (挪位置)
  • tmp 指向 cur.next (挪位置)

图解:

cur.next 指向 prev (反指)

prev 指向 cur (挪位置)

cur 指向 tmp (挪位置)

tmp 指向 cur.next (挪位置)

结束条件: 当 cur 指向 null

复杂度: $O(N)$

map

树

动态规划

三角形最小路径和

leetcode-cn.com/problems/tr…

m 行 * n 列
   2              2
  3 4             3 4
 6 5 7     =>     6 5 7
4 1 8 3           4 1 8 3
复制代码

解法一: 暴力求解 (递归)

思路:

• 从上到下递归
• 计算每一个路径的总和

// 伪代码
const sums = [];

function travel(i, j, lastSum = 0) {

  if (最后一行) {
    sums.push(lastSum + triangle[i][j]);
  } else {
    travel(i+1, j, lastSum + triangle[i][j]);
    travel(i+1, j+1, lastSum + triangle[i][j]);
  }
}

max(sums)
复制代码

解法二: DP

思路:

• 定义状态和状态方程
  • 状态 DP[i, j]: 从下往上走到 (i, j) 时, 所有的路径和中, 的最小值
  • 状态方程: DP[i, j] = min( DP[i+1, j], DP[i+1, j+1] ) + Triangle[i, j]
  • 初始值: DP[m-1, j] = Triangle[m-1, j] (最后一行的值就是它本身)

时间复杂度: $O(m \times n)$
空间复杂度: $O(m \times n)$ (因为需要一个二维数组)

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    if (triangle.length === 1) {
        return triangle[0][0];
    }

    const rowCount = triangle.length;
    const maxColumnCount = triangle[triangle.length - 1].length;

    // 覆盖传入的 triangle
    // 从倒数第二行开始覆盖, 最后一行就是 triangle 其值本身
    for (let i = rowCount - 2; i >= 0; i--) {
        for (let j = 0; j <= maxColumnCount - (rowCount - i); j++) {  // 列
            triangle[i][j] = triangle[i][j] + Math.min( triangle[i+1][j], triangle[i+1][j+1] );
        }
    }

    return triangle[0][0];
};`
复制代码