用户故事 | 刷算法面试题的 4 种思考方式

栏目: 编程工具 · 发布时间: 5年前

内容简介:不管是为了求职面试,还是为了提高自己的算法基础能力,“刷算法题”都是每个程序员的必经之路。如何对待刷题?如何让刷题变得更高效?我们搜集了来自《算法面试通关 40 讲》的用户分享,他们也许可以给你一点启发。刚看老师的课程没多久, 收获不多, 我就把自己的第一道练习题解题心得发出来吧。这个是老师讲的第一道 leetcode 算法题: 两数之和给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能

不管是为了求职面试,还是为了提高自己的算法基础能力,“刷算法题”都是每个 程序员 的必经之路。如何对待刷题?如何让刷题变得更高效?我们搜集了来自《算法面试通关 40 讲》的用户分享,他们也许可以给你一点启发。

@jason :最优解永远在探索中

刚看老师的课程没多久, 收获不多, 我就把自己的第一道练习题解题心得发出来吧。这个是老师讲的第一道 leetcode 算法题: 两数之和

题目:

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

解答如下:

完成这道题,第一次花了半个小时,时间还是蛮长的,毕竟是自己完成的第一道 leetcode 算法题。不过之前确实算法练习得很少,解法很简单,用的是穷举法,连续两次遍历,时间复杂度为 O(n²)。

复制代码

int[] twoSum(int[] nums, int target) {
if(nums.length<2) {
returnnew int[0];
}
for(inti=0;i< nums.length;i++) {
for(intj=i+1;j< nums.length;j++) {
if(nums[i] + nums[j] == target) {
returnnew int[]{i,j};
}
}
}
returnnew int[0];
}

后来看了一下评论里其他同僚的解法,发现有很多很优化的解法。于是我把代码优化了一下,变成了下面这样:

复制代码

int[] twoSum2(int[] nums,inttarget) {

Map<Integer, Integer>map=newHashMap<Integer, Integer>(SIZE);// 默认给 hashmap 初始化大小, 能够减少内部动态扩展空间, 复制速度造成的时间开销

// 将数组存入 hashmap

for(inti =0; i < nums.length; i++) {

// 值为 key, 索引为 value

map.put(nums[i], i);

}

// 遍历数组里的每一个元素

for(inti =0; i < nums.length; i++) {

// 计算需要从 hashmap 里面找出的元素

intcomplement = target - nums[i];

// 判断 hashmap 里面是否存在该元素, 并且该元素不能与当前 nums[i] 是同一个元素

if(map.containsKey(complement) &↦.get(complement) != i) {

returnnewint[]{i,map.get(complement)};

}

}

returnnewint[0];

}

将传入的数组转换成 hashmap, 利用 hashmap 查询速度快的优势 O(1),将整体查询时间降到 O(n),hashmap 通过以空间换取速度的方式,将查询速度提高到了 O(n),这里用到了分别两次的循环,虽然时间复杂度变成了 O(n),但实际上是两倍的 O(n)。

之后又思考了一下,发现一次循环也能解决问题,时间复杂度可以再次减半,变成真正的 O(n),于是便有了下面的代码。

复制代码

int[] twoSum3(int[] nums,inttarget) {
Map<Integer, Integer>map=newHashMap<Integer, Integer>(SIZE);// 默认给 hashmap 初始化大小, 能够减少内部动态扩展空间, 复制速度造成的时间开销
for(inti =0; i < nums.length; i++) {
intcomplement = target - nums[i];
if(map.containsKey(complement) &↦.get(complement) != i) {
returnnewint[]{i,map.get(complement)};
}
map.put(nums[i], i);
}
returnnewint[0];
}

之后我写了一个简单的测试案例来测试这 3 种算法的耗时,创建了一个长度为 10 万的数组,分别执行这 3 种算法,发现当数据量大的时候,第 2 种和第 3 种算法比第 1 种快了不是一个数量级。而且数据量越大,速度差异越明显:

复制代码

int[]nums =newint[100*1000];

for (inti =0; i < nums.length; i++) {
if(i==nums.length -1-1)
nums[i]=2;
elseif(i==nums.length -1)
nums[i]=7;
else
nums[i]=1;
}

long start =System.currentTimeMillis();
//int[] indexResult = twoSum(nums, 9); // 数组长度 100000 耗时 1578 ms
//int[] indexResult = twoSum2(nums, 9); // 数组长度 100000 耗时 20 ms
int[]indexResult = twoSum3(nums, 9);// 数组长度 100000 耗时 14 ms

longend=System.currentTimeMillis();
System.out.printf("%s, %s", nums[indexResult[0]], nums[indexResult[1]]);

System.out.printf("\r\n 时间花费: %d ms",end- start);

查看经典面试题: 两数之和

@ elbowrocket:用理论指导实践

之前做 leetcode 的题目一直没什么思路,我从课程中学到了如何运用所学理论去思考。

下面是今天刚看的题目:滑动窗口的最大值

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7]

解释:

滑动窗口的位置 最大值 [1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7

注意:你可以假设 k 总是有效的,1 ≤ k ≤ 输入数组的大小,且输入数组不为空。进阶:你能在线性时间复杂度内解决此题吗?

下面是通过学习后得到的思路:

思路:

1、根据优先队列的概念,我们假设一个大顶堆,那么一开始的 [1,3,-1],这样一排列成堆的样子就是 3 在最上面,-1 在左下角,1 在右下角… 下一步就是 [3,-1,-3] 了,1 就要被挤开了,挤开了也不影响什么,-3 再加进来就好了。总之我们需要做的是:

(1)、维护我们的 Heap,也就是删除离开窗口的元素,加入新的元素。这里时间复杂度是 logK

(2)、Max->Top,就是让结果是堆顶的元素。复杂度是 O(1),最后整体的复杂度是 NLogK。有没有更好的解法?

2、直接用队列,而且是双端队列,也就是两边都能进能出的队列。首先就是入队列,每次滑动窗口都把最大值左边小的数给杀死,也就是出队,后面再滑动窗口进行维护,这样相当于每一个数走过场,时间复杂度就是 O(N*1),比思路 1 要小。

代码如下:

复制代码

classSolution:
defmaxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
# 严谨判断输入的数字是否合法
ifnotnums:return[]
window, res = [], []
fori, xinenumerate(nums):
ifi>=kandwindow[0] <= i-k:# 窗口滑动时的规律
window.pop(0)
whilewindowandnums[window[-1]] <= x:# 把最大值左边的数小的就清除。
window.pop()
window.append(i)
ifi >= k-1:
res.append(nums[window[0]])
returnres

希望能学习到更多东西。

查看白板理论讲解: 滑动窗口的最大值

@梦想家罗西:学而时习之,不亦乐乎?

看老师的课程大概一周了,之前看数据结构和算法懵懵懂懂的,老师结合实例题,一下子清楚很多了,特别是动态规划哪一课,一下子茅塞顿开。

用户故事 | 刷算法面试题的 4 种思考方式 刷的一些算法题。

第一步:递归 + 暂存

复制代码

functionfib(n){
letmemo = [];
letr =null;
if(n <=1) {
r = n;
}elseif(memo[n]) {
r = memo[n];
}else{
memo[n] = fib(n -1) + fib(n -2);
}
returnr;
}

使用这种方法试了下 n=100 的时候直接挂了,效率依然很低。所以接下来第二步:

第二步:动态规划

复制代码

functionfib(n){
let f = [0,1];
for(leti=2;i<= n;i++) {
f[i] = f[i-2] + f[i-1];
}
returnf;
}

其实矩阵相乘效率更高,等我学会了再来更新代码,学会了简单得动态规划已经很开心了。

戳此查看: 让你茅塞顿开的动态规划

@Chenng:做题是一种享受,高效的思考模式受益终身

听完最后一课,突然有点不舍。本来学习算法的初衷是为了面试,现在发现做题本身就是一种享受。

课上学到很多收益终身的思考模式:

五种算法模式:

  • 递归

复制代码

functionrecursion(level, param1, param2) {
// 递归终止条件
if(level > MAX_LEVEL) {
// 打印结果
return;
}

// 处理当前层级的逻辑
processData(level,data);

// 递归
recursion(level +1, p1, p2);

// 如果需要,反向当前层级
reverseState(level);
}
  • 递归 DFS

复制代码

constvisited =newSet();
functiondfs(node, visited){
visited.add(node);

// 处理当前的 node

for(leti =0; i < node.children.length; i++) {
constchild = node.children[i];
if(!visited.has(child)) {
dfs(child, visited);
}
}
}
  • BFS

复制代码

const visited = new Set();
function bfs(grapg,start, end) {
const queue = [];
queue.push(start);
visited.add(start);

while (queue.length) {
node= queue.pop();
visited.add(node);
{1}
process(node);
nodes= generateRelatedNodes(node);
queue.push(nodes);
}
}
  • 二分查找

复制代码

functionbinarySearch(arr, x) {
letleft=0;
letright= arr.length -1;

while(left<=right) {
constmid= Math.floor((left+right) /2);

if(x === arr[mid]) {
returnmid;
}

if(x < arr[mid]) {
right=mid-1;
continue;
}

if(x > arr[mid]) {
left=mid+1;
continue;
}
}

return-1;
}
  • DP 方程

复制代码

// 状态定义
const dp = [[]];

// 初始状态
dp[0][0] = x;
dp[0][1] = y;

// DP 状态推导

for (let i = 0; i<=n;i++) {
for(letj=0;j<=matchMedia;j++) {
dp[i][j] =min(dp[i-1][j],dp[i][j-1]);
}
}
{1}
returndp[m][n]
{1}

四个切题步骤

  • Clarification:思考边界条件
  • Possible Solution:所有可能的解法、最优解
  • Coding
  • Test Cases

写在最后

课程的结束不是终点,而是起点,加油,开启自己成为真正工程师的道路。

查看课程回顾: 面试切题四件套

感谢上面四位同学的精彩留言,欢迎大家在文末分享你的刷题故事和经验,我们一起进步。

专栏简介

我是覃超,作为 Facebook 早期员工 & 多年面试官,我对各大知名企业算法面试的考察点和面试套路,有非常清晰的理解以及丰富的第一手经验。在《算法面试通关 40 讲》这门课程里,我会帮你建立一套完整的算法切题思路,通过“白板演练 + 代码讲解”的方式,手把手带你掌握高效解题套路,彻底理解题目背后的考点,锻炼算法思维,让你在面试和平时的工作中大显身手。

学完这门课,你将收获以下四个方面:

1、常见算法知识点理论讲解

2、高频面试题目思路剖析

3、LeetCode 高效解题四步法

4、有效提升算法面试通过率

课程已更新完毕,共 62 讲,目前已有超过 10000 人加入学习,课程广受好评,期待你的加入! 戳我立即订阅


以上所述就是小编给大家介绍的《用户故事 | 刷算法面试题的 4 种思考方式》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

UML参考手册

UML参考手册

兰博 / UML China / 机械工业出版社 / 2005-8 / 75.00元

《UML参考手册》在第1版的基础上进行了重大更新和扩展。UML的创建者James Rumbaugh、Ivar Jacobson和Grady Booch,清晰完整地讲述了UML的所有概念,包括对序列图、活动模型、状态机、组件、类和组件的内部结构以及特性描述的主要修订。手册式结构不仅有助于读者对UML的概念进行规范化的学习与理解,更为广大程序开发人员、系统用户和工程技术人员提供了方便快捷的查询方式。无......一起来看看 《UML参考手册》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换