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

全排列

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。可以按任意顺序返回答案

示例：

输入：nums = [1, 2, 3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路：

需要两个新变量：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;
}

反转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表。

可以假设每种输入只会对应一个答案，并且不能使用两次相同的元素

示例：

输入：head = [1,2,3,4,5]

输出：[5,4,3,2,1]

思路 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 ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例：

输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

输出：6

解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6 。

思路：以 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;
}