LeetCode-数组操作-Python<三>

2018-07-09 13:28:31来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

上一篇: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

 

要回家了,晚上再写。。剩下几题没贴,解决思路关键点还没写。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:python3安装

下一篇:python3-关于GitHub的最基本操作