博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
《剑指offer》分解让复杂问题更简单
阅读量:6568 次
发布时间:2019-06-24

本文共 3090 字,大约阅读时间需要 10 分钟。

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]];    }

转载地址:http://byvjo.baihongyu.com/

你可能感兴趣的文章
session cookie
查看>>
$.extend({},defaults, options) --(初体验三)
查看>>
android 一步一步教你集成tinker(热修复)
查看>>
到底有多少内存
查看>>
centos7.3 安装ovirt-engine4.0 版本
查看>>
Openstack的环境的Mitaka部署环境服务,实例(1)
查看>>
文档的压缩与打包
查看>>
python3 在不同操作系统安装第三方库方法
查看>>
python编写登录接口
查看>>
MySQL高可用方案之多级复制
查看>>
OVS 中的各种网络设备 - 每天5分钟玩转 OpenStack(128)
查看>>
Trafficserver Cluster模式
查看>>
亚马逊推出 Blox,用于 EC2 容器服务的开源工具集合
查看>>
Linux:在中国没有真正的新闻
查看>>
iOS推送功能极光推送的介绍与实现
查看>>
单用户模式与grub加密
查看>>
Chromium Graphics: 3D上下文及其虚拟化 - Part I
查看>>
jquery javascript获得网页的高度和宽度
查看>>
2019 -2-15 复习
查看>>
vim锁定屏幕
查看>>