Leetcode题解（1）- Easy
先做Easy级别的题目吧~（由于刚开始刷还没规划好，这篇里面先夹杂了两道中等难度的题）
# 1-两数之和
# 要求
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的 两个 整数。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
# 分析
最笨办法是O(n^2)，可以借助哈希表（字典）进行优化。遍历一遍元素，并将元素的值作为key下标作为value插入哈希表中。注意，遍历的同时，对于当前元素，拿目标值减去当前值，然后去哈希表里找是否存在，如果存在则说明找到了一对儿，直接返回即可。
# 代码
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
mem = {}
for index, val in enumerate(nums):
if (target - val) in mem.keys():
return [mem[target-val], index]
mem[val] = index
return []
2
3
4
5
6
7
8
9
10
11
12
13
# 2-两数相加 （中等难度）
# 题目
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
# 思路
两个链表一起读取，相加进位。这个题难点在于有很多特殊情况，不容易考虑周全。
比如以下特殊用例
[5] # 需要考虑进位
[5]
[9,8] # 需要考虑长度不均等
[1]
[1] # 需要考虑长度不均等和进位
[9,9]
2
3
4
5
6
7
8
9
# 代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
head = ListNode(0)
head.next = l1
carry = 0
while l1 and l2: # 两个列表长度相同的部分
s = l1.val + l2.val + carry
val, carry = s % 10, s // 10
l1.val = val
prev, l1, l2 = l1, l1.next, l2.next
l = l1 or l2 # 处理l1或l2余下的部分
prev.next = l
while l and carry:
s = l.val + carry
val, carry = s%10, s//10
l.val = val
prev, l = l, l.next
if carry: # 最后千万记得要处理进位
prev.next = ListNode(1)
return head.next
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 3-无重复字符的最长子串 （中等难度）
# 问题
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
# 思路
滑动窗口来解决，左右两个索引ij，用哈希表记录当前窗口中的元素。当读到j时如果不重复，则j继续读，如果重复，则记下窗口的长度，然后从哈希表中读取重复元素所在的位置，并将i移动到它的下一个位置，继续滑动窗口，最后得到最长的长度。
# 代码
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
ans = 0
mem = {}
i = 0
for j in range(0, len(s)):
if s[j] in mem.keys():
i = max(mem[s[j]], i)
ans = max(ans, j - i + 1)
mem[s[j]] = j + 1
return ans
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
上面是参照官方解答写的python代码，非常简洁。而且本来我认为当遇到重复值之后，挪动i之后应该清空mem，mem只记住当前窗口中出现的元素，但这个代码里面并没有清空mem，而是接着用了mem，玄机在于 i = max(mem[s[j]], i)这句，这句实现了：如果当前元素出现在mem中，并不意味着在当前窗口中一定遇到重复值，而是判断一下，如果重复元素的位置小于i则不是当前窗口中出现了重复值，不更新i，如果大于i则是出现了重复值，更新i。
寥寥几句就把很多情况和判断都给涵盖了，真是简洁啊。
# 7-整数反转
# 问题
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123 输出: 321 示例 2:
输入: -123 输出: -321 示例 3:
输入: 120 输出: 21 注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
# 思路
可以借助栈，123 % 10 = 3， 12 % 10 = 2， 1 % 10 = 1， 然后弹栈， 1 x 1 = 1， 1 + 2 x 10 = 21， 21 + 3 x 100 = 321，完成计算。
其实也可以在不借助栈的情况下完成，先弹出 123 % 10 = 3， 123 // 10 = 12，将3存放到另一个数字变量ans中。然后 12 % 10 = 2, 12 // 10 = 1，对于ans，有 3 * 10 + 2 = 32。继续，1 % 10 = 1, 1 // 10 = 0，对于ans有 32 * 10 + 1 = 321。不借助外部存储完成了反转。
# 代码
class Solution:
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
minus = 1
if x < 0:
minus = -1
x *= minus
ans = 0
while x != 0:
pop = x % 10
x = x // 10
ans = ans * 10 + pop
ans *= minus
# 由于leetcode要求溢出时返回0，而python写的时候该溢出的用例未溢出，所以判断一下溢出
if - 2 ** 31 < ans < 2 ** 31 - 1:
return ans
else:
return 0
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 9- 回文数
# 问题
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如， 121 是回文数， -121 不是回文数， 10 不是回文数。
# 思路
转为字符串，两端读取判断是否回文。
不转为字符串的话，就通过除10和取余将数字反转，然后判断反转前后的两个整数是否相等。
优化：例如，1221，是否可以加快速度呢？其实只要将后一半数字反转，与剩下的前一半数字比较，即可判断是否回文。(这个只反转一半的代码略)
# 代码
转换为字符串的解法：
class Solution:
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
data = str(x)
i, j = 0, len(data) - 1
while i < j:
if data[i] != data[j]:
return False
i += 1
j -= 1
return True
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
巧妙利用 python 语法：
class Solution:
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x >= 0 and str(x) == str(x)[::-1]:
a = True
else :
a = False
return a
2
3
4
5
6
7
8
9
10
11
反转整个数字的解法：
class Solution:
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
remainder = x % 10
devision = x // 10
reverse = remainder
while devision != 0:
remainder = devision % 10
devision = devision // 10
reverse = reverse * 10 + remainder
return x == reverse
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 13-罗马数字转整数
# 问题
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
2
3
4
5
6
7
8
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
2
3
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
2
示例 2:
输入: "IV"
输出: 4
2
示例 3:
输入: "IX"
输出: 9
2
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
2
3
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
2
3
# 思路
最主要是想清楚思路，不要陷入很多if else里面。 建立一个字符和值的对应，从左往右读取，如果当前字符代表的数字比下一个字符的大，则在总结果里加上，如果小，则减去。
上面思路虽然看起简单，在本题的前提下——输入的罗马数字一定是正确的——是没有问题的。
# 代码
class Solution:
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
num = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
score = 0
for i in range(0, len(s)):
if i < len(s) - 1 and num[s[i+1]] > num[s[i]]:
score -= num[s[i]]
else:
score += num[s[i]]
return score
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 14- 最长公共前缀
# 问题
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
2
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
2
3
说明: 所有输入只包含小写字母 a-z 。
# 思路
纵向扫描：从下标0开始，判断每一个字符串的下标0，判断是否全部相同。直到遇到不全部相同的下标。时间性能为O(n*m)。
横向扫描：前两个字符串找公共子串，将其结果和第三个字符串找公共子串……直到最后一个串。时间性能为O(n*m)。
借助trie字典树。将这些字符串存储到trie树中。那么trie树的第一个分叉口之前的单分支树的就是所求。（这个思路也挺好的，而且用到了高级一点的方法）
# 代码
# 纵向扫描
class Solution:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ''
if len(strs) == 1:
return strs[0]
cursor = -1
ok = True
while ok:
cursor += 1
if cursor == len(strs[0]): # 首个串已走完
cursor -= 1
break
current_char = strs[0][cursor]
for st in strs[1:]:
if cursor == len(st) or st[cursor] != current_char: # 串走完或不匹配
cursor -= 1
ok = False
break
return strs[0][:cursor+1]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25