LeetCode 6-10题

6.ZigZag Conversion

题目

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

P A H N

A P L S I I G

Y I R

And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

1 2	string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

代码

我的解法：

import numpy as np 
class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows==1:
            return s
        sLen = len(s)
        if sLen%(2*numRows-2)>0 and sLen%(2*numRows-2)<=numRows:
            numCols = 2*(sLen/(2*numRows-2))+1;
        elif sLen%(2*numRows-2)==0:
            numCols = 2*(sLen/(2*numRows-2));
        else:
            numCols = 2*(sLen/(2*numRows-2))+2;
        Array = np.full((numRows,numCols),-1)
        sout = ""
        for i in range(numRows):
            for j in range(numCols):
                if j%2:
                    if i!=0 and i!=(numRows-1):
                        Array[i][j]=(j/2+1)*(2*numRows-2)-i
                else:
                    Array[i][j]=j*(numRows-1)+i
                if Array[i][j]!=-1 and Array[i][j]<sLen:
                    sout += s[int(Array[i][j])]
        return sout

import numpy as np

class Solution(object):

def convert(self, s, numRows):

"""

:type s: str

:type numRows: int

:rtype: str

"""

if numRows==1:

return s

sLen = len(s)

if sLen%(2*numRows-2)>0 and sLen%(2*numRows-2)<=numRows:

numCols = 2*(sLen/(2*numRows-2))+1;

elif sLen%(2*numRows-2)==0:

numCols = 2*(sLen/(2*numRows-2));

else:

numCols = 2*(sLen/(2*numRows-2))+2;

Array = np.full((numRows,numCols),-1)

sout = ""

for i in range(numRows):

for j in range(numCols):

if j%2:

if i!=0 and i!=(numRows-1):

Array[i][j]=(j/2+1)*(2*numRows-2)-i

else:

Array[i][j]=j*(numRows-1)+i

if Array[i][j]!=-1 and Array[i][j]<sLen:

sout += s[int(Array[i][j])]

return sout

思路分析

使用数组完成，大体思路是把创造一个Array，里面每一个位置存放s的元素对应的index。那么在循环遍历的时候就可以逐次加s的元素，把它完成。所以一开始要求这个数组一共有多少列，然后轮询，根据数学推导出来的公式分别赋值，赋值结束后就得到结果，这个做法的问题在于需要数学推导很久，其实并不是最优解法。比较好的思路如下：

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1 or numRows >= len(s):
            return s

        L = [''] * numRows
        index, step = 0, 1

        for x in s:
            L[index] += x
            if index == 0:
                step = 1
            elif index == numRows -1:
                step = -1
            index += step

        return ''.join(L)

class Solution(object):

def convert(self, s, numRows):

"""

:type s: str

:type numRows: int

:rtype: str

"""

if numRows == 1 or numRows >= len(s):

return s

L = [''] * numRows

index, step = 0, 1

for x in s:

L[index] += x

if index == 0:

step = 1

elif index == numRows -1:

step = -1

index += step

return ''.join(L)

这里首先创造了一个二维的矩阵，每一行是一个string，它以index遍历s的每一个元素，以step控制前进的方向，如果第0行，是向下走，那么step累加，否则向上走，step递减。每次的元素加到对应行的string中，最后把L的所有行加在一起即可，这个编程简单，思路清晰，厉害的一笔。

注意点

L = [''] * numRows创造多维数组
numpy库的用法
''.join(L)指令的用法如下：
string.join(seq)是以string作为分隔符，将seq所有的元素(的字符串表示)合并为一个新的字符串

7. Reverse Integer

题目

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output:  321

Input: 123

Output: 321

Example 2:

Input: -123
Output:  -321

Input: -123

Output: -321

Example 3:

Input: 120
Output:  21

Input: 120

Output: 21

Note:
Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

代码

我的解法：

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        sout = ""
        if x>=0:
            s = str(x)
            slen = len(s)
            for i in range(slen):
                sout+=s[slen-1-i]
            print int(sout)
            if int(sout)>2**31-1:
                return 0
            else:
                return int(sout)
        else:
            s = str(-x)
            slen = len(s)
            for i in range(slen):
                sout+=s[slen-1-i]
            print int(sout)
            if -int(sout)<-2**31:
                return 0
            else:
                return -int(sout)

class Solution(object):

def reverse(self, x):

"""

:type x: int

:rtype: int

"""

sout = ""

if x>=0:

s = str(x)

slen = len(s)

for i in range(slen):

sout+=s[slen-1-i]

print int(sout)

if int(sout)>2**31-1:

return 0

else:

return int(sout)

else:

s = str(-x)

slen = len(s)

for i in range(slen):

sout+=s[slen-1-i]

print int(sout)

if -int(sout)<-2**31:

return 0

else:

return -int(sout)

思路分析

我的方法是把x转变成字符型，然后字符逆序，生成新的字符串，把它转化为int型后看他是否越界，越界返回0。

注意点

Python的指数运算不用^,而是使用**

8. String to Integer (atoi)

题目

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

代码

我的解法：

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        if len(str) == 0 : return 0
        ls = list(str.strip())
        if ls[0]=='-':
            sign = -1
        else:
            sign = 1
        if ls[0] in ['-','+']:
            ls = ls[1:]
        ret,i = 0,0
        while i<len(ls) and ls[i].isdigit():
            ret = ret*10 + ord(ls[i])-ord('0')
            i+=1
        return max(-2**31,min(sign*ret,2**31-1))

class Solution(object):

def myAtoi(self, str):

"""

:type str: str

:rtype: int

"""

if len(str) == 0 : return 0

ls = list(str.strip())

if ls[0]=='-':

sign = -1

else:

sign = 1

if ls[0] in ['-','+']:

ls = ls[1:]

ret,i = 0,0

while i<len(ls) and ls[i].isdigit():

ret = ret*10 + ord(ls[i])-ord('0')

i+=1

return max(-2**31,min(sign*ret,2**31-1))

思路分析

这里要注意几种情况，首先是数字前面和后面的空格，所以用str.strip()函数把空格消掉，然后要判断正负号，判断完后把正负号丢掉，轮询取出里面的数字，并且存到ret里面去，最后返回值要注意int类型的范围。

注意点

str.strip()可以去掉str前面和后面的空格
list()可以把str里的每个元素取出来
str.isdigit()可以判断字符串是否只由数字组成，是的话返回True，否则返回False
ord(char)返回char的Ascii位置对应的十进制整数

9. Palindrome Number

题目

Determine whether an integer is a palindrome. Do this without extra space

代码

我的解法：

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x<0:
            return False
        elif x<10:
            return True
        elif x%10==0:
            return False
        reverse = 0
        while x>reverse:
            reverse =10*reverse + x%10
            x = x/10
        return x==reverse or x==reverse/10

class Solution(object):

def isPalindrome(self, x):

"""

:type x: int

:rtype: bool

"""

if x<0:

return False

elif x<10:

return True

elif x%10==0:

return False

reverse = 0

while x>reverse:

reverse =10*reverse + x%10

x = x/10

return x==reverse or x==reverse/10

思路分析

这里要注意几点，首先我想到的方法是化成string类型然后比较，但是这样不符合题目Do this without extra space.的条件，所以可以直接把数字回文，然后比较二者是否相等，但是在回文数的练习中我们知道可能会有溢出的情况，那么我们可以考虑数字的一半是不是相等，所以思路应该这样。

首先，我们应该关心一些边缘情况。所有负数不是回文，例如：-123不是回文，所以我们可以为所有负数返回false。

现在让我们考虑如何恢复数字的后半部分。对于1221号码，如果我们做1221％10，我们得到最后一位数字1，为了得到第二位数字，我们需要从1221中删除最后一位数字，我们可以将它除以10,1221 / 10 = 122.然后我们可以通过做一个10,122％10 = 2的模数再次得到最后一个数字，如果我们把最后一个数字乘以10并加上第二个数字1 * 10 + 2 = 12，我们想要的还原号码。继续这个过程会给我们更多的数字还原的数字。

现在的问题是，我们怎么知道我们已经达到了一半呢？

由于我们将数字除以10，并将倒数乘以10，当原数小于倒数时，意味着我们已经处理了一半的数字。

注意点

任何末尾为0的数字不是回文
15和16行的语序要注意，不能乱换，不然会出问题，因为x已经被处理了

10. Regular Expression Matching

题目

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

'.' Matches any single character.

'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:

bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa", "a*") → true

isMatch("aa", ".*") → true

isMatch("ab", ".*") → true

isMatch("aab", "c*a*b") → true

代码

我的解法：

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if not p:
            return not s
        first_match = bool(s) and p[0] in {s[0],'.'}
        if len(p)>=2 and p[1]=='*':
            return self.isMatch(s,p[2:]) or (first_match and self.isMatch(s[1:],p))
        else:
            return first_match and self.isMatch(s[1:],p[1:])

class Solution(object):

def isMatch(self, s, p):

"""

:type s: str

:type p: str

:rtype: bool

"""

if not p:

return not s

first_match = bool(s) and p[0] in {s[0],'.'}

if len(p)>=2 and p[1]=='*':

return self.isMatch(s,p[2:]) or (first_match and self.isMatch(s[1:],p))

else:

return first_match and self.isMatch(s[1:],p[1:])

思路分析

如果没有'*'，问题会更容易，我们只需从左到右检查文本的每个字符是否匹配模式。

当'*'出现时，我们可能需要检查文本的许多不同的后缀，看它们是否与模式的其余部分相匹配。

递归解决方案是一种直接的方式来表示这种关系。

class Solution(object):
    def isMatch(self, text, pattern):
        if not pattern:
            return not text

        first_match = bool(text) and pattern[0] in {text[0], '.'}
        return first_match and self.isMatch(text[1:], pattern[1:])

class Solution(object):

def isMatch(self, text, pattern):

if not pattern:

return not text

first_match = bool(text) and pattern[0] in {text[0], '.'}

return first_match and self.isMatch(text[1:], pattern[1:])

如果模式中存在星号，它将位于第二个位置p的第二个位置。那么，我们可能会忽略这部分（0个），或者删除文本中的匹配字符（多个，删除一个继续匹配后面的）。如果我们在这些操作之后剩余的字符串匹配，则匹配初始输入。

class Solution(object):
    def isMatch(self, text, pattern):
        if not pattern:
            return not text

        first_match = bool(text) and pattern[0] in {text[0], '.'}

        if len(pattern) >= 2 and pattern[1] == '*':
            return (self.isMatch(text, pattern[2:]) or
                    first_match and self.isMatch(text[1:], pattern))
        else:
            return first_match and self.isMatch(text[1:], pattern[1:])

class Solution(object):

def isMatch(self, text, pattern):

if not pattern:

return not text

first_match = bool(text) and pattern[0] in {text[0], '.'}

if len(pattern) >= 2 and pattern[1] == '*':

return (self.isMatch(text, pattern[2:]) or

first_match and self.isMatch(text[1:], pattern))

else:

return first_match and self.isMatch(text[1:], pattern[1:])

但是这样的解法时间复杂度和空间复杂度都比较高，LeetCode官网上还有另一种DP的解法，但是我看不懂……

注意点

递归函数的书写方式
判断是否有效可以用bool或者lenth来算

ShiRui

上海拾睿教育科技有限公司

LeetCode 6-10题

6.ZigZag Conversion

7. Reverse Integer

8. String to Integer (atoi)

9. Palindrome Number

10. Regular Expression Matching