1~3 Leetcode 0020\0026\0088

0020 有效的括號 難度：簡單

題目描述：

給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判斷字符串是否有效。
有效字符串需滿足
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。

示例 1:
輸入: “()”
輸出: true
示例 2:
輸入: “()[]{}”
輸出: true
示例 3:
輸入: “(]”
輸出: false
示例 4:
輸入: “([)]”
輸出: false
示例 5:
輸入: “{[]}”
輸出: true

代碼展示（python）

class Solution:def isValid(self, s: str) -> bool:stack=[]map={"[":"]","{":"}","(":")"}for x in s:if x in map:stack.append(map[x])else:if len(stack)!=0:top_element=stack.pop()if x!=top_element:return Falseelse: continueelse: return Falsereturn len(stack)==0

思路展示

當讀取到的符號被判定為左括號的時候（即 in map），將其對應的右括號壓入棧中

當讀取到右括號的時候，與棧目前頂端（最新壓入的右括號）進行比對，如果一直就繼續，如果不正確就返回False

當棧中已經沒有括號（也就是沒有可以匹配的左括號時），又讀取到了右括號，說明是錯誤的，也是返回False

0026 刪除排序數組中的重復項 難度：簡單

題目描述

給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。
不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。

示例 1:
給定數組 nums = [1,1,2],
函數應該返回新的長度 2, 并且原數組 nums 的前兩個元素被修改為 1, 2。
你不需要考慮數組中超出新長度后面的元素。
示例 2:
給定 nums = [0,0,1,1,1,2,2,3,3,4],
函數應該返回新的長度 5, 并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。
你不需要考慮數組中超出新長度后面的元素。

代碼展示（python）

class Solution:def removeDuplicates(self, nums: List[int]) -> int:slowp=0for fastp in range(len(nums)):if(nums[slowp]!=nums[fastp]):slowp+=1nums[slowp]=nums[fastp]return slowp+1

思路展示

這道題因為是排序數組，所以難度降低了

主要的思路是使用“快慢指針”，代碼極其簡短

慢指針只有在數字不同的情況下才會移動，因此慢指針所指及其之前的是所有沒有重復的元素，因此只需要返回慢指針的數字+1，為數組的新長度

快指針在（0，len(nums)）的范圍內循環判斷，當與慢指針一致的時候，進行下一輪循環；不一致的時候，慢指針前進一步，慢指針原來所指的數字更改為快指針所指的數字

0088 合并兩個有序數組

題目描述

給定兩個有序整數數組 nums1 和 nums2，將 nums2 合并到 nums1 中，使得 num1 成為一個有序數組。
說明:
初始化 nums1 和 nums2 的元素數量分別為 m 和 n。
你可以假設 nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素。

輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出: [1,2,2,3,5,6]

代碼展示

class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""current = len(nums1)-1while(current>=0):if(n==0):return;if(m<1):n-=1nums1[current]=nums2[n]current-=1continue;if(n<1):m-=1nums1[current]=nums2[m]current-=1continue;if(nums1[m-1]>nums2[n-1]):m-=1nums1[current]=nums1[m]current-=1else: n-=1nums1[current]=nums2[n]current-=1

思路展示

注意某個數組為空的情況

使用三個指針，一個是nums1 的指針 m，一個是nums2 的指針 n，一個是表示目前正在進行替換的指針current

此處選擇了從后往前的順序進行數字插入，因為兩個數組是有序的，所以從后往前讀取，每次m和n讀取到數字進行比較，更大的那一個插入在現在current 的位置上，因此更大的那一個指針前移一個，current也前移一個。

總結

以上是生活随笔為你收集整理的【Leetcode 刷题题解】python语言+最优美解答+由易到难的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。