秋招突击——算法打卡——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];
                }   
            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;
}
};

分析总结

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