Algorithm
接着优化上周的算法题680. 验证回文字符串 Ⅱ.
看了官方的贪心做法,自己搞了一把,结果优点意外呀.
#include <iostream>
#include <string>
using namespace std;class Solution {
public://bool IsSeriousvalidPalindrome(string s){int i = 0;int j = s.size() - 1;while(i < j){if(s[i] == s[j]){i++;j--;}else{return false;}}return true;}bool validPalindrome(string s) {int i = 0;int j = s.size()-1;while(i < j){if(s[i] == s[j]){i++;j--;}else{//删除i位置 abcastring s1 = s.substr(i+1, j-i); //返回[i+1, j] //注意第2个参数表示个数bool b1 = IsSeriousvalidPalindrome(s1);//删除j位置s1 = s.substr(i, j-i); //返回[i, j) //bool b2 = IsSeriousvalidPalindrome(s1);//如果两者之一是回文,最终是回文if(b1 || b2){return true;}else{return false;}}}return true;}
};
发现占用内存比较大,把IsSeriousvalidPalindrome(string s)入参改为(const string& s),内存有所提升,但是还是占用比较大.
发现主要内存消耗在string s1在每个循环里都要分配内存,可以考虑不对它进行分配.可以把位置信息传进来,而没必要进行字符串的截取.
#include <iostream>
#include <string>
using namespace std;class Solution {
public://bool IsSeriousvalidPalindrome(const string& s, int i, int j){while(i < j){if(s[i] == s[j]){i++;j--;}else{return false;}}return true;}bool validPalindrome(string s) {int i = 0;int j = s.size()-1;while(i < j){if(s[i] == s[j]){i++;j--;}else{//1. 可以省略的函数调用后赋值// //删除i位置// bool b1 = IsSeriousvalidPalindrome(s, i+1, j);// //删除j位置// bool b2 = IsSeriousvalidPalindrome(s, i, j-1);//如果两者之一是回文,最终是回文//下面的那个条件判断有些多余return (IsSeriousvalidPalindrome(s, i+1, j) || IsSeriousvalidPalindrome(s, i, j-1));// if(IsSeriousvalidPalindrome(s, i+1, j) || IsSeriousvalidPalindrome(s, i, j-1))// {// return true;// }// else// {// return false;// }}}return true;}
};
这个效果还不错,注意代码精简的可以省略一些调用函数的中间变量.
Review
How To Ask Questions The Smart Way(4/8)
Make it easy to reply
Finishing your query with “Please send your reply to... ” makes it quite unlikely you will get an answer. If you can't be bothered to take even the few seconds required to set up a correct Reply-To header in your mail agent, we can't be bothered to take even a few seconds to think about your problem. If your mail program doesn't permit this, get a better mail program. If your operating system doesn't support any e-mail programs that permit this, get a better operating system.
In Web forums, asking for a reply by e-mail is outright rude, unless you believe the information may be sensitive (and somebody will, for some unknown reason, let you but not the whole forum know it). If you want an e-mail copy when somebody replies in the thread, request that the Web forum send it; this feature is supported almost everywhere under options like “watch this thread”, “send e-mail on answers”, etc.
We've found by experience that people who are careless and sloppy writers are usually also careless and sloppy at thinking and coding (often enough to bet on, anyway). Answering questions for careless and sloppy thinkers is not rewarding; we'd rather spend our time elsewhere.
So expressing your question clearly and well is important. If you can't be bothered to do that, we can't be bothered to pay attention. Spend the extra effort to polish your language. It doesn't have to be stiff or formal — in fact, hacker culture values informal, slangy and humorous language used with precision. But it has to beprecise; there has to be some indication that you're thinking and paying attention.
Spell, punctuate, and capitalize correctly. Don't confuse “its” with “it's”, “loose” with “lose”, or “discrete” with “discreet”. Don't TYPE IN ALL CAPS; this is read as shouting and considered rude. (All-smalls is only slightly less annoying, as it's difficult to read. Alan Cox can get away with it, but you can't.)
More generally, if you write like a semi-literate boob you will very likely be ignored. So don't use instant-messaging shortcuts. Spelling "you" as "u" makes you look like a semi-literate boob to save two entire keystrokes. Worse: writing like a l33t script kiddie hax0r is the absolute kiss of death and guarantees you will receive nothing but stony silence (or, at best, a heaping helping of scorn and sarcasm) in return.
If you are asking questions in a forum that does not use your native language, you will get a limited amount of slack for spelling and grammar errors — but no extra slack at all for laziness (and yes, we can usually spot that difference). Also, unless you know what your respondent's languages are, write in English. Busy hackers tend to simply flush questions in languages they don't understand, and English is the working language of the Internet. By writing in English you minimize your chances that your question will be discarded unread.
If you are writing in English but it is a second language for you, it is good form to alert potential respondents to potential language difficulties and options for getting around them. Examples:
-
English is not my native language; please excuse typing errors.
-
If you speak $LANGUAGE, please email/PM me; I may need assistance translating my question.
-
I am familiar with the technical terms, but some slang expressions and idioms are difficult for me.
-
I've posted my question in $LANGUAGE and English. I'll be glad to translate responses, if you only use one or the other.
If you make your question artificially hard to read, it is more likely to be passed over in favor of one that isn't. So:
-
Send plain text mail, not HTML. (It's not hard to turn off HTML.)
-
MIME attachments are usually OK, but only if they are real content (such as an attached source file or patch), and not merely boilerplate generated by your mail client (such as another copy of your message).
-
Don't send e-mail in which entire paragraphs are single multiply-wrapped lines. (This makes it too difficult to reply to just part of the message.) Assume that your respondents will be reading mail on 80-character-wide text displays and set your line wrap accordingly, to something less than 80.
-
However, do not wrap data (such as log file dumps or session transcripts) at any fixed column width. Data should be included as-is, so respondents can have confidence that they are seeing what you saw.
-
Don't send MIME Quoted-Printable encoding to an English-language forum. This encoding can be necessary when you're posting in a language ASCII doesn't cover, but many e-mail agents don't support it. When they break, all those =20 glyphs scattered through the text are ugly and distracting — or may actively sabotage the semantics of your text.
-
Never, ever expect hackers to be able to read closed proprietary document formats like Microsoft Word or Excel. Most hackers react to these about as well as you would to having a pile of steaming pig manure dumped on your doorstep. Even when they can cope, they resent having to do so.
-
If you're sending e-mail from a Windows machine, turn off Microsoft's problematic “Smart Quotes” feature (From Tools > AutoCorrect Options, clear the smart quotes checkbox under AutoFormat As You Type.). This is so you'll avoid sprinkling garbage characters through your mail.
-
In Web forums, do not abuse “smiley” and “HTML” features (when they are present). A smiley or two is usually OK, but colored fancy text tends to make people think you are lame. Seriously overusing smileys and color and fonts will make you come off like a giggly teenage girl, which is not generally a good idea unless you are more interested in sex than answers.
If you're using a graphical-user-interface mail client such as Netscape Messenger, MS Outlook, or their ilk, beware that it may violate these rules when used with its default settings. Most such clients have a menu-based “View Source” command. Use this on something in your sent-mail folder, verifying sending of plain text without unnecessary attached crud.
Be precise and informative about your problem
-
Describe the symptoms of your problem or bug carefully and clearly.
-
Describe the environment in which it occurs (machine, OS, application, whatever). Provide your vendor's distribution and release level (e.g.: “Fedora Core 7”, “Slackware 9.1”, etc.).
-
Describe the research you did to try and understand the problem before you asked the question.
-
Describe the diagnostic steps you took to try and pin down the problem yourself before you asked the question.
-
Describe any possibly relevant recent changes in your computer or software configuration.
-
If at all possible, provide a way to reproduce the problem in a controlled environment.
Do the best you can to anticipate the questions a hacker will ask, and answer them in advance in your request for help.
Giving hackers the ability to reproduce the problem in a controlled environment is especially important if you are reporting something you think is a bug in code. When you do this, your odds of getting a useful answer and the speed with which you are likely to get that answer both improve tremendously.
Simon Tatham has written an excellent essay entitled How to Report Bugs Effectively. I strongly recommend that you read it.
You need to be precise and informative. This end is not served by simply dumping huge volumes of code or data into a help request. If you have a large, complicated test case that is breaking a program, try to trim it and make it as small as possible.
This is useful for at least three reasons. One: being seen to invest effort in simplifying the question makes it more likely you'll get an answer, Two: simplifying the question makes it more likely you'll get a useful answer. Three: In the process of refining your bug report, you may develop a fix or workaround yourself.
When you are having problems with a piece of software, don't claim you have found a bug unless you are very, very sure of your ground. Hint: unless you can provide a source-code patch that fixes the problem, or a regression test against a previous version that demonstrates incorrect behavior, you are probably not sure enough. This applies to webpages and documentation, too; if you have found a documentation “bug”, you should supply replacement text and which pages it should go on.
Remember, there are many other users that are not experiencing your problem. Otherwise you would have learned about it while reading the documentation and searching the Web (you did do that before complaining, didn't you?). This means that very probably it is you who are doing something wrong, not the software.
The people who wrote the software work very hard to make it work as well as possible. If you claim you have found a bug, you'll be impugning their competence, which may offend some of them even if you are correct. It's especially undiplomatic to yell “bug” in the Subject line.
When asking your question, it is best to write as though you assume you are doing something wrong, even if you are privately pretty sure you have found an actual bug. If there really is a bug, you will hear about it in the answer. Play it so the maintainers will want to apologize to you if the bug is real, rather than so that you will owe them an apology if you have messed up.
使问题容易回复
以请将你的回复寄到……来结束你的问题多半会使你得不到回答。如果你觉得花几秒钟在邮件客户端设置一下回复地址都麻烦，我们也觉得花几秒钟思考你的问题更麻烦。如果你的邮件程序不支持这样做，换个好点的；如果是操作系统不支持这种邮件程序，也换个好点的。
在论坛，要求通过电子邮件回复是非常无礼的，除非你相信回复的信息可能比较敏感(而且有人会为了某些未知的原因，只让你而不是整个论坛知道答案)。如果你只是想在有人回复讨论串时得到电子邮件提醒，可以要求网页论坛发送给你。几乎所有论坛都支持诸如追踪此讨论串、有回复时发送邮件提醒等功能。
用清晰、正确、精准并语法正确的语句
我们从经验中发现，粗心的提问者通常也会粗心的写程序与思考(我敢打包票)。回答粗心大意者的问题很不值得，我们宁愿把时间耗在别处。
正确的拼字、标点符号和大小写是很重要的。一般来说，如果你觉得这样做很麻烦，不想在乎这些，那我们也觉得麻烦，不想在乎你的提问。花点额外的精力斟酌一下字句，用不着太僵硬与正式 -- 事实上，黑客文化很看重能准确地使用非正式、俚语和幽默的语句。但它**必须很**准确，而且有迹象表明你是在思考和关注问题。
正确地拼写、使用标点和大小写，不要将its混淆为it's，loose搞成lose或者将discrete弄成discreet。不要全部用大写，这会被视为无礼的大声嚷嚷(全部小写也好不到哪去，因为不易阅读。Alan Cox也许可以这样做，但你不行。)
更白话的说，如果你写得像是个半文盲[译注：小白])，那多半得不到理睬。也不要使用即时通讯中的简写或火星文，如将的简化为ㄉ会使你看起来像一个为了少打几个键而省字的小白。更糟的是，如果像个小孩似地鬼画符那绝对是在找死，可以肯定没人会理你(或者最多是给你一大堆指责与挖苦)。
如果在使用非母语的论坛提问，你可以犯点拼写和语法上的小错，但决不能在思考上马虎(没错，我们通常能弄清两者的分别)。同时，除非你知道回复者使用的语言，否则请使用英语书写。繁忙的黑客一般会直接删除用他们看不懂语言写的消息。在网络上英语是通用语言，用英语书写可以将你的问题在尚未被阅读就被直接删除的可能性降到最低。
如果英文是你的外语(Second language)，提示潜在回复者你有潜在的语言困难是很好的： [译注：以下附上原文以供使用]
English is not my native language; please excuse typing errors.
- 英文不是我的母语，请原谅我的错字或语法
If you speak $LANGUAGE, please email/PM me; I may need assistance translating my question.
- 如果你说某语言，请寄信/私讯给我；我需要有人协助我翻译我的问题
I am familiar with the technical terms, but some slang expressions and idioms are difficult for me.
- 我对技术名词很熟悉，但对于俗语或是特别用法比较不甚了解。
I've posted my question in $LANGUAGE and English. I'll be glad to translate responses, if you only use one or the other.
- 我把我的问题用某语言和英文写出来，如果你只用一种语言回答，我会乐意将其翻译成另一种。
使用易于读取且标准的文件格式发送问题
如果你人为地将问题搞得难以阅读，它多半会被忽略，人们更愿读易懂的问题，所以：
- 使用纯文字而不是HTML (关闭HTML并不难)
- 使用MIME附件通常是可以的，前提是真正有内容(譬如附带的源代码或patch)，而不仅仅是邮件程序生成的模板(譬如只是信件内容的拷贝)。
- 不要发送一段文字只是单行句子但多次断行的邮件(这使得回复部分内容非常困难)。设想你的读者是在80个字符宽的终端机上阅读邮件，最好设置你的断行点小于80字。
- 但是，也**不要**用任何固定断行资料(譬如日志档案拷贝或会话记录)。档案应该原样包含，让回复者有信心他们看到的是和你看到的一样的东西。
- 在英语论坛中，不要使用
Quoted-PrintableMIME编码发送消息。这种编码对于张贴非ASCII语言可能是必须的，但很多邮件程序并不支持这种编码。当它们分断时，那些文本中四处散布的=20符号既难看也分散注意力，甚至有可能破坏内容的语意。 - 绝对，**永远**不要指望黑客们阅读使用封闭格式编写的文档，像是微软公司的Word或Excel文件等。大多数黑客对此的反应就像有人将还在冒热气的猪粪倒在你门口阶梯上时你的反应一样。即便他们能够处理，他们也很厌恶这么做。
- 如果你从使用Windows的电脑发送电子邮件，关闭微软愚蠢的
智能引号功能 (从[选项] > [校订] > [自动校正选项], 按掉智能引号单选框)，以免在你的邮件中到处散布垃圾字符。 - 在论坛，勿滥用
表情符号和HTML功能(当它们提供时)。一两个表情符号通常没有问题，但花哨的彩色文本倾向于使人认为你是个无能之辈。过滥地使用表情符号、色彩和字体会使你看来像个傻笑的小姑娘。这通常不是个好主意，除非你只是对sex而不是有用的回复更有兴趣。
如果你使用图形用户界面的邮件程序(如微软公司的Outlook或者其它类似的)，注意它们的默认设置不一定满足这些要求。大多数这类程序有基于选单的查看源代码命令，用它来检查发送文件夹中的消息，以确保发送的是没有多餘杂质的纯文本文件。
精确的描述问题并言之有物
- 仔细、清楚地描述你的问题或Bug的症状。
- 描述问题发生的环境(机器配置、操作系统、应用程序、以及相关的信息)，提供经销商的发行版和版本号(如：
Fedora Core 4、Slackware 9.1等)。 - 描述在提问前你是怎样去研究和理解这个问题的。
- 描述在提问前为确定问题而采取的诊断步骤。
- 描述最近做过什么可能相关的硬件或软件变更。
- 尽可能的提供一个可以
重现这个问题的既定环境的方法
尽量去揣测一个黑客会怎样反问你，在他提问的时候预先给他答案。
以上几点中，当你报告的是你认为可能在代码中的问题时，给黑客一个可以重现你的问题的环境尤其重要。当你这么做时，你得到有效的回答的机会和速度都会大大的提升。
Simon Tatham写过一篇名为《如何有效的报告Bug》的出色文章。强力推荐你也读一读。
话不在多而在精
你需要提供精确有内容的信息。这并不是要求你简单的把成堆的出错代码或者资料完全转录到你的提问中。如果你有庞大而复杂的测试样例能重现程序挂掉的情境，尽量将它剪裁得越小越好。
这样做的用处至少有三点。 第一，表现出你为简化问题付出了努力，这可以使你得到回答的机会增加； 第二，简化问题使你更有可能得到**有用**的答案； 第三，在精炼你的bug报告的过程中，你很可能就自己找到了解决方法或权宜之计。
别动辄声称找到Bug
当你在使用软件中遇到问题，除非你非常、**非常**的有根据，不要动辄声称找到了Bug。提示：除非你能提供解决问题的源代码补丁，或者对前一版本的回归测试表现出不正确的行为，否则你都多半不够完全确信。这同样适用在网页和文件，如果你(声称)发现了文件的Bug，你应该能提供相应位置的修正或替代文件。
请记得，还有许多其它使用者没遇到你发现的问题，否则你在阅读文件或搜索网页时就应该发现了(你在抱怨前已经做了这些，是吧？)。这也意味着很有可能是你弄错了而不是软件本身有问题。
编写软件的人总是非常辛苦地使它尽可能完美。如果你声称找到了Bug，也就是在质疑他们的能力，即使你是对的，也有可能会冒犯到其中某部分人。这尤其严重当你在标题中嚷嚷着有Bug。
提问时，即使你私下非常确信已经发现一个真正的Bug，最好写得像是**你**做错了什么。如果真的有Bug，你会在回复中看到这点。这样做的话，如果真有Bug，维护者就会向你道歉，这总比你惹恼别人然后欠别人一个道歉要好一点。
Tips
1.早起倒逼早睡,加入团队能够让自己更容易坚持.
2.少玩手机,少看微信,感觉无聊或者困倦时深呼吸或者冥想.
