问题全部来自《剑指Offer》,顺序一致。
单例模式
1.使用字面量声明对象
|
|
或者通过闭包封装自己的私有变量和方法
2.利用闭包
本质上和上面的方法类似
|
|
还有一个酷炫的变种,不过是上面的构造函数写法
3.借助构造函数和JS中函数也是对象的特点
|
|
找出数组中重复的数字
Set,使用ES6内建的数据结构。
Object或Array(空间复杂度O(n)),换汤不换药,略。
传统方法,时间复杂度O(n),空间复杂度O(1)。交换当前元素和当前索引对应的元素,直到两者相等。(请参考原书中的前提,数字都在0~n-1之间)
传统方法,且不修改数组,利用折半查找,递归寻找重复的元素。时间复杂度O(nlogn),空间复杂度O(1)。
二维数组中的查找
前提:数组的每一行和每一列都递增
贪婪算法,从右上角开始。
|
|
替换字符串中的空格
JavaScript中很好实现,可以直接使用库函数。
|
|
使用传统方法,思路是先从前到后找到空格数,扩展出足够空间。再使用两个指针,从后到前,P1指向旧字符串的末尾,P2指向新字符串的末尾。碰到空格时,P2插入”%20”。碰到其他字符时,挨个复制即可。
这种双指针从后向前的思维还可以用在两有序数组合并。从尾到头比较A1和A2数字。
链表设计
|
|
从尾到头打印链表
前提:单向链表。使用递归
|
|
重建二叉树
前提:根据前序和中序遍历的结果。
|
|
通过前序遍历找到根节点,结合中序遍历找到左右子树,之后递归构建左右子树。
|
|
二叉树的下一个节点
前提:树的每个节点除了有两个子节点的指针,还有一个指向父节点的指针。寻找中序遍历的下一个节点。
|
|
二叉树中的节点和周围节点可能有四种关系(画图出来更直观)
- 左子树的父节点
- 右子树的父节点
- 父节点的左子树
- 父节点的右子树
从而有下面的流程:
- 关系2存在时,返回右子树的最左节点,否则到步骤2
- 关系3存在时,返回父节点,否则到步骤3
- 关系4存在时,向上回溯,对父节点使用步骤2,否则到步骤4
- (节点是根节点)返回null
|
|
用两个栈实现队列
前提,实现append和delete功能,完成在队尾插入和队首删除。
|
|
思路,栈1只允许正序存放,栈2只允许倒序存放,由于栈2的内容始终较老,因此插入总发生在栈1。删除总发生在栈2(栈2为空时除外)。JS中没有泛型的概念,所以无需考虑栈中的数据类型。
|
|
用两个队列实现栈
前提同上。
|
|
思路和上面类似,但不大一样。每次元素出队时,所有元素一定会转移到另一个队列中。因此,插入和删除一定发生在有元素的队列。
|
|
斐波那契数列
使用递归的代码好写,但是效率低;使用循环更好。
|
|
变种还有“青蛙跳台阶”等类最优子问题的问题。
旋转数组的最小数字
前提,将数组开头的部分元素搬运到数组的末尾,寻找最小的元素。
使用二分查找,右半边递增时,最小元素在左半边。左半边递增时,最小元素在右半边。注意下面两种情况:
- 数组未做旋转
- 旋转后,头尾元素相等
|
|
回溯法
通常适合用递归法实现,到达某个节点时,尝试所有可能,并在满足条件时递归到下一节点。
矩阵中的路径
前提,判断矩阵中有无一条不交叉路径能够返回指定字符串
|
|
机器人的运动范围
前提,m行n列的矩阵,机器人从(0,0)出发不能进入数位和大于k的格子,求能到的格子个数。
思路同上甚至更简单。
|
|
剪绳子
前提,绳长为整数,切成若干段,使得绳长乘积最大。
类似于《算法导论》里的裁切钢管。首先可以用动态规划。
|
|
经过数学推导,n>=5
时,2(n-2)>n
且3(n-3)>n
且2(n-2)>=3(n-3)
,因此有最优子问题的解法。根据贪婪算法,应该尽量多切长度为3的绳子段。
|
|
位运算
经常用于奇技淫巧。在C风格的解法中常用。JS中应该不常出现。
二进制中1的数目
通过移位操作,需要注意的是,对入参移位容易出现死循环,可以对1进行移位并比较。
二进制整数减1相当于右侧0值变成1,最右侧1变成0,此时和原数做按位与,可以消掉最右侧0。利用这个特点可以进一步提高效率。这种思路可以用来解决很多二进制问题。
|
|
数值的整数次方
前提,不得使用库函数,需要考虑大数问题
用类似二分法的思想,由2到4,由4到8,由8到16。时间复杂度O(logn)。同时注意边界情况。
|
|
按顺序打印从0到最大的n位数字
大数问题。自定义数据结构实现整数+1操作,或者通过递归for循环依次打印每一位数字,像下面这样。
删除链表节点
|
|
O(1)时间删除单向链表中某节点
通常思路,需要从头结点循环找到节点的上一个节点,将它的next
属性设置删除节点的next
。但是这么做是O(n)的复杂度。更好的方法是,借尸还魂,覆盖当前节点的next
节点,然后重设next
节点跳过下一节点。
(因为JS中没有指针一说,这种模拟不能完全还原原题的问题)
|
|
表示数值的字符串
考察思维的全面性。包括正数负数、小数、科学技术法都要考虑。格式遵循[+|-]?(\d+)(\.\d+)?([e|E][+|-]?\d+)?
|
|
JS下解决问题并不如C++自然。下面是C++风格的解法
调整整数数组中奇数和偶数的位置
前提,使得奇数都位于前边,偶数都位于后边。
考虑拓展性,用一个函数作为衡量指标,判断元素应该在前还是在后。
|
|
鲁棒性
链表的倒数第K的节点
|
|
考虑鲁棒性:
- 空数组
- k超过数组长度
- k=0
|
|
链表中环的入口节点
思路:
- 链表中有环存在时,走得快的指针将会追上走得慢的指针。
- 确定环的长度k后,让两个指针同速,一个领先k位出发,相遇的位置即是入口
考虑鲁棒性:
- 无环时
- 寻找相遇点的时候注意next属性是否存在
- 头结点为环入口时
|
|
反转链表
前提:反转链表并输出反转后的头节点。
考虑鲁棒性:
- 边界情况,如空链表或长度为1的链表
- 反转过程中链表断裂
|
|
合并两个排序的链表
类似归并排序。
考虑鲁棒性:
- 空链表
- 链表长度为1
|
|
树的子结构
前提:判断树A中是否能找到和树B结构一样的子树。
使用递归思路更简单。
|
|
形象化
二叉树的镜像
|
|
对称的二叉树
即前序和对称遍历结果一致。和上面类似。
|
|
顺时针打印矩阵
- 打印一行“删去”一行,打印一列“删去”一列。
- 最后一圈先向右再向下再向上再向左,根据顺序共有4种可能,通过if语句区分
|
|
剑指offer上的思路是利用每圈的起始x和y坐标相等,判断循环终止条件,再根据条件决定一圈打印几行。
|
|
包含min函数的栈
前提,设计栈的数据结构,使min、push和pop的时间复杂度都是O(1)。
注意:若使用变量保存最小元素,那么在最小元素出栈后会找不到次小元素。可见只使用一个变量是不够的,为配合原始栈的结构,需要有一个辅助栈记录最小元素的位置。(画图可以很容易理解)
|
|
栈的压入、弹出序列
前提:给定栈的压入顺序,判断某个出栈顺序是否可能
通过举例具象化思考。如入栈顺序为[1, 2, 3, 4, 5],[4, 3, 5, 2, 1]就是一个可能的例子。首先,4是第一个出栈元素,则[1,2,3]此时已经入栈,4出栈后,3位栈顶,出栈后,5不在栈内,将5入栈。剩下的5,2,1同理。因此,可以发现下面规律。
- 第一个出栈元素前的入栈序列此时正在栈内
- 之后所有的出栈元素,先在栈顶寻找,若有,则出栈;若没有,在栈外元素中寻找
- 若找到,将其入栈,若找不到,则返回false
- 如此循环直到栈空
|
|
从上到下打印二叉树
使用队列保证先后顺序。
|
|
进阶:分行从上到下打印二叉树
和上面类似,区别在入队时需要携带层数信息。
|
|
进阶2:之字形打印二叉树
前提:第一行从左到右打印,第二行从右到左打印,以此类推。
因为每层的顺序都相反,很适合栈存储。
|
|
二叉搜索树的后序遍历序列
前提:判断整数序列是否是某个二叉搜索树的后序遍历序列,并假设所有数字都不相同
利用二叉搜索树的特点,结合后序遍历时尾元素为根节点,递归判断。
|
|
二叉树中和为某值的路径
前提:找到所有满足要求的路径
|
|
分解
复杂链表的复制
前提:复杂链表中每个节点除了一个指向下个节点的指针外,还有一个指向任意节点的指针
困难在extra属性的复制,在O(n)的时间复杂度,O(1)的空间复杂度的要求下,问题可以分解成3步
- 在每个原始节点后接上复制节点
- 原样复制extra属性
- 将复制的链表拆出来
|
|
二叉搜索树和双向链表
前提:将一个二叉搜索树转换成一个排序的双向链表,不允许新建节点。
一般涉及到树结构的问题,使用递归都要更直观方便。本题中,可以把问题拆解成,将根节点和已组装好的左右双向链表组装。
|
|
序列化二叉树
要求:实习序列化和反序列化函数
通常情况需要两种遍历序列才能还原二叉树,这是因为二叉树非完全。对空缺的节点使用特殊字符,即可消除二义性,使用单一遍历序列还原二叉树。
|
|
字符串的排列
前提:不考虑重复字符的问题
要求:输入一个字符串,输出字符串中字符的所有排列
此题可以用递归,《剑指offer》上的解法简单易行。JS中对字符串的限制(只读)使得代码和C风格有别。这里我们考虑输入是一个字符数组。
|
|
求字符串的组合(也可以叫求子集)
总共的解数目为$2^n$。从最低位开始,向上寻找时,有两种可能:新字符不出现,新字符出现。
|
|
输入8个数字的数组放在正方体的8个顶点,有无可能每对面对应的4个顶点和相等
相等于寻找全排列,使得a1+a2+a3+a4=a5+a6+a7+a8,且a1+a3+a5+a7=a2+a4+a6+a8,且a1+a2+a5+a6=a3+a4+a7+a8。
|
|
8皇后问题
8皇后的限制条件在,不得同行同列,不得位于同一对角线。因此,为长度为8的数组初始化填入1~8,代表行数。填入的数代表列数,因为每行每列都只有一个皇后。所以全排列中,只需要删除满足下面条件的排列即可:
i-j != columns[i] - columns[j]
且j-i != columns[i] - columns[j]
,即不在一个对角线上
|
|
这种思路会带来重复的解,按照Matrix67的思路,可以通过位运算求解。使用row(列占用情况),ld(左下右上对角线占用),rd(右下左上对角线占用)三个变量存储当前列的禁用情况。使用“1”表示禁用,“0”表示可用。解决n皇后的问题代码仅在10行左右。详细解释见链接。
|
|
时间效率
数组中出现次数超过一半的数字
思路1:超过一半的数组一定出现在中位数的位置,结合快排的思想,找到中位数
思路2:遍历所有数字,遇到与major相同的元素时,计数器+1,反之-1。计数器为0时,更换major。返回最后的major
注意:最后需要检查数组是否有满足条件的元素
|
|
最小的k个数
同样的两种思路:
利用快排的中的partition,找到前k个数,时间复杂度O(n),但是会修改数组
1234567891011121314151617181920212223242526272829303132333435363738394041424344function partition(arr, start, end) {if (start >= end) {return;}let index = start -1;let split = arr[end];for (let i = start; i < end; i++) {if (arr[i] < split) {index++;if (i != index) {[arr[i], arr[index]] = [arr[index], arr[i]];}}}index++;arr[end] = arr[index];arr[index] = split;return index;}function minKNums(nums, k) {if (!nums || k <= 0) {return;}if (k >= nums.length) {return nums;}let start = 0,end = nums.length - 1,index = partition(nums, start, end);while(index != k-1) {if (index > k-1) {end = index - 1;} else {start = index + 1;}index = partition(nums, start, end);}console.log(nums.slice(0, k));}维护一个排序的长度为k的数据容器,当容器满时,根据容器最大值更新容器,时间复杂度O(nlogk),空间复杂度O(k),但是在k较小时,性能很接近
|
|
数据流的中位数
使用二叉树、最大堆最小堆完成。保证最大堆和最小堆的数目差不超过1即可。当然,首先要实现最大和最小堆
|
|
连续子数组的最大和
前提:数组由正负数组成。
经典的动态规划问题。用双指针的方法,采用贪婪算法,用f[i]
表示以第i位结尾的最大和,当f[i-1]<=0
时,可以抛弃之前的和,以当前元素为f[i]
。
|
|
1~n整数中1出现的次数
这种数学题,多半会有找规律的简单方法。普通的方法是,逐个寻找每个数字中1出现的次数,时间复杂度O(nlogn)。逐位寻找1出现的次数,再累加,时间复杂度可以降至O(logn)。
|
|
数字序列中某一位的数字
前提:数字以0123456789101112131415...
的格式序列化
需要找到规律。1位数占用10位,2位数占用180位,3位数占用2700位,……,n位数占用9 * (10 ^ n)位。通过循环确定位数后,对n取余,能知道是n位数第几个数的第几位。
|
|
把数组排成最小的数
要求:拼接数组中的数,使之最小
此题的思路在拓展排序的规则。当组合mn < nm
时,说明m应该在前,即元素间的比较准则是mn和nm的大小关系。注意大数问题,应该比较字符串。
|
|
把数字翻译成字符串
前提:0翻译成‘a’,1翻译成‘b’,逐位进行翻译,有时会有多种结果
要求:求可能的结果数目
动态规划,避免重复解决子问题。
|
|
礼物的最大价值
前提:从mn的格子中拿礼物,从左上角开始,每次向下或向右取一格,直到右下角
*要求:礼物价值总和最大
和上面的思路很类似,通过循环替代递归。比带有备忘录的递归更省时间和空间。坐标是(i, j)的格子最大总和只取决于(i-1, j)和(i, j-1)。因此可以用一维数组代替二维数组,减少空间使用。
|
|
最长的不包括重复字符的子字符串
要求:返回字符串的长度
用类似动态规划的思路,借助之前的结果递推。同时,使用Object存储对应字符上次出现的位置,可以保证O(n)的时间复杂度。
|
|
丑数
前提:丑数是指只包含因子2、3、5的数。求给定位置的丑数
普通的思路是通过循环依次判断数字是否为丑数直到找到。在允许空间消耗时,我们用数组去存储所有的丑数,并不断更新数组。
|
|
第一个只出现一次的字符
哈希表,JavaScript中使用Object即可。第一次扫描时去除所有重复元素,第二次扫描时,打印第一个字符。
|
|
类似问题都可以用哈希表解决。
数组中的逆序对
逆序对的存在是数组未排序的结果。因此使用排序算法得到交换元素的次数即可。最直观的使用冒泡排序,时间复杂度为O(n^2)。使用归并和快排可以达到O(nlogn)的时间复杂度。
略。
两个链表的第一个公共节点
因为链表从交汇节点后拥有相同的节点,所以,从后向前回溯,直到节点不同为止即可。时间复杂度O(m+n),空间复杂度O(m+n)。若不使用辅助栈,空间复杂度还可降至O(1)。
|
|
排序数组中查找数字(二分查找)
排序数组中数字出现的次数
思路是,查找到数字第一次出现的地方和最后一次出现的地方。通过二分法查找,数字较小时,在右半边;较大时,在左半边;相等时判断左/右是否还有该元素。
|
|
寻找从0~n-1中缺少的数字
数组事先排序时,借助二分法查找,时间复杂度O(logn);未排序时,通过求和和n(n-1)/2
求差得出(不考虑大数问题的话)。中间元素和下标相等时,在右半边寻找;不相等时,若左侧元素相等,则返回该元素,左侧元素不等时,在左半边寻找。
|
|
数组中和下标相等的元素
前提:数组元素都为整数,且单调递增。
|
|
二叉搜索树的第k大的节点(遍历)
利用二叉搜索树的中序遍历的特点,找到第k大的节点。
|
|
二叉树的深度
使用递归,比较左右子树的深度,取较大值。
|
|
判断一棵树是否是平衡二叉树
可以使用上面的思路,递归判断除叶节点外每个节点的左右子树深度。但是这样会重复遍历节点。但是如果使用后序遍历,就可以先遍历左右子树,再回到根节点。
|
|
数组中数字出现的次数(位运算)
在数组中找到唯二两个只出现一次的元素
前提:数组中其他元素都出现两次。
还是使用异或,不过这次异或的结果是两个数组的异或结果。找到结果中第一位1,说明这一位两个数不同,据此将数组分成两部分,分别异或,得到最终结果。时间复杂度O(n),空间复杂度O(1)。
|
|
在数组中找到唯一一个出现一次的数字
前提:其余数字都出现3次。
使用和上面类似的思路,使用二进制表示每一个数,用数组存储各位1出现的和,累加后,将每一位数字对3取余,得到的数字就是结果的二进制表示。
略
和为s的若干数字(双指针)
2个数
前提:数组是单调递增的。因此可以在头尾放两个指针,向中间靠拢,逼近最终结果。
|
|
正数序列
前提:打印出和为s的连续正数序列,长度最少为1。
若使用双指针,需要先确定上下界。这里的序列起始的上界为n/2
,下界是1。然后使用类似的方法,确定起始后,后移后界求序列。时间复杂度O(n^2)。然而,实际上,确定下界后,连续正数序列和与序列长度满足函数关系f(m, n) = (m + n)(n - m + 1) / 2
(其中m为起始值,n为截止值)。问题变成了检验后界是否满足一元二次方程组。
|
|
翻转字符串(多次翻转)
翻转单词的顺序
要求:翻转一句话中所有单词的顺序。
此题可以先翻转所有字符,再翻转每个单词内的字符顺序。
|
|
左旋转字符串
要求:将字符串头部的若干字符转移到字符尾部。
使用类似上面的思路,可以不用substring
方法,用翻转也可实现,不过在JS中无法对字符串自由写入,法2反而不如法1。
|
|
队列的最大值(队列)
滑动窗口的最大值
前提:固定滑动窗口的宽度
要求:返回窗口内的最大值组成的数组
使用双端队列去维护滑动窗口内的最大值。
|
|
队列的最大值
要求:设计队列,使max,shift和push的时间复杂度为1。
因为在push和shift操作时,队列就像上面的滑动窗口,可以用相同方法实现max。
略。
建模能力
n个骰子的点数(化递归为循环)
要求:输入n,返回n个骰子朝上一面的点数之和的概率分布。
使用循环的角度考虑,骰子递增时,点数和为k的可能性为k-6,k-5,k-4,……,k-1的可能性之和。因此我们可以得到下面的结果。
|
|
扑克牌中的顺子
前提:从扑克牌中随机取5张,大小王可以当做任意数字,判断是否为顺子
这里我们假设传入的数组已经按照扑克牌中的大小对牌进行了排序。整体分3步,首先向数组的指定项插入数字,然后判断0的数目,最后看0的数目是否能填满undefined
的个数。
|
|
约瑟夫问题
字面意义的解法就不说了。根据《剑指offer》上的递推公式,可以得到f(n,m)=[f(n-1,m)+m]%n
。因此,可以用循环实现。
|
|
股票的最大利润
也即起始、末尾数对最大差值区间。当遍历到f[i]
时,寻找之前的最小值,即可得到利润,遍历整个数组即可得到最大利润,时间复杂度为O(n)。
|
|
不使用控制结构语句求解1+2+3+…+n
使用递归等等价形式即可。
|
|
不用加减乘除做加法
使用异或可以得到没有进位的结果。可以通过位与运算得到都是1的位。和异或结果异或,直到位与结果都为0为止。
|
|
构建乘积数组
要求:给定数组A,构建数组B,其中每个元素是A中缺少对应位元素的总乘积。不能使用除法。
使用两个辅助数组分别存储数组从前到后和从后到前两段元素的乘积。空间复杂度O(n)的情况下,可以在O(n)时间上得到结果。
|
|