一亩三分地论坛

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

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

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

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-6-6 11:49:13 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 love1point 于 2015-8-3 02:16 编辑

写于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的所有题目




本帖最后由 love1point 于 2015-6-16 20:07 编辑
正在从100/210 像 200/210 迈进,我相信这个过程是比前面100题更艰辛和困难,但我坚信,这是个更大质变的过程!我很有热情往下做,我为自己骄傲和感动!一定会成功的!

目前leetcode刷了106/210,破百啦,加上lintcode的57题,刷了近163题啦。想和大家分享的是,其实,1天10题,是可以做到的!
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

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



经常刷论坛的朋友应该记得 “Leetcode 刷题记录!!!不信自己今年找不到工作!!!” (http://www.1point3acres.com/bbs/thread-135445-1-1.html) 这个帖子吧,由于得到大家的鼓励,目前点击量已到5400+(每天都有近100的点击),回复达185(当然大部分都是自己贴的题目),被加的大米达103。自己所有帖子的浏览量总共有好几千了,已经破万,哈哈。非常感谢大家的好的,不好的点评,但这都一点都没有影响到我刷题找工作的心情和目标!


作为姊妹篇,我就开了这个帖子啦,希望每天都可以搞几题,已经当刷题为乐趣了,我的最终极目标为“全世界刷题数做多的人”  : )      p.s.(刷题做多的人这句话是看玩笑的看不出来吗?哎,看不出来就去躲着难受吧,我可不管哈)

由于自己leetcode题目刷的差不多了,下一步就是对leetcode的题目就行总结和过遍数。

空余无聊时,我就开始做做lintcode的题目啦。
p.s, 本帖访问量也2900+啦,这是自己连续3周天天泡在论坛的结果啊,哈哈



评分

3

查看全部评分

 楼主| love1point 发表于 2015-6-28 20:13:40 | 显示全部楼层
zhuli19901106 发表于 2015-6-28 19:49
关于deep copy和shallow copy可以举这么个例子:
用python:
a = 3

谢啦,这块知识以前碰到过,不确定addAll 是否保证 l 里的元素不变的功能,即便看了别人的需要 addAll 这个方法,但自己还是想确认清楚来。觉得好多dfs的题目都是用addAll 把 temporary result 复制到 final result,已保证元素不被 后面的 一行 代码 l.remove(l.size()-1)给抹掉。

和你们讨论讨论这些题目的代码,会使我对该题的记忆更深哈。
回复 支持 1 反对 0

使用道具 举报

 楼主| love1point 发表于 2015-6-6 11:53:38 | 显示全部楼层
Fizz Buzz:
  1. class Solution {
  2.     /**
  3.      * param n: As description.
  4.      * return: A list of strings.
  5.      */
  6.     public ArrayList<String> fizzBuzz(int n) {
  7.         ArrayList<String> results = new ArrayList<String>();
  8.         for (int i = 1; i <= n; i++)
  9.         {
  10.             if (i % 3 == 0 && i % 5 == 0)
  11.             {
  12.                 results.add("fizz buzz");
  13.             }
  14.             else if (i % 5 == 0)
  15.             {
  16.                 results.add("buzz");
  17.             }
  18.             else if (i % 3 == 0)
  19.             {
  20.                 results.add("fizz");
  21.             }
  22.             else
  23.             {
  24.                 results.add(String.valueOf(i));
  25.             }
  26.         }
  27.         return results;
  28.     }
  29. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-6 12:01:08 | 显示全部楼层
Count 1 in binary:
  1. public class Solution {
  2.     /**
  3.      * @param num: an integer
  4.      * @return: an integer, the number of ones in num
  5.      */
  6.     public int countOnes(int num) {
  7.         // write your code here
  8.         int count = 0;
  9.         for(int i = 1; i < 33; i++)
  10.         {
  11.             if(getBits(num, i))
  12.             {
  13.                 count++;
  14.             }
  15.         }
  16.         return count;
  17.     }
  18.    
  19.     public boolean getBits(int num, int i)
  20.     {
  21.         return (num & (1 << i))!=0;
  22.     }
  23. };
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-6 15:22:19 | 显示全部楼层
Reverse Linked List:
  1. /**
  2. * Definition for ListNode.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int val) {
  7. *         this.val = val;
  8. *         this.next = null;
  9. *     }
  10. * }
  11. */
  12. public class Solution {
  13.     /**
  14.      * @param head: The head of linked list.
  15.      * @return: The new head of reversed linked list.
  16.      */
  17.     public ListNode reverse(ListNode head) {
  18.         // write your code here
  19.         if(head == null || head.next == null)
  20.         {
  21.             return head;
  22.         }
  23.         
  24.         ListNode second = head.next;
  25.         head.next = null;
  26.         
  27.         ListNode rest = reverse(second);
  28.         second.next = head;
  29.         
  30.         return rest;
  31.     }
  32. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-6 17:58:18 | 显示全部楼层
Binary tree level order travesal:
  1. /**
  2. * Definition of TreeNode:
  3. * public class TreeNode {
  4. *     public int val;
  5. *     public TreeNode left, right;
  6. *     public TreeNode(int val) {
  7. *         this.val = val;
  8. *         this.left = this.right = null;
  9. *     }
  10. * }
  11. */


  12. public class Solution {
  13.     /**
  14.      * @param root: The root of binary tree.
  15.      * @return: Level order a list of lists of integer
  16.      */
  17.     public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
  18.         // write your code here
  19.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  20.         
  21.         if(root == null)
  22.         {
  23.             return result;
  24.         }
  25.         
  26.         LinkedList<TreeNode> curr = new LinkedList<TreeNode>();
  27.         LinkedList<TreeNode> next = new LinkedList<TreeNode>();
  28.         curr.offer(root);
  29.         
  30.         ArrayList<Integer> numberList = new ArrayList<Integer>();
  31.         
  32.         while(!curr.isEmpty())
  33.         {
  34.             TreeNode head = curr.pop();
  35.             numberList.add(head.val);
  36.             
  37.             if(head.left != null)
  38.             {
  39.                 next.offer(head.left);
  40.             }
  41.             
  42.             if(head.right != null)
  43.             {
  44.                 next.offer(head.right);
  45.             }
  46.             
  47.             if(curr.isEmpty())
  48.             {
  49.                 curr= next;
  50.                 next = new LinkedList<TreeNode>();
  51.                 result.add(numberList);
  52.                 numberList = new ArrayList<Integer>();
  53.             }
  54.         }
  55.         return result;
  56.     }
  57. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-6 18:03:02 | 显示全部楼层
Binary tree level order traversal ii:
  1. /**
  2. * Definition of TreeNode:
  3. * public class TreeNode {
  4. *     public int val;
  5. *     public TreeNode left, right;
  6. *     public TreeNode(int val) {
  7. *         this.val = val;
  8. *         this.left = this.right = null;
  9. *     }
  10. * }
  11. */


  12. public class Solution {
  13.     /**
  14.      * @param root: The root of binary tree.
  15.      * @return: buttom-up level order a list of lists of integer
  16.      */
  17.     public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
  18.         // write your code here
  19.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  20.         
  21.         if(root == null)
  22.         {
  23.             return result;
  24.         }
  25.         
  26.         LinkedList<TreeNode> curr = new LinkedList<TreeNode>();
  27.         LinkedList<TreeNode> next = new LinkedList<TreeNode>();
  28.         curr.offer(root);
  29.         
  30.         ArrayList<Integer> numberList = new ArrayList<Integer>();
  31.         
  32.         while(!curr.isEmpty())
  33.         {
  34.             TreeNode head = curr.pop();
  35.             numberList.add(head.val);
  36.             
  37.             if(head.left != null)
  38.             {
  39.                 next.offer(head.left);
  40.             }
  41.             
  42.             if(head.right != null)
  43.             {
  44.                 next.offer(head.right);
  45.             }
  46.             
  47.             if(curr.isEmpty())
  48.             {
  49.                 curr= next;
  50.                 next = new LinkedList<TreeNode>();
  51.                 result.add(numberList);
  52.                 numberList = new ArrayList<Integer>();
  53.             }
  54.         }
  55.         ArrayList<ArrayList<Integer>> reverseResult = new ArrayList<ArrayList<Integer>>();
  56.         for(int i = result.size()-1; i >= 0; i--)
  57.         {
  58.             reverseResult.add(result.get(i));
  59.         }
  60.         return reverseResult;
  61.     }
  62. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-6 18:20:28 | 显示全部楼层
Valid palindrome:
  1. public class Solution {
  2.     /**
  3.      * @param s A string
  4.      * [url=home.php?mod=space&uid=160137]@return[/url] Whether the string is a valid palindrome
  5.      */
  6.     public boolean isPalindrome(String s) {
  7.         // Write your code here
  8.         if(s == null || s.length() == 0)
  9.         {
  10.             return true;
  11.         }
  12.         
  13.         s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
  14.         
  15.         for(int i = 0; i < s.length(); i++)
  16.         {
  17.             if(s.charAt(i) != s.charAt(s.length()-1-i))
  18.             {
  19.                 return false;
  20.             }
  21.         }
  22.         return true;
  23.     }
  24. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-7 10:05:19 | 显示全部楼层
Two sum:
  1. public class Solution {
  2.     /*
  3.      * @param numbers : An array of Integer
  4.      * @param target : target = numbers[index1] + numbers[index2]
  5.      * @return : [index1 + 1, index2 + 1] (index1 < index2)
  6.      */
  7.     public int[] twoSum(int[] numbers, int target) {
  8.         // write your code here
  9.         int[] result = new int[2];
  10.         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  11.         for(int i = 0; i < numbers.length; i++)
  12.         {
  13.             if(map.containsKey(target - numbers[i]))
  14.             {
  15.                 result[0] = map.get(target - numbers[i]) + 1;
  16.                 result[1] = i + 1;
  17.                 return result;
  18.             }
  19.             else
  20.             {
  21.                 map.put(numbers[i], i);
  22.             }
  23.         }
  24.         return result;
  25.     }
  26. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-7 11:02:00 | 显示全部楼层
Single number:
  1. public class Solution {
  2.         /**
  3.          *@param A : an integer array
  4.          *return : a integer
  5.          */
  6.         public int singleNumber(int[] A) {
  7.             if(A == null || A.length == 0)
  8.             {
  9.                 return 0;
  10.             }
  11.             
  12.                 int n = A[0];
  13.                 for(int i = 1; i < A.length; i++) {
  14.                         n = n ^ A[i];
  15.                 }

  16.                 return n;
  17.         }
  18. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-7 11:27:56 | 显示全部楼层
Binary tree preorder traversal:
  1. /**
  2. * Definition of TreeNode:
  3. * public class TreeNode {
  4. *     public int val;
  5. *     public TreeNode left, right;
  6. *     public TreeNode(int val) {
  7. *         this.val = val;
  8. *         this.left = this.right = null;
  9. *     }
  10. * }
  11. */
  12. public class Solution {
  13.     /**
  14.      * @param root: The root of binary tree.
  15.      * @return: Preorder in ArrayList which contains node values.
  16.      */
  17.     public ArrayList<Integer> preorderTraversal(TreeNode root) {
  18.         // write your code here
  19.         ArrayList<Integer> result = new ArrayList<Integer>();
  20.         
  21.         helper(root, result);
  22.         
  23.         return result;
  24.     }
  25.    
  26.    
  27.     public ArrayList<Integer> helper(TreeNode root, ArrayList<Integer> result)
  28.     {
  29.         
  30.         
  31.         if(root == null)
  32.         {
  33.             return result;
  34.         }
  35.       
  36.         result.add(root.val);
  37.          
  38.         helper(root.left, result);
  39.         
  40.         helper(root.right, result);
  41.         
  42.         return result;
  43.     }
  44. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-7 13:15:35 | 显示全部楼层
Linked List cycle:
  1. /**
  2. * Definition for ListNode.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int val) {
  7. *         this.val = val;
  8. *         this.next = null;
  9. *     }
  10. * }
  11. */
  12. public class Solution {
  13.     /**
  14.      * @param head: The first node of linked list.
  15.      * @return: True if it has a cycle, or false
  16.      */
  17.     public boolean hasCycle(ListNode head) {  
  18.         // write your code here
  19.         if(head == null || head.next == null)
  20.         {
  21.             return false;
  22.         }
  23.         
  24.         ListNode fast = head;
  25.         ListNode slow = head;
  26.         
  27.         while(fast != null && fast.next != null)
  28.         {
  29.             fast = fast.next.next;
  30.             slow = slow.next;
  31.             
  32.             if(fast == slow)
  33.             {
  34.                 return true;
  35.             }
  36.         }
  37.         return false;
  38.     }
  39. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-7 13:29:14 | 显示全部楼层
Linked List cycle ii:
  1. /**
  2. * Definition for ListNode.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int val) {
  7. *         this.val = val;
  8. *         this.next = null;
  9. *     }
  10. * }
  11. */
  12. public class Solution {
  13.     /**
  14.      * @param head: The first node of linked list.
  15.      * @return: The node where the cycle begins.
  16.      *           if there is no cycle, return null
  17.      */
  18.     public ListNode detectCycle(ListNode head) {  
  19.         // write your code here
  20.         if(head == null || head.next == null)
  21.         {
  22.             return null;
  23.         }
  24.         
  25.         ListNode fast = head;
  26.         ListNode slow = head;
  27.         
  28.         while(fast != null && fast.next != null)
  29.         {
  30.             fast = fast.next.next;
  31.             slow = slow.next;
  32.             
  33.             if(fast == slow)
  34.             {
  35.                 fast = head;
  36.                 while(fast != slow)
  37.                 {
  38.                     slow = slow.next;
  39.                     fast = fast.next;
  40.                 }
  41.                 return fast;
  42.             }
  43.         }
  44.         return null;
  45.     }
  46. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-7 13:37:04 | 显示全部楼层
Best time to buy and sell stock ii:
  1. class Solution {
  2.     /**
  3.      * @param prices: Given an integer array
  4.      * @return: Maximum profit
  5.      */
  6.     public int maxProfit(int[] prices) {
  7.         // write your code here
  8.         int diff = 0;
  9.         int result = 0;
  10.         for(int i = 0; i < prices.length - 1; i++)
  11.         {
  12.             diff = prices[i+1] - prices[i];
  13.             if(diff > 0)
  14.             {
  15.                 result = result + diff;
  16.             }
  17.         }
  18.         return result;
  19.     }
  20. };
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-7 14:02:23 | 显示全部楼层
Climbing stairs:
  1. public class Solution {
  2.     /**
  3.      * @param n: An integer
  4.      * @return: An integer
  5.      */
  6.     public int climbStairs(int n) {
  7.         // write your code here
  8.         int f1 = 1;
  9.         int f2 = 2;
  10.         
  11.         if(n == 1)
  12.         {
  13.             return f1;
  14.         }
  15.         
  16.         if(n == 2)
  17.         {
  18.             return f2;
  19.         }
  20.         
  21.         int f3 = 0;
  22.         
  23.         for(int i = 3; i <= n; i++)
  24.         {
  25.             f3 = f1 + f2;
  26.             f1 = f2;
  27.             f2 = f3;
  28.         }
  29.         return f2;
  30.     }
  31. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-7 15:08:03 | 显示全部楼层
Search insert position:
  1. public class Solution {
  2.     /**
  3.      * param A : an integer sorted array
  4.      * param target :  an integer to be inserted
  5.      * return : an integer
  6.      */
  7.     public int searchInsert(int[] A, int target) {
  8.         // write your code here
  9.         int left = 0;
  10.         int right = A.length - 1;
  11.         
  12.         while(left <= right)
  13.         {
  14.             int mid = (left + right) / 2;
  15.             if(A[mid] == target)
  16.             {
  17.                 return mid;
  18.             }
  19.             else if(A[mid] < target)
  20.             {
  21.                 left = mid + 1;
  22.             }
  23.             else
  24.             {
  25.                 right = mid - 1;
  26.             }
  27.         }
  28.         return left;
  29.     }
  30. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-8 10:24:25 | 显示全部楼层
Anagrams:
  1. public class Solution {
  2.     /**
  3.      * @param strs: A list of strings
  4.      * @return: A list of strings
  5.      */
  6.     public ArrayList<String> anagrams(String[] strs) {
  7.         // write your code here
  8.         ArrayList<String> result = new ArrayList<String>();
  9.         
  10.         HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>();
  11.         
  12.         
  13.         
  14.         for(int i = 0; i < strs.length; i++)
  15.         {
  16.             char[] c = strs[i].toCharArray();
  17.             Arrays.sort(c);
  18.             String a = String.valueOf(c);
  19.             if(!map.containsKey(a))
  20.             {
  21.                 ArrayList<Integer> array = new ArrayList<Integer>();
  22.                 array.add(i);
  23.                 map.put(a, array);
  24.             }
  25.             else
  26.             {
  27.                 map.get(a).add(i);
  28.             }
  29.         }
  30.         
  31.         for(ArrayList<Integer> l : map.values())
  32.         {
  33.             if(l.size() > 1)
  34.             {
  35.                 for(Integer i : l)
  36.                 {
  37.                     result.add(strs[i]);
  38.                 }
  39.             }
  40.         }
  41.         return result;
  42.         
  43.     }
  44. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-8 14:28:02 | 显示全部楼层
Permutations:
  1. public class Solution {
  2.     public ArrayList<ArrayList<Integer>> permute(int[] nums) {
  3.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  4.         
  5.         result.add(new ArrayList<Integer>());
  6.         
  7.         for(int i = 0; i < nums.length; i++)
  8.         {
  9.             ArrayList<ArrayList<Integer>> curr = new ArrayList<ArrayList<Integer>>();
  10.             for(ArrayList<Integer> l : result)
  11.             {
  12.                 for(int j = 0; j < l.size()+1; j++)
  13.                 {
  14.                     l.add(j, nums[i]);
  15.                     ArrayList<Integer> temp = new ArrayList<Integer>(l);
  16.                     curr.add(temp);
  17.                     l.remove(j);
  18.                 }
  19.             }
  20.             result = new ArrayList<ArrayList<Integer>>(curr);
  21.         }
  22.         return result;
  23.     }
  24. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-8 16:43:57 | 显示全部楼层
Sort colors:
  1. class Solution {
  2.     /**
  3.      * @param nums: A list of integer which is 0, 1 or 2
  4.      * @return: nothing
  5.      */
  6.     public void sortColors(int[] nums) {
  7.         // write your code here
  8.         int index0 = 0;
  9.         int index1 = 0;
  10.         
  11.         for(int i = 0; i < nums.length; i++)
  12.         {
  13.             if(nums[i] == 0)
  14.             {
  15.                 nums[i] = 2;
  16.                 nums[index1++] = 1;
  17.                 nums[index0++] = 0;
  18.             }
  19.             else if(nums[i] == 1)
  20.             {
  21.                 nums[i] = 2;
  22.                 nums[index1++] = 1;
  23.             }
  24.         }
  25.         
  26.     }
  27. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-8 16:53:42 | 显示全部楼层
Find peak number:
  1. class Solution {
  2.     /**
  3.      * @param A: An integers array.
  4.      * @return: return any of peek positions.
  5.      */
  6.     public int findPeak(int[] A) {
  7.         // write your code here
  8.         for(int i = 1; i < A.length -1; i++)
  9.         {
  10.             if(A[i] > A[i-1] && A[i] > A[i+1])
  11.             {
  12.                 return i;
  13.             }
  14.         }
  15.         return 0;
  16.     }
  17. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-8 17:13:22 | 显示全部楼层
Maximum subarray:
  1. public class Solution {
  2.     /**
  3.      * @param nums: A list of integers
  4.      * @return: A integer indicate the sum of max subarray
  5.      */
  6.     public int maxSubArray(ArrayList<Integer> nums) {
  7.         // write your code
  8.         int local = nums.get(0);
  9.         int max = nums.get(0);
  10.         for(int i = 1; i < nums.size(); i++)
  11.         {
  12.             local = Math.max(local+nums.get(i), nums.get(i));
  13.             max = Math.max(max, local);
  14.         }
  15.         return max;
  16.     }
  17. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 14:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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