K 个一组翻转链表、最小栈、打家劫舍

K 个一组翻转链表

题目描述

给你链表的头节点 head，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路

递归地翻转。

工具函数：传入头节点 a 和尾节点 b，翻转 [a, b) 范围内的链表，并返回新的头节点 prev

主函数：

先 for 循环找出尾节点 b。若循环过程中出现 b == null，说明这部分链表构不成 k 个，因此不翻转，直接返回 head

用 newHead 存储工具函数返回的结果。这便是整个链表的头部，最后返回的是这个

因为 a 翻转后变成了链表的最后一个节点，所以 a.next 递归地接 reverseKGroup(b, k)（b 因为是左闭右开，所以不算在上一个区间里面，实际上是下一个链表的开头）

题解

ts
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  if (!head) {
    return null;
  }

  let a = head,
    b = head;

  for (let i = 0; i < k; i++) {
    if (!b) {
      return head;
    }
    b = b.next;
  }

  const newHead = reverse(a, b);
  a.next = reverseKGroup(b, k);

  return newHead;
}

const reverse = (a, b) => {
  let prev = null,
    cur = a;

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

  return prev;
};

最小栈

题目描述

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。

void push(int val) 将元素 val 推入堆栈。

void pop() 删除堆栈顶部的元素。

int top() 获取堆栈顶部的元素。

int getMin() 获取堆栈中的最小元素。

示例:

输入：

["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"]

[[], [-2], [0], [-3], [], [], [], []]

输出：

[null, null, null, null, -3, null, 0, -2]

解释：

ts
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   // --> 返回 -3
minStack.pop();
minStack.top();      // --> 返回 0
minStack.getMin();   // --> 返回 -2

思路

空间换时间：维护一个最小栈。

入栈：当 minStack.length === 0 或入栈元素的值 ≤ 最小栈栈顶元素，则入最小栈

删除：当被删除元素的值 === 最小栈栈顶元素的值，则弹出栈顶

题解

ts
class MinStack {
  minStack: number[];
  stack: number[];

  constructor() {
    this.minStack = [];
    this.stack = [];
  }

  push(val: number): void {
    if (this.minStack.length === 0 || this.getMin() >= val) {
      this.minStack.push(val);
    }
    this.stack.push(val);
  }

  pop(): void {
    const val = this.stack.pop();
    const minVal = this.getMin();

    if (minVal === val) {
      this.minStack.pop();
    }
  }

  top(): number {
    return this.stack[this.stack.length - 1];
  }

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

打家劫舍

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例：

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

输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4。

思路

dp(start) 的定义：从第 start 个房子开始抢，能抢到的最大金额

在第 start 个房子有两个选择：

不抢它：转到 start + 1
抢它：那就不能抢 start + 1 了，下一次只能从 start + 2 开始

然后在二者之间取最大值

题解

ts
function rob(nums: number[]): number {
  const memo = Array.from({ length: nums.length }, () => -1);

  const dp = (start: number) => {
    if (start >= nums.length) {
      return 0;
    }

    if (memo[start] !== -1) {
      return memo[start];
    }

    const notChooseRob = dp(start + 1);
    const chooseRob = dp(start + 2) + nums[start];

    const res = Math.max(notChooseRob, chooseRob);
    memo[start] = res;

    return res;
  };

  return dp(0);
}