准备跳槽了....
大家好,我是吴师兄。
不知不觉又到年底,不知道大家年初做的计划完成了多少,反正我是打算把【2021年度计划】改成【2022年度计划】。
而一到年底就意味着要过年,一过年就又来到了金三银四跳槽高峰期。
如果打算那个时候跳槽,那现在就需要准备,否则一晃荡 2022 年上半年都还在原地踏步。
关于面试准备,大部分时候都还是需要看八股文或者说背八股文的,并且要吃透才行,否则面试官一问细节问题就容易掉坑里,比如一些算法题。
今天来给大家分享两个算法解题中容易出错的细节点,这些都是算法训练营同学中实际出现的案例,很有参考意义。
1、快排漏了等号
首先给大家看二期算法训练营中的一个视频,是关于快速排序的。http://mpvideo.qpic.cn/0bc3taabyaaaraapknujzvqvbggddsmaahaa.f10002.mp4?dis_k=7e3407dd6315ba8da2986bc25cba9e86&dis_t=1637211684&vid=wxv_2127951233297465351&format_id=10002&support_redirect=0&mmversion=false
不吹牛,你认真看完这个视频,你后面都能默写出快速排序代码的经典写法。
如果你会写错,那很可能是这个细节问题造成的。
这是一个学员百思不得其解的问题,为啥少了等号就会超时呢?
很简单,这样会进入死循环。
这个问题用文字描述起来不方便,所以我特意做了一个动画在直播答疑的时候演示了一遍。
通过这个动画,可以看出,如果少了等号,那么在这块代码中:
// 只有当遇到小于 pivot 的元素时,right 才停止移动
// 此时,right 指向了一个小于 pivot 的元素,这个元素不在它该在的位置上
while( left < right && nums[right] > pivot ){
// 如果 right 指向的元素是大于 pivot 的,那么
// right 不断的向左移动
right--;
}
// 将此时的 nums[left] 赋值为 nums[right]
// 执行完这个操作,比 pivot 小的这个元素被移动到了左侧
nums[left] = nums[right];
一旦出现 right 指向的元素值等于了 pivot,那么就会把这个元素值赋值给 left 指向的元素。
那么接下来就来到下面这块代码:
// 只有当遇到大于 pivot left 才停止移动
// 此时,left 指向了一个大于 pivot 的元素,这个元素不在它该在的位置上
while( left < right && nums[left] < pivot){
// 如果 left 指向的元素是小于 pivot 的,那么
// left 不断的向右移动
left++;
}
// 将此时的 nums[right] 赋值为 nums[left]
// 执行完这个操作,比 pivot 大的这个元素被移动到了右侧
nums[right] = nums[left];
此时,left 指向的元素值也等于了 pivot,那么就会把这个元素值赋值给 right 指向的元素。
这样,就出现了反复横跳的场景,陷入了死循环。
2、或的顺序问题
这是在 LeetCode 第 34 号问题在排序数组中查找元素的第一个和最后一个位置出现的一个细节问题。
她的代码和课程上讲的代码 99% 的地方相同,唯独两行代码不一样,但问题就出在这两行代码。
正确的逻辑应该是这样的。
// 并且中间位置 mid 的右边没有元素,即中间位置 mid 为当前区间的结束位置
// 或者中间位置 mid 的后一个元素大于目标值 target
// 说明 mid 指向了 target 的结束位置
if(mid == nums.length - 1 || nums[mid + 1] > target){
// mid 指向了 target 的结束位置,返回这个结果
return mid;
}
但是她写成了这种样子。
// 并且中间位置 mid 的右边没有元素,即中间位置 mid 为当前区间的结束位置
// 或者中间位置 mid 的后一个元素大于目标值 target
// 说明 mid 指向了 target 的结束位置
if(nums[mid + 1] > target || mid == nums.length - 1 ){
// mid 指向了 target 的结束位置,返回这个结果
return mid;
}
导致出现了越界的错误提示。
如果 mid 的值是 nums 的长度减一。
那么在原先的代码中会先执行 mid == nums.length - 1
,而不会执行nums[mid + 1] > target
。
而一旦顺序发生颠倒,那么就会先执行nums[mid + 1] > target
,此时就出现了数组越界的情况。
这个问题很简单,但很多时候自己死活看不出来,但别人一点就透,所以特意用语音给她解释了一番。
总结
以上这两个细节问题或许在某些人眼里有些可笑:这么简单的地方都会出错??!
但这就是事实,很多算法题本身并不难,难的地方在于细节方面,这些细节如果没有人帮忙的话,会导致好几天都想不明白。
一旦被别人点破,那几分钟就能想明白,这或许就是需要结伴学习的一个目的吧:有问题可以讨论,可以提高学习的效率。
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十