9.3 阿里笔试代码

事实证明，一个公司如果有多场笔试，真的是看运气。尤其是题量只有 2 的阿里，从投票结果可以看出，9.3 题目不难。第二题没 AC 有点小遗憾，但是人生总遗憾，倒也无妨，希望自己顺利进面，后续面试加油。第二题笔试写法 O(n^2) 超时，差不多花了有 30min 优化，目标很明确，降一个 n 到 O(nlogn)，边界没处理好导致失败告终，结束后找到的 BUG，当前已修改。笔试里，第一题 100%，第二题超时 61.67%。值得一提的是，每次重要笔试面试都会在牛客许愿，也发现好神奇。因为看好多人在问第二题代码，所以贴一下，给有需要的人。若有疑问，欢迎交流

// 第一题
#include <iostream>
#include <string>
using namespace std;

int n, flag, ans;
string str1, str2;

int main() {
    cin >> n >> str1 >> str2;
    for (int i = 0; i < n; ++i) {
        if (str1[i] == str2[i] && flag == 1) {
            ++ans;
            flag = 0;
            continue;
        }
        if (str1[i] != str2[i] && flag == 0) {
            flag = 1;
        }
    }
    if (flag == 1) ++ans;
    cout << ans << endl;
    return 0;
}

// 第二题
#include <iostream>
#include <cmath>
using namespace std;

long long a, b, c, ans;
int xMin, xMax, yMin, yMax;

int find_yMin() {
    int l = 0, r = 1e9;
    while (l != r) {
        int mid = ((long long)l + r) >> 1;
        if (pow(mid, 3) >= a) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

int find_yMax() {
    int l = 0, r = 1e9;
    while (l != r) {
        int mid = ((long long)l + r + 1) >> 1;
        if (pow(mid, 3) <= b) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

int find_left(int i, int yMin, int yMax) {
    int l = yMin, r = yMax;
    while (l != r) {
        int mid = ((long long)l + r) >> 1;
        if (pow(i, 2) - pow(mid, 3) >= -c) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

int find_right(int i, int yMin, int yMax) {
    int l = yMin, r = yMax;
    while (l != r) {
        int mid = ((long long)l + r + 1) >> 1;
        if (pow(i, 2) - pow(mid, 3) <= c) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

int main() {
    cin >> a >> b >> c;
    xMin = ceil(sqrt(a));
    xMax = floor(sqrt(b));
    // cout << xMin << " " << xMax << endl;
    yMin = find_yMin();
    yMax = find_yMax();
    // cout << yMin << " " << yMax << endl;
    for (int i = xMin; i <= xMax; ++i) {
        if (pow(i, 2) - pow(yMin, 3) < -c) continue;
        if (pow(i, 2) - pow(yMax, 3) > c) continue;
        int left = find_left(i, yMin, yMax);
        int right = find_right(i, yMin, yMax);
        if (left == right && abs(pow(i, 2) - pow(left, 3)) > c) continue;
        ans += right - left + 1;
        // cout << left << " " << right << endl;
    }
    cout << ans << endl;
    return 0;
}