Leetcode一句话题解

最近无聊，刷了一批Leetcode水题，用简要题解记录一下做题过程，也小小帮助一下被坑所困的人。

1~10

1. Two Sum

   1. $O(n^2)$：暴力枚举
   2. $O(nlogn)$：排序+two-pointers或者map/set大法好
   3. $O(n)$：哈希表

2. Add Two Numbers

   $O(n)$，边处理边进位，注意最后一位进位和链表为空的边界情况

3. Longest Substring Without Repeating Characters

   1. $O(nlogn)$，滑动窗口，用一个set维护当前的字符集，如果新加入的字符以前出现过，抛弃左边重复的字符，所有字符有且仅有被遍历一遍
   2. $O(n)$，把set换为哈希表

4. Median of Two Sorted Arrays

   $O(log(min(m,n))$，特判数组大小为(0,*)(1,*)(2,*)的情况，二分查找，注意奇怪的边界情况

5. Longest Palindromic Substring

   $O(n)$，强上manacher算法

6. ZigZag Conversion

   手动模拟一下“ZIGZAG”的样子，模拟过程

7. Reverse Integer

   按位取出，重新分配，注意溢出问题

8. String to Integer (atoi)

   按位取出，重新分配，注意符号和溢出问题

9. Palindrome Number

   $O(n)$，从两边向中间判断

10. Regular Expression Matching

    $O(mn)$，DP，按下一个是否为’*’分类讨论

11~20

1. Container With Most Water

   $O(n)$，two pointers，移动高度较小的指针，使结果尽量大。

2. Integer to Roman

   模拟题，按照罗马数字的规则追加相应的字符串。

3. Roman to Integer

   模拟题，按照罗马数字的规则加上相应的数字。

4. Longest Common Prefix

   模拟题，按照长度排序，然后搜索最短的字符串最大能匹配到所有的字符串的第多少个字符。

5. 3Sum

   $O(n^2)$，two pointers，枚举一个数，然后在后面的序列寻找满足的两个数，注意去重。

6. 3Sum Closest

   与3Sum相同， 只是记录的时候判断并记录距离最小的值。

7. Letter Combinations of a Phone Number

   模拟题，每次循环往上次生成的序列中的每个元素尾部追加相应字符。

8. 4Sum

   与3Sum相同，只是需要枚举两个值。

9. Remove Nth Node From End of List

   简单的链表操作，注意删除首节点的情况。

10. Valid Parentheses

    使用一个栈维护一下之前的左括号，按照右括号判断，若无对应的左括号则无法匹配。

21-30

to be continued…