Polaris-hzn8

排序数组中两个数字之和 原题链接：https://leetcode.cn/problems/kLl5u1/ 给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。 1.双指针1234567891011121314151617181920class Solution {public: vector<int> twoSum(vector<int>& numbers, int target) { vector<int> ans; int low = 0, high = numbers.size() - 1; while (low < high) { int sum = numbers[low] + numbers[high]; if (sum == target) { ans.push_back(low); ans.push_back(high); break; } else if (sum < target) { low++; } else if (sum > target) { high--; } } return ans; }}; 时间复杂度：$O(n)$ 空间复杂度：$O(1)$ 2.二分查找12345678910111213141516171819202122class S ...

数组中和为0的三个数 原题链接：https://leetcode.cn/problems/1fGaJU/ 1.暴力法暴力法虽然测试用例能正确输出，但是程序时间复杂度太高直接超时， 123456789101112131415161718192021222324252627class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; //使用双指针解决剩余两个数字 for (int j = i + 1; j < nums.size(); ++j) { for (int k = j + 1; k < nums.size(); ++k) { if (nums[i] + nums[j] + nums[k] == 0) { //判定符合要求的答案是否重复 //ans.push_back({nums[i], nums[j], nums[k]}); if (ans.size() == 0) ans.push_back({nums[i], nums[j], nums[k]}); else { int flag = 1; for (in ...

单词长度的最大乘积 原题链接：https://leetcode.cn/problems/aseY1I/ 给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。 1.暴力法暴力法虽然测试用例能正确输出，但是程序时间复杂度太高直接超时， 1234567891011121314151617181920212223242526class Solution {public: bool have_same_char(string str1, string str2) { for (char c = 'a'; c <= 'z'; ++c) { int flag1 = 0; int flag2 = 0; for (int i = 0; i < str1.size(); ++i) if (str1[i] == c) {flag1 = 1; break;} for (int i = 0; i < str2.size(); ++i) if (str2[i] == c) {flag2 = 1; break;} if (flag1 && flag2) return true; } return false; } int maxProduct(vector<string>& words) { int max = 0; for (int i = 0; i < words.size(); ++i) { for (int j = i; j < words.size(); ++j) { int temp = words[i].size() * words[j].size() ...

快速排序 1.快速排序 注：经典快速排序总是指定数组的最后一个元素作为基准值，随机快速排序指定数组或者某一部分中的随机值作为基准值。 （1）主要思想快速排序的主要思想是分治思想： 任取一个元素作为分界点pivot 对数组区间进行调整（调整方式有很多种），所有比pivot小的元素都放在前面，比pivot大的元素都放在后面，形成左右两个子表 递归处理左右两端区间 （2）局限性快速排序局限性： 快速排序是所有内部排序方法中最好的一个 快速排序是一种不稳定的排序方法 快速排序不是原地排序（程序中使用了递归需要递归调用栈的支持，而栈的长度取决于递归调用的深度） 平均时间复杂度O(nlog2n)：QSort—O(log2n)、Partition—O(n) 平均情况下需要使用O(logn)的栈空间，最坏情况下栈空间可以达到O(n) 快速排序不适用与对原本有序或基本有序的记录序列进行排序（划分元素值的随机性越好，排序速度越快，即非自然排序） 改变划分元素的选取方法，最多只能改变算法平均时间性能，无法改变最坏情况下的时间性能O(n2) 由于每次枢轴pivot记录的关键字都是大于其他所有记录的关键字，致使一次划分之后得到的子序列（1）的长度为0，这时的快速排序就已经退化成为了没有改进措施的冒泡排序了。 2.快速排序模板（1）思路1： 将low值取出单独存放在key中， 对数组进行排序，排序方式为：当右侧比key小时将high覆盖low处值、当左侧比key大时将low覆盖high处 直到low与high相遇时，将key放回low与high相遇的位置 一轮排序完毕（key所在位置为最终有序位置） 递归处理左右两边区间 1234567891011121314151617181920//写法1:使用2个变量 low highint partition(int arr[], int low, int high) { int key = arr[low];//取low处元素的值作为比较参考 while(low < high) {\] while(low < high && arr[high] >= key) --high;//右侧比key元素大的元素结点不动 arr[low] = arr[hi ...

归并排序 1.归并排序（1）基本思想 确定分界点mid = (low + high) / 2 先对左边进行归并排序，然后对右边进行归并排序 将两个有序子序列归并为一个有序序列 （2）归并排序特性 归并排序时间效率为O（nlog2n） 归并排序空间效率为O（n） 归并排序是一个稳定的排序算法 注：关于2路归并的归并树（倒立的二叉树） 二叉树的第h层最多有2h-1个结点，即满足 n ≤ 2h-1 即为 h - 1 = $\lceil log_2n \rceil$ n个元素进行2路归并，归并趟数为$\lceil log_2n \rceil$ 2.归并排序模板12345678910111213141516171819202122//写法1:for循环写法//[low...mid]和[mid+1...high]各自有序 将两个部分归并void merge(int A[], int n, int low, int mid, int high) {//需要传入数组大小n以节省不必要的空间浪费 int i, j, k; int *B = (int *)malloc(n * sizeof(int));//辅助数组B for (k = low; k <= high; ++k) B[k] = A[k]; for (i = low, j = mid + 1, k = i; i <= mid && j <= high; ++k) {//核心归并操作 if (B[i] <= B[j]) A[k] = B[i++]; else A[k] = B[j++]; } while(i <= mid) A[k++] = B[i++];//未归并完的部分直接复制到尾部 while(j <= high) A[k++] = B[j++];}void mergeSort(int A[], int n, int low, int high) { if (low < high) { int mid = (low + high)/2;//从中间划分 mergeSort(A, n, ...

二分模板 1.二分模板二分的本质并不是单调性，而是一种边界。 定义某种性质，使得右半边的部分全部满足该种性质，而左半边的部分全部都不满足该种性质。而二分可以寻找性质的边界。 12345678910111213141516171819//区间[low, high]被划分成[low, mid - 1]和[mid, high]时使用:while (low < high) { int mid = low + high + 1 >> 1; if (check(mid)) low = mid; else high = mid - 1;}//区间[low, high]被划分成[low, mid]和[mid + 1, high]时使用:while (low < high) { int mid = low + high >> 1; if (check(mid)) high = mid;//check判断mid是否满足性质 else low = mid + 1;}//小数二分const double eps = 1e-6;//eps表示精度 取决于题目对精度的要求while (high - low > 1e-8) { double mid = (low + high) / 2; if (check(mid)) low = mid; else high = mid;} 1.AcWing789.数的范围 123456789101112131415161718192021222324252627282930313233343536373839#include<iostream>using namespace std;const int MAX = 1e6 + 10;int n, m, arr[MAX];//整数二分模板//思路：对数组进行二分 分别查找某个数字出现范围的起始坐标与终止坐标int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d", ...

大整数运算 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.算法模板1234for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++; /*具体问题逻辑*/} 常见双指针问题： 对于一个序列，用两个指针维护一段区间 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作 2.双指针练习（1）AcWIng799.最长连续不重复子序列方法1：暴力法1234567891011121314151617181920212223242526272829#include<iostream>using namespace std;const int MAX = 100010;int n;int a[MAX], mark[MAX];bool check(int low, int high) { for (int i = low + 1; i <= high; ++i) { for (int j = low; j < i; ++j) { if (a[i] == a[j]) return false; } } return true;}int main() { int res = 0; cin >> n; for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { if (check(j, i)) res = max(res, i - j + 1); } } cout << res << endl; return 0;} 方法2：双指针法仔细考虑暴力法就会发现，暴力法在解题时有很多地方是重复计算了： 比如 j = 0，i ...

二进制中1的个数 AcWing801.二进制中1的个数 求n的第k位数字: n >> k & 1 返回n的最后一位1：lowbit(n) = n & -n 1234567891011121314151617181920#include<iostream>using namespace std;int lowbit(int x) { return x & -x;}int main() { int n; scanf("%d", &n); while (n--) { int x; int res = 0; scanf("%d", &x); while (x) { x -= lowbit(x);//每次减去x的最后一位1 res++; } printf("%d", res); } return 0;}