不管是为了求职面试, 还是为了提高自己的算法基础能力,"刷算法题" 都是每个程序员的必经之路. 如何对待刷题? 如何让刷题变得更高效? 我们搜集了来自《算法面试通关 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);
查看经典面试题: 两数之和 https://time.geekbang.org/course/detail/130-42703
@ 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[]
- Windows, res = [], []
- fori, xinenumerate(nums):
- ifi>=kandwindow[0] <= i-k:# 窗口滑动时的规律
- Windows.pop(0)
- whilewindowandnums[Windows[-1]] <= x:# 把最大值左边的数小的就清除.
- Windows.pop()
- Windows.append(i)
- ifi>= k-1:
- res.append(nums[Windows[0]])
- returnres
希望能学习到更多东西.
查看白板理论讲解: 滑动窗口的最大值 https://time.geekbang.org/course/detail/130-41561
@梦想家罗西: 学而时习之, 不亦乐乎?
看老师的课程大概一周了, 之前看数据结构和算法懵懵懂懂的, 老师结合实例题, 一下子清楚很多了, 特别是动态规划哪一课, 一下子茅塞顿开.
刷的一些算法题.
第一步: 递归 + 暂存
- 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;
- }
其实矩阵相乘效率更高, 等我学会了再来更新代码, 学会了简单得动态规划已经很开心了.
戳此查看: 让你茅塞顿开的动态规划 https://time.geekbang.org/course/detail/130-69763
@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
写在最后
课程的结束不是终点, 而是起点, 加油, 开启自己成为真正工程师的道路.
查看课程回顾: 面试切题四件套 https://time.geekbang.org/course/detail/130-73458
感谢上面四位同学的精彩留言, 欢迎大家在文末分享你的刷题故事和经验, 我们一起进步.
专栏简介
我是覃超, 作为 Facebook 早期员工 & 多年面试官, 我对各大知名企业算法面试的考察点和面试套路, 有非常清晰的理解以及丰富的第一手经验. 在《算法面试通关 40 讲》这门课程里, 我会帮你建立一套完整的算法切题思路, 通过 "白板演练 + 代码讲解" 的方式, 手把手带你掌握高效解题套路, 彻底理解题目背后的考点, 锻炼算法思维, 让你在面试和平时的工作中大显身手.
学完这门课, 你将收获以下四个方面:
1, 常见算法知识点理论讲解
2, 高频面试题目思路剖析
3,LeetCode 高效解题四步法
4, 有效提升算法面试通过率
课程已更新完毕, 共 62 讲, 目前已有超过 10000 人加入学习, 课程广受好评, 期待你的加入! 戳我立即订阅 .
来源: http://www.tuicool.com/articles/iAJBBjA