摘要：第五題對稱二叉樹難度簡單給定一個二叉樹，檢查它是否是鏡像對稱的。第十六題最大連續的個數難度簡單給定一個二進制數組，計算其中最大連續的個數。第十八題平方數之和難度簡單給定一個非負整數，你要判斷是否存在兩個整數和，使得。

最近忙著調教新裝備，沒有及時的寫題解，但是沒有在偷懶沒刷題喔~
來認真整理下最近做的題目~

之前考慮按tag來刷題，后來收到了推薦的leetcode題解，就根據上面的說明陸續刷題啦~
tag主要做了：數組、雙指針
找時間要開始部署gitbook了，然后將題解部署到電子書上~

第一題

387. 字符串中的第一個唯一字符
難度：簡單
給定一個字符串，找到它的第一個不重復的字符，并返回它的索引。如果不存在，則返回-1。

案例:
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.

我的題解：

class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        mapa = dict()
        for i in s:
            if i not in mapa:
                mapa[i] = 1
            else:
                mapa[i] += 1
        for j in range(len(s)):
            a = s[j]
            if a in mapa and mapa[a] == 1:
                return j
        return -1

我的思路：
做兩次循環，第一次循環用來做映射表，用hash表可以快速查詢。
第二遍從頭檢查，在hash表中僅出現一次的字母，即最早不重復的字母。

第二題

283. 移動零
難度：簡單
給定一個數組 nums，編寫一個函數將所有0移動到數組的末尾，同時保持非零元素的相對順序。

案例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
返回 2.

我的題解：

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        l = len(nums)
        j = 0
        for i in range(l):
            if nums[i] !=0:
                nums[j] = nums[i]
                j +=1
        nums[j:l] = [0 for i in range(l-j)]

我的思路：
從頭遍歷數組，如果對應數組的值不為0，則利用慢指針，將非零項向前移動歸并。
最后一個非零項對應的索引到數組的最后則被0包圍了~

第三題

268. 缺失數字
難度：簡單
給定一個包含0, 1, 2, ..., n中 n 個數的序列，找出 0 .. n 中沒有出現在序列中的那個數。

案例:
輸入: [3,0,1]
輸出: 2
輸入: [9,6,4,2,3,5,7,0,1]
輸出: 8

我的題解：

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum = 0
        l =len(nums)
        sum_a = (1+l)*l/2
        for i in nums:
            sum += i
        return sum_a - sum```

我的思路：
缺少的值 = 未缺失數的序列綜合 - 當前的序列總和

第四題

229. 求眾數 II
難度：簡單
給定一個大小為 n 的數組，找出其中所有出現超過? n/3 ?次的元素。

說明: 要求算法的時間復雜度為O(n)，空間復雜度為O(1)。

案例:
輸入: [3,2,3]
輸出: [3]
輸入: [1,1,1,3,3,2,2,2]
輸出: [1,2]

我的題解：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """ 
        a = dict()
        b = list()
        n = len(nums) / 3
        for i in nums:
            if i not in a:
                a[i] = 1
            else:
                a[i] += 1
        for j in a:
            if a[j] > n:
                b.append(j)
        return b

我的思路：
同第一題的思路一致，兩次循環，第一次檢查每個數的重復情況。
第二遍循環用于找出對應的值。

第五題

101. 對稱二叉樹
難度：簡單
給定一個二叉樹，檢查它是否是鏡像對稱的。
例如，二叉樹[1,2,2,3,4,4,3]是對稱的。
但是下面這個[1,2,2,null,3,null,3]則不是鏡像對稱的:

我的題解：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.isSame(root.left,root.right)
    
    def isSame(self,leftNode,rightNode):
        if leftNode == None:
            return rightNode == None
        if rightNode == None:
            return leftNode == None
        if rightNode.val == leftNode.val:
            return self.isSame(leftNode.left,rightNode.right) and self.isSame(leftNode.right,rightNode.left)
        return False

我的思路：
使用遞歸的思路，跳出條件為，左右節點不一致，包括兩者某一個為空的情況。
當還存在下一級的左右節點的時候，就做遞歸進行查找。

第六題

905. 按奇偶排序數組
難度：簡單
給定一個非負整數數組A，返回一個由A的所有偶數元素組成的數組，后面跟A的所有奇數元素。
你可以返回滿足此條件的任何數組作為答案。

示例：
輸入：[3,1,2,4]
輸出：[2,4,3,1]
輸出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也會被接受。

我的題解：

class Solution(object):
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        n = [0]*len(A)
        k = 0
        j = len(A) - 1
        for i in range(len(A)):
            if A[i] % 2 ==1: #奇數
                n[j] = A[i]
                j -= 1
            else:
                n[k] = A[i]
                k += 1
        return n

我的思路：
新建一個數組，然后頭尾兩個指針，分別用于指向偶數和奇數。

第七題

832. 翻轉圖像
難度：簡單
給定一個二進制矩陣A，我們想先水平翻轉圖像，然后反轉圖像并返回結果。
水平翻轉圖片就是將圖片的每一行都進行翻轉，即逆序。例如，水平翻轉[1, 1, 0]的結果是[0, 1, 1]。
反轉圖片的意思是圖片中的0全部被1替換，1全部被0替換。例如，反轉[0, 1, 1]的結果是[1, 0, 0]。

我的題解：

class Solution(object):
    def flipAndInvertImage(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        #逆序
        return [[j ^ 1 for j in i[::-1]] for i in A]

我的思路：
python感覺有很多小作弊的方式，比如這題先進行了逆序，然后再進行了位運算。
僅僅用了一行代碼也是很奇特了。

第八題

922. 按奇偶排序數組 II
難度：簡單
給定一個非負整數數組A，A中一半整數是奇數，一半整數是偶數。
對數組進行排序，以便當A[i]為奇數時，i也是奇數；當A[i]為偶數時，i也是偶數。
你可以返回任何滿足上述條件的數組作為答案。

我的題解：

class Solution(object):
    def sortArrayByParityII(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        count0 = 0
        count1 = 1
        re = []
        for i in A:
            if i%2 == 0:
                re.insert(count0, i)
                count0 += 2
            else:
                re.insert(count1, i)
                count1 += 2
        return re

我的思路：
適用兩個指針，一個從0開始，一個從1開始，每次的步數為2，對應放入奇數和偶數幾顆。

第九題

509. 斐波那契數
難度：簡單
斐波那契數，通常用F(n)表示，形成的序列稱為斐波那契數列。該數列由0和1開始，后面的每一項數字都是前面兩項數字的和。也就是：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

給定N，計算F(N)。

我的題解：

class Solution(object):
    def fib(self, N):
        """
        :type N: int
        :rtype: int
        """
        if N == 0:return 0
        if N==1 or N == 2:return 1
        return (self.fib(N-1)+self.fib(N-2))

我的思路：
因為每一個數的構成，都是由前面的數的基礎構成，所以用遞歸的思路去尋找遞歸棧。
遞歸棧的跳出條件為：n=0/1/2。

第十題

561. 數組拆分 I
難度：簡單
給定長度為2n的數組, 你的任務是將這些數分成 n 對, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得從1 到 n 的 min(ai, bi) 總和最大。

輸入: [1,4,3,2]
輸出: 4
解釋: n 等于 2, 最大總和為 4 = min(1, 2) + min(3, 4).

提示:
n 是正整數,范圍在 [1, 10000].
數組中的元素范圍在 [-10000, 10000].

我的題解：

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return sum(nums[::2])

我的思路：
最大的算法，其實是排序后獲取2個一組中最小的那個數，獲得的總值最大。

第十一題

867. 轉置矩陣
難度：簡單
給定一個矩陣A， 返回A的轉置矩陣。
矩陣的轉置是指將矩陣的主對角線翻轉，交換矩陣的行索引與列索引。
我的題解：

class Solution(object):
    def transpose(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        return zip(*A)

我的思路：
zip()函數，打包為元組的列表。
zip(*)返回二維矩陣。--->解壓

第十二題

1002. 查找常用字符
難度：簡單
給定僅有小寫字母組成的字符串數組 A，返回列表中的每個字符串中都顯示的全部字符（包括重復字符）組成的列表。例如，如果一個字符在每個字符串中出現3次，但不是4次，則需要在最終答案中包含該字符3次。
你可以按任意順序返回答案。
示例 1：

輸入：["bella","label","roller"]
輸出：["e","l","l"]

我的題解：

class Solution(object):
    def commonChars(self, A):
        """
        :type A: List[str]
        :rtype: List[str]
        """
        tmp = list(A[0])
        for i in range(1,len(A)):
            tmp_list =list()
            for j in A[i]:
                if j in tmp:
                    index = tmp.index(j)
                    del tmp[index]
                    tmp_list.append(j)
            tmp = tmp_list
        return tmp

我的思路：
最基礎的思路是雙重循環，外層數組要是遍歷一維，內層主要是循環每個二維。
最開始以a[0]作為重復值的參考，如果比對過程中發現了重復的值，就記錄下來，并因為考慮到參考值本身可能存在重復值，所以刪除對應索引上的值，并根據記錄下來的重復值，不斷的遍歷過程中，就減少，最終獲得的就是正確值。

第十三題

350. 兩個數組的交集 II
難度：簡單
給定兩個數組，編寫一個函數來計算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]

說明：
輸出結果中每個元素出現的次數，應與元素在兩個數組中出現的次數一致。
我們可以不考慮輸出結果的順序。

我的題解：

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        l = list()
        for i in nums2:
            if i in nums1:
                index = nums1.index(i)
                del nums1[index]
                l.append(i)
        return l

我的思路：
另外增加一個數組用于記錄重復值，因為可能存在同個數組中重復值，所以需要刪除對應的索引上的值。

第十四題

349. 兩個數組的交集
難度：簡單
給定兩個數組，編寫一個函數來計算它們的交集。

示例:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2]
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [9,4]

說明:
輸出結果中的每個元素一定是唯一的。
我們可以不考慮輸出結果的順序。

我的題解：

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        l = dict()
        a = list()
        for i in nums2:
            if i in nums1:
                if i not in l:
                    l[i] = 1
        for key in l:
            a.append(key)
        return a

我的思路：
循環其中一個數組，并新建hash記錄重復值。最后遍歷hash表，得出最終結果。

第十五題

566. 重塑矩陣
難度：簡單
在MATLAB中，有一個非常有用的函數reshape，它可以將一個矩陣重塑為另一個大小不同的新矩陣，但保留其原始數據。
給出一個由二維數組表示的矩陣，以及兩個正整數r和c，分別表示想要的重構的矩陣的行數和列數。
重構后的矩陣需要將原始矩陣的所有元素以相同的行遍歷順序填充。
如果具有給定參數的reshape操作是可行且合理的，則輸出新的重塑矩陣；否則，輸出原始矩陣。
示例：

輸入: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
輸出: 
[[1,2,3,4]]
解釋:
行遍歷nums的結果是 [1,2,3,4]。新的矩陣是 1 * 4 矩陣, 用之前的元素值一行一行填充新矩陣。
我的題解：

class Solution(object):
    def matrixReshape(self, nums, r, c):
        """
        :type nums: List[List[int]]
        :type r: int
        :type c: int
        :rtype: List[List[int]]
        """
        l_a = len(nums)
        l_b = len(nums[0])
        if l_a*l_b != r*c:
            return nums
        if l_a == r:
            return nums
        list_a = list()
        list_b = list()
        count = 0
        for i in range(l_a):
            for j in range(l_b):
                list_b.append(nums[i][j])
                count += 1
                if count == c:
                    list_a.append(list_b)
                    list_b = list()
                    count = 0
        return list_a

我的思路：
首先判斷行數和列數是否和給出的值一致，乘積是否一致，用于判斷是否是否直接輸出結果或者是否可行。
然后新建兩個數組用于新建矩陣，遍歷原有矩陣即可。

第十六題

485. 最大連續1的個數
難度：簡單
給定一個二進制數組， 計算其中最大連續1的個數。

示例 1:

輸入: [1,1,0,1,1,1]
輸出: 3
解釋: 開頭的兩位和最后的三位都是連續1，所以最大連續1的個數是3

注意：
輸入的數組只包含0和1。
輸入數組的長度是正整數，且不超過10,000。

我的題解：

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_l = 0
        count = 0
        for i in nums:
            if i == 1 :
                count +=1
            else: ###遇到0
                if count > max_l:
                    max_l = count
                count = 0
        if count > max_l:
            max_l = count             
        return max_l

我的思路：
使用動態規劃的思路，記錄每次的最大值并進行比對。最后輸出最大值。

第十七題

167. 兩數之和 II - 輸入有序數組
難度：簡單
給定一個已按照升序排列 的有序數組，找到兩個數使得它們相加之和等于目標數。

函數應該返回這兩個下標值index1 和index2，其中index1必須小于index2。

說明:

返回的下標值（index1 和 index2）不是從零開始的。

你可以假設每個輸入只對應唯一的答案，而且你不可以重復使用相同的元素。

我的題解：

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        l = len(numbers)
        i = 0
        j = l - 1
        l_a = list()
        while  i < j:
            if numbers[i]+numbers[j] == target:
                l_a.append(i+1)
                l_a.append(j+1)
                return l_a
            elif numbers[i]+numbers[j] > target:
                j -= 1
            else:
                i +=1
        return null

我的思路：
使用頭尾兩個指針，當兩者對應的值相加，當大于目標值的時候，則尾指針左移，當小于目標值得時候，則尾指針右移。

第十八題

633. 平方數之和
難度：簡單
給定一個非負整數 c ，你要判斷是否存在兩個整數a和b，使得a2+b2= c。

示例:

輸入: 5
輸出: True
解釋: 1  1 + 2  2 = 5

我的題解：

import math
class Solution(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        a = int(math.sqrt(c))
        b = 0
        while a > b:
            if a**2 + b**2 == c:
                return True
            elif a**2 + b**2 > c:
                a -= 1
            else:
                b += 1
        if a**2 + b**2 == c:
            return True
        else:
            return False           

我的思路：
兩個指針，一個從0開始，一個從開方數開始，不斷逼近，判定是否平方和為對應值。

第十九題

345. 反轉字符串中的元音字母
難度：簡單
編寫一個函數，以字符串作為輸入，反轉該字符串中的元音字母。
示例:

輸入: "hello"
輸出: "holle"

我的題解：

class Solution(object):
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """
        y = ["a","e","i","o","u","A","E","I","O","U"]
        p = 0 
        q = len(s) - 1
        s = list(s)
        while p<=q:
            if s[q] not in y and s[p] not in y:
                p += 1
                q -= 1
            elif s[p] in y and s[q] not in y:
                q -= 1
            elif s[q] in y and s[p] not in y:
                p += 1
            else:
                flag = s[q]
                s[q] = s[p]
                s[p] = flag
                p += 1
                q -= 1
        return "".join(s)

我的思路：
使用自定義hash表，并使用雙指針，不斷逼近，當于到兩者都是元音的時候，進行數值交換。

第二十題

141. 環形鏈表
難度：簡單
給定一個鏈表，判斷鏈表中是否有環。
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果pos是-1，則在該鏈表中沒有環。

我的題解：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        l1 = head
        l2 = head.next
        while l1 and l2 and l2.next:
            if l1 == l2:
                return True
            l1 = l1.next
            l2 = l2.next.next
        return False

我的思路：
使用快慢兩個指針，一個步數為1，一個步數為2，當存在環的時候，兩者一定會相遇。

第二十一題

985. 查詢后的偶數和
難度：簡單
給出一個整數數組A和一個查詢數組queries。
對于第i次查詢，有val=queriesi, index = queriesi，我們會把val加到A[index]上。然后，第i次查詢的答案是A中偶數值的和。
（此處給定的 index = queriesi 是從 0 開始的索引，每次查詢都會永久修改數組 A。）
返回所有查詢的答案。
你的答案應當以數組 answer 給出，answer[i] 為第 i 次查詢的答案。
示例：

輸入：A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
輸出：[8,6,2,4]
解釋：
開始時，數組為 [1,2,3,4]。
將 1 加到 A[0] 上之后，數組為 [2,2,3,4]，偶數值之和為 2 + 2 + 4 = 8。
將 -3 加到 A[1] 上之后，數組為 [2,-1,3,4]，偶數值之和為 2 + 4 = 6。
將 -4 加到 A[0] 上之后，數組為 [-2,-1,3,4]，偶數值之和為 -2 + 4 = 2。
將 2 加到 A[3] 上之后，數組為 [-2,-1,3,6]，偶數值之和為 -2 + 6 = 4。

我的題解：

class Solution(object):
    def sumEvenAfterQueries(self, A, queries):
        """
        :type A: List[int]
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        l =list()
        sum = 0
        sum_a = 0
        for j in A:
            if j%2 ==0:
                sum_a += j
        for i in range(len(queries)):
            A[queries[i][1]] += queries[i][0]#增加數值
            if A[queries[i][1]] % 2 ==0:#是偶數
                if queries[i][0]%2 ==0:#是偶數
                    sum = sum_a + queries[i][0]
                else:#是奇數
                    sum = sum_a +  A[queries[i][1]]
            else:#是奇數
                if queries[i][0]%2 ==0:#是偶數
                    sum = sum_a
                else:
                    sum = sum_a - A[queries[i][1]] + queries[i][0]
            l.append(sum)
            sum_a =sum
        return l

我的思路
每次比對前，比對所加數的奇偶，以及對應的數原有的奇偶。
當奇數+奇數，則總值加上倆奇數之和；當奇數+偶數，則總值不增加；當偶數加偶數，則總數增加新增值；當偶數+奇數，則總值減少原有偶數值。

按tag來刷，會對對應思路有更為深刻的理解，小李要繼續加油呀！