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)
|
1 2 3 4 |
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:
|
1 2 |
string convert(string text, int nRows); |
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
代码
我的解法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
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的元素，把它完成。所以一开始要求这个数组一共有多少列，然后轮询，根据数学推导出来的公式分别赋值，赋值结束后就得到结果，这个做法的问题在于需要数学推导很久，其实并不是最优解法。比较好的思路如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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:
|
1 2 3 |
Input: 123 Output: 321 |
Example 2:
|
1 2 3 |
Input: -123 Output: -321 |
Example 3:
|
1 2 3 |
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.
代码
我的解法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
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.
代码
我的解法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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，否则返回Falseord(char)返回char的Ascii位置对应的十进制整数
9. Palindrome Number
题目
Determine whether an integer is a palindrome. Do this without extra space
代码
我的解法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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 '*'.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
'.' 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 |
代码
我的解法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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:]) |
思路分析
如果没有'*'，问题会更容易，我们只需从左到右检查文本的每个字符是否匹配模式。
当'*'出现时，我们可能需要检查文本的许多不同的后缀，看它们是否与模式的其余部分相匹配。
递归解决方案是一种直接的方式来表示这种关系。
|
1 2 3 4 5 6 7 8 |
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个），或者删除文本中的匹配字符（多个，删除一个继续匹配后面的）。如果我们在这些操作之后剩余的字符串匹配，则匹配初始输入。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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来算