农家小舍

文章目录题解分析代码实现实现一个函数，完成复杂链表的复制功能；在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。题解分析普通链表复制非常简单，只需遍历一遍，复制创建每个节点即可。但因此复杂链表中有一个next指针，指向不确定的节点，所以普通方式修改复制next指针时，需要在复制每个指针时遍历一遍链表；无法在O(N)时间内完成。因链表是可以随意拼接、断开的；因此可以先把新创建的节点连接在源节点后面，在全部完成（包括设定nex

文章目录题解分析代码实现实现一个函数用来判断字符串是否表示数值（包括整数和小数）题解分析一个标识数字的字符串可能包括以下字符类型：空格；数组：0~9；正负号小数点幂符号：e/E；为了解决此类问题，需要使用有限状态自动机，字符串有如下状态：0：开始的空格；1：幂符号前的正负号；2：小数点前的数字；3：小数点、小数点后的数字；4：小数点前为空格时：小数点、小数点后的数字；5：幂符号；6：幂符号后的正负号；7：幂符号后的数字；8：结尾的空格；合法的结束状态有：2、3、7

文章目录题解分析代码实现定义带min函数的栈数据结构：实现一个能够得到栈中最小元素的min函数；调用min、push及pop的时间复杂度为O(1)；题解分析普通栈的push()和pop()函数的复杂度为O(1)，但获取栈最小值min()函数需要遍历整个栈，复杂度为O(N)；要将min()函数复杂度降为O(1)，需要借助辅助栈：数据栈All：存储所有元素，实现入栈push()函数、出栈pop()函数、获取栈顶top()函数的正常逻辑；辅助栈Ordered：存储所有非严格降序元素的子序列（栈

文章目录题解分析代码实现用两个栈实现一个队列：实现添加appendTail（在队列尾部插入整数）与删除deleteHead（在队列头部删除整数）函数的功能；若队列中没有元素，deleteHead 操作返回-1；题解分析队列是先进先出，而栈是先进后出；为了能使队列移除头部元素，就需要保证栈顶元素是最先进入的元素：使用双队列：一个存放正常入队的元素的input，另外一个存放倒序元素（从第一个出栈，再入栈即为倒序）的output；入队：直接加入栈input即可；出队：若output不为空，则

根据中位数与旋转点相对位置查找切分数组查找给定一个没有重复元素的旋转数组（它对应的原数组是有序的），求给定元素在旋转数组内的下标（不存在的返回-1），时间复杂度为logN。如[4，5，6，7，0，1，2]就是一个旋转数组：查找3，返回-1； 查找0，返回4；根据中位数与旋转点相对位置查找从中位数与旋转点的相对位置看，可以有：旋转点在中位数右侧：中位数及其左侧元素全部...

单例模式简介同步锁方式静态变量方式单例模式简介单例模式是一种常见的设计模式，它的核心结构为一个特殊的单例类。通过单例模式可以保证系统中一个类只有一个实例。常见的实现方式有：懒汉模式：不到万不得已是不会去实例化类，也就是说在第一次用到类实例的时候才会去实例化。 饿汉模式：在单例类定义的时候就进行实例化；无论是否用到，先实例化再说。一般情况下，单例模式都需要考虑线程安全，...

全组合递归法二进制位法指定位数组合字符串组合：包括全组合和指定位数组合。全组合求一个字符串可以产生的所有组合；如abc，它的组合有a、b、c、ab、ac、bc、abc。以下所有算法默认都无法处理字符串中有重复字符的情况，因此最终结果使用set存放，以自动去除重复的子串。递归法遍历字符串，每个字符可以取或者不取。defgetAllCombin...

交换法字典序法字符串全排列：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a，b，c所能排列出来的所有字符串abc，acb，bac，bca，cab和cba。交换法把字符串分成两部分：第一个字符，和剩余的字符串。因此求字符串的排列，就可以：可以出现在第一个字符位置的字符：把第一个字符和字符串中剩余的所有字符交换； 固定第一个字符，递归求剩余字符...

如何从一个字符串中查找最长的不重复子串呢？可以有多种实现方式，以下是几种方式的python实现。队列方式依次把字符串中每个字符放到队列中，当遇到重复时，把重复字符及其前面的字符全部从队列中移除。defLongestSubStringQueue(strFull):subLen=0subStr=[]forsinstrFull:...

查找过半数字基于Partition函数计数方式查找过半数字数组中有某个数字出现的次数超过数组长度的一半，请找出这个数字。最简单直接的方式是排序数组，然后中位数处的数字即为所要查找的数字，但是排序本身时间复杂度太高。后面介绍一下其他更快的查找方式（设所有数字都非负，若未找到则返回-1）。基于Partition函数在快速排序算法中，需要先选择一个数字对数组进行分割（大的放...

查找重复数字辅助数组方式交换位置方式二分查找方式查找重复数字在长度为N的数组里存储0~N-1间的数字，其中有些数字是重复的，但不知哪些数字重复和重复次数，如何找到任意一个重复的数字。最简单的方式，可以依次遍历每个数字，然后查看后面是否有与此数字相同的数字；或者排序后，查看是否有相同的数字（相邻的数字相同）。但这些方式时间复杂度太高，后面给出一些其他实现方式，以下实现并...

迷宫问题与图遍历算法简介辅助结构辅助函数深度优先搜索广度优先搜索两种搜索与最短路径算法简介我们常遇到的走迷宫问题，其实就是利用图的遍历（Traversing Graph）来求解图的连通性，常见的两种遍历方法：深度优先搜索（Depth-First Search）：类似于树的先根遍历；从某点出发，遍历‘未被访问的’临节点，然后重复此过程（找到一个未访问的临节点...