剑指offer 66与67


剑指offer 66与67

1.面试题66. 构建乘积数组

从左往右开始构建,然后从右往左开始构建,最后数组中存储的就是结果。

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int len = a.size();
        vector<int> res(len);
        if(len==0) return res;

        int k=1;
        for(int i=0;i<len;i++) {
            res[i] = k;
            k = k*a[i];
        }
        k = 1;
        for(int i=len-1;i>=0;i--) {
            res[i] *= k;
            k = k*a[i];
        }

        return res;

    }
};

2.面试题67. 把字符串转换成整数

设置一个flag标记,用来判断当前字符串所代表的是正数还是负数。

class Solution {
public:
    int strToInt(string str) {

        int n = str.size();
        int i = 0;
        while(str[i]==' ' && i<n) {
            i++;
        }
        bool flag = true; // 表示正数

        if(str[i] == '-') flag = false;
        // 检测首字符
        if(str[i] == '+' || str[i] == '-')
            i++;
        int res = 0;
        // 当前字符串可以转
        while(i<n && isDigit(str[i])) {
            int tmp = str[i]-'0';
            if(res > INT_MAX/10 || (res==INT_MAX/10 && tmp>7)) // 溢出
                return flag ? INT_MAX : INT_MIN;
            res = res*10 + tmp;
            i++;
        }
        return flag ? res : -res;
    }


    bool isDigit(char x) {
        return x>='0' && x<='9';
    }
};

更多内容,订阅公众号

文章作者: light-city
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 light-city !
评论
  目录