Open ChenJiaH opened 4 years ago
首发于微信公众号《前端成长记》,写于 2020.05.07
本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:
题目地址
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
这道题感觉就是构造函数,仅此而已,给函数的原型加一些方法。差异就在方法实现本身上,这个就写一个个人的思路吧,内部维护每次操作后的最小值数组。当然用差值数组和最小值也是可以的。
Ⅰ.内部维护最小值数组
代码:
/** * initialize your data structure here. */ var MinStack = function() { // 栈内数据用数组存储 this.stacks = [] this.mins = [] }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function(x) { this.stacks.push(x) // 比当前最小值小的数都需要存住 if (!this.mins.length || this.mins[this.mins.length - 1] >= x) { this.mins.push(x) } }; /** * @return {void} */ MinStack.prototype.pop = function() { // 如果推出的是最小值,那最小值数组也同步更新即可 if (this.stacks.pop() === this.mins[this.mins.length - 1]) { this.mins.pop() } }; /** * @return {number} */ MinStack.prototype.top = function() { return this.stacks.length ? this.stacks[this.stacks.length - 1] : undefined }; /** * @return {number} */ MinStack.prototype.getMin = function() { return this.mins[this.mins.length - 1] };
结果:
O(1)
Ⅱ.差值数组和最小值
/** * initialize your data structure here. */ var MinStack = function() { // 栈内数据用数组存储 this.stacks = [] this.min = Infinity }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function(x) { if (!this.stacks.length) { this.min = x // x - this.min = 0 this.stacks.push(0) } else { // 先存差值再更新最小值 this.stacks.push(x - this.min) if (x < this.min) this.min = x } }; /** * @return {void} */ MinStack.prototype.pop = function() { // 当前值比最小值小,则需要 let val = this.stacks.pop() if (val < 0) { this.min -= val } }; /** * @return {number} */ MinStack.prototype.top = function() { if (this.stacks[this.stacks.length - 1] < 0) { // 当前最小值就是推出项的值 return this.min } else { return this.stacks[this.stacks.length - 1] + this.min } }; /** * @return {number} */ MinStack.prototype.getMin = function() { return this.min };
这里看到有用栈的,JS 里面我就不构建了。另外还看见一种把值和最小值混合存储的思路,挺有意思的。
Ⅰ.混合存储
/** * initialize your data structure here. */ var MinStack = function() { // 栈内数据用数组存储 this.stacks = [] this.min = Infinity }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function(x) { // 先推上一步的最小值,再推原数据 if (x <= this.min) { this.stacks.push(this.min) this.min = x } this.stacks.push(x) }; /** * @return {void} */ MinStack.prototype.pop = function() { // 如果推出值等于当前最小值,则将最小值更新为上一个最小值 if (this.stacks.pop() === this.min) { this.min = this.stacks.pop() } }; /** * @return {number} */ MinStack.prototype.top = function() { return this.stacks[this.stacks.length - 1] }; /** * @return {number} */ MinStack.prototype.getMin = function() { return this.min };
我个人是不推荐混合存储的,因为如果需要拓展查最大值,那整体逻辑实际上都需要调整。而前面两种方法,都只需要增加最大值数组或者最大值即可。
编写一个程序,找到两个单链表相交的起始节点。
如下面的两个链表:
在节点 c1 开始相交。
注意:
null
O(n)
这道题如果不加限制的话,方法还是很多的,比如说打标识,或者哈表表都可以解决问题。如果要满足内存要求的话,必然就不能使用哈希表。要满足保持原有结构,那就不能用打标识的方法了。这里有个取巧的方案,因为不存在循环,两者相加的总长度相等,所以如果存在交点,那结尾必然相等。
Ⅰ.打标识
/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { // 因为是内存引用指向,取巧了 while(headA) { headA.FLAG = true headA = headA.next } while(headB) { if (headB.FLAG) return headB headB = headB.next } return null };
O(m + n)
Ⅱ.哈希表法
/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let hash = new Set() while(headA) { hash.add(headA) headA = headA.next } while(headB) { if (hash.has(headB)) return headB headB = headB.next } return null };
Ⅲ.双指针法
/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { // 用两个指针同时右移,A完了之后指向B继续右移 let pA = headA let pB = headB while(pA !== pB) { pA = pA ? pA.next : headB pB = pB ? pB.next : headA } return pA };
这里一般的二重循环就不说了,跟两个数组中找同样的数一样,没有什么区别,效率也比较底下。另外看见一个有意思的思路是,把两个链表拼成环,转化成找环节点的问题。
Ⅰ.转换环
/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { if (headA == null || headB == null) return null; let curA = headA,curB = headB; while(curA.next != null){ curA = curA.next; } curA.next = headA; let fast = headB,slow = headB; while(fast != null&&fast.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ slow = headB; while(slow != fast){ slow = slow.next; fast = fast.next; } curA.next = null; return fast; } } curA.next = null; return null; };
这里要满足空间复杂度要求,那就不能用哈希表法;要满足不改变原始数据结构,那就不能用标识法。所以这种情况下我更建议使用双指针法来直接作答,而转换为环虽然是一个思路,但是其实由一个问题转换为另一个问题,心智负担没有降低。
给定一个已按照 升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
示例:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
这道题有几个地方做了说明了,需要注意一下:有序的升序数组、下标不从零开始、不能重复使用相同元素。之前第一期的两数之和的方法就不做分析了(两次遍历和哈希表),这里可以利用有序数组来提高效率,利用首尾指针,来做判断,可以理解为夹逼原则。
Ⅰ.双指针夹逼
/** * @param {number[]} numbers * @param {number} target * @return {number[]} */ var twoSum = function(numbers, target) { let start = 0 let end = numbers.length - 1 while(start < end) { const sum = numbers[start] + numbers[end] if (sum === target) { // 不从零开始,所以需要加一 return [start + 1, end + 1] } else if (sum > target) { end-- } else { start++ } } // 由于有唯一输出,所以必然有结果,也不需要做特殊处理 return [-1, -1] };
看了一下解法,没有效率更高的方式了。一些基本的解法在第一期的第一题可以查阅。另外有一个是以一个数为基准,二分查找,但是这样的话其实只是在两次循环基础上做了优化,甚至还不如哈希表效率高。所以,这里就没有看见其他有不同思路的解法了。
既然数组有序,我们就可以用夹逼原则来求解,在这道题我觉得是最合适,也是最高效的解法了。
给定一个正整数,返回它在 Excel 表中相对应的列名称。
例如,
1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ...
输入: 1 输出: "A" 输入: 28 输出: "AB" 输入: 701 输出: "ZY"
这道题其实很清晰,就是将10进制转成26进制的问题。直接用取余运算就行,唯一的难点在于如何转成26进制。
Ⅰ.取余
/** * @param {number} n * @return {string} */ var convertToTitle = function(n) { let str = '' while( n > 0) { // 因为A代表1,减一就能从0开始匹配进制转换 n-- str += String.fromCharCode(n % 26 + 'A'.charCodeAt()) n = Math.floor(n / 26) } return str.split('').reverse().join('') };
看了一下解法,思路没有什么区别,有一个有意思的就是强行转换成一行,这里也列一下。
Ⅰ.单行代码
/** * @param {number} n * @return {string} */ var convertToTitle = function(n, s = '') { return !n-- ? s : convertToTitle(~~(n / 26), String.fromCharCode('A'.charCodeAt() + n % 26) + s); };
这道题本质上就是一道进制转换的题目,没有什么太大的难度。
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
⌊ n/2 ⌋
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
输入: [3,2,3] 输出: 3 输入: [2,2,1,1,1,2,2] 输出: 2
这道题就是找出出现次数最多的元素,按照常规的思路的话有这么两种方式。
由于这里是找多数元素,有个前提是保证出现次数大于一半,这里也可以取巧,先排序,排序后中间那个数一定是多数元素。
Ⅰ.哈希法
/** * @param {number[]} nums * @return {number} */ var majorityElement = function(nums) { let hash = {} for(let i = 0; i < nums.length; i++) { if (hash[nums[i]] === undefined) { hash[nums[i]] = 1 } else { hash[nums[i]] += 1 // 大于等于一半就可以直接认定为众数了 if (hash[nums[i]] >= nums.length / 2) { return nums[i] } } } let count = 0 let val = null for(let key in hash) { if (hash[key] > count) { count = hash[key] val = key } } return val };
Ⅱ.分治法
/** * @param {number[]} nums * @return {number} */ var majorityElement = function(nums) { function countEle(arr, num, l, h) { let count = 0 for(let i = l; i <= h; i++) { if (arr[i] === num) { count += 1 } } return count } function getEle(arr, l, h) { debugger if (l === h) { // 就一个元素,直接返回 return arr[l] } // 取中位数,减法主要为了防止溢出 let mid = parseInt((h - l) / 2 + l) // 左边的众数 let left = getEle(arr, l, mid) // 右边的众数 let right = getEle(arr, mid + 1, h) // 如果左右两边数组为同一个众数,则直接返回 if (left === right) { return left } // 比较众数出现次数,注意:要用父数组取出现次数做比较 // 要不像这种将返回错误结果:[4,5,4,4,4,5] let leftCount = countEle(arr, left, l, h) let rightCount = countEle(arr, right, l, h) return leftCount > rightCount ? left : right } return getEle(nums, 0, nums.length - 1) };
O(nlog(n))
Ⅲ.排序法
/** * @param {number[]} nums * @return {number} */ var majorityElement = function(nums) { return nums.sort()[nums.length >>> 1] };
发现了一种叫做 Boyer Moore 投票算法。这个算法通俗点解释起来还是很容易理解的,其实可以理解为互相抵消。每一个众数和一个其他数抵消,剩下的必然就是众数了。
Ⅰ.投票算法
/** * @param {number[]} nums * @return {number} */ /** * @param {number[]} nums * @return {number} */ var majorityElement = function(nums) { let count = 0 let candidate = null for(let i = 0; i < nums.length; i++) { if (count === 0) { candidate = nums[i] } // 同样的数累加,不同的数相减,可以理解为同数量抵消,抵消完产生新的备选数 count += (nums[i] === candidate) ? 1 : -1 } return candidate };
比较显而易见的是,这道题使用投票算法只需遍历一次,也不需要额外的空间,为最优解。
(完)
本文为原创文章,可能会更新知识点及修正错误,因此转载请保留原出处,方便溯源,避免陈旧错误知识的误导,同时有更好的阅读体验 如果能给您带去些许帮助,欢迎 ⭐️star 或 ✏️ fork (转载请注明出处:https://chenjiahao.xyz)
背景
本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:
目录
Easy
155.最小栈
题目地址
题目描述
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
示例:
题目分析设想
这道题感觉就是构造函数,仅此而已,给函数的原型加一些方法。差异就在方法实现本身上,这个就写一个个人的思路吧,内部维护每次操作后的最小值数组。当然用差值数组和最小值也是可以的。
编写代码验证
Ⅰ.内部维护最小值数组
代码:
结果:
O(1)
Ⅱ.差值数组和最小值
代码:
结果:
O(1)
查阅他人解法
这里看到有用栈的,JS 里面我就不构建了。另外还看见一种把值和最小值混合存储的思路,挺有意思的。
Ⅰ.混合存储
代码:
结果:
O(1)
思考总结
我个人是不推荐混合存储的,因为如果需要拓展查最大值,那整体逻辑实际上都需要调整。而前面两种方法,都只需要增加最大值数组或者最大值即可。
160.相交链表
题目地址
题目描述
编写一个程序,找到两个单链表相交的起始节点。
如下面的两个链表:
在节点 c1 开始相交。
注意:
null
.O(n)
时间复杂度,且仅用O(1)
内存。题目分析设想
这道题如果不加限制的话,方法还是很多的,比如说打标识,或者哈表表都可以解决问题。如果要满足内存要求的话,必然就不能使用哈希表。要满足保持原有结构,那就不能用打标识的方法了。这里有个取巧的方案,因为不存在循环,两者相加的总长度相等,所以如果存在交点,那结尾必然相等。
编写代码验证
Ⅰ.打标识
代码:
结果:
O(m + n)
Ⅱ.哈希表法
代码:
结果:
O(m + n)
Ⅲ.双指针法
代码:
结果:
O(m + n)
查阅他人解法
这里一般的二重循环就不说了,跟两个数组中找同样的数一样,没有什么区别,效率也比较底下。另外看见一个有意思的思路是,把两个链表拼成环,转化成找环节点的问题。
Ⅰ.转换环
代码:
结果:
O(m + n)
思考总结
这里要满足空间复杂度要求,那就不能用哈希表法;要满足不改变原始数据结构,那就不能用标识法。所以这种情况下我更建议使用双指针法来直接作答,而转换为环虽然是一个思路,但是其实由一个问题转换为另一个问题,心智负担没有降低。
167.两数之和II输入有序数组
题目地址
题目描述
给定一个已按照 升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
示例:
题目分析设想
这道题有几个地方做了说明了,需要注意一下:有序的升序数组、下标不从零开始、不能重复使用相同元素。之前第一期的两数之和的方法就不做分析了(两次遍历和哈希表),这里可以利用有序数组来提高效率,利用首尾指针,来做判断,可以理解为夹逼原则。
编写代码验证
Ⅰ.双指针夹逼
代码:
结果:
O(n)
查阅他人解法
看了一下解法,没有效率更高的方式了。一些基本的解法在第一期的第一题可以查阅。另外有一个是以一个数为基准,二分查找,但是这样的话其实只是在两次循环基础上做了优化,甚至还不如哈希表效率高。所以,这里就没有看见其他有不同思路的解法了。
思考总结
既然数组有序,我们就可以用夹逼原则来求解,在这道题我觉得是最合适,也是最高效的解法了。
168.Excel表列名称
题目地址
题目描述
给定一个正整数,返回它在 Excel 表中相对应的列名称。
例如,
示例:
题目分析设想
这道题其实很清晰,就是将10进制转成26进制的问题。直接用取余运算就行,唯一的难点在于如何转成26进制。
编写代码验证
Ⅰ.取余
代码:
结果:
O(n)
查阅他人解法
看了一下解法,思路没有什么区别,有一个有意思的就是强行转换成一行,这里也列一下。
Ⅰ.单行代码
代码:
结果:
O(n)
思考总结
这道题本质上就是一道进制转换的题目,没有什么太大的难度。
169.求众数
题目地址
题目描述
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于
⌊ n/2 ⌋
的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例:
题目分析设想
这道题就是找出出现次数最多的元素,按照常规的思路的话有这么两种方式。
由于这里是找多数元素,有个前提是保证出现次数大于一半,这里也可以取巧,先排序,排序后中间那个数一定是多数元素。
编写代码验证
Ⅰ.哈希法
代码:
结果:
O(n)
Ⅱ.分治法
代码:
结果:
O(nlog(n))
Ⅲ.排序法
代码:
结果:
O(nlog(n))
,完全是数组排序的复杂度查阅他人解法
发现了一种叫做 Boyer Moore 投票算法。这个算法通俗点解释起来还是很容易理解的,其实可以理解为互相抵消。每一个众数和一个其他数抵消,剩下的必然就是众数了。
Ⅰ.投票算法
代码:
结果:
O(n)
思考总结
比较显而易见的是,这道题使用投票算法只需遍历一次,也不需要额外的空间,为最优解。
(完)