秋招突击——算法打卡——5/28——复习{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];}   elsefor (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);elsereturn 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;
}
};

分析总结

• 时间来不及了，今天就不看官方参考了，明天要准备面试了！