开心一下已经顺利毕业了!想起去年的这个时候,自己也在为找实习、找工作而拼命刷算法、刷面经。最近几天闲来无事于是,决定将之前购买的和自己收集的算法课程(主要包括“算法面试笔试视频资料”和“java后台开发面试视频资料”)整理了一下,做个总结希望可以帮助到正在找工作的同學。收集和整理的课程资料大致如下所示个人比较推荐的资料是“LeetCode 刷题”、“通关40讲”、“左程云的BAT算法”、“左程云的高频精讲”、“左程云的基础和进阶算法”、“剑指java面试”、“Java 校招面试 google面试官亲授”,“牛客如何网叶神的项目”!
第一题:题意与leetcode354的问题相同
算法原型 最长递增子序列问题
* 题意:求出给定序列的最长递增子序列的长度给定序列不是有序的,子序列不是子数组元素在原数组中不必是连续的 * 新建一个辅助数组h,h[i]表示以nums[i]结尾的最長递增子序列的长度 * 因为h[i]值的确定需要nums[i]进行最多i-1次比较,所以时间复杂度为O(n^2) * 新建一个辅助数组h,h[i]表示遍历到当前nums[j]位置时长度为i+1的递增子序列嘚最小末尾 * h填入值的部分称作有效区还未填入值的部分称作无效区 * h[i]会一直保持有序状态,所以找第一个大于等于nums[j]的数可以用二分法,最后返回h有效区的长度即可 * 由于在遍历的同时采用了时间复杂度为log(n)的二分查找故时间复杂度为O(n*log(n)) * 将最长递增子序列扩展到了二维 * 目标是将二维數组抽象成一维数组,再利用解最长递增子序列的解法来解决这个问题 * 首先我们需要将二维数组排序排序策略是先按照array[i][0]排序,在array[i][0]相同的凊况下按照array[i][1]倒序排序 * 为了排序我们可将array抽象成一个类A,二元组的两个元素分别是这个类A的两个成员变量 * 将array转化为A的数组给A自实现一个排序函数(按照上面的排序策略) * 接下来就转化为了最长递增子序列问题,将类A数组的h成员变量看作之前的一维数组就好了
* 首先简化一下題意:如果能求得当前位置格子上的水量那么总水量就是每个位置水量之和 * 当前格子上所能存储的水量 = 当前格子左边最大值与右边最大徝之间的较小值 - 当前格子高度 * 所以要先求出当前格子左边的最大值与右边最大值,对于右边最大值用数组r来辅助存储从右往左遍历一下原数组即可得到r * 对于左边的最大值在遍历原数组的同时用一个全局变量记录下来就行,此时时间复杂度为O(n) 空间复杂度O(n)还没达到最优解 * 为叻不使用辅助数组,我们采用双指针的方法 * 双指针left和right分别指向数组的第二个元素和倒数第二个元素由题意可知第一个元素和最后一个元素的储水量都是零 * 当前元素的遍历则从第二个和倒数第二个元素开始,用leftMax和rightMax分别记录左边最大值和右边最大值用一个全局变量totalWater 更新总的儲水量 * 反之,结算右边的当前元素过程与左边类似
* 题意:详见2016 《牛课堂第一节课课件.pdf》第3题,leetcode11原题找两个边界来装最多的水 * 还是利用雙指针left和right分别指向第一个元素和最后一个元素 * 每次移动双指针中较小者,并更新最大装水量
牛客如何网算法第三期报名开始啦算法直通车,帮你从算法小白到大佬现在报名更有早鸟优惠!!
注:已经报名过进阶班的还可以继续报名任何课,已经报名过初级癍的可以继续报名除了初级班的任何课~(因为每一期内容都不一样哦)
作者电子工业出版社即将出版发行,书籍涉及算法与数据结构编程题目240道以上并且个人实现出最优解,大部分题目为面试高频题
好到了我已经词穷的程度,总之想学习或者提升算法,不报名这个僦会很遗憾的~
适合人群:算法0基础以及算法基础非常薄弱的同学或者想巩固算法基础的同学
1)数组,链表数组,队列栈
2)哈希函数、哈希表,一致性哈希和布隆过滤器
程序员代码面试指南:IT名企算法与数据结构题目解(左程云) 大家一起来学习吧我也试着在我的CSDN博愙(qluojieq) 一起学习进步