算法技巧

二维子矩阵的和 原题链接：https://leetcode.cn/problems/O4NDxx/ 给定一个二维矩阵 matrix，以下类型的多个请求： 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。 实现 NumMatrix 类： NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。 1.二维前缀和1234567891011121314151617181920class NumMatrix {public: vector<vector<int>> prefix; NumMatrix(vector<vector<int>>& matrix) { /* 初始化前缀和数组 */ if (matrix.size() == 0) return; int m = matrix.size(); int n = matrix[0].size(); prefix.assign(m + 1, vector<int>(n + 1, 0)); //prefix.resize(m + 1, vector<int>(n + 1)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + matrix[i][j]; } int sumRegion(int x1, int y1, int x2, int y2) { /* 利用前缀和数组进行面积和su ...

左右两边子数组和相等 原题链接：https://leetcode.cn/problems/tvdfij/solutions/ 给你一个整数数组 nums ，请计算数组的中心下标。 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于最左端，那么左侧数之和视为0，因为在下标左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。 如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标返回-1 1.前缀和12345678910111213141516171819202122class Solution {public: int pivotIndex(vector<int>& nums) { int ans = INT32_MAX; int len = nums.size(); //1.初始化前缀和数组 int *prefix = new int[len + 10](); for (int i = 1; i <= len; ++i) prefix[i] = prefix[i - 1] + nums[i - 1]; //2.开始计算首先处理首位两种特殊情况 if (prefix[len] - prefix[1] == 0) return 0; if (prefix[len - 1] == 0) ans = min(ans , len - 1); //3.处理一般情况 for (int i = 1; i < len - 1; ++i) { if (prefix[i] == prefix[len] - prefix[i + 1]) ans = min(ans, i); } return ans == INT32_MAX ? -1 : ans; }}; 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 2.前缀和优化利用一些简单的数学知识知识，可以对前缀和的思路进行进一步的优 ...

大整数运算 1.AcWing791.高精度加法12345678910111213//大整数加法vector<int> add(vector<int> &A, vector<int> &B) { vector<int> C; int t = 0;//进位数据 for (int i = 0; i < A.size() || i < B.size(); ++i) { if (i < A.size()) t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(1);//最高位进位 return C;} 2.AcWing792.高精度减法12345678910111213141516171819202122232425262728293031//大整数减法vector<int> sub(vector<int> &A, vector<int> &B) { vector<int> C; int t = 0; for (int i = 0; i < A.size(); ++i) {//A.size() > B.size() 故可以省略简写if条件 t = A[i] - t;//检查本位是否有借位 if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1;//判断是否需要借位 else t = 0; } while (C.size() > 1 && C.back() == 0) C.pop_back();//最高位前导零处理 return C;}bool cmp(vector<int> ...

前缀和与差分 1.AcWing795.一维前缀和1234567891011121314int n, m;int arr[MAX], prefix[MAX];int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]); for (int i = 1; i <= n; ++i) prefix[i] = prefix[i - 1] + arr[i];//前缀和数组初始化 while (m--) { int low, high; scanf("%d %d", &low, &high); printf("%d\n", prefix[high] - prefix[low - 1]); } return 0;} 2.AcWing796.二维前缀和1234567891011121314151617int n, m, q;int arr[MAX][MAX], prefix[MAX][MAX];nt main() { scanf("%d %d %d", &n, &m, &q); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &arr[i][j]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + arr[i][j];//前缀初始化 while (q--) { int x1, y1, x2, y2; ...

离散化与区间合并 1.离散化模板离散化问题的性质，整个值域的跨度很大，但是数据非常的稀疏。 123456789101112131415//将所有值排序 并去掉重复元素vector<int> nums;sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());//二分求出x对应的离散化的值int find(int x) {//找到第一个大于等于x的位置 int low = 0, high = nums.size() - 1; while (low < high) { int mid = low + high >> 1; if (nums[mid] >= x) high = mid; else low = mid + 1; } return high + 1;//映射到1, 2, ...n} 2.AcWing802.区间和1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<iostream>#include<algorithm>#include<vector>using namespace std;typedef pair<int, int> PAIR;const int MAX = 300010;int n, m;int a[MAX];int prefix[MAX];vector<int> nums;//离散化数据存储容器vector<PAIR> add, query;//二分求出x对应的离散化的值int find(int x) {//找到第一个大于等于x的位置 int low = 0, high = nums.size() - 1; while (low < high) { int mid ...

二进制求和 原题链接：https://leetcode.cn/problems/add-binary/ 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。 1.参考解答==思路==：大整数加法 1

加一 原题链接：https://leetcode.cn/problems/plus-one/ 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数0之外，这个整数不会以零开头。 1.参考解答==思路==：大整数加法 将最后一位加1 如果最后一位在加法操作后等于10，则需要进行进位 如果在下标为0的数字位等于10，则需要将数字的整体位数加1 1

罗马数字转整数 原题链接：https://leetcode.cn/problems/roman-to-integer/ 罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。 12345678字符 数值I 1V 5X 10L 50C 100D 500M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII 而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值。同样地数字9表示为 IX。 这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给定一个罗马数字，将其转换成整数。 1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution {public: int romanToInt(string s) { int ans = 0; for (int i = 0; i < s.length(); ++i) { if (s[i] == 'I') { //特殊判断 if (s[i + 1] == 'V' || s[i + 1] == 'X') { ans += (s[i + 1] == 'V' ...

回文数 原题链接：https://leetcode.cn/problems/palindrome-number/ 给你一个整数 x ，如果 x 是一个回文整数，返回 true；否则返回 false。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 提示：-231 <= x <= 231 - 1 1.整数反转利用整数反转的思想，来处理回文数字问题 12345678910111213class Solution {public: bool isPalindrome(int x) { if (x < 0) return false; long long ans = 0; long long raw = x; while (x) { ans = ans * 10 + x % 10; x /= 10; } return raw == ans; }}; 2.字符串反转1234567891011121314class Solution {public: bool isPalindrome(int x) { if (x < 0) return false; string raw = to_string(x); string ans = raw; for (int i = 0, j = raw.length() - 1; i < j; ++i, --j) { char c = ans[i]; ans[i] = ans[j]; ans[j] = c; } return raw == ans; }};

整数反转 原题链接：https://leetcode.cn/problems/reverse-integer/ 给你一个 32 位的有符号整数 x ，返回其数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。 假设环境不允许存储 64 位整数（有符号或无符号）（只允许使用int类型的变量） 提示：-231 <= x <= 231 - 1 1234input:120output:21input:0output:0 123456789101112131415161718class Solution {public: int reverse(int x) { int ans = 0; while (x) { if (ans > INT_MAX / 10 || ans < INT_MIN / 10 || ans == INT_MAX / 10 && x % 10 > 7 || ans == INT_MIN / 10 && x % 10 < -8 ) { ans = 0; break; } ans = ans * 10 + x % 10; x /= 10; } return ans; }};