一亩三分地论坛

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

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

[Leetcode] 真心照不出错误,在自己电脑上也跑出了所有的可能的结果。

[复制链接] |试试Instant~ |关注本帖
tobias0705 发表于 2014-7-22 01:46:16 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 tobias0705 于 2014-7-22 10:34 编辑

这道题是吧输入的一句话反过来。但是就是找不到我的代码的错误在哪里。leetcode上说runtime error。告诉我再输入“a”的时候出了问题。但是我在自己电脑上也试过了,没问题啊。
求各位帮我看看。谢谢啦。
  1. #include"iostream"
  2. #include"string"
  3. #include"solutions.h"

  4. using namespace std;

  5. void main(void)
  6. {
  7.         string myStr("             ");

  8.         solution mySln;

  9.         cout << myStr << endl;
  10.         
  11.         mySln.strRev1(myStr);

  12.         cout << myStr << endl;

  13.         cout << myStr.at(0) << endl;

  14.         system("PAUSE");
  15. }

  16. /***********Class Definition*********/
  17. /***********solutions.h***********/
  18. #pragma once;
  19. #ifndef SOLUTION
  20. #define SOLUTION

  21. #include"string"
  22. #include"iostream"
  23. #include<assert.h>

  24. using namespace std;

  25. class solution
  26. {

  27. public:

  28.         void strRev(string &s);

  29. //protected:

  30. };

  31. void solution::strRev(string &s)
  32. {

  33.         int wordLen = 0, len, start = s.length();

  34.         string temp;

  35.         if (s.length() != 0)
  36.         {
  37.                 while (s.at(0) == ' ') s.erase(0, 1); // Delete the spaces ahead.

  38.                 len = s.length();

  39.                 while (s.at(len - 1) == ' ') // Delete the space consecutivly.
  40.                 {
  41.                         s.erase(len - 1, 1);

  42.                         len = s.length();
  43.                 }


  44.                 for (int i = len - 1; i >= 0; i--)
  45.                 {
  46.                         wordLen += 1;

  47.                         if (i <= len - 1)
  48.                         {
  49.                                 if ((s.at(i) == ' ') && (s.at(i + 1) != ' '))
  50.                                 {
  51.                                         start = i;

  52.                                         temp.append(s, start + 1, wordLen - 1);
  53.                                         temp.append(" ");

  54.                                         wordLen = 0;
  55.                                 }
  56.                                 else if ((s.at(i) == ' ') && (s.at(i + 1) == ' '))
  57.                                 {
  58.                                         s.erase(i, 1);

  59.                                         len = s.length();

  60.                                         wordLen = 0;
  61.                                 }
  62.                                 else if (i == 0)
  63.                                 {
  64.                                         start = i;

  65.                                         temp.append(s, start, wordLen);

  66.                                         wordLen = 0;
  67.                                 }
  68.                         }
  69.                 }

  70.                 s.assign(temp);
  71.         }
  72.         else
  73.         {
  74.                 printf("\nThere is not any words in this sentencs. \n");
  75.         }
  76. }
  77. #endif
复制代码
sqzhang17 发表于 2014-7-22 01:55:41 | 显示全部楼层
没学过C++~(这是C++吧~)~我使用java~
但是我如果遇上lz这样的问题一般都是每一步都print语句输出结果~看看这个结果是不是你想要的~如果不是的话肯定就是有问题了呗~然后再去检查你的逻辑上有没有什么问题~最后检查有没有syntax的问题~虽然麻烦点~但是找到错误后的印象会很深刻~帮顶了~
回复 支持 反对

使用道具 举报

 楼主| tobias0705 发表于 2014-7-22 02:01:16 | 显示全部楼层
sqzhang17 发表于 2014-7-22 01:55
没学过C++~(这是C++吧~)~我使用java~
但是我如果遇上lz这样的问题一般都是每一步都print语句输出结果~看 ...

十分感谢!这是C++,楼主的java用的不顺手。。。。所以就用C++了。
回复 支持 反对

使用道具 举报

ralf 发表于 2014-7-22 02:08:50 | 显示全部楼层
楼主试一下输入为" "就知道了
回复 支持 反对

使用道具 举报

ralf 发表于 2014-7-22 02:19:14 | 显示全部楼层
本帖最后由 ralf 于 2014-7-22 02:20 编辑

顺便附上自己的删除头尾空格的函数
  1. string whitespaces(" \t\f\v\n\r");
复制代码
  1. void trim(string& str)
  2. {
  3.        string::size_type pos = str.find_last_not_of(whitespaces);
  4.        if(pos != string::npos)
  5.        {
  6.               str.erase(pos + 1);
  7.               pos = str.find_first_not_of(whitespaces);
  8.               if(pos != string::npos)
  9.                     str.erase(0, pos);
  10.        }
  11.        else
  12.              str.clear();
  13. }
复制代码
回复 支持 反对

使用道具 举报

ralf 发表于 2014-7-22 02:26:47 | 显示全部楼层
另外不建议在leetcode oj里输出到标准输出,类似这种“printf("\nThere is not any words in this sentencs. \n"); “  如果字符串为空return就好了,输出到标准输出可能会干扰oj的判断
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2014-7-22 02:29:08 | 显示全部楼层
没有仔细分析楼主的逻辑,但是一看楼主的代码就知道run time error问题在哪了。楼主在代码中用到了很多C++的函数,请楼主回答以下几个问题:
(1). s.length() 时间复杂度多少?
(2). s.erase() 时间复杂度多少?
(3). s.append() 时间复杂度多少?
(4). s.assign() 时间复杂度多少?
(5). 甚至我还想问一下s.at()时间复杂度多少?(当然这个肯定是O(1)).
我觉得lz既然是耍算法题,涉及到时间复杂度的,尽量少用那些函数,因为你要确定你知道你所用的函数究竟花费了多少时间,并不是说就一行代码就一定是O(1)的。比如s.erase()函数,我很久不写代码了不记得C++内部这个函数具体时间复杂度是多少了,但是很可能这个函数是o(n)的时间+ o(n)的空间,更不要提append()函数了,append()函数肯定是O(n)的时间复杂度(如果你实现没有给这个字符串分配足够内存的话,比如c++的reserve()函数可以提前分配好足够的 空间,这样你append的时候就可以直接在后面添加,就是O(1)的。但是通常append都是要在内存中寻找一个足够大的地方,然后把原字符串copy过去,末尾加上你要append的字符)。我没有仔细看楼主的逻辑也没有分析时间复杂度,但是我就是依据我的理解给楼主提个醒,如果你用那么多函数,你就要心里十分明白这些c++函数内部具体是如何实现的,时间复杂度是多少,这样你才能知道你的程序的具体的时间复杂度是多少。
回复 支持 反对

使用道具 举报

smzfeng 发表于 2014-7-22 02:37:24 | 显示全部楼层
luzhuzeng 发表于 2014-7-21 13:29
没有仔细分析楼主的逻辑,但是一看楼主的代码就知道run time error问题在哪了。楼主在代码中用到了很多C++ ...

我的理解是 runtime error和时间复杂度没有关系吧?
回复 支持 反对

使用道具 举报

一剑终情 发表于 2014-7-22 02:40:08 | 显示全部楼层
luzhuzeng 发表于 2014-7-21 12:29
没有仔细分析楼主的逻辑,但是一看楼主的代码就知道run time error问题在哪了。楼主在代码中用到了很多C++ ...

虽然说的很好,可是时间复杂度跟run time error没关系啊
回复 支持 反对

使用道具 举报

ralf 发表于 2014-7-22 02:41:43 | 显示全部楼层
smzfeng 发表于 2014-7-22 02:37
我的理解是 runtime error和时间复杂度没有关系吧?

re一个,算法太慢超时是 time limit exceed
回复 支持 反对

使用道具 举报

 楼主| tobias0705 发表于 2014-7-22 03:25:49 | 显示全部楼层
ralf 发表于 2014-7-22 02:08
楼主试一下输入为" "就知道了

输入了这个没有问题..
回复 支持 反对

使用道具 举报

 楼主| tobias0705 发表于 2014-7-22 03:26:08 | 显示全部楼层
ralf 发表于 2014-7-22 02:19
顺便附上自己的删除头尾空格的函数

谢谢啦,我来参考一下。
回复 支持 反对

使用道具 举报

 楼主| tobias0705 发表于 2014-7-22 03:27:41 | 显示全部楼层
ralf 发表于 2014-7-22 02:26
另外不建议在leetcode oj里输出到标准输出,类似这种“printf("\nThere is not any words in this sentencs ...

明白啦~谢谢你
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2014-7-22 05:31:46 | 显示全部楼层
一剑终情 发表于 2014-7-21 12:40
虽然说的很好,可是时间复杂度跟run time error没关系啊

哦,抱歉都快忘记了这些错误之间的区别了...可能我说错了吧,楼主见谅
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2014-7-22 05:31:53 | 显示全部楼层
ralf 发表于 2014-7-21 12:41
re一个,算法太慢超时是 time limit exceed

哦,抱歉都快忘记了这些错误之间的区别了...可能我说错了吧,楼主见谅
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2014-7-22 05:32:46 | 显示全部楼层
smzfeng 发表于 2014-7-21 12:37
我的理解是 runtime error和时间复杂度没有关系吧?

哦,抱歉都快忘记了这些错误之间的区别了...可能我说错了吧,楼主见谅
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2014-7-22 05:51:05 | 显示全部楼层
补充一下,我太久不写程序了,SB到把Runtime error都理解错了。楼主和各位大神见谅。又仔细研究了一下lz的代码,觉得可能出问题的地方列一下,大家一起探讨:
(1). while (s.at(0) == ' ') s.erase(0, 1); // Delete the spaces ahead.
这一点如果对于全部是空格的s来说,s.at(0)会不会出问题.查了一下C++中at()函数,"The function automatically checks whether pos is the valid position of a character in the string (i.e., whether pos is less than the string length), throwing an out_of_range exception if it is not." 这样说的话如果s全是空字符,那么最终s的length会变成0,那么s.at(0)就会在内部抛出异常。所以lz可以尝试更改成while(s.length > 0 && s.at(0)==' ')来尽量避免这个;
(2).同样的道理,如果s全是空字符,那么在
if (s.length() != 0)
        {
                while (s.at(0) == ' ') s.erase(0, 1); // Delete the spaces ahead.

                len = s.length();

                while (s.at(len - 1) == ' ') // Delete the space consecutivly.
                {
                        s.erase(len - 1, 1);

                        len = s.length();
                }
这也会有同样的问题,因为此时s.length 是0,也就是len是0,那么你的s.at(len - 1)的定位是-1,应该是错误的;同样的问题会引起erase函数的错误,比如erase怎么能从-1的index开始erase呢?
lz可以先改一下这一点,估计就问题不大了,后面的暂时不分析了。楼主在刚开始分成了s.length 等于0和不等于0两种情况,但是要注意的是,在if(s.length() != 0)这个大括号中,随时会出现s.length() == 0的情况,所以在这个if语句中也要随时注意判断s的长度是否为0,否则就容易出错。这题本来就不难,考察的就是细节以及你是否思维缜密,你用那么多函数意义真不大,分析起来时间空间复杂度都不容易,直接利用c的类似指针的东西从头到尾来一遍就行了,另外弄一个大小一样的字符串,o(n)时间+O(n)空间很容易就出来了(如果你要优化空间的话另说)。一点个人看法,说错了见谅,一起讨论
回复 支持 反对

使用道具 举报

lyl 发表于 2014-7-22 07:19:48 | 显示全部楼层
luzhuzeng 发表于 2014-7-22 02:29
没有仔细分析楼主的逻辑,但是一看楼主的代码就知道run time error问题在哪了。楼主在代码中用到了很多C++ ...

对不起 我笑了。。。
回复 支持 反对

使用道具 举报

lzd1127 发表于 2014-7-22 07:24:47 | 显示全部楼层
lyl 发表于 2014-7-22 07:19
对不起 我笑了。。。

笑啥?有空笑,不能给点insights?
回复 支持 反对

使用道具 举报

ssx2014 发表于 2014-7-22 08:27:46 | 显示全部楼层
lyl 发表于 2014-7-22 07:19
对不起 我笑了。。。

虽然有点离题,但不说的挺好的嘛。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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