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

zhuli19901106 发表于 2015-6-26 11:23
刚ac掉这题，今天主要在刷lintcode，所以leetcode放了一会儿。
这题已经排好序了，线性扫一遍就行。

我看看你的代码？

love1point 发表于 2015-6-26 11:26
我看看你的代码？

不太好吧。。我一般都是想破了头实在做不出来，才看别人代码的。建议再想一下，这题O(n)复杂度能搞定的。

love1point 发表于 2015-6-26 11:26
我看看你的代码？

要搜答案的话，github上很多人都有自己的leetcode repo，所以其实答案随手就有的，如果看了就等于认输了。

Summary ranges:    https://leetcode.com/problems/summary-ranges/
idea: 记得这两行代码  right++;
                left = right;


以及这行
    if(left == right)
                {
                    result.add(String.valueOf(nums[left]));
                }

1. public class Solution {
   
2.     public ArrayList<String> summaryRanges(int[] nums) {
   
3.         ArrayList<String> result = new ArrayList<String>();
   
4.         if(nums == null || nums.length == 0)
   
5.         {
   
6.             return result;
   
7.         }
   
8.         
   
9.         int left = 0;
   
10.         int right = 0;
    
11.         while(right < nums.length)
    
12.         {
    
13.             if(right + 1 < nums.length && nums[right] + 1 == nums[right + 1])
    
14.             {
    
15.                     right++;
    
16.             }
    
17.             else
    
18.             {
    
19.                 if(left == right)
    
20.                 {
    
21.                     result.add(String.valueOf(nums[left]));
    
22.                 }
    
23.                 else
    
24.                 {
    
25.                     result.add(String.valueOf(nums[left] + "->" + nums[right]));
    
26.                 }
    
27.                   
    
28.                 right++;
    
29.                 left = right;
    
30.             }
    
31.         }
    
32.         return result;
    
33.     }
    
34. }

复制代码

zhuli19901106 发表于 2015-6-26 11:30
不太好吧。。我一般都是想破了头实在做不出来，才看别人代码的。建议再想一下，这题O(n)复杂度能搞定的。

我的代码在154层。

刚一直time limit exceeded.
就是下面这个if导致的，搞了很久。平时我就习惯写两个 if 嵌套着，结果就是超时，很奇怪。我一开始这么写，一直检查不出来。我一直以为o(n)时间是不是不行，所以刚才想看看你的代码
if(right + 1 < nums.length)
{
     if(nums[right] + 1 == nums[right + 1])
}


-----------------------------------------
   if(right + 1 < nums.length && nums[right] + 1 == nums[right + 1])
            {
                    right++;
            }

赞赞赞赞赞赞

love1point 发表于 2015-6-26 12:51
我的代码在154层。

刚一直time limit exceeded.

好吧，我的代码：

1. class Solution {
   
2. public:
   
3.     vector<string> summaryRanges(vector<int>& nums) {
   
4.         vector<string> ans;
   
5.         string s;
   
6.         int i, j;
   
7.         int n = nums.size();
   
8.         
   
9.         i = 0;
   
10.         while (i < n) {
    
11.             j = i + 1;
    
12.             while (j < n && nums[j - 1] + 1 == nums[j]) {
    
13.                 ++j;
    
14.             }
    
15.             if (j == i + 1) {
    
16.                 s = to_string(nums[i]);
    
17.             } else {
    
18.                 s = to_string(nums[i]) + "->" + to_string(nums[i] + j - i - 1);
    
19.             }
    
20.             ans.push_back(s);
    
21.             i = j;
    
22.         }
    
23.         return ans;
    
24.     }
    
25. };
    

复制代码

多个if条件尽量并列吧，否则嵌了太多层的话，代码可读性简直毁了。&&和||的短路逻辑经常会用到，可以让代码简短点。

还有就是碰见vector<vector<bool> > &matrix的时候，可以用typedef给起个别名，缩短代码长度。<br/>
还可以用个vector<vector<bool> > &a = matrix; 也是取个别名，这样代码长度也可以变短。<br/>
这种类型定义很长的情况在leetcode里还挺常见，再比如unordered_map<TreeNode *， unordered_set<TreeNode *> >::iterator，面试的时候要是手写就累死了。<br/>(囧。。还以为编辑用的是html)

zhuli19901106 发表于 2015-6-26 13:12
好吧，我的代码：多个if条件尽量并列吧，否则嵌了太多层的话，代码可读性简直毁了。&&和||的短路逻辑经常 ...

嗯，我刚并列 if 后就ac过了。

只是觉得超时是for循环导致的，感觉if就是o(1)，估计lc对这要求高了点

love1point 发表于 2015-6-26 13:22
嗯，我刚并列 if 后就ac过了。

只是觉得超时是for循环导致的，感觉if就是o(1)，估计lc对这要求高了点

请注意TLE很可能是因为错误逻辑导致的死循环。。而不是算法的效率不过关