很久以前被第四题：Median of Two Sorted Arrays卡住了，而且discuss看不明白也没耐心去看，导致信心受挫LeetCode一直没去刷。感觉这是我一直以来的软肋：缺乏勇气。在我看到牛客的同学们都刷了不少LeetCode，而自己春招笔试6中3之后，腾讯一面手撕非常简单的代码都出错（感觉这是除了项目不对口外挂掉的最大原因），感觉得面对现实了，现在，重新开始。
——2018/05/25
目前大概是自己先折腾，然后看讨论区，高票答案都是有其精妙之处的。这篇博客就记录题解的大致思路，包含了较为详细注释的代码就放在github上了。
https://github.com/BewareMyPower/AtOffer/tree/master/leetcode
001 Two Sum
无序数组，找出和为target的两个数，用hashmap存储遍历的数x及其下标，若target-x在hashmap中，即找出一组解。
two_sum.cc
002 Add Two Numbers
用链表模拟大数加法的问题，用carry表示是否进位，注意每次判断2个链表对应节点相加时，大于10时需要把carry置为1，小于10时把carry置为0，不要漏掉其中一个else，否则carry会被默认为之前的值。
add_two_numbers.cc
003 Longest Substring Without Repeating Characters
双指针法，记录子串s[start..i)，start为起始位置，i为当前位置，用哈希表记录字符和字符最近一次出现的位置。这里由于字符是char，可以用vector<int> hash(256, -1);来取代unordered_map，当然，前提是下标用int表示不会溢出。
longest_substring_without_repeating_characters.cc
004 Median of Two Sorted Arrays
中位数的蛋疼之处在于元素数量是奇数还是偶数，这题有个非常巧妙的解决方法，使用割的概念，参考【分步详解】两个有序数组中的中位数和Top K问题。
median_of_two_sorted_arrays.cc
005 Longest Palindromic Substring
这题一开始我按照类似最大回文子序列的思路做了，然后求s和reverse(s)的最大公共子串长度，然后发现不对，因为需要s和reverse(s)的公共子串对应位置相同。比如s1长度为6，s2为s1的转置。则子串s1[0..2]对应的是子串s2[3..5]，这样才有意义。
后来发现这种做法把问题想复杂了，其实只需要依次从位置0~n-1构造回文串的中心（比如abcxxcba的中心为xx），尽可能构造足够长的回文串即可。注意迭代终止条件加上一个优化条件start + maxlen/2 < len。
longest_palindromic_substring.cc
006 ZigZag Conversion
读懂题意后很简单，之所以medium难度大概是考验细心程度吧。
zigzag_conversion.cc
007 Reverse Integer
注意溢出判断，在乘以10之前和INT_MAX/10比较即可。特殊情况，INT_MIN的绝对值比INT_MAX大1，因此无法通过负号运算转换成正数。至于用long long来防止溢出，个人觉得没意思。
reverse_integer.cc
008 String to Integer (atoi)
注意题意规定，这题用C直接操作字符指针写起来更方便。正负号的判断比较巧妙（参考源码）。关键还是溢出的判断，不同于007 Reverse Integer，这里要考虑乘以10之前和INT_MAX/10相等的情况，再进一步通过正负号和最低位数字判断。注意不要写INT_MIN % 10这种代码，因为C/C++的负数求余仍然是负数。
009 Palindrome Number
首先负数肯定是不行的，然后分位数为奇偶的情况讨论（迭代收敛条件是分离出的第一个数<=第二个数）：
1221->{1221/10=122, 0*10+1=1}->{122/10=12, 1*10+2=12}->12==12,true!
121->{121/10=12, 0*10+1=1}->{12/10=1, 1*10+2=12}->1==12/10,true!
但是有陷阱，按这种算法，对10而言会被判断为true，过程如下
10->{1,0}->{1,1}->1==1,true!
究其原因是0*10并未从1位数变成2位数。如果判断个位为0时返回false，那么又有特殊情况0，所以这题虽然是easy难度，但是陷阱不少！
panlindrome_number.cc
010 Regular Expression Matching
剑指offer原题，但是书上给出的递归解法在LeetCode上效率低下，动态规划的思路容易想到，但不容易想清楚，尤其是关于*匹配1次以上的情况下，隐含有s[i - 1] == p[j - 2]（其中p[j - 1]为模式串的新字符且为*），否则*必然只能匹配0次。
不知为什么这个DP思路想起来总有点不顺，对我来说确实Hard难度。
regular_expression_matching.cc
011 Container With Most Water
看懂题意后还算简单，初始宽度最大，然后慢慢缩小宽度，只能增大高度min(x[lo], x[hi])。严格的证明参考https://segmentfault.com/a/1190000008824222
container_with_most_water.cc
012 Integer to Roman
罗马文字规则是按位数，0-9的表示和10~90的表示仅仅是把IVX换成了XLC。
| 数值 | 5k | 5k+1 | 5k+2 | 5k+3 | 5k+4 |
|---|---|---|---|---|---|
| 0~4 | I | II | III | IV | |
| 5~9 | V | VI | VII | VIII | IX |
前4列，第2行比第1行多了V，不过表达第5列稍微麻烦了点。简单直接的做法是直接把这10个对应关系记录到表格中，然后从十进制高位到低位，一个个查表。
integer_to_roman.cc
013 Roman to Integer
这题之所以easy难度，在于规律，若前一位小于后一位，则必然是IV、IX这种，否则直接加上该位表示的数就行。
roman_to_integer.cc
014 Longest Common Prefix
easy难度，注意边界条件，在判断第i个字符相等之前判断i是否越界。
longest_common_prefix.cc
015 3Sum
思路一开始就是先定下1个元素，然后变成twoSum问题，但是这里要查找所有解，还要去重。所以关键是先排序，这样首先避免了重复元素的查找，比如-2,-2,-1,-1,-1,0,1,1,1,1,2就只需要在每个区间内查找。twoSum问题也和一般的twoSum问题求解方式不同，因为要找到所有解，所以用从最低和最高从外向内逼近的的思想，如果用二分法反而复杂度更高。
3sum.cc
016 3Sum Closest
和上一题思路一致，不同在于，从外向内逼近时，sum < target时lo++，sum > target时hi--，并且每次都比较abs(sum - target)是否小于当前diff，若diff == 0则无需继续查找。
PS：之前把nums[i] != nums[i - 1]写成了nums[i] == nums[i - 1]导致测试用例只通过了113/125。
3sum_closest.cc
网友评论