[leetcode]第二部分

1-Longest Substring Without Repeating Characters

问题描述

给定一个字符串,找到没有重复字符的最长字串。

示例一
输入:abcabcbb
输出:abc
------
示例二
输入:bbbbb
输出:b
------
示例三
输入:pwwkew
输出:wke

注意:返回结果必须是一个字串,pwke是一个子序列而不是字串。

解决思路

最开始的时候想的是最简单粗暴的方法暴力解决:两个循环,第一层循环,索引从0开始,找不重复的子字符串,每次递增1,第二层遍历判断是否有重复,通过借助一个hashSet的结构,可以将其算法复杂度限制在O(n^2)上。提交不成功,原因:某个例子超时。

于是考虑:得找到一个O(n)的方法来解决,也就是只遍历一遍。考虑到:定义两个指针i,j,从前往后,假设s[i,j]中没有重复的字符,那么只需要判断s[j+1]与前面是否有重复字符。如果没有,那么第二个指针继续向前j=j+1;否则的话,找到与哪个字符重复,第一个指针移到下一位,即:i=pre[s[j+1]] + 1, pre[s[j+1]] = j+1, j = j+1,其中pre中存储的是字符的存储位置。这样能保证时间复杂度限制在O(n),提交成功,耗时110ms

代码

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 1 or len(s) == 0:
            return len(s)
        maxLen = 0
        idx = 0
        eIdx = 1
        flagList = s[idx]
        flagDict = {s[idx]: idx}
        while(idx<len(s) and eIdx < len(s)):
            if s[eIdx] not in flagList:
                flagList = s[idx : eIdx+1]
                flagDict[s[eIdx]] = eIdx
            else:
                nowLen = len(flagList)
                nowLen = eIdx - idx
                if nowLen > maxLen:
                    maxLen = nowLen
                idx = flagDict[s[eIdx]] + 1
                flagDict[s[eIdx]] = eIdx
                flagList = s[idx: eIdx+1]
            #print idx, eIdx, flagList
            eIdx += 1
        #print idx, eIdx
        nowLen = eIdx - idx
        if nowLen > maxLen:
            maxLen = nowLen
        return maxLen

2-Median of Two Sorted Arrays

问题描述

有两个长度分别为mn、并且已经排好序的数组: nums1nums2
找到这两个数组的中位数,总体运行时间复杂度控制在 O(log (m+n))

示例一
输入:
nums1 = [1, 3]
nums2 = [2]
输出:2.0
------
示例二
输入:
nums1 = [1, 2]
nums2 = [3, 4]
输出:2.5

解题思路

找两个有序数组之间的中位数,思考一下,计算一个数列的中位数,如果该数列为单数,那么中位数为:s[len(s)/2],否则的话为:(s[len(s)/2-1]+s[len(s)])/2.0。那么,其实很明显,主要把问题转化为:找到两个有序数组的第len(s)/2len(s)/2-1个数就行。

那么怎么获取第k小的数呢?很简单,使用两个指针,分别指向两个数组的开头,然后进行比较和遍历即可。

代码

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m = len(nums1)
        n = len(nums2)
        target = (m+n)/2
        if target == 0:
            if m > 0:
                return nums1[0] * 2 / 2.0
            elif n > 0:
                return nums2[0] * 2 / 2.0
            else:
                return 0.0
        if (m+n) % 2 != 0:
            ret = self.findKthNum(nums1, nums2, target) * 2 / 2.0
        else:
            ret = ( self.findKthNum(nums1, nums2, target-1) + self.findKthNum(nums1, nums2, target) ) / 2.0
        return ret


    def findKthNum(self, nums1, nums2, k):
        m = len(nums1)
        n = len(nums2)
        if m == 0:
            if k < n:
                return nums2[k]
            else:
                return None
        if n == 0:
            if k < m:
                return nums1[k]
            else:
                return None
        i = 0
        j = 0
        nowIdx = 0
        while (i<m and j <n):
            #print nowIdx, i, j, k
            if nums1[i] <= nums2[j]:
                if nowIdx == k:
                    return nums1[i]
                else:
                    nowIdx += 1
                    i += 1
            else:
                if nowIdx == k:
                    return nums2[j]
                else:
                    j += 1
                    nowIdx += 1
        if i == m:
            return nums2[k-nowIdx+j]
        if j == n:
            return nums1[k-nowIdx+i]

3-Longest Palindromic Substring

问题描述

给定一个字符串s,找到s中最长的回文子字符串。可以假定字符串的最长长度为 1000

示例一
输入: "babad"
输出: "bab"
*注意:"aba"也是一个答案*
------
示例二
输入: "cbbd"
输出:"bb"

解决思路

拿到这个问题的时候丝毫摸不着头脑,于是偷偷查找了下网上的资料。偷懒找到了一个解法~主要思想是:动态规划,附一个动态规划的博客。动态规划的核心思想是:使用数学表达式来描述状态,以及如何进行状态之间的转移。在这里,我们先用数学形式来描述和求解这个问题:使用一个变量$a[i][j]$表示子字符串$s[i:j]$是否为回文字符串(取值为TrueFalse)。定义状态之间的转移:

$$a[i][j]=\begin{cases} a[i+1][j-1] & \text{if s[i] == s[j]}\\
False & \text{if s[i] != s[j]}
\end{cases}$$

初始化:很明显,当$i=j$时,$a[i][j]=True$。此外,我们通过看公式不难发现:$a[i][j]$的状态变化依赖于$a[i+1][j-1]$,因此考虑将$i$从后向前遍历,然后将$j$从$i$向后面遍历,另外的考虑到如果相邻两个字符相同,那么该值也应该为True,此时$i-1 >= j + 1$。

代码

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        m = len(s)
        if m <= 1:
            return s
        # init the matrix, the diagonal value is True while others is false
        maxLen = 0
        res = ""
        a = [[ False for i in range(m)] for i in range(m)]
        for i in range(m):
            for j in range(m):
                if i >= j:
                    a[i][j] = True
        for i in range(m, -1, -1):
            for j in range(i, m):
                if s[i] == s[j] and (j-i <= 2 or a[i+1][j-1]):
                    a[i][j] = True
                    if j-i+1 >= maxLen:
                        maxLen = j-i+1
                        res = s[i:j+1]
        return res

4-ZigZag Conversion

问题描述

在给定指定行数之后,使用一个Z字型的模式描写"PAYPALISHIRING"是按照下面的形式描述:

P   A   H   N
A P L S I I G
Y   I   R

然后按照行进行读取,生成的字符串为:"PAHNAPLSIIGYIR"

需要完成一个函数将字符串基于行数完成这个转化:

string convert(string s, int numRows);
示例一
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"
------
示例二
输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"

解释:

P     I    N
A   L S  I G
Y A   H R
P     I

解决思路

拿到这个问题的时候,第一个想法是:找到一个规律,计算出每一行下一个的标识是多少。例如,假设有numRows行,那么第一行第二列的下标值为2*(numRows-1),依次类推,每次都增加2*(numRows-1);而到了第i行,每列之间的间隔顺序分别是2*(numRows-1)-i*2i*2,找到这个规律后,只要不断叠加,直到下标超过字符串的长度为止。需要特别注意的是:第一行和第二行中每次间隔都是一样的,不用特殊处理。


图例: 每列之间的下标间隔示例(numRows=4

第二种方案:考虑使用一个字符串数组来存储每一行的字符,从前往后遍历整个字符串,判断应该将当前的字符应该添加到哪个字符串中,最后再遍历字符串数组。

代码

方案1

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if len(s) <= numRows or numRows == 1:
            return s
        tGap = 2 * (numRows - 1)
        zigStr = ""
        for i in range(numRows):
            j = i
            loop = 0
            gap2 = i * 2
            gap1 = tGap - gap2
            while j < len(s):
                zigStr += s[j]
                if loop % 2 == 0:
                    j = j + gap1
                    if gap1 == 0:
                        j = j + gap2
                else:
                    j = j + gap2
                    if gap2 == 0:
                        j = j + gap1
                loop += 1
        return zigStr

方案2

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        m = len(s)
        if m < numRows:
            m = numRows
        rows = []
        for i in range(m):
            rows.append('')
        goingDown = False
        curRow = 0
        for i in range(len(s)):
            rows[curRow] = rows[curRow] + s[i]
            if curRow == 0 or curRow == numRows -1:
                goingDown = not goingDown
            if goingDown:
                curRow += 1
            else:
                curRow -= 1
        ret = ""
        for i in range(len(rows)):
            ret += rows[i]
        return ret

5-Reverse Integer

问题描述

给定一个32-位有符号的整数,将其位进行翻转。

示例一
输入: 123
输出: 321
------
示例二
输入: -123
输出: -321
------
示例三
输入: 120
输出: 21

注意:假设我们只能存储范围在$[−2^{31}, 2^{31} − 1]$之间的32位有符号整型。当翻转的整数溢出时,该函数返回0。

解决思路

感觉这一题需要关注点在于:如何解决溢出的问题。考虑到整数的范围:[-2147483648, 2147483647]。一个有点作弊的想法是:使用语法自带的异常来处理,从而返回默认值0(o(╯□╰)o,这个想法好像没办法实现,因为溢出并不会报错)。

如果是负数,则先转化为正数,最后返回的时候将其转为负数即可。下面只考虑正数的情况:一般的做法,每次取整数的最后一位,然后每次乘以10,累加起来,核心思路是:

ret = 0
while num > 0:
    flag = num % 10
    ret = ret * 10 + flag
    num = num / 10

接下来就看怎么判断溢出了,分析一下,当$ret >= INTMAX/10$的时候再乘以10,则可能会溢出,分两种情况:
– $ret > INTMAX/10$:肯定会溢出
– $ret == INTMAX/10$:需要判断flag的值是否大于$INTMAX\%10$,如果大于则会溢出。

另外,需要特别注意的是:负数的值比整数多一,因此需要对边界进行个调整。时间复杂度方面,一个while循环,$O(\log(x))$,$log(x)$表示x的位数。

另外,每台机器的$MAXINT$值不一样,在题干给定的条件下,我这里直接使用了math.pow(2,31)计算。

代码


class Solution(object): def reverse(self, x): """ :type x: int :rtype: int """ ret = 0 maxValue = math.pow(2, 31) - 1 minValue = - 1 * math.pow(2, 31) #print minValue, maxValue neg = False threshold1 = maxValue % 10 threshold2 = maxValue / 10 if x < 0: neg = True threshold1 = -1 * minValue % 10 threshold2 = -1 * minValue / 10 x = -1 * x while x != 0: flag = x % 10 if ret > threshold2 or (ret == threshold2 and flag > threshold1): return 0 ret = ret * 10 + flag x = x/10 if neg: ret = -1 * ret return ret

##6-String to Integer (atoi)

问题描述

实现一个函数atoi将字符串转化为一个整数。
该函数先忽略必要的空白字符,直到第一个非空白的字符。然后,从这个字符开始,第一个是可选的加号或减号,后面是一些数字.将其编译为一个数字。

字符串可能会在构成整数的字符后面包含其它的字符,可以将这些字符忽视,并且不会影响该函数的行为。

如果非空白字符的第一个序列不是一个有效的整数,或者如果该字符串要么是空字符串.要么只包含空白字符,不用执行任何转化。

如果没有有效的转化.返回0

注意
– 只有空白字符' '被看做是空白字符
– 假设我们在只能存储32位有符号整数的范围$[-2^{31},2^{31}-1]$的环境中运行。如果整数值超过可表示值的范围,返回INT_MAX($2^{31}-1$)或者INT_MIN(${-2}^{31}$)

示例一
输入: "42"
输出: 42
------
示例二
输入: "   -42"
输出: -42
解释: 第一个非空字符是'-',是一个减号。然后处理尽可能多的数字,字后返回42。
------
示例三
输入: "4193 with words"
输出: 4193
解释: 在遇到 '3' 时转化就停止了,因为下一个字符不是数字字符。
------
示例四
输入: "words and 987"
输出: 0
解释: 第一个非空字符是'w',不是一个数字字符或者 +/- 符号,因此不会执行有效的转化。
------
示例五
输入: "-91283472332"
输入: -2147483648
解释: 数字 "-91283472332" 超过了32位有符号数字的范围,因此返回INT_MIN (−231)。

解题思路

分析下,我们需要处理的字符包含0-9/+/-/' ',其中,如果是空白字符,那么可以忽略,直到第一个数字字符或符号字符表明匹配正式开始,然后直到最后或者是其它字符为止。

另外,考虑到溢出的问题,可以参考上一题整数翻转的考虑来进行处理,在加之前判断是否溢出:
– $ret > INTMAX/10$:肯定会溢出
– $ret == INTMAX/10$:需要判断flag的值是否大于$INTMAX\%10$,如果大于则会溢出。

写好代码之后,第一次提交报错了,输入为" +0 123"时,应该不做转换,我这边进行了处理,还是没看清楚题目,空格符号只针对前面还没正式开始的情况,开始了之后遇到空格也应该要停止。

代码

import math

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        # init the digit dict
        digitDict = {'1': 1, '0': 0, '3': 3, '2': 2, '5': 5, '4': 4, '7': 7, '6': 6, '9': 9, '8': 8}

        # to denote the process is start or not
        isStart = False
        # to denote the number is positive or not
        isPositive = True
        isOverFlow = False
        maxInt = int(math.pow(2, 31)) - 1
        minInt = -1 * int(math.pow(2, 31))
        threahold1 = maxInt / 10
        threahold2 = maxInt % 10
        ret = 0
        for i in range(len(str)):
            w = str[i]
            if w == ' ':
                if isStart:
                    break
                else:
                    continue
            elif w == '+':
                if not isStart:
                    isStart = True
                    isPositive = True
                else:
                    break
            elif w == '-':
                if not isStart:
                    isStart = True
                    isPositive = False
                    threahold1 = -1 * minInt / 10
                    threahold2 = -1 * minInt % 10
                else:
                    break
            elif w in digitDict:
                n = digitDict[w]
                if not isStart:
                    isStart = True
                if  (ret > threahold1  or (ret == threahold1 and n > threahold2)):
                    isOverFlow = True
                    break
                ret = ret * 10 + n
            else:
                break
        if isPositive:
            if isOverFlow:
                return maxInt
            else:
                return ret
        else:
            if isOverFlow:
                return minInt
            else:
                return -1 * ret

7-Palindrome Number

问题描述

判断一个整数是否是一个回文数字。当数组向前读取和向后读取都相同时,整数是一个回文数字。

示例一
输入:121
输出:true
------
示例二
输入:-121
输出:false
解释:从左到右,读取为-121,从右到左,变成了121-。
------
输入:10
输出:false
解释:从右到左,读取为01,因此他不是一个回文数字。

进一步:
是否可以在不将其转变为字符串的情况下解决这个问题?

解题思路

看到这个题目的时候,第一想法是用两个指针分别表示,可是题干里面明确说了不建议使用字符串的方式进行比较…于是乎,想到:可不可以每次获得首尾两个数字进行比较呢?判断首尾是否相同,不相同直接返回,相同则继续进行比较,直到中间没有数字或者数字小于10为止。

提交之后,发现当中间有0的时候,这种方法就失败了,因为在计算中间值的时候会把0给去掉…

于是,换个思路:其实题干给了个很好的提示:将数字翻转过来,判断与原始数字是否相等就可以解决这个问题啦。(不过需要特别注意:溢出的问题~~~,虽然好像如果溢出的话,肯定就不是回文了,但是建议还是做个判断。)

此外,可以进一步进行简化,不一定需要全部翻转才能判断,例如我只翻转一半,将其与前一部分进行比较,如果后面的和前面的一样的话,也能证明该数字是一个回文数字。只不过需要考虑到位数为单数和双数的情况。

代码

方案一

class Solution(object):

    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False
        res = self.getReverse(x)
        if res == x:
            return True
        else:
            return False


    def getReverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        ret = 0
        MAX_INT = pow(2, 31)
        while x>0:
            flag = x % 10
            if ret > MAX_INT/10 or (ret == MAX_INT/10 and flag > MAX_INT%10):
                return MAX_INT
            ret = ret * 10 + flag
            x = x/10
        return ret
打赏

mickey

记录生活,写给几十年后的自己。