20- 有效的括號

問題

給定一個只包括 '('，')'锰瘸，'{'，'}'昂灵，'['避凝，']' 的字符串，判斷字符串是否有效眨补。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合管削。
左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串撑螺。

思路

顯然應(yīng)該用棧來解決含思。

不過留意一點，題目中規(guī)定了字符串中只包括括號甘晤，所以只需一個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- 合并兩個有序鏈表

問題

將兩個有序鏈表合并為一個新的有序鏈表并返回艇炎。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的酌伊。

示例：

輸入：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- 刪除排序數(shù)組中的重復項

問題

給定一個排序數(shù)組，你需要在原地刪除重復出現(xiàn)的元素，使得每個元素只出現(xiàn)一次居砖，返回移除后數(shù)組的新長度虹脯。

不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成奏候。

示例 :

給定數(shù)組 nums = [1,1,2],

函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2循集。

你不需要考慮數(shù)組中超出新長度后面的元素。

思路

一快一慢兩個指針蔗草，慢指針代表當前去重后的結(jié)果的進度咒彤，快指針代表當前檢查的進度，遇到重復元素咒精，快指針跳過镶柱，遇到不重復，則值復制到慢指針處模叙，兩者都往前移動歇拆，直到快指針掃完全部。

代碼

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- 移除元素

問題

給定一個數(shù)組 nums 和一個值 val范咨，你需要原地移除所有數(shù)值等于 val 的元素故觅，返回移除后數(shù)組的新長度。

不要使用額外的數(shù)組空間渠啊，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成输吏。

元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素替蛉。

思路

與26相同的思路评也，雙指針。

由于本題中條件【元素的順序可以改變】灭返，可以進一步優(yōu)化盗迟。雙指針法在某些特殊情況下效率比較低，例如 41235 要刪4熙含，需要把1235都挪一次罚缕，產(chǎn)生了很多挪動。

改進方法：當前要刪怎静，則將當前與最后一個元素交換位置邮弹，并刪除最后一個元素，然后繼續(xù)檢查當前是否要刪蚓聘，直到不要刪腌乡，再往后接著判斷。

代碼

# 雙指針
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
        
        
# 優(yōu)化方法：交換
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- 實現(xiàn) strStr()

問題

實現(xiàn) strStr() 函數(shù)。

給定一個 haystack（草堆） 字符串和一個 needle （針）字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)急迂。如果不存在影所，則返回 -1。

示例 :

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

思路

基本思路就是從頭第一個字符開始依次往后找僚碎。

更高效的KMP算法：
如何更好的理解和掌握 KMP 算法? - 逍遙行的回答 - 知乎
https://www.zhihu.com/question/21923021/answer/37475572

【【【TODO：添加KMP算法的寫法】】】

代碼

# 基礎(chǔ)寫法
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- 搜索插入位置

問題

給定一個排序數(shù)組和一個目標值猴娩，在數(shù)組中找到目標值，并返回其索引勺阐。如果目標值不存在于數(shù)組中卷中，返回它將會被按順序插入的位置。

你可以假設(shè)數(shù)組中無重復元素渊抽。

示例 :
輸入: [1,3,5,6], 5
輸出: 2

輸入: [1,3,5,6], 2
輸出: 1

輸入: [1,3,5,6], 7
輸出: 4

輸入: [1,3,5,6], 0
輸出: 0

思路

由于排序數(shù)組仓坞，最基本的就是按順序從前往后找。
可通過二分查找提高效率腰吟。

代碼

# 二分查找无埃。需注意最后的判斷，因為如果找不到毛雇，要返回能插入的位置嫉称。
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- 報數(shù)

問題

報數(shù)序列是一個整數(shù)序列，按照其中的整數(shù)的順序進行報數(shù)灵疮，得到下一個數(shù)织阅。
比如說，
n=1時震捣， 1
n=2時荔棉，讀前面一項，是 一個一蒿赢，所以此時是 11
n=3時润樱，讀前面一項，是 二個一羡棵，所以此時是 21
n=4時壹若，讀前面一項，是 一個二 一個一皂冰，所以此時是 1211
n=5時店展，讀前面一項，是 一個一 一個二 二個一秃流，所以此時是 111221
以此類推赂蕴。
給定一個正整數(shù) n（1 ≤ n ≤ 30），輸出報數(shù)序列的第 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- 最大子序和

問題

給定一個整數(shù)數(shù)組 nums 碧注，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和席怪。

示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6纤控。

進階:
如果你已經(jīng)實現(xiàn)復雜度為 O(n) 的解法挂捻，嘗試使用更為精妙的分治法求解。

思路

參考這里：連續(xù)子數(shù)組的最大和

代碼

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- 加一

問題

給定一個由整數(shù)組成的非空數(shù)組所表示的非負整數(shù)，在該數(shù)的基礎(chǔ)上加一箱吕。

最高位數(shù)字存放在數(shù)組的首位芥驳， 數(shù)組中每個元素只存儲一個數(shù)字。

你可以假設(shè)除了整數(shù) 0 之外茬高，這個整數(shù)不會以零開頭兆旬。

示例 1:

輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123。

思路

主要處理進位怎栽，所以從后往前處理丽猬，特別注意最后仍然需要進位，導致數(shù)組長度需要在前面+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