研一月总结之LeetCode攀登之旅(6)
- 2019 年 10 月 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 I
1.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.作者的话
最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！ 更多内容，请关注本公众号算法系列！
