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 = None

class 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。

思路

主要处理进位，所以从后往前处理，特别注意最后仍然需要进位，导致数组长度需要在前面+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