leetcode python solution

Algorithms

(:100: 代表答主提交答案时在前 100 %)

1. Two Sum: Solution

2. Add Two Numbers: Solution :100:

3. Longest Substring Without Repeating Characters: Solution

4. Median of Two Sorted Arrays: Solution :100:

5. Longest Palindromic Substring: Solution

(这道题对 Python 有毒, 只要时间复杂度大于等于 O(n2) 绝对 TLE, 其它语言 O(n3) 也能过...)

tips: Python 用 Manacher’s Algorithm 比较稳, 其它算法基本 TLE. 本例里用将每个字符当作回文串中心对匹配方式,还是可能 TLE.

6. ZigZag Conversion:Solution

tips: 以每 (2 * numRows - 2) 个字符串为一组进行操作,最后一组不足 (2 * numRows - 2) 个字符用特殊字符补齐,最后返回前再将特殊字符去掉

7. Reverse Integer: Solution

8. String to Integer (atoi): Solution

9. Palindrome Number: Solution

10. Regular Expression Matching: Solution

tips: 用动态规划的思路可以解, 递归 Python 会 TLE. 用 re 库可以一句话解决: (return re.match(r'^{0}$'.format(p), s)) 不过不推荐.

11. Container With Most Water: Solution :100:

tips: bf 做复杂度 O(n2) Python 会 TLE. 用两个游标分别从数组首位出发谁小谁移动, 纪录其中最大值, 复杂度 O(n)

12. Integer to Roman: Solution

13. Roman to Integer: Solution :100:

14. Longest Common Prefix: Solution

动态规划思路: 复杂度 O(n2), 状态是: n 个字符串 n <= len(strs) 的最长公共前缀, 转移方程: D(n) = min{D(n-1), L(j)}, 0 <= j <= min{D(n-1), len(str(n))} (大概是这样)

15. 3Sum: Solution

tips: K Sum Problem

16. 3Sum Closest: Solution

tips: 可以看作是有个固定数字的 4 Sum 问题,稍微改下 3 Sum 代码即可, 时间复杂度不增加 O(nlogn)

17. Letter Combinations of a Phone Number: Solution

tips: 简单替换后直接算 kronecker 积, 复杂度 O(n)

18. 4Sum: Solution

19. Remove Nth Node From End of List: Solution

20. Valid Parentheses: Solution

21. Merge Two Sorted Lists: Solution

22. Generate Parentheses: Solution

tips: backtracking

23. Merge k Sorted Lists: Solution

tips: 分治法 归并排序

24. Swap Nodes in Pairs: Solution

25. Reverse Nodes in k-Group: Solution

26. Remove Duplicates from Sorted Array: Solution

tips1: 虽然只是让返回去除重复后的数组长度,但是oj还是会判断代码是否真的去掉的是重复的元素,否则即使你返回的长度正确oj依然会 WA
tips2: 不能用len(set(nums)) 一句完成,因为 set 申请了新的空间,而题目要求不能使用新的空间

27. Remove Element: Solution

28. Implement strStr(): Solution

29. Divide Two Integers: Solution