文章目录
- 复习
- Z字形变换
- 实现代码
- 参考代码
- 两数之和
- 复习代码
- 新作
- 整数反转
- 个人实现
- 实现代码
- 参考做法
- 字符串转换整数
- 个人解法
- 分析总结
复习
Z字形变换
实现代码
- 这里使用了他的思想，但是没有用他的代码，虽然已经比上次简洁了，但是还是不够，在学习一下他的代码！
string convert(string s,int numRows){
string res[numRows];
string r ;
if (numRows == 1 ) return s;
for (int i = 0; i < s.size(); ++i) {
if (i % (2 * numRows - 2) == 0)
res[0] += s[i];
if(i % (2 * numRows - 2) == (numRows - 1))
res[numRows - 1] += s[i];
else{
for (int j = 1; j < numRows - 1; ++j) {
if(i % (2 * numRows - 2) == j || i % (2 * numRows - 2) == (2 * numRows - 2 - j))
res[j] += s[i];
}
}
}
for (int i = 0; i < numRows; ++i) {
r += res[i];
}
return r;
}
参考代码
string convert(string s,int n){
string r ;
if (n == 1 ) return s;
// 分别遍历一下numRows还有整个字符串
for (int i = 0; i < n; ++i) {
if(i == 0 || i == n - 1)
for (int j = i; j < s.size(); j += (2 * n -2)) {
r += s[j];
}
else
for (int j = i,k = 2 * n - 2 - i; j < s.size() || k < s.size();j += (2 * n -2) , k += (2 * n -2)) {
if(j < s.size()) r += s[j];
if(k < s.size()) r += s[k];
}
}
return r;
}
两数之和
- 这题很清晰，就是模拟两个数字的相加过程，需要注意的是，就是三个数相加，分别是节点1、节点2、还有addNum，有一个不为空，就继续往上加
复习代码
注意
- 创建一个临时头节点，方便操作
- 操作指针，要判定当前指针是否为空
- 指针记得向后移动
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
auto dummy = new ListNode(),cur = dummy;
int addNum = 0;
while(l1 || l2 || addNum){
if(l1) addNum += l1->val ,l1 = l1->next;
if(l2) addNum += l2->val ,l2 = l2->next;
cur->next = new ListNode(addNum % 10);
cur = cur->next;
addNum = addNum / 10;
}
return dummy->next;
}
新作
整数反转
个人实现
- 因为int类型存储有限，所以想的是直接使用string类型的数据进行处理，就不用担心对应的超范围问题，然后使用stoi函数。同时超过范围的检测，也是使用string进行遍历检测。
不过，今天又是一遍过！
实现代码
int reverse(int x){
bool isPos = x < 0 ? false:true;
string s = to_string(abs(x));
std::reverse(s.begin(), s.end());
// 判定反转后的数字是否超过范围
string m = to_string((int)pow(2,31) - 1);
if (s.size() == m.size())
{
for (int i = 0; i < m.size(); i ++) {
if (s[i] > m[i] ) return 0;
if (s[i] < m[i]) break;
}
}
if (isPos)
return stoi(s);
else
return 0- stoi(s);
}
参考做法
-
通过求余10，来获取当前的位数，然后通过乘以10，来变成对应的数字
-
如果不能存储超过范围的数字，那就通过因式变化实现。
- 下述想法实现的确实比我的简洁很多，而且操作字符串，确实比操作数字要慢很多。
- 字符串底层实现reverse的时间复杂度是，底层是通过反转迭代器来实现的，双指针同时遍历，所以时间复杂度是O(n),和这个算法差不多，只不过我有多遍历了一次判定是否越界。
- 如果会溢出，就变换形态。
int reverse(int x){
int r = 0;
while (x){
if (r > 0 && r > (INT_MAX - x % 10) / 10) return 0;
if (r < 0 && r < (INT_MIN - x % 10) / 10) return 0;
r = r * 10 + x % 10;
x /= 10;
}
return r;
}
字符串转换整数
题目链接
个人解法
- 单纯逐个遍历，然后根据不同的情况进行不同的操作，执行效果如下。逻辑比较松散，需要看看官方思路是怎么做的，会不会完整一点。
class Solution {
public:
int myAtoi(string s){
bool numFlag = false,sigFlag = false;
int r = 0 ,sig = 1;
for (int i = 0; i < s.size(); ++i) {
// 去除前导空格
if (s[i] == ' ' && r == 0) {
if(numFlag || sigFlag) break;
continue;
}
// 判定是否是正负号
if (s[i] == '-' && r == 0 && !sigFlag) {
if (numFlag) break;
sigFlag = true;
sig = -1;
continue;
}
if (s[i] == '+' && r == 0 && !sigFlag) {
if (numFlag) break;
sigFlag = true;
sig = 1;
continue;
}
// 跳过开头的零
if (s[i] == '0' && r == 0) {
numFlag = true;
continue;
}
// 获取数字
if (s[i] <= '9' && s[i] >= '0') {
numFlag = true;
// 需要判定是否会发生越界
int num = s[i] - '0';
if ( r > (INT_MAX - num) / 10){
if (sig == 1) return INT_MAX;
else return INT_MIN;
}
r = r * 10 + num;
}
// 非数字，直接退出，并返回已经拼接成的数字
else break;
// s
}
return r * sig;
}
};
分析总结
- 时间来不及了，今天就不看官方参考了，明天要准备面试了！
