Leetcode题解|Leetcode题解 - Easy - 2 Leetcode题解-Easy-2

20- 有效的括号问题给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
思路显然应该用栈来解决。
不过留意一点，题目中规定了字符串中只包括括号，所以只需一个mapping存右括号，如果不在右括号中就一定是左括号，直接append进栈即可，无需判断当前字符是不是非括号字符。
代码

class Solution: def isValid(self, s): """ :type s: str :rtype: bool """ stack = [] mapping = { ')': '(', ']': '[', '}': '{', } for c in s: if c in mapping: if stack and stack[-1] == mapping[c]: stack.pop(-1) else: return False else: stack.append(c) return not stack

21- 合并两个有序链表问题将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
思路特别要留意指针操作
代码

# Definition for singly-linked list. # class ListNode: #def __init__(self, x): #self.val = x #self.next = Noneclass Solution: def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ head = ListNode(-1) current = head while l1 and l2: if l1.val <= l2.val: current.next = l1 current = l1 l1 = l1.next else: current.next = l2 current = l2 l2 = l2.next if l1: current.next = l1 if l2: current.next = l2 return head.next

26- 删除排序数组中的重复项问题给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 :
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
思路一快一慢两个指针，慢指针代表当前去重后的结果的进度，快指针代表当前检查的进度，遇到重复元素，快指针跳过，遇到不重复，则值复制到慢指针处，两者都往前移动，直到快指针扫完全部。
代码

class Solution: def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) <= 1: return len(nums)left = 0 right = 1 while right < len(nums): if nums[right] != nums[left]: left += 1 nums[left] = nums[right] right += 1 return left + 1

27- 移除元素问题给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路与26相同的思路，双指针。
由于本题中条件【元素的顺序可以改变】，可以进一步优化。双指针法在某些特殊情况下效率比较低，例如 41235 要删4，需要把1235都挪一次，产生了很多挪动。
改进方法：当前要删，则将当前与最后一个元素交换位置，并删除最后一个元素，然后继续检查当前是否要删，直到不要删，再往后接着判断。
代码

# 双指针 class Solution: def removeElement(self, nums, val): """ :type nums: List[int] :type val: int :rtype: int """ if len(nums) < 1: return 0 left = -1 right = 0 while right < len(nums): if nums[right] != val: left += 1 nums[left] = nums[right] right += 1 return left + 1# 优化方法：交换 class Solution: def removeElement(self, nums, val): """ :type nums: List[int] :type val: int :rtype: int """ if len(nums) < 1: return 0 left = 0 right = len(nums) - 1 while left <= right: if nums[left] == val: nums[left] = nums[right] right -= 1 else: left += 1 return left

特别注意：
26、27两题要注意一些特殊情况能否正确处理，例如

[] [3] val=4 [3] val=3 [3,3,3] val=3

28- 实现 strStr() 问题实现 strStr() 函数。
给定一个 haystack（草堆）字符串和一个 needle （针）字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 :

输入: haystack = "hello", needle = "ll" 输出: 2

思路基本思路就是从头第一个字符开始依次往后找。
更高效的KMP算法：
如何更好的理解和掌握 KMP 算法? - 逍遥行的回答 - 知乎
https://www.zhihu.com/question/21923021/answer/37475572
【【【TODO：添加KMP算法的写法】】】
代码

# 基础写法 class Solution: def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int """ if not needle: return 0 if not haystack: return -1 j = 0 for i in range(0, len(haystack)): if i + len(needle) <= len(haystack): if haystack[i: i+len(needle)] == needle: return i return -1

35- 搜索插入位置问题给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

示例 : 输入: [1,3,5,6], 5 输出: 2输入: [1,3,5,6], 2 输出: 1输入: [1,3,5,6], 7 输出: 4输入: [1,3,5,6], 0 输出: 0

思路由于排序数组，最基本的就是按顺序从前往后找。
可通过二分查找提高效率。
代码

# 二分查找。需注意最后的判断，因为如果找不到，要返回能插入的位置。 class Solution: def searchInsert(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ start = 0 end = len(nums) - 1 while start <= end: mid = (start + end) // 2 if nums[mid] == target: return mid elif nums[mid] < target: start = mid +1 else: end = mid - 1 if nums[mid] < target: return mid + 1 else: return mid

38- 报数问题报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。
比如说，
n=1时， 1
n=2时，读前面一项，是一个一，所以此时是 11
n=3时，读前面一项，是二个一，所以此时是 21
n=4时，读前面一项，是一个二一个一，所以此时是 1211
n=5时，读前面一项，是一个一一个二二个一，所以此时是 111221
以此类推。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
思路模拟人怎么来读取就可以，不过感觉代码写的比较笨2333
代码

class Solution: def countAndSay(self, n): """ :type n: int :rtype: str """ if n <= 0: return '' if n == 1: return '1' last_str = '1' for i in range(1, n): cur_char = '' cur_count = 0 cur_str = '' for c in last_str: if c == cur_char: cur_count += 1 elif cur_count != 0: cur_str += str(cur_count) + cur_char cur_count = 1 cur_char = c else: cur_char = c cur_count = 1 if cur_count != 0: cur_str += str(cur_count) + cur_char last_str = cur_str return last_str

53- 最大子序和问题给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
思路参考这里：连续子数组的最大和
代码

import sys class Solution: def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ sum_ = sys.maxsize * -1 max_ = sum_ for i in nums: if sum_ < 0: sum_ = i else: sum_ += i if max_ < sum_: max_ = sum_ return max_

58- 最后一个单词的长度问题给定一个仅包含大小写字母和空格的字符串，返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指由字母组成，但不包含任何空格的字符串。
示例:
输入: "Hello World"
输出: 5
思路思路很简单，注意特殊比如 abc_ 这种空格在最后的情况，所以要先trim掉空格
代码

class Solution: def lengthOfLastWord(self, s): """ :type s: str :rtype: int """ ret = 0 s = s.strip() for i in s: if i == ' ': ret = 0 else: ret += 1 return ret

66- 加一问题给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
思路 【Leetcode题解|Leetcode题解 - Easy - 2】主要处理进位，所以从后往前处理，特别注意最后仍然需要进位，导致数组长度需要在前面+1的情况。
代码

class Solution: def plusOne(self, digits): """ :type digits: List[int] :rtype: List[int] """ up = 1 for i in range(len(digits)-1, -1, -1): digits[i] += up if digits[i] > 9: up = 1 digits[i] %= 10 else: up = 0 if up: digits = [up, ] + digits return digits