位运算，双指针，二分，排序算法

文章目录 位运算二进制中1的个数题解代码我们需要0题解代码 排序模版排序1题解代码模版排序2题解代码模版排序3题解代码 双指针最长连续不重复子序列题解代码 二分查找题解代码

位运算

1. bitset< 16 >将十进制数转为16位的二进制数

int x = 25; cout << bitset<16>(x) << endl; 二进制中1的个数

题解

1. 就是每个数与上1判断低位是否是1，是1就加，否则不加，判断完后，这个数右移1位，再判断，直到这个数变为0为止

代码 // 3 011 & 001 1 count++ // >> 001 & 001 1 count++ #include<iostream> #include<vector> using namespace std; int main() { int n; cin >> n; vector<int> v(n); for (int i = 0; i < n; i++) cin >> v[i]; for (int i = 0; i < n; i++) { int count = 0; int val = v[i]; while (val) { if (val & 1) count++; val /= 2; } v[i] = count; } for (int i = 0; i < n; i++) cout << v[i] << " "; return 0; } 我们需要0

题解

1. 利用了x ^ x = 0和0 ^ x = x这两个性质

代码 // 1 ^ 2 ^ 3 ^ x ^ x ^ x // 1 ^ 2 ^ 3 ^ x = 0 // 1 ^ 2 ^ 3 ^ x ^ x == 0 ^ x // 1 ^ 2 ^ 3 == x #include<iostream> #include<vector> using namespace std; int main() { int t, n; cin >> t; int k = 0; int x = 0; while (t--) { cin >> n; vector<int> v(n+1); int sum = 0; for (int i = 1; i <= n; i++) cin >> v[i]; for (int i = 1; i <= n; i++) sum ^= v[i]; cout << sum << '\n'; } return 0; } 排序

1. 使用unique之前要确保数组是有序的，有序的才能确保所有元素都是唯一的 2.unique会把重复的元素移动到数组的末尾，最后返回第一个重复元素的迭代器

模版排序1

题解

1. 先排序，然后用unique进行返回第一个重复元素的迭代器，最后用erase删除这些重复元素

代码 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n; cin >> n; vector<int> v(n); for(int i = 0;i < n;i++) cin >> v[i]; sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(auto x : v) cout << x << " "; return 0; } 模版排序2

题解

1. 自己写一个排序的逻辑，自定义类型的排序 2.升序的，逆置完之后就可以变为降序的了

代码 #include<iostream> #include<vector> #include<algorithm> using namespace std; const int N = 2e5 + 10; struct Book { int a; int b; int c; bool operator<(const Book& v) const { if (a == v.a && b == v.b) return c < v.c; if (a == v.a) return b < v.b; return a < v.a; } }u[N]; int main() { int n = 0; cin >> n; for (int i = 0; i < n; i++) cin >> u[i].a >> u[i].b >> u[i].c; sort(u, u + n); reverse(u, u + n); for (int i = 0; i < n; i++) cout << u[i].a << " " << u[i].b << " " << u[i].c << '\n'; return 0; } 模版排序3

题解

1. 这题用了桶排序的思想 2.记录出现数字的次数，然后用次数控制循环，输出[ ]里的数就是存进去的数，可以按顺序输出了

代码 // 桶排序 #include<iostream> #include<vector> #include<algorithm> using namespace std; const int N = 2e5 + 10; int v[N]; int main() { int n = 0; cin >> n; for(int i = 1;i <= n;i++) { int x; cin >> x; v[x]++; } for(int i = 0;i <= 2e5;i++) { // v[i] 是出现的次数 for(int j = 0;j < v[i];j++) { // i是出现的数字 cout << i << " "; } } cout << '\n'; return 0; } 双指针

1. 一快一慢(快慢指针) 2.区间内维护某个东西(滑动窗口)

最长连续不重复子序列

题解

1. 开始的时候i = 1,j = 0 2.j向右走的条件j+1下标的数不在数组中 3. 如果出现重复的数，更新i,让i向后走 4. 代码中使用桶的思想解决

代码 #include<iostream> #include<vector> #include<algorithm> const int N = 1e5 + 10; using namespace std; int a[N],b[N]; void solve() { int n = 0; cin >> n; for(int i = 1;i <= n;i++) cin >> a[i]; int ans = 0; // 初始化桶数组 for(int i = 1;i <= n;i++) b[a[i]] = 0; for(int i = 1,j = 0;i <= n;i++) { // j < n并且后一个数不在桶数组中 while(j < n && !b[a[j+1]]) b[a[++j]]++; // 更新最大长度 ans = max(ans,j - i + 1); // i之后要++,让i往后走一个,把之前在桶数组中的数删除 b[a[i]]--; } cout << ans << '\n'; } int main() { int T = 0; cin >> T; while(T--) { solve(); } return 0; } 二分

1. 二分的步骤

查找

题解

1. 保证了l始终小于r, l + 1 == r 2.这样保证了a[l] < x, a[r] >= x，后续可以判断a[r] == x

代码 #include<iostream> #include<vector> #include<algorithm> using ll = long long; const int N = 2e5 + 10; using namespace std; int a[N]; void solve() { int n = 0, q = 0; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; while (q--) { int x; cin >> x; int l = 0, r = n; while (l + 1 != r) { int mid = l + (r - l) / 2; if (a[mid] < x) l = mid; else r = mid; } if (a[r] == x) cout << r << " "; else cout << -1 << " "; } } int main() { solve(); return 0; }