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

我心飞翔 分类:javascript

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

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

标签

  • 链表
  • 头插法
  • 中等

题目

leetcode 传送门

这里不贴题了,leetcode打开就行,题目大意:

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

image.png

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

基本思路

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

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

image.png

image.png

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

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

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

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

image.png

操作步骤:

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

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

image.png

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)

标签

  • DFS + 回溯
  • 中等

题目

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等边界条件剪枝即可。

基本步骤

  1. 我们还是根据之前的 解决 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…

回复

我来回复
  • 暂无回复内容