Leetcode 刷题记录！！！不信自己今年找不到工作！！！

补充内容 (2015-6-3 14:03):
重复提交了一道题，删

subsets后面有新的做法，此题做法，删

LRU Cache:  https://leetcode.com/problems/lru-cache/
idea: 这题是比较难的了，通常只要onsite有些公司才会考。用到了双链表，hashmap等数据结构

1. 
   
2. public class LRUCache {
   
3.    
   
4.     private HashMap<Integer, DoubleLinkedListNode> map = new HashMap<Integer, DoubleLinkedListNode>();
   
5.     private DoubleLinkedListNode head;
   
6.     private DoubleLinkedListNode end;
   
7.     private int capacity;
   
8.     private int len;
   
9.    
   
10.     public LRUCache(int capacity) {
    
11.         this.capacity = capacity;
    
12.         len = 0;
    
13.     }
    
14.    
    
15.     public int get(int key) {
    
16.         if(map.containsKey(key))
    
17.         {
    
18.             DoubleLinkedListNode lastest = map.get(key);
    
19.             removeNode(lastest);
    
20.             setHead(lastest);
    
21.             return lastest.value;
    
22.         }
    
23.         else
    
24.         {
    
25.             return -1;
    
26.         }
    
27.     }
    
28.    
    
29.     public void removeNode(DoubleLinkedListNode node)
    
30.     {
    
31.         DoubleLinkedListNode cur = node;
    
32.         DoubleLinkedListNode pre = cur.pre;
    
33.         DoubleLinkedListNode post = cur.next;
    
34.         
    
35.         if(pre != null)
    
36.         {
    
37.             pre.next = post;
    
38.         }
    
39.         else
    
40.         {
    
41.             head = post;
    
42.         }
    
43.         
    
44.         if(post != null)
    
45.         {
    
46.             post.pre = pre;
    
47.         }
    
48.         else
    
49.         {
    
50.             end = pre;
    
51.         }
    
52.     }
    
53.    
    
54.     public void setHead(DoubleLinkedListNode node)
    
55.     {
    
56.         node.next = head;
    
57.         node.pre = null;
    
58.         if(head != null)
    
59.         {
    
60.             head.pre = node;
    
61.         }
    
62.         
    
63.         head = node;
    
64.         if(end == null)
    
65.         {
    
66.             end = node;
    
67.         }
    
68.     }
    
69.    
    
70.     public void set(int key, int value) {
    
71.         if(map.containsKey(key))
    
72.         {
    
73.             DoubleLinkedListNode oldNode = map.get(key);
    
74.             oldNode.value = value;
    
75.             removeNode(oldNode);
    
76.             setHead(oldNode);
    
77.         }
    
78.         else
    
79.         {
    
80.             DoubleLinkedListNode newNode = new DoubleLinkedListNode(key, value);
    
81.             if(len < capacity)
    
82.             {
    
83.                 setHead(newNode);
    
84.                 map.put(key, newNode);
    
85.                 len++;
    
86.             }
    
87.             else
    
88.             {
    
89.                 map.remove(end.key);
    
90.                 end = end.pre;
    
91.                 if(end != null)
    
92.                 {
    
93.                     end.next = null;
    
94.                 }
    
95.                 setHead(newNode);
    
96.                 map.put(key, newNode);
    
97.             }
    
98.         }
    
99.     }
    
100. }
     
101. 
     
102. class DoubleLinkedListNode
     
103. {
     
104.     public int key;
     
105.     public int value;
     
106.     public DoubleLinkedListNode pre;
     
107.     public DoubleLinkedListNode next;
     
108.    
     
109.     public DoubleLinkedListNode(int key, int value)
     
110.     {
     
111.         this.value = value;
     
112.         this.key = key;
     
113.     }
     
114. }

复制代码

Insert interval:  https://leetcode.com/problems/insert-interval/

idea： 此题要考虑三种情况，还是有点小难度，就是把数学例子变成代码

1. 
   
2. public class Solution {
   
3.     public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
   
4.         List<Interval> result = new ArrayList<Interval>();
   
5.         for(Interval interval : intervals)
   
6.         {
   
7.             if(interval.end < newInterval.start)
   
8.             {
   
9.                 result.add(interval);
   
10.             }
    
11.             else if(interval.start > newInterval.end)
    
12.             {
    
13.                 result.add(newInterval);
    
14.                 newInterval = interval;
    
15.             }else if(interval.end >= newInterval.start || interval.start <= newInterval.end)
    
16.             {
    
17.                 newInterval = new Interval(Math.min(interval.start,newInterval.start), Math.max(interval.end,newInterval.end));
    
18.             }
    
19.         }
    
20.         result.add(newInterval);
    
21.         return result;
    
22.     }
    
23. }

复制代码

Permutations:  https://leetcode.com/problems/permutations/
idea: 代码不难看懂

1. 
   
2. public class Solution {
   
3.     public ArrayList<ArrayList<Integer>> permute(int[] nums) {
   
4.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
   
5.         
   
6.         result.add(new ArrayList<Integer>());
   
7.         
   
8.         for( int i = 0; i < nums.length; i++)
   
9.         {
   
10.             ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>();
    
11.             for(ArrayList<Integer> l : result)
    
12.             {
    
13.                 for(int j = 0; j < l.size()+1; j++)
    
14.                 {
    
15.                     l.add(j, nums);
    
16.                     
    
17.                     ArrayList<Integer> temp = new ArrayList<Integer>(l);
    
18.                     current.add(temp);
    
19.                     
    
20.                     l.remove(j);
    
21.                 }
    
22.             }
    
23.             result = new ArrayList<ArrayList<Integer>>(current);
    
24.         }
    
25.         return result;
    
26.     }
    
27. }

复制代码

calalia 发表于 2015-5-30 22:13
楼楼加油~~

向你看齐，谢谢

正能量。谢谢楼主分享

annawuyi 发表于 2015-6-2 18:41
正能量。谢谢楼主分享

谢谢支持。

Merge two sorted lists:  https://leetcode.com/problems/merge-two-sorted-lists/
idea： 此题也比较容易了

1. public class Solution {
   
2.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
   
3.         ListNode p1 = l1;
   
4.         ListNode p2 = l2;
   
5.         
   
6.         ListNode resultHead = new ListNode(0);
   
7.         ListNode p = resultHead;
   
8.         
   
9.         while(p1 != null && p2 != null)
   
10.         {
    
11.             if(p1.val <= p2.val)
    
12.             {
    
13.                 p.next = p1;
    
14.                 p1 = p1.next;
    
15.             }
    
16.             else
    
17.             {
    
18.                 p.next = p2;
    
19.                 p2 = p2.next;
    
20.             }
    
21.             p = p.next;
    
22.         }
    
23.         if(p1 != null)
    
24.         {
    
25.             p.next = p1;
    
26.         }
    
27.         if(p2 != null)
    
28.         {
    
29.             p.next = p2;
    
30.         }
    
31.         return resultHead.next;
    
32.     }
    
33. }

复制代码

Contains duplicate:  https://leetcode.com/problems/contains-duplicate/
idea：此题很容易，用到hashset

1. 
   
2. public class Solution {
   
3.     public boolean containsDuplicate(int[] nums) {
   
4.         HashSet<Integer> set = new HashSet<Integer>();
   
5.         
   
6.         for(int i =0; i < nums.length; i++)
   
7.         {
   
8.             if(set.contains(nums))
   
9.             {
   
10.                 return true;
    
11.             }
    
12.             else
    
13.             {
    
14.                 set.add(nums);
    
15.             }
    
16.         }
    
17.         return false;
    
18.     }
    
19. }

复制代码