研一月总结之LeetCode攀登之旅(6)
研一月总结之LeetCode攀登之旅(6)
研一月总结之LeetCode攀登之旅(6)
0.说在前面
1.Z形排列
1.1 思想
1.2 实现
2.atoi
2.1 思想
2.2 实现
3.作者的话
0.说在前面
入学研一至今一个月，做个小总结。
现在的内心状态是“心累”。目前方向未定，甚感迷茫，paper无望，已绝望，跟之前考研的所有的想法均有落差，这也许是自己要去提升的一个“落差度”吧。
在这一个月内，算上这篇文章，再加上后天未上传的，共23篇，github上上传代码6个仓库+，还有本地未上传的，加起来共有8个代码仓库左右，每个仓库代码量不低于300行。公众号文章算上本节15篇。
哎，上研恼火。。。
不说了，自己消化，今天主要分析Z形排列与aoti问题。
1.Z形排列
将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数：
P A H N
A P L S I I G
Y I R之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"
实现一个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);示例 1:
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"示例 2:
输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"
解释:
P I N
A L S I G
Y A H R
P I1.1 思想
P I N
A L S I G
Y A H R
P I
0 6 12
1 5 7 11 13
2 4 8 10
3 9从index角度看，第一行与最后一行构成了等差数列，且公差为6，那么中间的两行其实也是这样的，除去4 5这种夹在两列中间的数，都为等差数列，公差一致，那么这道题的核心在于将夹在两列中间的数对应与原字符串中的index找出来即可！
怎么找？
分为两种情况：
第一种：特殊点，也就是上面构成等差数列的三列。
我们知道当所给的行不同，那么公差也必然不同，于是推出，公差必然与行有关，上述的所给的总行为4，当前行为1时，可以计算出6=2*(4-1)+0，那么当当前行为第二行时候，可以计算出7=2*(4-1)+1。于是往下推导，可以得到当前字符在原字符串中的index=2*(numRows-1)+i(i表示第几行)，那么这样计算出来的只是第1列与第二列的数据，如果是很多数据占据了很多列，就得加上列，也就是与原先的公差d=2*(numRows-1)成线性关系，于是最终的index=2*(numRows-1)*x+i。x表示列，i表示行。
第二种：夹在中间的数
取上述的一部分数据：
1 5 7
2 4 8可以看到夹在中间的数为4，5。会发现一个规律，也就是2+2=4,1+2*2=5，那么这个也是同上面一致，只是公差有间隔而已，根据总行与当前行，类推，2=2*(4-3) 2*2=2*(4-2),于是推导出所加的这个数的index1=2*(numRows-1-i)因为i是从0算起，所以得再减去1，最后4或者5的index1=index+index1
1.2 实现
class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if len(s)<=numRows or numRows==1:
return s
s1=''
for i in range(numRows):
x=0
while 2*(numRows-1)*x + i<len(s):
t = 2*(numRows-1)*x + i
s1+=s[t]
if i!=0 and i!=numRows-1 and (t+2*(numRows-1-i))<len(s):
s1+=s[t+2*(numRows-1-i)]
x+=1
return s1 2.atoi
实现 atoi，将字符串转为整数。
该函数首先根据需要丢弃任意多的空格字符，直到找到第一个非空格字符为止。如果第一个非空字符是正号或负号，选取该符号，并将其与后面尽可能多的连续的数字组合起来，这部分字符即为整数的值。如果第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
字符串可以在形成整数的字符后面包括多余的字符，这些字符可以被忽略，它们对于函数没有影响。
当字符串中的第一个非空字符序列不是个有效的整数；或字符串为空；或字符串仅包含空白字符时，则不进行转换。
若函数不能执行有效的转换，返回 0。
说明：
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。如果数值超过可表示的范围，则返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。2.1 思想
对于本题而言，问题说明已经很详细了，这里主要使用python语言去实现。
- 定义问题边界
- 利用内置函数去除空格处理
- 利用内置函数判断是否是数字
- 利用int强制转换str为int
2.2 实现
相应的解释在代码中，请查看！
class Solution:
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
# 定义边界
INT_MAX = 2**31-1
INT_MIN = -2**31
# 去空格
str_new = str.strip()
# 定义最终结果字符
saved_s = ''
# 字符为空或开头直接为非字符
if len(str_new)==0 or str_new[0].isdigit()==False and str_new[0]!='-' and str_new[0]!='+':
return 0
# 遍历
for i in range(len(str_new)):
# 首位有+-号时,让+-号存储到最终结果字符里面
if str_new[i] == '+' or str_new[i] == '-' or str_new[i].isdigit():
saved_s+=str_new[i]
# 判断下一个是否为数字
if i + 1 < len(str_new) and str_new[i + 1].isdigit() == False:
break
# 最终结果字符只有+-,直接返回0
if saved_s=='+'or saved_s=='-':
return 0
# 获取数字结果
number = int(saved_s)
# 判断是否越界
if number>INT_MAX:
return INT_MAX
elif number<INT_MIN:
return INT_MIN
else:
return number
s = Solution()
a = s.myAtoi('-abc')
print(a)3.作者的话
最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！ 更多内容，请关注本公众号算法系列！