全排列、反转链表、最大子数组和

全排列

思路：

需要两个新变量：used 记录已使用的，res 保存所有返回结果

功能函数的入参也是 track 和 used，结束条件是 track.length 到顶。

接着的是回溯算法，先 push 数字进去，在 use 中记录该数字已使用，等回溯完又把数字 pop 出来，在 use 中标记为未使用

tsCopy
function permute(nums: number[]): number[][] {
  let used = new Array(nums.length).fill(false);
  let res = [];

  const backtrack = (nums, track, used) => {
    if (track.length === nums.length) {
      return res.push([...track]);
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) {
        continue;
      }

      track.push(nums[i]);
      used[i] = true;

      backtrack(nums, track, used);

      track.pop();
      used[i] = false;
    }
  };

  backtrack(nums, [], used);

  return res;
}

反转链表

思路 1：迭代

tsCopy
function reverseList(head: ListNode | null): ListNode | null {
  let cur = head,
    prev = null;

  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }

  return prev;
}

思路 2：尾递归。head.next 本身不会直接修改 last，但它的 next 反转操作改变了 last 之后的链表结构

tsCopy
function reverseList(head: ListNode | null): ListNode | null {
  // 1. 空链表 2. 只有一个节点，可以直接返回本身
  if (head === null || head.next === null) {
    return head;
  }

  // 从 head.next 开始的子链表反转结果，last 返回该子链表的头节点
  const last = reverseList(head.next);
  // head.next 指的是当前节点的下一个子节点。这个子节点的 next 需要指向 head
  head.next.next = head;
  // 断掉 head 和 head.next 的联系
  head.next = null;

  // 由于链表一直调用，last 最终会返回原链表的最后一个节点
  return last;
}

最大子数组和

思路：以 nums[i] 为结尾的「最大子数组和」为 dp[i]。

dp[i] 有两种「选择」：

1. 与前面的相邻子数组连接，形成一个和更大的子数组

2. 不与前面的子数组连接，自成一派，自己作为一个子数组。

在这两种选择中择优，就可以计算出最大子数组

tsCopy
function maxSubArray(nums: number[]): number {
  const n = nums.length;
  let res = -Infinity;
  let dp = new Array(n);

  // base case，第一个元素前面没有子数组
  dp[0] = nums[0];

  // 状态转移方程
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
  }

  // 得到 nums 的最大子数组。这里起始从 0 开始比较，所以不能跟上面一起循环
  for (let i = 0; i < n; i++) {
    res = Math.max(dp[i], res);
  }

  return res;
}