LeetCode-數組操作-Python<三>

上一篇:LeetCode鏈表相加-Python<二>

以前沒怎麼做過演算法題，來來去去都是那些迴圈，所以先從數組簡單題開始做。

這兩天最大心得：

• 總在邊界里考慮不周到，導致錯誤
• 做暈的時候，連變數名都跟參數重名了
• 有時候，開始考慮的情況太粗糙

幸好，都找出了問題，並通過。下麵貼貼代碼：

題目：無重覆字元的最長子串

給定一個字元串，找出不含有重覆字元的最長子串的長度。

示例：

給定 "abcabcbb" ，沒有重覆字元的最長子串是 "abc" ，那麼長度就是3。

給定 "bbbbb" ，最長的子串就是 "b" ，長度是1。

給定 "pwwkew" ，最長子串是 "wke" ，長度是3。請註意答案必須是一個子串，"pwke" 是 子序列  而不是子串。

通過代碼：

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """       
        maxLen = 0
        tmp = 0
        d = {}
        left = 0
        
        for j in range(len(s)):
            
            if s[j] in d and d[s[j]]>=left:
                left = d[s[j]]+1
            
            tmp = j - left + 1
            maxLen = max(tmp,maxLen)
            d[s[j]] = j   #哪怕重覆也把索引更新到最新了
        
        return maxLen

 題目：有效的括弧

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字元串，判斷字元串是否有效。

有效字元串需滿足：

1. 左括弧必須用相同類型的右括弧閉合。
2. 左括弧必須以正確的順序閉合。

註意空字元串可被認為是有效字元串。

示例 1:

• 輸入: "()"  ，輸出: true
• 輸入: "()[]{}"，輸出: true
• 輸入: "(]"，輸出: false
• input:"([)]"，output：false
• input:"{[]}"，output：true

通過代碼：

class Solution:
    
    def isLeft(self,a):
        if a=='(':
            return 1
        elif a=='[':
            return 1
        elif a=='{':
            return 1
        elif a.isspace():
            return 3
        else:
            return 2
        
    def leftStr(self,a):
        if a==')':
            return '('
        elif a==']':
            return '['
        elif a=='}':
            return '{'
        else:
            print("匹配報錯")
        
    
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []       
        for i in range(len(s)):          
            if self.isLeft(s[i])==1:
                stack.append(s[i])
            elif self.isLeft(s[i])==2:               
                if 0>=len(stack):
                    return False
                else:
                    tmp =stack.pop()
                    print(tmp)
                    left = self.leftStr(s[i])
                    print(left)
                    if tmp==left:                       
                        pass
                    else:
                        return False
            else:
                pass
        
        if len(stack)>0:
            return False
        else:
            return True
   
        
        

題目： 刪除數組重覆項

給定一個排序數組，你需要在原地刪除重覆出現的元素，使得每個元素只出現一次，返回移除後數組的新長度。

不要使用額外的數組空間，你必須在原地修改輸入數組併在使用 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。

你不需要考慮數組中超出新長度後面的元素。

 通過代碼：

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """      
        if (len(nums)==0):
            return 0
        i=0
        for j in range(1,len(nums)):
            if (nums[j]!=nums[j-1]): 
                i=i+1
                nums[i]=nums[j]                               
        
        return i+1

要回家了，晚上再寫。。剩下幾題沒貼，解決思路關鍵點還沒寫。