目录
快速排序
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int arr[N];
void quick_sort(int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
int val = arr[mid];
int p1 = l - 1, p2 = r + 1;
while (p1 < p2) {
while (arr[++p1] < val);
while (arr[--p2] > val);
if (p1 < p2) swap(arr[p1], arr[p2]);
}
quick_sort(l, p2);
quick_sort(p2 + 1, r);
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) cin >> arr[i];
quick_sort(0, n - 1);
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
cout << "\n";
return 0;
}
归并排序
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int arr[N], tmp[N];
void merge_sort(int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
else tmp[k++] = arr[j++];
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= r) tmp[k++] = arr[j++];
for (i = l; i <= r; ++i) arr[i] = tmp[i - l];
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) cin >> arr[i];
merge_sort(0, n - 1);
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
cout << "\n";
return 0;
}
堆排序
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int heap[N], sz;
void down(int u) {
int t = u;
int ls = u << 1;
int rs = u << 1 | 1;
if (ls <= sz && heap[ls] <= heap[t]) t = ls;
if (rs <= sz && heap[rs] <= heap[t]) t = rs;
if (t != u) {
swap(heap[u], heap[t]);
down(t);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> heap[i];
sz = n;
for (int i = n >> 1; i >= 1; --i) down(i);
while (k--) {
int res = heap[1];
cout << res << " ";
swap(heap[1], heap[sz--]);
down(1);
}
return 0;
}
n n n皇后问题
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10;
int n;
char g[N][N];
bool is_valid(int x, int y) {
for (int i = 0; i < n; ++i) if (g[i][y] == 'Q') return false;
for (int i = 0; i < n; ++i) if (g[x][i] == 'Q') return false;
int nx = x, ny = y;
while (nx >= 0 && ny >= 0) {
if (g[nx][ny] == 'Q') return false;
nx--, ny--;
}
nx = x, ny = y;
while (nx < n && ny >= 0) {
if (g[nx][ny] == 'Q') return false;
nx++, ny--;
}
nx = x, ny = y;
while (nx >= 0 && ny < n) {
if (g[nx][ny] == 'Q') return false;
nx--, ny++;
}
nx = x, ny = y;
while (nx < n && ny < n) {
if (g[nx][ny] == 'Q') return false;
nx++, ny++;
}
return true;
}
void dfs(int row, int k) {
if (k == 0) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << g[i][j];
}
cout << "\n";
}
cout << "\n";
return;
}
// 枚举列
for (int i = 0; i < n; ++i) {
if (is_valid(row, i)) {
g[row][i] = 'Q';
dfs(row + 1, k - 1);
g[row][i] = '.';
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = '.';
}
}
dfs(0, n);
return 0;
}
最大和子数组
class Solution {
public:
int maxSubArray(vector<int>& nums) {
const int N = 1e5 + 10;
int arr[N];
int f[N];
int n = nums.size();
for (int i = 0; i < n; ++i) {
arr[i + 1] = nums[i];
}
memset(f, -0x3f, sizeof f);
int res = -0x3f3f3f3f;
arr[0] = 0;
for (int i = 1; i <= n; ++i) {
f[i] = max(arr[i], f[i - 1] + arr[i]);
res = max(res, f[i]);
}
return res;
}
};
爬楼梯
class Solution {
public:
int climbStairs(int n) {
const int N = 46;
int f[N] = {
0};
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; ++i) f[i] = f[i - 1] + f[i - 2];
return f[n];
}
};
中心扩展法求最长回文子序列
采用中心扩展法, 分别枚举所有可能的回文串的中心位置
然后再将回文串长度的类别分为奇数和偶数, 分别统计答案
#include <string>
using namespace std;
class Solution {
public:
int countSubstrings(string s) {
int res = 0;
int n = s.size();
for (int i = 0; i < n; ++i) {
int l = i, r = i;
while (l >= 0 && r < n && s[l--] == s[r++]) res++;
l = i, r = i + 1;
while (l >= 0 && r < n && s[l--] == s[r++]) res++;
}
return res;
}
};
分割回文串
先用DP预处理所有合法的子串, 然后DFS所有分割方式
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
class Solution {
public:
const int N = 20;
bool f[20][20];
void dfs(string &str, vector<vector<string>> &res, vector<string> &tmp, int u) {
if (u >= str.size()) {
res.push_back(tmp);
return;
}
for (int v = u; v < str.size(); ++v) {
if (f[u][v]) {
tmp.push_back(str.substr(u, v - u + 1));
dfs(str, res, tmp, v + 1);
tmp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
memset(f, false, sizeof f);
int n = s.size();
// 预处理回文子串
for (int i = 0; i < n; ++i) {
f[i][i] = true;
if (i + 1 < n && s[i] == s[i + 1]) {
f[i][i + 1] = true;
}
}
for (int len = 3; len <= n; ++len) {
for (int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1;
if (s[i] == s[j] && f[i + 1][j - 1]) {
f[i][j] = true;
}
}
}
vector<vector<string>> res;
vector<string> tmp;
dfs(s, res, tmp, 0);
return res;
}
};
动态规划求最长回文子序列
class Solution {
public:
int longestPalindromeSubseq(string s) {
const int N = 1010;
int f[N][N] = {
0};
int n = s.size();
for (int i = 0; i < n; ++i) f[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1;
if (s[i] == s[j]) f[i][j] = f[i + 1][j - 1] + 2;
else f[i][j] = max(f[i + 1][j], f[i][j - 1]);
}
}
return f[0][n - 1];
}
};
最长回文子串
动态规划预处理每个状态是否是合法的, 同时记录最长的回文字符串
class Solution {
public:
string longestPalindrome(string s) {
const int N = s.size() + 10;
bool f[N][N];
memset(f, false, sizeof f);
int n = s.size();
for (int i = 0; i < n; ++i) f[i][i] = true;
int start = 0, sz = 1;
for (int i = 0; i < n; ++i) {
int j = i + 1;
if (s[i] == s[j]) {
f[i][j] = true;
start = i, sz = 2;
}
}
for (int len = 3; len <= n; ++len) {
for (int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1;
if (s[i] == s[j] && f[i + 1][j - 1]) {
f[i][j] = true;
if (j - i + 1 > sz) {
sz = j - i + 1;
start = i;
}
}
}
}
string res = "";
for (int i = start; i < start + sz; ++i) res += s[i];
return res;
}
};
单调栈
栈底到栈顶的存储的柱子高度是递减的, 当新加入的柱子高度大于当前栈顶的高度的时候, 说明能够形成凹槽, 然后边弹栈边计算积水面积
class Solution {
public:
int trap(vector<int>& height) {
const int N = height.size() + 10;
int stack[N], top = 0;
int res = 0;
for (int i = 0; i < height.size(); ++i) {
int val = height[i];
while (top && val > height[stack[top]]) {
int pre = stack[top--];
if (!top) break;
// 计算两个柱子之间的距离
int d = i - stack[top] - 1;
// 减去凹槽的高度
int h = min(height[stack[top]], height[i]) - height[pre];
res += h * d;
}
stack[++top] = i;
}
return res;
}
};
双指针算法
C - Shortest Duplicate Subarray
问题陈述
给你一个正整数
N N N 和一个长度为 N N N 的整数序列
请判断 A A A 是否存在一个非空(连续)子数组，它有一个重复值，多次出现在 A A A 中。如果存在这样的子数组，求最短的子数组的长度。
维护滑动窗口, 使用 s e t set set记录是否有重复元素, 如果有重复元素缩短左侧窗口, 直到没有重复元素, 然后递增右侧窗口
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, arr[N];
unordered_set<int> s;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) cin >> arr[i];
int res = INF;
int l = 0;
for (int r = 0; r < n; ++r) {
while (s.count(arr[r])) {
res = min(res, r - l + 1);
s.erase(arr[l++]);
}
s.insert(arr[r]);
}
if (res == INF) res = -1;
cout << res << endl;
return 0;
}
贪心策略: 定义两个指针指向两侧, 每次移动高度较小的那个指针, 这样能够围成的面积有可能变大
class Solution {
public:
int maxArea(vector<int>& height) {
int res = 0;
int l = 0, r = height.size() - 1;
while (l < r) {
int h = min(height[l], height[r]);
res = max(res, h * (r - l));
height[l] < height[r] ? l++ : r--;
}
return res;
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int l = 0, r = price.size() - 1;
vector<int> res;
while (l < r) {
int sum = price[l] + price[r];
if (sum == target) {
res.push_back(price[l]);
res.push_back(price[r]);
break;
}
else if (sum < target) l++;
else r--;
}
return res;
}
};
class Solution {
public:
ListNode* middleNode(ListNode* head) {
// 定义快慢指针, 快指针走到终点, 慢指针走到中间
ListNode *u = head;
ListNode *v = head;
while (u != nullptr) {
if (u->next == nullptr) break;
u = (u->next)->next;
v = v->next;
}
return v;
}
};
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *u = head;
ListNode *v = head;
while (u != nullptr && v != nullptr) {
if (u->next == nullptr) break;
u = u->next->next;
v = v->next;
if (u == v) return true;
}
return false;
}
};
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode *u = head;
ListNode *v = head;
cnt--;
while (cnt--) u = u->next;
while (u->next != nullptr) {
u = u->next;
v = v->next;
}
return v;
}
};
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
class Solution {
public:
bool isSubsequence(string s, string t) {
int i = 0, j = 0;
int n = s.size(), m = t.size();
if (n == 0) return true;
while (i < n && j < m) {
if (s[i] == t[j]) {
if (i == n - 1) {
cout << i << endl;
return true;
}
i++;
}
j++;
}
return false;
}
};
将所有0移动到数组末尾, 同时保证剩余元素相对位置不变
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
// i是处理好的下一个位置, j遍历整个数组
int i = 0, j = 0;
while (j < n) {
if (nums[j]) {
swap(nums[i], nums[j]);
i++;
}
j++;
}
}
};
修改 + 分割回文串
f [ i ] [ j ] f[i][j] f[i][j]代表考虑前 i i i个字符并且已经分割了 j j j个回文子串的所有方案的集合
属性: 修改的最少字符
如何进行集合划分/状态转移
考虑第 j j j个回文子串的起始位置 i 0 i_0 i0
f [ i ] [ j ] = m i n ( f [ i 0 ] [ j − 1 ] + c o s t ( S , i 0 + 1 , i ) ) f[i][j] = min(f[i_0][j - 1] + cost(S, i_0 + 1, i)) f[i][j]=min(f[i0][j−1]+cost(S,i0+1,i))
时间复杂度: O ( n 3 k ) O(n ^ 3k) O(n3k)
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 110;
int n;
//f[i][j]考虑前i个字符, 已经分割了j个子串的最小修改字符次数
int f[N][N];
class Solution {
public:
// 计算将l到r修改为回文串需要的最小代价
int cost(string &s, int l, int r) {
int res = 0;
for (int i = l, j = r; i < j; ++i, --j) {
if (s[i] != s[j]) res++;
}
return res;
}
int palindromePartition(string s, int k) {
n = s.size();
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= min(i, k); ++j) {
// 如果只分割了一个子串, 那么就是从开头到当前位置
if (j == 1) f[i][j] = cost(s, 0, i - 1);
// 枚举最后一个回文子串的起始位置
else {
for (int l = j - 1; l < i; ++l) {
f[i][j] = min(f[i][j], f[l][j - 1] + cost(s, l, i - 1));
}
}
}
}
return f[n][k];
}
};
滑动窗口
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
int l = 0, r = 0;
int res = 0;
int cnt = 0;
while (r < n) {
if (nums[r] == 0) cnt++;
while (cnt > k) {
if (nums[l] == 0) cnt--;
l++;
}
res = max(res, r - l + 1);
r++;
}
return res;
}
};
class Solution {
public:
int characterReplacement(string s, int k) {
int n = s.size();
int l = 0, r = 0;
// 记录每个字符出现的次数
int cnt[26] = {
0};
int max_cnt = 0;
int res = 0;
while (r < n) {
cnt[s[r] - 'A']++;
max_cnt = max(max_cnt, cnt[s[r] - 'A']);
if (r - l + 1 - max_cnt > k) {
cnt[s[l] - 'A']--;
l++;
}
res = max(res, r - l + 1);
r++;
}
return res;
}
};
class Solution {
public:
int get(char c) {
if (c == 'F') return 0;
return 1;
}
int maxConsecutiveAnswers(string answerKey, int k) {
int n = answerKey.size();
int l = 0, r = 0;
int cnt[2] = {
0};
int max_cnt = 0;
int res = 0;
while (r < n) {
int &val = cnt[get(answerKey[r])];
val++;
max_cnt = max(max_cnt, val);
if (r - l + 1 - max_cnt > k) {
cnt[get(answerKey[l])]--;
l++;
}
res = max(res, r - l + 1);
r++;
}
return res;
}
};
外层枚举的是不同字符的种类
class Solution {
public:
int longestSubstring(string s, int k) {
int n = s.size();
int res = 0;
for (int i = 1; i <= 26; ++i) {
int cnt[26] = {
0};
int l = 0, r = 0;
int type_cnt = 0;
int tmp = 0;
while (r < n) {
// 当前窗口中字符类型数量小于等于i
if (type_cnt <= i) {
int u = s[r] - 'a';
if (cnt[u] == 0) type_cnt++;
cnt[u]++;
if (cnt[u] == k) tmp++;
r++;
}
// 当前窗口字符数量大于i, 缩小窗口
else {
int u = s[l] - 'a';
if (cnt[u] == k) tmp--;
cnt[u]--;
if (cnt[u] == 0) type_cnt--;
l++;
}
if (type_cnt == i && tmp == i) res = max(res, r - l);
}
}
return res;
}
};
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) return 0;
int n = nums.size();
int l = 0, r = 0;
int res = 0;
int curr = 1;
while (r < n) {
curr *= nums[r];
while (curr >= k) {
curr /= nums[l];
l++;
}
// 以r结尾的子数组的数量
res += r - l + 1;
r++;
}
return res;
}
};
栈
class Solution {
public:
string removeDuplicates(string s) {
string res = "";
for (char c : s) {
if (!res.empty() && res.back() == c) res.pop_back();
else res.push_back(c);
}
return res;
}
};
京公网安备 11010502036488号