一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 16804|回复: 244
收起左侧

[算法题] Leetcode 刷题记录!!!不信自己今年找不到工作!!!

  [复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-5-29 09:35:14 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 love1point 于 2015-11-11 14:03 编辑

11/11/2015







Accepted


Wrong Answer


Runtime Error


Time Limit Exceed


Others

Accepted
45%

Wrong Answer
16%

Others
26%


234 / 303
questions solved


2047
total submissions

919
accepted submissions

44.9 %
acceptance rate




















8. 5. 2015:





Accepted


Wrong Answer


Runtime Error


Time Limit Exceed


Others

Accepted
39%

Wrong Answer
18%

Runtime Error
11%

Others
28%


125 / 251
questions solved

1555
total submissions
612
accepted submissions
39.4 %
acceptance rate


















8.1. 2015:


124 / 242
questions solved


1436
total submissions

563
accepted submissions

39.2 %
acceptance rate

















Update: 8.1.2015, 8:40pm: 目前leetcode刷了122/226





更新与7.3.2015, 11:40am: 目前leetcode刷了107/214,破百啦,加上lintcode的53题,刷了近160题啦





写于2015.6.28,8:39pm:  从2015年5月29日开始系统大量的刷题,到今天2015.6.28一个月整啦。这一个月,代码量上去了,数据结构上去了,算法上去了。查了一下,一个月来,在地里的在线时间达376小时。平均一天十多小时在地里。自己有问题时,地里的朋友有给我及时的回答,特别感谢地里 id 是 s开头的和z开头的两位朋友详细的回答。现在easy 和 medium的问题不大了,下一阶段就是把leetcode的48道hard题给做完,自己已经做了13道。加油,35hard,每天3道hard,一个月内搞定。争取到7月中旬内能搞定leetcode的所有题目











正在从100/210 像 200/210 迈进,我相信这个过程是比前面100题更艰辛和困难,但我坚信,这是个更大质变的过程!我很有热情往下做,我为自己骄傲和感动!一定会成功的!


目前leetcode刷了103/212,破百啦,加上lintcode的50题,刷了近150题啦。想和大家分享的是,其实,1天10题,是可以做到的!

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

半个月,我新题刷了70题。其中有40题刷了两遍。。加上以前刷的30题,总共刷了140题。加上有的题目其实过了好几遍,全部的量应该有200-300题了吧
-----------------------------------------------------------------------------------------------

Single numer: https://leetcode.com/problems/single-number/

Given an array of integers, every element appears twice except for one. Find that single one.

idea1: 异或。即俩数,不同为1,相同为0。^这个向上的标志在java里是异或两个数,比如数字1 和 1, 二进制为 01 和 01,01 ^ 01的结果为 00。可以发现,异或后最后一个数字即为单独出现的数字,其他都相互抵消了。


public class Solution {
    public int singleNumber(int[] nums) {
        int x = 0;
        for(int a : nums)
        {
            x = x ^ a;
        }
        return x;
    }
}


idea2:Single number(虽然题目不让用额外空间,但该题用hashmap计数也能过lc)
  1. public class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  4.         for(int i = 0; i < nums.length; i++)
  5.         {
  6.             if(map.containsKey(nums[i]))
  7.             {
  8.                 map.put(nums[i], map.get(nums[i])+1);
  9.                
  10.             }
  11.             else
  12.             {
  13.                 map.put(nums[i], 1);
  14.             }
  15.         }
  16.         
  17.         for(int j = 0; j < nums.length; j++)
  18.         {
  19.             if(map.get(nums[j]) == 1)
  20.             {
  21.                 return nums[j];
  22.             }
  23.         }
  24.         return 0;
  25.     }
  26. }
复制代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



补充内容 (2015-5-30 16:38):
严格要求自己动手敲每一题

找到工作后定回来写超详细的感想和提供内推

这里人多,通过大家来督促自己刷好题

补充内容 (2015-5-30 21:28):
不追求数量,每题做透透的,其实自己是可以做出题目来,只是时间问题

补充内容 (2015-5-30 22:00):
自己敲出每一题,很能发现自己的缺漏和问题所在,好像又回到了当年高考做题的感觉。哈哈

补充内容 (2015-5-31 15:17):
秉承IT就是要信息共享,我贴出我的代码,欢迎大家提问和讨论,我尽量在几小时内迅速解答。所有我贴出的代码都是经过leetcode accepted 过的,但不一定是最优解,欢迎大家讨论你们更优的解法

补充内容 (2015-5-31 17:40):
今天做了几道关于String的,自己老是在输出长度时出现问题。总结出,在做String类型关于输出长度要用if(flag) 来控制输出。

补充内容 (2015-5-31 18:55):
今天两次做题时,该用循环时全都写成 if, 看来是晕了

补充内容 (2015-6-1 09:39):
今日做题感想: 不少人想找码农工作,但和我以前一样,面试怕被问到算法编程题。最近感想是,自己实实在在自己去敲代码AC过了,就会对面试更期待,而不是又爱又虚。继续做题吧。

补充内容 (2015-6-1 10:12):
不得不说,监督的力量是强大的。以前刷题时,网上有很多资料,有很多代码可以看,自己就不怎么想就把别人代码敲进来,可是到后来再做同一题时, 自己还是不会做,会的会,不会的还是不会。

补充内容 (2015-6-1 10:14):
这几天把自己做的题放到一亩三分地,因为这里人非常多,还可以”享受“ 汪峰似的每天自己的帖子上头条,自己感觉被监督了,刷题效果感觉非常好。题目越做越好,当然,那几十道题已经做了好几遍。

补充内容 (2015-6-1 16:27):
以前我也看过不少人的代码,但别人的代码永远是别人的,如果我们没有自己理解起来用自己的风格去敲出来代码,下次遇到还是不会。即使看完别人的解法,还是要自己用自己的编码style把它AC出来,才有底气

补充内容 (2015-6-1 16:45):
我目前提交的代码大家不要注释也能很清楚明白吧,如果不明白的话,欢迎大家在帖子里评论或留言

补充内容 (2015-6-1 22:11):
本贴尤其欢迎转专业的同学来讨论哈。因为从你们的问题中,我又可以过一遍题,双赢哈

补充内容 (2015-6-2 10:33):
从今天起,我尽量再贴出每道AC过的题的总结或思路,方便大家,以及自己日后的过遍数

补充内容 (2015-6-2 11:05):
我现在每天都会上来回答问题,保证非常快的回答大家。找到工作后,也会每天上来回答问题,尤其想帮助转专业的同学的问题!!! I want you!!!!

补充内容 (2015-6-2 19:27):
这几天每天做了不少题,一坐在电脑面前就是好几小时。等到找到工作后,自己再回来看自己每天的心路历程和做题记录,一定会为自己的付出而感到欣慰。打完鸡血,继续刷吧

补充内容 (2015-6-2 20:02):
这几天我会加入最新的leetcode题目。其实,刷题是一种熟练感觉,没有人可以非常熟练without大量练习。当我们量到一定程度,质到一定程度,我们更应该强调质,量只有在那些我们始终无法解决的题目类型时效果更好。

补充内容 (2015-6-2 20:04):
当我们质上去后,遇到新题,我们都能从容不迫,可以解出来。不然,leetcode已经有204题,且没几天又增加新题。。。我们可以通过test case来修改我们的代码,我们会发现自己没考虑到的情况。test case 屌啊

补充内容 (2015-6-3 07:16):
啊啊啊啊。Warald神和小K姐给我帖子加大米和加油,我还好意思不坚持下去吗?必须每天都刷啊!!!

补充内容 (2015-6-3 09:07):
刚用了论坛里的贴代码功能,这样代码看起来比较舒服了!

补充内容 (2015-6-3 09:09):
请那些因为不懂做题而产生不想刷题的同学相信我这句话:题目是越刷越爱刷,真会爱不释手,因为尝到甜头了,真的看的见自己代码更上一层楼!!!

补充内容 (2015-6-3 10:32):
遇到自己不会做的题,看看别人的代码后,一定要自己将代码变成自己的代码风格写出来,不然下次我们还是不会

补充内容 (2015-6-4 14:39):
连续第6天刷题,到目前为止刷了应该有40多道吧,但之前零零碎碎没有系统性的也刷了几十道题,当然有重复的

补充内容 (2015-6-4 18:11):
加上以前做的已经这6天的,目前leetcode solved 89/205 problems
现在平均每天可以6-10题

补充内容 (2015-6-5 11:49):
It is seventh days. AC 93/205

补充内容 (2015-6-5 23:28):
改刷的题目和题型也都刷了,现在准备用专题来复习,总结同类型题,继续做吧

补充内容 (2015-6-6 17:56):
连续刷题进入第八天了。今天做了点lintcode的题和cc150的。但感觉还是leetcode做好啊。现在,每天不刷点的题就觉得今天什么任务没完成似的。看来已养成习惯了。



评分

14

查看全部评分

本帖被以下淘专辑推荐:

 楼主| love1point 发表于 2015-6-28 12:31:19 | 显示全部楼层
Compare version numbers:  https://leetcode.com/problems/compare-version-numbers/

idea: 这题题目虽然看起来很长,但脱去外壳,本质就是字符串比较大小。没什么算法思想。主要考察数据结构了。比如正则表达式,字符串转数字等方法。
  1. public class Solution {
  2.     public int compareVersion(String version1, String version2) {
  3.         String[] array1 = version1.split("\\.");
  4.         String[] array2 = version2.split("\\.");
  5.         int i = 0;
  6.         while(i < array1.length || i < array2.length)
  7.         {
  8.             if(i < array1.length && i < array2.length)
  9.             {
  10.                 if(Integer.parseInt(array1[i]) > Integer.parseInt(array2[i]))
  11.                 {
  12.                     return 1;
  13.                 }
  14.                 else if(Integer.parseInt(array1[i]) < Integer.parseInt(array2[i]))
  15.                 {
  16.                     return -1;
  17.                 }
  18.             }
  19.             else if(i < array1.length)
  20.             {
  21.                 if(Integer.parseInt(array1[i]) != 0)
  22.                 {
  23.                     return 1;
  24.                 }
  25.             }
  26.             else if(i < array2.length)
  27.             {
  28.                 if(Integer.parseInt(array2[i]) != 0)
  29.                 {
  30.                     return -1;
  31.                 }
  32.             }
  33.             i++;
  34.         }
  35.         return 0;
  36.     }
  37. }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| love1point 发表于 2015-6-14 19:18:01 | 显示全部楼层
本帖最后由 love1point 于 2015-6-17 17:29 编辑

Subsets:  https://leetcode.com/problems/subsets/

idea: 这题用dfs递归出来。套用dfs模板,结果很快出来
  1. public class Solution {
  2.     public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
  3.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  4.         ArrayList<Integer> curr = new ArrayList<Integer>();
  5.         if(nums == null || nums.length == 0)
  6.         {
  7.             return result;
  8.         }
  9.         Arrays.sort(nums);
  10.         subsets(nums, 0, curr, result);
  11.         return result;
  12.     }
  13.    
  14.     public void subsets(int[] nums, int j, ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result)
  15.     {
  16.         ArrayList<Integer> temp = new ArrayList<Integer>(curr);
  17.         result.add(temp);
  18.         
  19.         for(int i = j; i < nums.length; i++)
  20.         {
  21.             curr.add(nums[i]);
  22.             subsets(nums, i+1, curr, result);
  23.             curr.remove(curr.size()-1);
  24.         }
  25.     }
  26. }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| love1point 发表于 2015-5-29 09:40:50 | 显示全部楼层
本帖最后由 love1point 于 2015-6-13 12:38 编辑

Word Ladder: https://leetcode.com/problems/word-ladder/

随着leetcode刷到后期,更体会到算法思想对于解题的重要性!我们无法背诵代码。但当我们知道某道题的解题思路,解题步骤,这比记代码更容易了吧。当我们下次碰到相同或类似的题目,我们脑海就会懂得如何做了。后面的功夫,就是实际coding的能力了,也就是数据结构等基本功,其实,数据结构也就那么几种,熟练运用hashmap的containsKey,get(key), size(),put(k, v)等方法。String, 就是s. charAt(),equals() 等。ArrayList<>的get()等,Linkedlist<> 的 push(), poll()等。实际coding没别的办法了,就是多练,多敲,多错,错了就去查资料,记忆起来。

这道题就是要知道解体的步骤了。实现不是非常难。要是第一次刷题的朋友,第一遍只要记住该题解题步骤,我觉得就够了。
  1. public class Solution {
  2.     public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
  3.         if (wordDict.size() == 0)
  4.                 return 0;

  5.         wordDict.add(endWord);

  6.         LinkedList<String> wordQueue = new LinkedList<String>();
  7.         LinkedList<Integer> distanceQueue = new LinkedList<Integer>();

  8.         wordQueue.add(beginWord);
  9.         distanceQueue.add(1);

  10.         //track the shortest path
  11.         int result = Integer.MAX_VALUE;
  12.         while (!wordQueue.isEmpty()) {
  13.                 String currWord = wordQueue.pop();
  14.                 Integer currDistance = distanceQueue.pop();

  15.                 if (currWord.equals(endWord)) {
  16.                         result = Math.min(result, currDistance);
  17.                 }

  18.                 for (int i = 0; i < currWord.length(); i++) {
  19.                         char[] currCharArr = currWord.toCharArray();
  20.                         for (char c = 'a'; c <= 'z'; c++) {
  21.                                 currCharArr = c;

  22.                                 String newWord = new String(currCharArr);
  23.                                 if (wordDict.contains(newWord)) {
  24.                                         wordQueue.add(newWord);
  25.                                         distanceQueue.add(currDistance + 1);
  26.                                         wordDict.remove(newWord);
  27.                                 }
  28.                         }
  29.                 }
  30.         }

  31.         if (result < Integer.MAX_VALUE)
  32.                 return result;
  33.         else
  34.                 return 0;
  35.     }
  36.    
  37.    
  38. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-29 10:19:25 | 显示全部楼层
本帖最后由 love1point 于 2015-6-13 23:21 编辑

Spiral matrix:   https://leetcode.com/problems/spiral-matrix/
这道题,题目很容易理解,但如果自己写起来,还是有很多地方需要注意的。建议就是,放进例子然后跟着代码走一遍,之后记忆大概整个代码框架。记忆也是有规律可行的。这道题的意义我觉得就是让我练代码,2位数组练熟悉,没什么算法思想
  1. public class Solution {
  2.     public List<Integer> spiralOrder(int[][] matrix) {
  3.         List<Integer> result = new ArrayList<Integer>();
  4.         
  5.         if(matrix == null || matrix.length == 0)
  6.         {
  7.             return result;
  8.         }
  9.         
  10.         int m = matrix.length;
  11.         int n = matrix[0].length;
  12.         
  13.         int x = 0;
  14.         int y = 0;
  15.         
  16.         while (m > 0 && n > 0)
  17.         {
  18.             if(m == 1)
  19.             {
  20.                 for(int i = 0; i < n; i++ )
  21.                 {
  22.                     result.add(matrix[x][y++]);
  23.                 }
  24.                 break;
  25.             }
  26.             else if(n == 1)
  27.             {
  28.                 for(int i = 0; i < m; i++)
  29.                 {
  30.                     result.add(matrix[x++][y]);
  31.                 }
  32.                 break;
  33.             }
  34.             
  35.             for(int i = 0; i < n-1; i++)
  36.             {
  37.                 result.add(matrix[x][y++]);
  38.             }
  39.             
  40.             
  41.             for(int i = 0; i < m-1; i++)
  42.             {
  43.                 result.add(matrix[x++][y]);
  44.             }
  45.             
  46.             
  47.             for(int i = 0; i < n-1; i++)
  48.             {
  49.                 result.add(matrix[x][y--]);
  50.             }
  51.             
  52.             
  53.             for(int i = 0; i < m-1; i++)
  54.             {
  55.                 result.add(matrix[x--][y]);
  56.             }
  57.             
  58.             x++;
  59.             y++;
  60.             m=m-2;
  61.             n=n-2;
  62.             
  63.         }
  64.         return result;
  65.     }
  66. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-30 15:52:21 | 显示全部楼层
本帖最后由 love1point 于 2015-6-13 23:28 编辑

Search for a range:   https://leetcode.com/problems/search-for-a-range/
这道题思路比较简单了。先把等于target的元素的index放到数组了。这题要注意的是,可能等于target的数大于2,比如[1,2,2,2], target 2。arr 就是[1,2,3],所以要用 arr.get(arr.size()-1)。也要知道ArrayList取元素是用get方法
  1. public class Solution {
  2.     public int[] searchRange(int[] nums, int target) {
  3.         ArrayList<Integer> arr = new ArrayList<Integer>();
  4.         int[] result = new int[2];
  5.         for(int i = 0; i < nums.length; i++)
  6.         {
  7.             if(nums == target)
  8.             {
  9.                 arr.add(i);
  10.             }
  11.         }
  12.         
  13.         if(arr.isEmpty())
  14.         {
  15.             result[0] = -1;
  16.             result[1] = -1;
  17.         }
  18.         else
  19.         {
  20.             result[0] = arr.get(0);
  21.             result[1] = arr.get(arr.size()-1);
  22.         }
  23.         return result;
  24.     }
  25. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-30 16:35:42 | 显示全部楼层
本帖最后由 love1point 于 2015-7-31 02:08 编辑

Valid Parentheses:   https://leetcode.com/problems/valid-parentheses/

这道题可用hashmap。当遇到所有左括号,把他们放到栈里。如果是右括号,则弹出来stack的元素,然后获得该元素的value,比较value与遇到的右括号是否相等。该题帮助我们练习hashmap的几个方法。
  1. public class Solution {
  2.     public boolean isValid(String s) {
  3.         HashMap<Character, Character> map = new HashMap<Character, Character>();
  4.         map.put('(', ')');
  5.         map.put('{', '}');
  6.         map.put('[', ']');
  7.         
  8.         LinkedList<Character>  stack = new LinkedList<Character>();
  9.         for(int i = 0; i < s.length(); i++)
  10.         {
  11.             Character curr = s.charAt(i);
  12.             if(map.keySet().contains(curr))
  13.             {
  14.                 stack.push(curr);
  15.             }
  16.             else
  17.             {
  18.                 if(map.values().contains(curr))
  19.                 {
  20.                     if(map.get(stack.peek())==curr)
  21.                     {
  22.                         stack.pop();
  23.                     }
  24.                     else
  25.                     {
  26.                         return false;
  27.                     }
  28.                 }
  29.                
  30.             }
  31.         }
  32.         
  33.         return stack.isEmpty();
  34.     }
  35. }
复制代码
回复 支持 反对

使用道具 举报

stellari 发表于 2015-5-30 18:15:08 | 显示全部楼层

楼主别嫌我多嘴。一般涉及排序过的数组肯定是用二分查找来做的,包括这道题。用线性查找就太简单了,面试官不会让你这么简单就通过的。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-30 18:57:54 | 显示全部楼层
stellari 发表于 2015-5-30 18:15
楼主别嫌我多嘴。一般涉及排序过的数组肯定是用二分查找来做的,包括这道题。用线性查找就太简单了,面试 ...

当然不会嫌你多嘴啊。

非常感谢你的回复。

这些只是我能想到的解法,不是最优解。我打算先做出题来,然后慢慢优化  :)
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-30 19:07:12 | 显示全部楼层
本帖最后由 love1point 于 2015-6-15 17:55 编辑

Two sum:  https://leetcode.com/problems/two-sum/

以下这个直观的方法估计面试官不会让你就此打住,肯定需要用hashmap解决
Naive solution: 两重循环,直接相加俩数进去判断
  1. public class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         int[] result = new int[2];
  4.         for(int i = 0; i < nums.length; i++)
  5.         {
  6.             for(int j = i + 1; j < nums.length; j++)
  7.             {
  8.                 if(nums + nums[j] == target)
  9.                 {
  10.                     result[0] = i + 1;
  11.                     result[1] = j + 1;
  12.                 }
  13.             }
  14.         }
  15.         return result;
  16.     }
  17. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-30 19:34:32 | 显示全部楼层
本帖最后由 love1point 于 2015-8-2 09:46 编辑

// Two sum 这题应该最能指示leetcode的人气了吧,截至目前提交次数为53+万次,有多少人在刷题啊// After 1.5 months, submission is 661251

Two sum:
  1. public class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  4.         int[] result = new int[2];
  5.         
  6.         if(nums == null || nums.length == 0)
  7.         {
  8.             return result;
  9.         }
  10.         
  11.         for(int i = 0; i < nums.length; i++)
  12.         {
  13.             if(map.containsKey(nums[i]))
  14.             {
  15.                 result[0] = map.get(nums[i]) + 1;
  16.                 result[1] = i + 1;
  17.             }
  18.             else
  19.             {
  20.                 map.put(target-nums[i], i);
  21.             }
  22.         }
  23.         return result;
  24.     }
  25. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-30 19:46:42 | 显示全部楼层
本帖最后由 love1point 于 2015-6-15 18:00 编辑

Best time to buy and sell stock II :   https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/这题简单。
idea:相邻俩数进行相减,由于可以进行无数次交易,但I 版本只能一次交易。相减得到正数,即为收益,累加这些数。
  1. public class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int profit = 0;
  4.         for(int i = 1; i < prices.length; i++)
  5.         {
  6.             int diff = prices - prices[i - 1];
  7.             if(diff > 0)
  8.             {
  9.                 profit += diff;
  10.             }
  11.         }
  12.         return profit;
  13.     }
  14. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-30 20:00:29 | 显示全部楼层
本帖最后由 love1point 于 2015-6-15 18:03 编辑

Linked List cycle: https://leetcode.com/problems/linked-list-cycle/

idea: 网上大部分解法都是这种,快慢指针,快的每次走两步,慢的每次走两步,如果有环,二者肯定会相遇,就像在800米跑道,俩同学一起跑步,二者速度不同,最终他们肯定会相遇,因操场是圆的
  1. public class Solution {
  2.     public boolean hasCycle(ListNode head) {
  3.         ListNode fast = head;
  4.         ListNode slow = head;
  5.         
  6.         if(head == null)
  7.         {
  8.             return false;   
  9.         }
  10.         
  11.         while(fast != null && fast.next != null)
  12.         {
  13.             slow = slow.next;
  14.             fast = fast.next.next;
  15.             if(fast == slow)
  16.             {
  17.                 return true;
  18.             }
  19.             
  20.         }
  21.         return false;
  22.     }
  23. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-30 20:58:30 | 显示全部楼层
本帖最后由 love1point 于 2015-6-15 18:08 编辑

Binary tree preorder traversal: https://leetcode.com/problems/binary-tree-preorder-traversal/
idea: 递归代码比较简单。前序顺序就是根,左,右。理解了此题,inorder和postorder就改一行代码的顺序即可。
  1. public class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> result = new ArrayList<Integer>();
  4.         
  5.          if(root == null)
  6.         {
  7.             return result;
  8.         }
  9.         
  10.         helper(root, result);
  11.         
  12.         return result;
  13.     }
  14.    
  15.     public List<Integer> helper(TreeNode root, List<Integer> result)
  16.     {
  17.         if(root == null)
  18.         {
  19.             return result;
  20.         }
  21.         else
  22.         {
  23.             result.add(root.val);
  24.         }
  25.         
  26.         helper(root.left, result);
  27.         
  28.         helper(root.right, result);
  29.         
  30.         return result;
  31.     }
  32. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-30 21:57:10 | 显示全部楼层
本帖最后由 love1point 于 2015-6-15 18:10 编辑

Reverse Linked List:  https://leetcode.com/problems/reverse-linked-list/
idea: 此代码应该是网上能找到的最短的代码了。可以用俩个节点为例子进行过代码。用到了递归
  1. public class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         if(head == null || head.next == null)
  4.         {
  5.             return head;
  6.         }
  7.         
  8.         ListNode second = head.next;
  9.         head.next = null;
  10.         
  11.         ListNode rest = reverseList(second);
  12.         second.next = head;
  13.         
  14.         return rest;
  15.         
  16.     }
  17. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-31 08:40:21 | 显示全部楼层
本帖最后由 love1point 于 2015-6-15 18:16 编辑

Climbing stairs:  https://leetcode.com/problems/climbing-stairs/
idea: 这题用动归。 代码走一遍,很容易记下了。每次能爬一格或者两格,比如在第三格,它只能从第一格或第二格来的。所以。f(n) = f(n-1) + f(n-2),f(n) 为 爬到第n 格的可能性组合。初始状态f(0) =1,因为第一格只有一种可能性,就是从地面到第一格爬一步。f(1) = 2, 两种,从地面直接爬两格,或者一格一格爬,从地面到一楼,一楼到二楼。
  1. public class Solution {
  2.     public int climbStairs(int n) {
  3.         if(n == 0)
  4.         {
  5.             return 0;
  6.         }
  7.         
  8.         int[] f = new int[3];
  9.         f[0] = 1;
  10.         f[1] = 2;
  11.         
  12.         if(n == 1)
  13.         {
  14.             return f[0];
  15.         }
  16.         if(n == 2)
  17.         {
  18.             return f[1];
  19.         }
  20.         
  21.         for(int i = 2; i < n; i++)
  22.         {
  23.             f[2] = f[0] + f[1];
  24.             f[0] = f[1];
  25.             f[1] = f[2];
  26.         }
  27.         return f[2];
  28.     }
  29. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-31 11:57:47 | 显示全部楼层
本帖最后由 love1point 于 2015-6-22 15:30 编辑

Count primes:  https://leetcode.com/problems/count-primes/

idea: 目前我还没找到比较容易记忆和理解的解法,暂且跟着代码走一遍好了,感觉好像也不太会考这种题。以后有看到好的代码再取代了。

        更新: 已找到很好解释改代码的算法思想,再次体会到算法思想的牛逼。 先假设大于等于2的数且小于n的数为Prime, 如果该数为prime,在循环范围内,它的2倍数就不是prime。


  1. public class Solution {
  2.     public int countPrimes(int n) {
  3.      if(n <= 2)
  4.      {
  5.          return 0;
  6.      }
  7.      boolean[] result = new boolean[n];
  8.      for(int i = 2; i < n; i++)
  9.      {
  10.          result[i] = true;
  11.      }
  12.      
  13.      for(int i = 2; i < n; i++)
  14.      {
  15.          if(result[i])
  16.          {
  17.              for(int j = 2 * i; j < n; j += i)
  18.              {
  19.                  result[j] = false;
  20.              }
  21.          }
  22.      }
  23.      
  24.      int count = 0;
  25.       for(int i = 2; i < n; i++)
  26.      {
  27.          if(result[i])
  28.          {
  29.              count++;
  30.          }
  31.      }
  32.      return count;
  33.     }
  34. }
复制代码

回复 支持 反对

使用道具 举报

PeaceinUESTC 发表于 2015-5-31 12:27:58 | 显示全部楼层
我想问下你怎么知道自己刷题的时候答案是正确的或者最优解?
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-31 15:13:08 | 显示全部楼层
PeaceinUESTC 发表于 2015-5-31 12:27
我想问下你怎么知道自己刷题的时候答案是正确的或者最优解?

我这些代码都是在leetcode accepted之后贴上来的。但不一定是最优解啊
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-31 15:13:27 | 显示全部楼层
本帖最后由 love1point 于 2015-6-15 18:21 编辑

Sort colors:  https://leetcode.com/problems/sort-colors/

idea: 这题暂且记住如下代码,代码还是比较好记得。思路就是我们先把0排在一起,1排在一起,剩下的就是2了
  1. public class Solution {
  2.     public void sortColors(int[] nums) {
  3.         int index0 = 0;
  4.         int index1 =0;
  5.         for(int i = 0; i < nums.length; i++)
  6.         {
  7.             if(nums == 0)
  8.             {
  9.                 nums = 2;
  10.                 nums[index1++] = 1;
  11.                 nums[index0++] = 0;
  12.             }
  13.             else
  14.             {
  15.                 if(nums == 1)
  16.                 {
  17.                     nums = 2;
  18.                     nums[index1++] = 1;
  19.                 }
  20.             }
  21.                
  22.             }
  23.     }
  24. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-5-31 16:55:47 | 显示全部楼层
本帖最后由 love1point 于 2015-6-20 16:44 编辑

implement strStr(): https://leetcode.com/problems/implement-strstr/

idea: 记住要用 if(flag) 来控制输出。用个具体例子来过代码,比如 haystack 为 apple,  needle 为 ap.

  1. public class Solution {
  2.     public int strStr(String haystack, String needle) {
  3.         int m = haystack.length();
  4.         int n = needle.length();
  5.         for(int i = 0; i < m - n + 1; i++)
  6.         {
  7.             boolean check = true;
  8.             for(int j = 0; j < n; j++)
  9.             {
  10.                
  11.                 if(haystack.charAt(i+j) != needle.charAt(j))
  12.                 {
  13.                     check = false;
  14.                     break;
  15.                 }
  16.             }
  17.             if(check)
  18.             {
  19.                 return i;
  20.             }
  21.         }
  22.       
  23.         return -1;

  24.     }
  25. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 05:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表