《左耳听风》-ARTS-打卡记录-第十二周

Algorithm350. 两个数组的交集 II这次查看了官方的做法,原来采用了哈希表的方法,真是很巧妙啊.class Solution {public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {if (0 == num...

CodingLife99

325人浏览 · 2020-08-28 20:19:00

CodingLife99 · 2020-08-28 20:19:00 发布

Algorithm

350. 两个数组的交集 II

这次查看了官方的做法,原来采用了哈希表的方法,真是很巧妙啊.

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (0 == nums1.size() || 0 == nums1.size())
        {
            return vector<int>();
        }
        else
        {
            vector<int> vecInt;
            map<int, int> hashmap;
            vector<int> vecLong = (nums1.size() >= nums2.size()) ? nums1 : nums2;
            vector<int> vecShort = (nums1.size() < nums2.size()) ? nums1 : nums2;

            //创建短数组的hashmap
            for (vector<int>::iterator i = vecShort.begin(); i != vecShort.end(); i++)
            {
                if (hashmap.find(*i) == hashmap.end())
                {
                    //hashmap.insert({ *i, 1 });
                    hashmap.insert(pair<int, int>(*i, 1));
                }
                else
                {
                    hashmap[*i]++;
                }
            }

            //遍历长数组,并处理重复的元素
            for (vector<int>::iterator i = vecLong.begin(); i != vecLong.end(); i++)
            {
                if (hashmap.find(*i) != hashmap.end())
                {
                    //如果长数组的元素在hashmap中,则hashmap中的个数自减,并把内容加到result中
                    hashmap[*i]--;
                    vecInt.push_back(*i);
                    if (hashmap[*i] == 0)
                    {
                        hashmap.erase(*i);
                    }
                    if (hashmap.size() == 0)
                    {
                        return vecInt;
                    }
                }
            }
            return vecInt;
        }
    }
};

把map改为unordered_map,发现执行时间提升了很多,原因是map是有序的字典,需要耗费一些性能.

和官方的用时差不太多,感觉官方的写法很简洁;有一点感觉官方没有考虑那就是,如果nums2和nums1交集部分在最前面的话,在找够之后就可以返回intersection了,没必要再接着遍历了.不过加上这一句,没有明显的提升这是怎么回事呢,有空问问小伙伴们.

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return intersect(nums2, nums1); //这种用法很巧妙啊
        }
        unordered_map <int, int> m;
        for (int num : nums1) {
            ++m[num];
        }
        vector<int> intersection;
        for (int num : nums2) {
            if (m.count(num)) {
                intersection.push_back(num);
                --m[num];
                if (m[num] == 0) {
                    m.erase(num);
                }
            }
        }
        return intersection;
    }
};

// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/
// 来源：力扣(LeetCode)

Review

How To Ask Questions The Smart Way(6/8)

When asking about code

Don't ask others to debug your broken code without giving a hint what sort of problem they should be searching for. Posting a few hundred lines of code, saying "it doesn't work", will get you ignored. Posting a dozen lines of code, saying "after line 7 I was expecting to see <x>, but <y> occurred instead" is much more likely to get you a response.

The most effective way to be precise about a code problem is to provide a minimal bug-demonstrating test case. What's a minimal test case? It's an illustration of the problem; just enough code to exhibit the undesirable behavior and no more. How do you make a minimal test case? If you know what line or section of code is producing the problematic behavior, make a copy of it and add just enough supporting code to produce a complete example (i.e. enough that the source is acceptable to the compiler/interpreter/whatever application processes it). If you can't narrow it down to a particular section, make a copy of the source and start removing chunks that don't affect the problematic behavior. The smaller your minimal test case is, the better (see the section called “Volume is not precision”).

Generating a really small minimal test case will not always be possible, but trying to is good discipline. It may help you learn what you need to solve the problem on your own — and even when it doesn't, hackers like to see that you have tried. It will make them more cooperative.

If you simply want a code review, say as much up front, and be sure to mention what areas you think might particularly need review and why.

Don't post homework questions

Hackers are good at spotting homework questions; most of us have done them ourselves. Those questions are for you to work out, so that you will learn from the experience. It is OK to ask for hints, but not for entire solutions.

If you suspect you have been passed a homework question, but can't solve it anyway, try asking in a user group forum or (as a last resort) in a “user” list/forum of a project. While the hackers willspot it, some of the advanced users may at least give you a hint.

Prune pointless queries

Resist the temptation to close your request for help with semantically-null questions like “Can anyone help me?” or “Is there an answer?” First: if you've written your problem description halfway competently, such tacked-on questions are at best superfluous. Second: because they are superfluous, hackers find them annoying — and are likely to return logically impeccable but dismissive answers like “Yes, you can be helped” and “No, there is no help for you.”

In general, asking yes-or-no questions is a good thing to avoid unless you want a yes-or-no answer.

Don't flag your question as “Urgent”, even if it is for you

That's your problem, not ours. Claiming urgency is very likely to be counter-productive: most hackers will simply delete such messages as rude and selfish attempts to elicit immediate and special attention. Furthermore, the word 'Urgent' (and other similar attempts to grab attention in the subject line) often triggers spam filters - your intended recipients might never see it at all!

There is one semi-exception. It can be worth mentioning if you're using the program in some high-profile place, one that the hackers will get excited about; in such a case, if you're under time pressure, and you say so politely, people may get interested enough to answer faster.

This is a very risky thing to do, however, because the hackers' metric for what is exciting probably differs from yours. Posting from the International Space Station would qualify, for example, but posting on behalf of a feel-good charitable or political cause would almost certainly not. In fact, posting “Urgent: Help me save the fuzzy baby seals!” will reliably get you shunned or flamed even by hackers who think fuzzy baby seals are important.

If you find this mysterious, re-read the rest of this how-to repeatedly until you understand it before posting anything at all.

Courtesy never hurts, and sometimes helps

Be courteous. Use “Please” and “Thanks for your attention” or “Thanks for your consideration”. Make it clear you appreciate the time people spend helping you for free.

To be honest, this isn't as important as (and cannot substitute for) being grammatical, clear, precise and descriptive, avoiding proprietary formats etc.; hackers in general would rather get somewhat brusque but technically sharp bug reports than polite vagueness. (If this puzzles you, remember that we value a question by what it teaches us.)

However, if you've got your technical ducks in a row, politeness does increase your chances of getting a useful answer.

(We must note that the only serious objection we've received from veteran hackers to this HOWTO is with respect to our previous recommendation to use “Thanks in advance”. Some hackers feel this connotes an intention not to thank anybody afterwards. Our recommendation is to either say “Thanks in advance” first and thank respondents afterwards, or express courtesy in a different way, such as by saying “Thanks for your attention” or “Thanks for your consideration”.)

Follow up with a brief note on the solution

Send a note after the problem has been solved to all who helped you; let them know how it came out and thank them again for their help. If the problem attracted general interest in a mailing list or newsgroup, it's appropriate to post the followup there.

Optimally, the reply should be to the thread started by the original question posting, and should have ‘FIXED’, ‘RESOLVED’ or an equally obvious tag in the subject line. On mailing lists with fast turnaround, a potential respondent who sees a thread about “Problem X” ending with “Problem X - FIXED” knows not to waste his/her time even reading the thread (unless (s)he personally finds Problem X interesting) and can therefore use that time solving a different problem.

Your followup doesn't have to be long and involved; a simple “Howdy — it was a failed network cable! Thanks, everyone. - Bill” would be better than nothing. In fact, a short and sweet summary is better than a long dissertation unless the solution has real technical depth. Say what action solved the problem, but you need not replay the whole troubleshooting sequence.

For problems with some depth, it is appropriate to post a summary of the troubleshooting history. Describe your final problem statement. Describe what worked as a solution, and indicate avoidable blind alleys after that. The blind alleys should come after the correct solution and other summary material, rather than turning the follow-up into a detective story. Name the names of people who helped you; you'll make friends that way.

Besides being courteous and informative, this sort of followup will help others searching the archive of the mailing-list/newsgroup/forum to know exactly which solution helped you and thus may also help them.

Last, and not least, this sort of followup helps everybody who assisted feel a satisfying sense of closure about the problem. If you are not a techie or hacker yourself, trust us that this feeling is very important to the gurus and experts you tapped for help. Problem narratives that trail off into unresolved nothingness are frustrating things; hackers itch to see them resolved. The goodwill that scratching that itch earns you will be very, very helpful to you next time you need to pose a question.

Consider how you might be able to prevent others from having the same problem in the future. Ask yourself if a documentation or FAQ patch would help, and if the answer is yes send that patch to the maintainer.

Among hackers, this sort of good followup behavior is actually more important than conventional politeness. It's how you get a reputation for playing well with others, which can be a very valuable asset.

询问有关代码的问题时

别要求他人帮你有问题的代码调试而不提示一下应该从何入手。张贴几百行的代码，然后说一声：它不会动会让你完全被忽略。只贴几十行代码，然后说一句：在第七行以后，我期待它显示 <x>，但实际出现的是 <y>比较有可能让你得到回应。

最有效描述程序问题的方法是提供最精简的Bug展示测试示例(bug-demonstrating test case)。什么是最精简的测试示例? 那是问题的缩影；一小个程序片段能刚好展示出程序的异常行为，而不包含其他令人分散注意力的内容。怎么制作最精简的测试示例？如果你知道哪一行或哪一段代码会造成异常的行为，复制下来并加入足够重现这个状况的代码(例如，足以让这段代码能被编译/直译/被应用程序处理)。如果你无法将问题缩减到一个特定区块，就复制一份代码并移除不影响产生问题行为的部分。总之，测试示例越小越好(查看话不在多而在精一节)。

一般而言，要得到一段相当精简的测试示例并不太容易，但永远先尝试这样做的是种好习惯。这种方式可以帮助你了解如何自行解决这个问题 —- 而且即使你的尝试不成功，黑客们也会看到你在尝试取得答案的过程中付出了努力，这可以让他们更愿意与你合作。

如果你只是想让别人帮忙审查(Review)一下代码，在信的开头就要说出来，并且一定要提到你认为哪一部分特别需要关注以及为什么。

别把自己家庭作业的问题贴上来

黑客们很擅长分辨哪些问题是家庭作业式的问题；因为我们中的大多数都曾自己解决这类问题。同样，这些问题得由**你**来搞定，你会从中学到东西。你可以要求给点提示，但别要求得到完整的解决方案。

如果你怀疑自己碰到了一个家庭作业式的问题，但仍然无法解决，试试在使用者群组，论坛或(最后一招)在项目的使用者邮件列表或论坛中提问。尽管黑客们**会**看出来，但一些有经验的使用者也许仍会给你一些提示。

去掉无意义的提问句

避免用无意义的话结束提问，例如有人能帮我吗？或者这有答案吗？。

首先：如果你对问题的描述不是很好，这样问更是画蛇添足。

其次：由于这样问是画蛇添足，黑客们会很厌烦你 -- 而且通常会用逻辑上正确，但毫无意义的回答来表示他们的蔑视，例如：没错，有人能帮你或者不，没答案。

一般来说，避免用 是或否、对或错、有或没有类型的问句，除非你想得到是或否类型的回答。

即使你很急也不要在标题写`紧急`

这是你的问题，不是我们的。宣称紧急极有可能事与愿违：大多数黑客会直接删除无礼和自私地企图即时引起关注的问题。更严重的是，紧急这个字(或是其他企图引起关注的标题)通常会被垃圾信过滤器过滤掉 -- 你希望能看到你问题的人可能永远也看不到。

有半个例外的情况是，如果你是在一些很高调，会使黑客们兴奋的地方，也许值得这样去做。在这种情况下，如果你有时间压力，也很有礼貌地提到这点，人们也许会有兴趣回答快一点。

当然，这风险很大，因为黑客们兴奋的点多半与你的不同。譬如从 NASA 国际空间站(International Space Station)发这样的标题没有问题，但用自我感觉良好的慈善行为或政治原因发肯定不行。事实上，张贴诸如紧急：帮我救救这个毛绒绒的小海豹！肯定让你被黑客忽略或惹恼他们，即使他们认为毛绒绒的小海豹很重要。

如果你觉得这点很不可思议，最好再把这份指南剩下的内容多读几遍，直到你弄懂了再发文。