leetcode题解（1）

Leetcode题解（1）- Easy

开始Leetcode之旅吧。先刷 “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插入哈希表中。注意，遍历的同时，对于当前元素，拿目标值减去当前值，然后去哈希表里找是否存在，如果存在则说明找到了一对儿，直接返回即可。
## 代码 
```python 
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-两数相加 （中等难度） 
## 题目 
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 
输出：7 -> 0 -> 8 
原因：342 + 465 = 807
## 思路 
两个链表一起读取，相加进位。这个题难点在于有很多特殊情况，不容易考虑周全。
比如以下特殊用例 
``` 
[5] # 需要考虑进位 
[5]
[9,8] # 需要考虑长度不均等 
[1]
[1] # 需要考虑长度不均等和进位 
[9,9]
```
## 代码 
```python 
# 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
```
# 3-无重复字符的最长子串 （中等难度） 
## 问题 
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 
示例 2:
输入: "bbbbb" 
输出: 1 
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 
示例 3:
输入: "pwwkew" 
输出: 3 
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
## 思路
滑动窗口来解决，左右两个索引ij，用哈希表记录当前窗口中的元素。当读到j时如果不重复，则j继续读，如果重复，则记下窗口的长度，然后从哈希表中读取重复元素所在的位置，并将i移动到它的下一个位置，继续滑动窗口，最后得到最长的长度。
## 代码 
```python 
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
``` 
上面是参照官方解答写的python代码，非常简洁。而且本来我认为当遇到重复值之后，挪动i之后应该清空mem，mem只记住当前窗口中出现的元素，但这个代码里面并没有清空mem，而是接着用了mem，玄机在于 <code>i = max(mem[s[j]], i)</code>这句，这句实现了：如果当前元素出现在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。不借助外部存储完成了反转。
## 代码 
```python 
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 
```
# 9- 回文数 
## 问题 
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如， 121 是回文数， -121 不是回文数， 10 不是回文数。
## 思路
转为字符串，两端读取判断是否回文。
不转为字符串的话，就通过除10和取余将数字反转，然后判断反转前后的两个整数是否相等。
优化：例如，1221，是否可以加快速度呢？其实只要将后一半数字反转，与剩下的前一半数字比较，即可判断是否回文。(这个只反转一半的代码略)
## 代码 
转换为字符串的解法： 
```python 
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 
```
巧妙利用 python 语法： 
```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 
```
反转整个数字的解法： 
``` 
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 
```
# 13-罗马数字转整数
## 问题 
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 
``` 
字符 数值 
I 1 
V 5 
X 10 
L 50 
C 100 
D 500 
M 1000 
``` 
例如， 罗马数字 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。 
``` 
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1: 
``` 
输入: "III" 
输出: 3 
``` 
示例 2: 
``` 
输入: "IV" 
输出: 4 
```` 
示例 3: 
``` 
输入: "IX" 
输出: 9 
``` 
示例 4: 
``` 
输入: "LVIII" 
输出: 58 
解释: L = 50, V= 5, III = 3. 
``` 
示例 5: 
``` 
输入: "MCMXCIV" 
输出: 1994 
解释: M = 1000, CM = 900, XC = 90, IV = 4. 
```
## 思路 
最主要是想清楚思路，不要陷入很多if else里面。 
建立一个字符和值的对应，从左往右读取，如果当前字符代表的数字比下一个字符的大，则在总结果里加上，如果小，则减去。
上面思路虽然看起简单，在本题的前提下——输入的罗马数字一定是正确的——是没有问题的。
## 代码 
```python 
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
```
# 14- 最长公共前缀 
## 问题 
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1: 
``` 
输入: ["flower","flow","flight"] 
输出: "fl" 
```
示例 2: 
``` 
输入: ["dog","racecar","car"] 
输出: "" 
解释: 输入不存在公共前缀。 
```
说明: 
所有输入只包含小写字母 a-z 。
## 思路
- 纵向扫描：从下标0开始，判断每一个字符串的下标0，判断是否全部相同。直到遇到不全部相同的下标。时间性能为O(n*m)。
- 横向扫描：前两个字符串找公共子串，将其结果和第三个字符串找公共子串……直到最后一个串。时间性能为O(n*m)。
- 借助trie字典树。将这些字符串存储到trie树中。那么trie树的第一个分叉口之前的单分支树的就是所求。（这个思路也挺好的，而且用到了高级一点的方法）
## 代码 
```python 
# 纵向扫描 
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] 
```

leetcode题解（1）

Leetcode题解（1）- Easy

近期文章

近期评论

标签

热门

文章归档

分类目录

功能