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

zhuli19901106 发表于 2015-6-27 17:36
那这数据可太宽容了，稍微严格点的OJ也不会让过的。

你要推到极端，那100 万个节点迭代也有可能超时啊

love1point 发表于 2015-6-27 17:45
你要推到极端，那100 万个节点迭代也有可能超时啊

这就极端了么。。对于非递归的O(n)的算法，100万~500万的数据大致运行时间是1s
如果用递归，要么爆栈退出，要么因为频繁的函数调用而超时。你可以试试project euler上的题目，体验过常数优化就能体会递归和迭代的效率差异了。

love1point 发表于 2015-6-27 17:45
你要推到极端，那100 万个节点迭代也有可能超时啊

话说你不关注算法效率，这样真不好~
比如strStr这种问题，你至少得在kmp和bm里会一个，否则面试官肯定不买账的。

zhuli19901106 发表于 2015-6-27 17:47
这就极端了么。。对于非递归的O(n)的算法，100万~500万的数据大致运行时间是1s
如果用递归，要么爆栈退 ...

“对于非递归的O(n)的算法，100万~500万的数据大致运行时间是1s”， 你这数据哪里来的啊， 来自某个paper？
处理不同的数据类型，时间应该也差挺多的吧? (我不确定)

对于lc里的题目，大部分树和链表递归解法都能过的哈，只是有时他们会要求迭代做法，但感觉意义不大也不是非常多

zhuli19901106 发表于 2015-6-27 17:47
这就极端了么。。对于非递归的O(n)的算法，100万~500万的数据大致运行时间是1s
如果用递归，要么爆栈退 ...

你知道的oj太多了哈，我平时大部分时间就是loop (paper, paper, paper, 实验，实验，实验)

zhuli19901106 发表于 2015-6-27 17:52
话说你不关注算法效率，这样真不好~
比如strStr这种问题，你至少得在kmp和bm里会一个，否则面试官肯定不 ...

嗯，我这一轮刷题会注意总结和算法效率

但对于strstr这题，我知道的北美大部分面试官自己本身就不会kmp，所以这题他们根本就不要求我们实现kmp, 真的。

love1point 发表于 2015-6-27 17:55
“对于非递归的O(n)的算法，100万~500万的数据大致运行时间是1s”， 你这数据哪里来的啊， 来自某个paper ...

leetcode比一般的acm式的OJ要宽容，因为面向的用户不是ACMer，而是找工作的人。
但有些面试官又是搞竞赛出身，所以他们对效率要求还是很严格的，你必须做到optimal solution才能pass。
我那个数据是从几年刷OJ感受出来的，一般都是这么个情况。而且面GF这种顶尖公司，面试官是ACMer的概率实在很大。

Remove nth node from end of list: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

idea: 双指针，一个先跑n步。然后两个指针同时跑，然后变化下指针即可

p.s. 另一种解法，还不正确，到时我再看看。  先算出链表长度，然后指针跑到要被删除节点的前一个节点，然后把要被删除节点的前一个节点的next 指向 要被删除节点的下一个。但有bug，就是这种[1], 1

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) { val = x; }
   
7. * }
   
8. */
   
9. public class Solution {
   
10.     public ListNode removeNthFromEnd(ListNode head, int n) {
    
11.         if(head == null || n <= 0)
    
12.         {
    
13.             return head;
    
14.         }
    
15.         
    
16.         ListNode helper = new ListNode(0);
    
17.         helper.next = head;
    
18.         ListNode fast = helper;
    
19.         ListNode slow = helper;
    
20.         
    
21.         for(int i = 0; i < n; i++)
    
22.         {
    
23.             fast = fast.next;
    
24.         }
    
25.         
    
26.         while(fast.next != null)
    
27.         {
    
28.             fast = fast.next;
    
29.             slow = slow.next;
    
30.         }
    
31.         
    
32.         slow.next = slow.next.next;
    
33.         
    
34.         return helper.next;
    
35.     }
    
36. }

复制代码

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. }

复制代码

3 sum closest: https://leetcode.com/problems/3sum-closest/

idea： 题目刷到后期，会发现其实套路都是一样。n sum问题大部分都是双指针，或三指针等解决。这题比较简单。一些细节注意就可以。

1. public class Solution {
   
2.     public int threeSumClosest(int[] nums, int target) {
   
3.         int result = 0;
   
4.         int min = Integer.MAX_VALUE;
   
5.         Arrays.sort(nums);
   
6.         
   
7.         for(int i = 0; i < nums.length; i++)
   
8.         {
   
9.             int j = i + 1;
   
10.             int k = nums.length - 1;
    
11.             while(j < k)
    
12.             {
    
13.                 int sum = nums[i] + nums[j] + nums[k];
    
14.                 int diff = Math.abs(sum - target);
    
15.                
    
16.                 if(diff < min)
    
17.                 {
    
18.                     min = diff;
    
19.                     result = sum;
    
20.                 }
    
21.                
    
22.                 if(sum < target)
    
23.                 {
    
24.                     j++;
    
25.                 }
    
26.                 else
    
27.                 {
    
28.                     k--;
    
29.                 }
    
30.             }
    
31.         }
    
32.         return result;
    
33.     }
    
34. }

复制代码