Leetcode算法题401-500

401-410¶

411-420¶

415. 字符串相加¶

class Solution {
public:
    string addStrings(string num1, string num2) {
        vector<int> A, B;
        int k = 0;
        string res = "";
        for (int i = num1.size() - 1; i >= 0; i--) {
            A.push_back(num1[i] - '0');
        }
        for (int i = num2.size() - 1; i >= 0; i--) {
            B.push_back(num2[i] - '0');
        }
        for (int i = 0; i < A.size() || i < B.size(); i++) {
            if (i < A.size()) k += A[i];
            if (i < B.size()) k += B[i];
            res += char(k % 10 + '0');
            k /= 10;
        }
        if (k) res += char('1');
        reverse(res.begin(), res.end());
        return res;
    }
};

421-430¶

431-440¶

440. 字典序的第K小数字¶

class Solution {
public:
    int getCnt(int prefix, int n) {
        long long p = 1;
        auto A = to_string(n), B = to_string(prefix);
        int dt = A.size() - B.size();
        int res = 0;
        for (int i = 0; i < dt; ++i) {
            res += p;
            p *= 10;
        }
        A = A.substr(0, B.size());
        if (A == B) res += n - prefix * p + 1;
        else if (A > B) res += p;
        return res;
    }

    int findKthNumber(int n, int k) {
        int prefix = 1;
        while (k > 1) {
            int cnt = getCnt(prefix, n);
            if (k > cnt) {
                k -= cnt;
                prefix++;
            } else {
                prefix *= 10;
                --k;
            }
        }
        return prefix;
    }
};

441-450¶

451-460¶

461-470¶

461. 汉明距离¶

本题属于位运算的组合题。先使用异或的性质去除所有二进制不同位的位，再使用与计算二进制中1的个数。

class Solution {
public:
    int hammingDistance(int x, int y) {
        x ^= y;
        int n = 0;
        while (x) {
            x &= (x - 1);
            ++n;
        }
        return n;
    }
};

471-480¶

481-490¶

491-500¶

496. 下一个更大元素 I¶

本题本质上是一个单调栈的模板题，唯一不同的地方就是使用了两个vector存放数据，因此，在找到num2所有元素的下一个更大元素存入哈希表。再将num1中的元素通过哈希表查出对应的答案。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
        // key为nums2中的值，value为对应值下一个更大的元素
        unordered_map<int, int> heap;
        // 存放单调栈
        int stack[1001], top = 0, x;
        vector<int> res;
        for (int i = nums2.size() - 1; i >= 0; i--) {
            x = nums2[i];
            while (top && stack[top] < x) --top;
            if (top) heap[x] = stack[top];
            else heap[x] = -1;
            stack[++top] = x;
        }
        for (int item:nums1){
            res.push_back(heap[item]);
        }
        return res;
    }
};