精华内容
下载资源
问答
  • LeetCode经典算法分享

    千次阅读 2018-11-23 09:37:15
    为什么要学习算法 1李开复曾经把基础课程比拟为“内功”,把新的语言、技术、标准比拟为“外功”。 整天赶时髦的人最后只懂得招式,没有功力,是不可能成为高手的。真正学懂计算机的人(不只是“编程匠”)都对数学...

    为什么要学习算法

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

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

    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的题目需要刷到一定程度才能能引起质变,但是前提是每一题需要透彻理解,举一反三,这个过程需要花费大量时间去理解。

    展开全文
  • String str = strs[0]; for(i=1;i<strs.length;i++){ while(strs[i].indexOf(str) != 0){ //由于要找的是公共前缀,因此这里需要判断第一次出现的索引是否为0 ​ str = str.substring(0,str.length()-1);...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 218,131
精华内容 87,252
关键字:

leetcode经典算法