前端算法面试必刷题系列[39]

吐槽君发布于 3年前分类：javascript

这个系列没啥花头，就是纯 leetcode 题目拆解分析，不求用骚气的一行或者小众取巧解法，而是用清晰的代码和足够简单的思路帮你理清题意。让你在面试中再也不怕算法笔试。

69. 反转链表 II (reverse-linked-list-ii)

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

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

基本思路

链表的头插法，这个图画的非常清楚，直接引用了。底部有参考链接。

整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。

那么第一步是如何实现的?

下面我们具体解释如何实现。使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量，它们的意义如下：

curr：指向待反转区域的第一个节点 left；
next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；
pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。

第 1 步，我们使用 ①、②、③ 标注「穿针引线」的步骤。

操作步骤：

先将 curr 的下一个节点记录为 next；
执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；
执行操作 ③：把 pre 的下一个节点指向 next。

第 1 步完成以后「拉直」的效果如下：

curr 继续往前走，直到走完所有反转区域。

写法实现

var reverseBetween = function(head, left, right) {
  const preHead = new ListNode(0);
  preHead.next = head;
  let pre = preHead;
  // pre 永远指向反转区域的前一个节点
  for (let i = 0; i < left - 1; i++) {
    pre = pre.next;
  }
  // curr 指向当前待反转区域的第一个节点
  let curr = pre.next;
  for (let i = 0; i < right - left; i++) {
    // next 永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化
    let next = curr.next;
    // 把 curr 的下一个节点指向 next 的下一个节点；
    curr.next = next.next;
    // 把 next 的下一个节点指向 pre 的下一个节点；
    next.next = pre.next;
    // 把 pre 的下一个节点指向 next。
    pre.next = next;
  }
  return preHead.next;
};

70. 复原 IP 地址 (restore-ip-addresses)

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

输入：s = "0000"
输出：["0.0.0.0"]

基本思路

DFS + 回溯

这个回溯其实跟之前的也差不多，只是说全排列简单的选取数字就行，而这个需要对字符串进行切分。

每三个数作为选取的分支条件，每次可以选 1个，2个，或者3个这三条路走。

再根据先导 0，255等边界条件剪枝即可。

基本步骤

我们还是根据之前的解决 DFS + 回溯一样把模板搞出来

var dfsProblems = function(s) {
    let res = []
    let dfs = (curPath, start(可选参数)) => {
        if (符合条件) { 
            res.push(xFunction(curPath))
        }
        if (剪枝条件) return
        // 下面是根据题意 有几个岔路，开始选择
        for() {
            curPath.push(xxx)
            dfs(curPath, start(可选参数)) // 递归深搜
            // 回溯
            curPath.pop()
        }
    }
    dfs([], start(可选参数))
    return res
}

所有题目基本都是这个套路，只是情境变化而已。这题用 start 来做个游标，加一个参数。之后步骤下面的代码注释足够理解了，不赘述。

写法实现

var restoreIpAddresses = function(s) {
  let [res, len] = [[], s.length]
  let dfs = (curPath, segStart) => {
    // 如果1. 找到了4段合法 IP 并且2. 遍历完了字符串，那么就是一种答案
    if (curPath.length === 4) {
      if (segStart === len) {
        res.push(curPath.join('.'))
      } else {
        // 还没遍历完，剪枝
        return
      }
    }
    // 每个 curPath 中的元素长度可能为 1,2,3 遍历
    for (let segLen = 1; segLen <= 3; segLen++) {
      // 直接超出长度
      if (segStart + segLen > len) {
        return;
      }
      // 除非只有一位 0 ，不能有先导 0
      if (segLen !== 1 && s[segStart] === '0') {
        return
      }
      // 当前被切出的片段
      let segStr = s.substring(segStart, segStart + segLen);
      if (segLen === 3 && segStr * 1 > 255) {
        // 不能超255
        return
      }
      // 回溯基本操作
      curPath.push(segStr)
      dfs(curPath, segStart + segLen)
      curPath.pop()
    }
  }
  dfs([], 0)
  return res
};

let s = "25525511135";
console.log(restoreIpAddresses(s))

另外向大家着重推荐下这位大哥的文章，非常深入浅出，对前端进阶的同学非常有作用，墙裂推荐！！！核心概念和算法拆解系列

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦
搜索我的微信号infinity_9368，可以聊天说地
加我暗号 "天王盖地虎" 下一句的英文，验证消息请发给我
presious tower shock the rever monster，我看到就通过，暗号对不上不加哈，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧

参考

leetcode-cn.com/problems/re…
leetcode-cn.com/problems/re…

我来回复

暂无回复内容

前端算法面试必刷题系列[39]

69. 反转链表 II (reverse-linked-list-ii)

标签

题目

基本思路

写法实现

70. 复原 IP 地址 (restore-ip-addresses)

标签

题目

基本思路

基本步骤

写法实现

参考

回复