专栏首页code秘密花园《剑指offer》分解让复杂问题更简单

《剑指offer》分解让复杂问题更简单

1.复杂链表的复制

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用)

思路

拆分成三步

1.复制一份链表放在前一个节点后面,即根据原始链表的每个节点N创建N ,把N直接放在N的next位置,让复制后的链表和原始链表组成新的链表。

2.给复制的链表random赋值,即N`.random=N.random.next。

3.拆分链表,将N`和N进行拆分,保证原始链表不受影响。

代码

function Clone(pHead) {
      if (pHead === null) {
        return null;
      }
      cloneNodes(pHead);
      cloneRandom(pHead);
      return reconnetNodes(pHead);
    }

    function cloneNodes(pHead) {
      var current = pHead;
      while (current) {
        var cloneNode = {
          label: current.label,
          next: current.next
        };
        current.next = cloneNode;
        current = cloneNode.next;
      }
    }

    function cloneRandom(pHead) {
      var current = pHead;
      while (current) {
        var cloneNode = current.next;
        if (current.random) {
          cloneNode.random = current.random.next;
        } else {
          cloneNode.random = null;
        }
        current = cloneNode.next;
      }
    }

    function reconnetNodes(pHead) {
      var cloneHead = pHead.next;
      var cloneNode = pHead.next;
      var current = pHead;
      while (current) {
        current.next = cloneNode.next;
        current = cloneNode.next;
        if (current) {
          cloneNode.next = current.next;
          cloneNode = current.next;
        } else {
          cloneNode.next = null;
        }
      }
      return cloneHead;
    }

2.二叉搜索树转换为双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

思路

1.排序的双向链表-中序遍历二叉树

2.记录链表的最后一个节点

3.每次遍历:设置树节点的left和链表的right进行链接,链接成功后当前节点成为链表的末尾节点,并返回。

代码

function Convert(pRootOfTree) {
      var lastNode = null;
      lastNode = convertToList(pRootOfTree, lastNode);
      while (lastNode && lastNode.left) {
        lastNode = lastNode.left;
      }
      return lastNode;
    }

    function convertToList(treeNode, lastNode) {
      if (!treeNode) {
        return null;
      }
      if (treeNode.left) {
        lastNode = convertToList(treeNode.left, lastNode);
      }
      treeNode.left = lastNode;
      if (lastNode) {
        lastNode.right = treeNode;
      }
      lastNode = treeNode;
      if (treeNode.right) {
        lastNode = convertToList(treeNode.right, lastNode);
      }
      return lastNode;
    }

3.字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路

1.把字符串分成两部分,第一个字符和后面的字符 2.整个字符串的全排列等于:第一个字符+后面字符的全排列,第一个字符和后面的字符诸葛交换。

第一个字符+后面字符的全排列3.除了第一个字符其他字符的全排列等于:第二个字符+后面字符的全排列。

3.递归,记录一个当前节点的位置,该位置指向最后一个节点时记录一次排列。

代码

function Permutation(str) {
      var result = [];
      if (!str) {
        return result;
      }
      var array = str.split('');
      permutate(array, 0, result);
      result.sort();
      return [... new Set(result)];
    }

    function permutate(array, index, result) {
      if (array.length - 1 === index) {
        result.push(array.join(''));
      }
      for (let i = index; i < array.length; i++) {
        swap(array, index, i);
        permutate(array, index + 1, result);
        swap(array, i, index);
      }
    }

    function swap(arr, i, j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }

本文分享自微信公众号 - code秘密花园(code_mmhy),作者:ConardLi

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【算法专栏】二叉树的几种遍历方式(原创)

    ConardLi
  • 【剑指offer】8.斐波那契数列

    题目描述 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

    ConardLi
  • 多网站项目的 CSS 架构

    我在互联网行业的第四份工作,是在我国一家领先的媒体新闻公司中任职一名 CSS/HTML 专家,我的主要职责就是开发可重用的、可扩展的、用于多网站的 CSS 架构...

    ConardLi
  • Leetcode 82. Remove Duplicates from Sorted List II

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • javascript探秘之从零到一实现单向 & 双向链表

    前端工程师对于算法和数据结构这块的知识的掌握程度,是进阶高级工程师的非常重要的标志之一,为了总结一下数据结构和算法方面的知识,笔者今天继续把链表这一块的知识补上...

    徐小夕
  • 《javascript数据结构和算法》读书笔记(3):链表

    储存多个元素,数组是最常用的。无论何种语言,都实现了数组。但是大多数语言中,数组的长度是固定的。数组修改操作的成本非常高。

    一粒小麦
  • 重读《学习JavaScript数据结构与算法-第三版》- 第6章 链表(一)

    本章为重读《学习JavaScript数据结构与算法》的系列文章,该章节主要讲述数据结构-链表,以及实现链表的过程和原理。

    胡哥有话说
  • 数据结构知否知否系列之 — 线性表的顺序与链式存储篇(8000 多字长文)

    线性表是由 n 个数据元素组成的有限序列,也是最基本、最简单、最常用的一种数据结构。

    五月君
  • qt学习第2天:QRadioButtonTest+ButtonGroup单选后提示消息,QComBox

    项目名称:QRadioButtonTest 运行结果:选中按钮后其他则无法继续选择,点击save后提示选择了那个按钮 在QRadioButtonTest.h...

    cuptobjut
  • Word2Vec

           以前对于文本类型的数据,都是通过tf-idf进行处理的,这个可以参见以前写的博客,这里就不在详细介绍了。最近项目组老大跟我说了word2vec这种...

    用户1171305

扫码关注云+社区

领取腾讯云代金券