LeetCode经典算法分享

大家好，我是讯享网，很高兴认识大家。

为什么要学习算法

1李开复曾经把基础课程比拟为“内功”，把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。真正学懂计算机的人（不只是“编程匠”）都对数学有相当的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——而这种思维和手段的**演绎就是“算法”。

2无论是阿里巴巴、腾讯、百度这些国内一线互联网企业，还是 Google、Facebook、Airbnb 等硅谷知名互联网公司，在招聘工程师的过程中，对算法和数据结构能力的考察都是重中之重。

3用相应的算法来解决实际工作和面试中的算法问题，都是可以通过学习和训练不断提高的

很多人会在在 LeetCode 网站上做大量练习，但随着 LeetCode 上题目越来越多，不可能在短时间内把题目全部做完，如何有选择性地来练习，就成为大多数人必须面对的难题。

算法的几个基础知识

时间复杂度

[1]只要高阶项，不要低阶项

[2]不要高阶项系数

产生堆积样本的发生器

寻找一个完全准确的方法（容易实现，无需考虑时间复杂度）

数据完全拷贝两份，分别传递到测试函数和完全正确的函数中，进行结果比较

对数器的概念和使用

递归

在递归的过程中，系统会将代码行、形参、局部变量等信息压入系统栈中，当遇到return后将栈顶信息弹出还原现场并将值带回，然后执行接下来的语句

任何递归行为都可以改成非递归（无需系统压栈，自己手动压栈）---> 从递归改为迭代

计算递归行为的时间复杂度Master公式

T(n)=aT(n/b)+O(n^d)

1) log(b,a) > d -> 复杂度为O(N^log(b,a))

讯享网

2) log(b,a) = d -> 复杂度为O(N^d * logN)

3) log(b,a) < d -> 复杂度为O(N^d)

a是子过程调用多少次

b被拆成子问题的样本量

d是除去子过程剩下的时间复杂度的幂

适用范围：每次发生的规模都一样

公式记忆：我们实际上是比较n^logba和n^d，如果他们不等，那么T(n)取他们中的较大者，如果他们的阶相等，那么我们就将他们的任意一个乘以logn就可以了

比如二分查找 T(n)=2T(n/2)+O(n)

a=2,b=2，额外操作的时间复杂度为O(1),即d=0 时间复杂度为logN

经典算法举例：

图中的代码时间复杂度没有达到要求，可以改成非递归利用二分查找节省时间复杂度，这里不贴代码了

 / * 解法二 * 利用非递归和二分查找把时间复杂度降为log(n) * @param nums */ public int nonRecursive(int[] nums){ //dp[i]代表以nums[i]结尾的最长递增子序列的长度 int[] dp =new int[nums.length]; //ends[r]存储最大递增子序列长度为r+1序列的最小结尾值 int[] ends =new int[nums.length]; //他们之间的关系：如果num[i]=ends[r] 那么dp[i] = r ends[0]=nums[0]; dp[0]=1; int l=0,m=0,r=0; for (int i = 1; i < nums.length; i++) { //nums[i]是否要放在ends的末尾 Boolean isNext = false; while (l <= r) { m = (int)(l+r)/2; if(l==r){ //ends里的已有数找不到比nums[i]小的数所以要放在最后 if(ends[m] <= nums[i]){ isNext =true; } break; } if(ends[m] <= nums[i]){ l = m + 1; }else{ r = m - 1; } } if(isNext){ //ends里的已有数找不到比nums[i]小的数所以要放在最后 ends[r+1] = nums[i]; r = r+1; }else{ //ends里的已有数找到比nums[i]小的数所以要替换原来的值 ends[r] = nums[i]; } dp[i] = r+1; } int max =-10000; for (int i = 0; i < nums.length; i++) { //System.out.print(dp[i]+" "); max =Math.max(max, dp[i]); } return max; }

讯享网

总结:尽量刷经典题目，网上虽然很多题解但，是很多只有代码，没有详细的思路不建议去模仿。站在不同的角度分析问题写出来的代码可能完全不一样。除非分析和思路很清晰否则个人感觉价值不大。LeetCode的题目需要刷到一定程度才能能引起质变，但是前提是每一题需要透彻理解，举一反三，这个过程需要花费大量时间去理解。

为什么要学习算法

算法的几个基础知识

经典算法举例：

相关推荐