Leetcode算法题1301-1400

1301-1310¶

1311-1320¶

1314. 矩阵区域和¶

class Solution {
public:
    //获取边界条件
    int get(vector <vector<int>> &arr,int m, int n, int x, int y ) {
        x = min(max(x, 0), m);
        y = min(max(y, 0), n);
        return arr[x][y];
    }

    vector <vector<int>> matrixBlockSum(vector <vector<int>> &mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector <vector<int>> sum(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = mat[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            }
        }
        vector <vector<int>> ans(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans[i][j] = get(sum, m, n, i + k + 1, j + k+ 1) - get(sum, m, n, i - k, j + k + 1) -
                            get(sum, m, n, i + k + 1, j - k) + get(sum, m, n, i - k, j - k);
            }
        }

        return ans;
    }
};

1321-1330¶

1331-1340¶

1331. 数组序号转换¶

本题就是整数离散化，再用二分查找出对应的元素索引。

class Solution {
public:
    int find(vector<int> &arr, int n) {
        int r = arr.size() - 1, l = 0;
        if (r <= 0)return r + 1;
        int mid;
        while (l < r) {
            mid = l + r + 1 >> 1;
            if (arr[mid] <= n) {
                l = mid;
            } else r = mid - 1;
        }
        return l + 1;
    }

    vector<int> arrayRankTransform(vector<int> &arr) {
        int n = arr.size();
        vector<int> res(arr);
        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(), arr.end()), arr.end());
        for (int i = 0; i < n; ++i) {
            res[i] = find(arr, res[i]);
        }
        return res;
    }
};

1341-1350¶

1351-1360¶

1361-1370¶

1371-1380¶

1381-1390¶

1390. 四因数¶

class Solution {
public:
    int sumFourDivisors(vector<int> &nums) {
        vector < unordered_map < int, int > * > primes;
        for (auto x: nums) {
            unordered_map<int, int> *map = new unordered_map<int, int>;
            for (int i = 2; i <= x / i; ++i) {
                while (x % i == 0) {
                    x /= i;
                    (*map)[i] += 1;
                }
            }
            if (x > 1) (*map)[x] += 1;
            int divisors = 1;
            for (auto &it: *map) {
                divisors *= it.second + 1;
                if (divisors > 4) break;
            }
            if (divisors == 4) primes.push_back(map);
        }
        int res = 0;
        for (auto its: primes) {
            int tmp = 1;
            for (auto it: *its) {
                int p = it.first, a = it.second, t = 1;
                while (a--) t = p * t + 1;
                tmp *= t;
            }
            res += tmp;
        }
        return res;
    }
};

1391-1400¶