Week 1
货仓选址
思路
绝对值不等式：$|a_1 - x| + |a_2 - x| + |a_3 - x| + … + |a_n - x| \ge |a_n-a_1| + |a_{n-1}-a_{2}|+… $ 结论：当n为奇数，x应在中位数；当n为偶数时，x应在中间两个数之间。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
int a[N];
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
int ans = 0;
for (int i = 0; i < n; i++) ans += abs(a[i]-a[n/2]);
cout << ans;
return 0;
}
数字三角形-DP
思路
从下到上，$ f[i][j] = max(f[i+1][j]+w[i][j], f[i+1][j+1]+w[i][j]) $
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 505;
int f[N][N], w[N][N];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> w[i][j];
for (int i = 1; i <= n; i++)
f[n][i] = w[n][i];
for (int i = n-1; i >= 1; i--)
for (int j = 1; j <= i; j++)
f[i][j] = max(f[i+1][j]+w[i][j], f[i+1][j+1]+w[i][j]);
cout << f[1][1];
return 0;
}
简化(等价变换)版代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 505;
int f[N][N];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> f[i][j];
for (int i = n-1; i >= 1; i--)
for (int j = 1; j <= i; j++)
f[i][j] += max(f[i+1][j], f[i+1][j+1]);
cout << f[1][1];
return 0;
}
Week 2
蛇形矩阵
代码
#include <iostream>
using namespace std;
const int N = 105;
int n, m;
const int dx[]{-1, 0, 1, 0}, dy[]{0, 1, 0, -1};
int q[N][N];
int main() {
cin >> n >> m;
int x = 0, y = 0, d = 1;
for (int i = 1; i <= n * m; i++) {
q[x][y] = i;
int a = x + dx[d], b = y + dy[d];
if (a < 0 || a >= n || b < 0 || b >= m || q[a][b]) {
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
cout << q[i][j] << ' ';
cout << endl;
}
return 0;
}
红与黑-Flood Fill算法
思路
Flood-Fill
- BFS（最短距离）
while 队列为空
{
取出队头t
枚举t的4个邻格
if 格子是陆地并且未开发
标记为已被开发
插入队列
}
- DFS（更方便）
dfs(x, y)
{
将(x, y)标记为已开发
枚举(x, y)的四个邻格
if 格子是陆地并且未开发
dfs该格子
}
代码
BFS
#include <iostream>
#include <queue>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 25;
int n, m;
char g[N][N];
int bfs(int sx, int sy) {
queue<PII> Q;
Q.push({sx, sy});
g[sx][sy] = '#';
int res = 0;
const int dx[]{-1, 0, 1, 0}, dy[]{0, 1, 0, -1};
while (!Q.empty()) {
auto t = Q.front();
Q.pop();
res++;
for (int i = 0; i < 4; i++) {
int nx = t.x + dx[i], ny = t.y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] != '.') continue;
g[nx][ny] = '#';
Q.emplace(nx, ny);
}
}
return res;
}
int main() {
while (cin >> m >> n , n || m) {
for (int i = 0; i < n; i++)
cin >> g[i];
int x, y;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == '@') {
x = i;
y = j;
}
cout << bfs(x, y) << endl;
}
return 0;
}
DFS
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25;
char g[N][N];
int n, m;
const int dx[]{-1, 0, 1, 0}, dy[]{0, 1, 0, -1};
int dfs(int x, int y) {
g[x][y] = '#';
int res = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] != '.') continue;
res += dfs(nx, ny);
}
return res;
}
int main() {
while (cin >> m >> n, n || m) {
int x, y;
for (int i = 0; i < n; i++) {
cin >> g[i];
for (int j = 0; j < m; j++)
if (g[i][j] == '@') {
x = i;
y = j;
}
}
cout << dfs(x, y) << endl;
}
return 0;
}
回文平方
代码
#include <iostream>
#include <algorithm>
using namespace std;
char get(int n) { return n <= 9 ? '0' + n : 'A' - 10 + n; }
string base(int n, int b) {
string s = "";
while (n) {
s += get(n % b);
n /= b;
}
reverse(s.begin(), s.end());
return s;
}
bool check(const string &s) {
for (int i = 0, j = s.length() - 1; i < s.length(); i++, j--)
if (s[i] != s[j]) return false;
return true;
}
int main() {
int b;
cin >> b;
for (int i = 1; i <= 300; i++) {
auto t = base(i * i, b);
if (check(t)) {
cout << base(i, b) << " " << t << endl;
}
}
return 0;
}
剪绳子-浮点数二分
思路
二分 最优化->判定问题
- 情况1：可以[mid, r]
- 情况2：不可以[l, mid)
保留k位小数：r-l < 1e-4
代码
#include <iostream>
using namespace std;
const int N = 100005;
int n, m;
int w[N];
bool check(double mid) {
int cnt = 0;
for (int i = 0; i < n; i++) cnt += w[i] / mid;
return cnt >= m;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> w[i];
double l = 0.0, r = 1e9;
for (int i = 0; i < 100; i++) { // while (r-l > 1e-4)
double mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
printf("%.2f\n", l);
return 0;
}
扩展题
#include <iostream>
using namespace std;
double n;
bool check(double mid) {
return mid*mid*mid < n;
}
int main() {
cin >> n;
double l = -22.0, r = 22.0;
while (r - l > 1e-8) {
double mid = (l+r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.6f\n", l);
return 0;
}
分巧克力-整数二分
思路
$ \sum_{i=0}^{n-1} \lfloor \frac {h_i} {mid} \rfloor \times \lfloor \frac{w_i}{mid} \rfloor\ge k $
- 成立：$[mid, r], l = mid$
- 不成立：$[l, mid-1], r = mid-1 $
代码
#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e5+5;
int h[N], w[N];
int n, k;
bool check(int mid) {
ll s = 0;
for (int i = 0; i < n; i++) {
s += 1LL * (h[i]/mid) * (w[i]/mid);
if (s >= k) return true;
}
return false;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> h[i] >> w[i];
int l = 0, r = 1e5;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid-1;
}
cout << l << endl;
return 0;
}
二分模板
int bsearch_1(int l, int r) {
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid+1;
}
return l
}
int bsearch_2(int l, int r) {
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid-1;
}
}
扩展题
数的范围
#include <iostream> #include <algorithm> using namespace std; int n, q; int a[100010]; int main() { cin >> n >> q; for (int i = 0; i < n; i++) cin >> a[i]; int k; while (q--) { cin >> k; int l = lower_bound(a, a+n, k)-a; int r = upper_bound(a, a+n, k)-a; printf("%d ", a[l]==k? l : -1); printf("%d\n", a[r-1]==k? r-1 : -1); } return 0; }旋转数组的最小数字-不具有单调性，但具有二段性
class Solution { public: int findMin(vector<int>& nums) { if (nums.empty()) return -1; int n = nums.size(); while (n > 1 && nums[0] == nums[n-1]) n--; if (nums[0] <= nums[n-1]) return nums[0]; int l = 0, r = n-1; while (l < r) { int mid = l + r >> 1; if (nums[0] > nums[mid]) r = mid; else l = mid+1; } return nums[r]; } };
校门外的树-区间合并
思路
先求出所有移动树木的操作的区间的并集，那么马路上剩余部分即为最终剩下树木的部分。
区间合并算法
- 将所有区间按左端点从小到大排序
- 从左到右遍历每个区间[L, R]
- $ l_i \le R $， $R = max(R, r_i) $
- $ l_i > R$, 则将[L, R] 存下来，L, R<- $ l_i, r_i $
代码
#include <iostream>
#include <algorithm>
using namespace std;
#define x first
#define y second
const int N = 105;
pair<int, int> seg[N];
int l, m;
int main() {
cin >> l >> m;
for (int i = 0; i < m; i++)
cin >> seg[i].x >> seg[i].y;
sort(seg, seg+m);
int res = l + 1;
int L = seg[0].x, R = seg[0].y;
for (int i = 1; i < m; i++)
if (seg[i].x <= R) R = max(R, seg[i].y);
else {
res -= R - L + 1;
L = seg[i].x;
R = seg[i].y;
}
res -= R - L + 1;
cout << res << endl;
return 0;
}
扩展题-挤牛奶
#include <iostream>
#include <algorithm>
using namespace std;
#define x first
#define y second
const int N = 5005;
pair<int, int> seg[N];
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> seg[i].x >> seg[i].y;
sort(seg, seg+n);
int L = seg[0].x, R = seg[0].y;
int a = 0, b = 0;
for (int i = 1; i < n; i++)
if (seg[i].x <= R) R = max(R, seg[i].y);
else {
b = max(b, seg[i].x-R);
a = max(a, R-L);
L = seg[i].x;
R = seg[i].y;
}
a = max(a, R-L);
cout << a << " " << b << endl;
return 0;
}
奖学金
代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int cnt = 0;
struct node {
int id;
int grades[3];
int get_sum() const {
int s = 0;
for (int i = 0; i < 3; i++)
s += grades[i];
return s;
}
friend istream& operator>>(istream& in, node &a) {
a.id = ++cnt;
for (int i = 0; i < 3; i++)
in >> a.grades[i];
return in;
}
friend bool operator<(const node &a, const node &b) {
int sa = a.get_sum(), sb = b.get_sum();
if (sa != sb) return sa < sb;
else if (a.grades[0] != b.grades[0]) return a.grades[0] < b.grades[0];
else return a.id > b.id;
}
};
int n;
priority_queue<node> Q;
int main() {
cin >> n;
node tmp;
for (int i = 0; i < n; i++) {
cin >> tmp;
Q.push(tmp);
}
for (int i = 0; i < 5; i++) {
auto t = Q.top();
Q.pop();
cout << t.id << " " << t.get_sum() << endl;
}
return 0;
}
Week 3
翻硬币-递推
思路
枚举递推：每一个操作是唯一确定的
代码
#include <iostream>
#include <algorithm>
using namespace std;
string a, b;
void turn(int i) { a[i] == '*' ? a[i] = 'o' : a[i] = '*'; }
int main() {
cin >> a >> b;
int res = 0;
for (int i = 0; i < a.length()-1; i++)
if (a[i] != b[i]) {
turn(i);
turn(i+1);
++res;
}
cout << res << endl;
return 0;
}
扩展题-费解的开关
- 思路
- 枚举第一行的点击方法，共32种，完成第一行的点击后，固定第一行，
- 从第一行开始递推，若达到第n行不全为0，说明这种点击方式不合法。
- 在所有合法的点击方式中取点击次数最少的就是答案。
- 对第一行的32次枚举涵盖了该问题的整个状态空间，因此该做法是正确的
- 时间复杂度：
32*20*5*500 = 一百六十万 对第一行操作有32种可能 * 对前四行有20种操作可能 * 每一次操作都要改变5个灯的状态 * 最多读入的时候可能有500次light矩阵- 最关键的两个性质
- 每一个位置最多只会被点击一次
- 如果固定了第一行，那么满足题意的点击方案最多只有一种
- 代码
#include <iostream> #include <algorithm> #include <climits> #include <cstring> using namespace std; char s[5][5]; void turn(int i, int j) { const int dx[]{0, -1, 0, 1, 0}, dy[]{0, 0, 1, 0, -1}; for (int k = 0; k < 5; k++) { int nx = i + dx[k], ny = j + dy[k]; if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue; s[nx][ny] ^= 1; } } int work() { int res = INT_MAX; for (int k = 0; k < 1 << 5; k++) { char back[5][5]; memcpy(back, s, sizeof s); int cnt = 0; for (int j = 0; j < 5; j++) { if ((k >> j) & 1) { turn(0, j); ++cnt; } } for (int i = 0; i < 4; i++) for (int j = 0; j < 5; j++) if (s[i][j] == '0') { turn(i+1, j); ++cnt; } bool ok = true; for (int j = 0; j < 5; j++) if (s[4][j] == '0') ok = false; if (ok) res = min(res, cnt); memcpy(s, back, sizeof back); } return res <= 6 ? res : -1; } int main() { int n; cin >> n; while (n--) { for (int i = 0; i < 5; i++) cin >> s[i]; cout << work() << endl; } return 0; }
找硬币
哈希表做法$O(n)$
思路
对于当前的元素t，查看之前集合中是否存在m-t，若存在则更新答案，否则添加到集合中。
代码
#include <iostream>
#include <algorithm>
#include <climits>
#include <unordered_set>
using namespace std;
int n, m;
unordered_set<int> S;
int main() {
cin >> n >> m;
int v1 = INT_MAX, v2;
int a, b;
while (n--) {
cin >> a;
b = m - a;
if (S.count(b)) {
if (a > b) swap(a, b);
if (v1 > a) {
v1 = a;
v2 = b;
}
} else S.insert(a);
}
printf(v1 == INT_MAX ? "No Solution" : "%d %d\n", v1, v2);
return 0;
}
双指针做法$O(nlogn)$
思路
Note
双指针算法：如果i++和j--单调性相反就能用双指针做法。
$a[i]+a[j] \le m \ and \ j 最大$
代码
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
const int N = 1e5+5;
int a[N];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a+n);
for (int i = 0, j = n-1; i < n; i++) {
while (i < j && a[i] + a[j] > m) j--;
if (i < j && a[i]+a[j] == m) {
cout << a[i] << " " << a[j] << endl;
return 0;
}
}
cout << "No Solution";
return 0;
}
十三号星期五
思路
- 枚举每个月第一天距离1900-1-1过了多少天days
- 星期：$(days+12)\ mod \ 7 $
代码
#include <iostream>
using namespace std;
const int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int n;
int weekdays[7];
int main() {
cin >> n;
int days = 0;
for (int year = 1900; year < 1900+n; year++) {
for (int i = 1; i <= 12; i++) {
weekdays[(days + 12) % 7]++;
days += month[i];
if (i == 2 && (year % 4 == 0 && year % 100 != 0 || year % 400 == 0)) days++;
}
}
for (int i = 5, j = 0; j < 7; i = (i+1) % 7, j++)
cout << weekdays[i] << " ";
return 0;
}
平方矩阵 II
代码
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int main() {
while (cin >> n, n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
cout << abs(j-i) + 1 << ' ';
cout << '\n';
}
cout << endl;
}
return 0;
}
Longest-increasing-subsequence
思路
- dp[i]: 长度为i的LIS的最后一个元素的最小值
- eg:[0,3,1,6,2,2,7] for each x:
- 0, dp = [0]
- 3, dp = [0, 3]
- 1, dp = [0, 1]
- 6, dp = [0, 1, 6]
- 2, dp = [0, 1, 2]
- 2, dp = [0, 1, 2]
- 7, dp = [0, 1, 2, 7]
- ans = len(dp)
代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = []
for x in nums:
i = bisect_left(dp, x)
if i == len(dp):
dp.append(x)
else:
dp[i] = x
return len(dp)
棋盘挑战-八皇后问题
思路
- 如何判断某些位置能不能填：对角线用截距编号
- dg: y=x+b, b = y-x+n
- udg: y=-x+b, b = y+x
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int path[N], col[N], dg[2*N], udg[2*N];
int n, ans;
void dfs(int x) {
if (x > n) {
ans++;
if (ans <= 3) {
for (int i = 1; i <= n; i++)
cout << path[i] << ' ';
cout << '\n';
}
}
for (int y = 1; y <= n; y++) {
if (!col[y] && !dg[y-x+n] && !udg[y+x]) {
path[x] = y;
col[y] = dg[y-x+n] = udg[y+x] = true;
dfs(x+1);
col[y] = dg[y-x+n] = udg[y+x] = false;
// path[x] = 0;
}
}
}
int main() {
cin >> n;
dfs(1);
cout << ans;
return 0;
}
扩展题-解数独
class Solution {
public:
vector<pair<int, int>> P;
bool check(const vector<vector<char>>& board, int r, int c, char n) {
for (int i = 0; i < 9; i++)
if (board[r][i] == n || board[i][c] == n) return false;
r = r / 3 * 3;
c = c / 3 * 3;
for (int i = r; i < r + 3; i++)
for (int j = c; j < c + 3; j++)
if (board[i][j] == n) return false;
return true;
}
bool dfs(vector<vector<char>>& board, int idx) {
if (idx == (int)P.size()) return true;
int r = P[idx].first, c = P[idx].second;
for (int i = 1; i <= 9; i++)
if (check(board, r, c, i+'0')) {
board[r][c] = i+'0';
if (dfs(board, idx+1)) return true;
board[r][c] = '.';
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (board[i][j] == '.')
P.emplace_back(i, j);
dfs(board, 0);
}
};
货币系统-完全背包
思路
代码
#include <iostream>
using namespace std;
using ll = long long;
const int N = 30, M = 10005;
ll f[N][M];
int n, m;
int w[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> w[i];
f[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k * w[i] <= j; k++)
f[i][j] += f[i-1][j-k*w[i]];
cout << f[n][m] << endl;
return 0;
}
时间优化
- $ f[i][j] = f[i-1][j]+f[i-1][j-w[i]]+f[i-1][j-2w[i]]+…+f[i-1][j-kw[i]] $
- $ f[i][j-v] = f[i-1][j-w[i]]+f[i-1][j-2w[i]]+…+f[i-1][j-kw[i]] $
- 由1-2得：$ f[i][j] = f[i-1][j]+f[i][j-v] $
#include <iostream>
using namespace std;
using ll = long long;
const int N = 30, M = 10005;
ll f[N][M];
int n, m;
int main() {
cin >> n >> m;
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
int v;
cin >> v;
for (int j = 0; j <= m; j++) {
f[i][j] = f[i-1][j];
if (j >= v) f[i][j] += f[i][j-v];
}
}
cout << f[n][m] << endl;
return 0;
}
空间优化
#include <iostream>
using namespace std;
using ll = long long;
const int N = 30, M = 10005;
ll f[M];
int n, m;
int main() {
cin >> n >> m;
f[0] = 1;
for (int i = 1; i <= n; i++) {
int v;
cin >> v;
for (int j = v; j <= m; j++) {
f[j] += f[j-v];
// f[i][j] = f[i-1][j] + f[i][j-v]
}
}
cout << f[m] << endl;
return 0;
}
阶乘
思路
- $ n! = 2^{\alpha}*5^{\beta}*x $
- $ ans = \frac{n!}{10^k}\ mod\ 10=$
我们进行观察，因为0只可能由2的倍数和5的倍数相乘得到，所以在进行乘法的过程中，我们将2和5的倍数给清理掉，这样就保证了不会出现0，然后我们控制其范围，每次相乘取其个位，因为个位肯定是非零元素，十位以后的数字完全没有必要保留下来，最后，我们将多处理的2或者5重新乘回去再取余即可
代码
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int d2 = 0, d5 = 0;
int ans = 1;
for (int i = 2; i <= n; i++) {
int x = i;
while (x % 2 == 0) x /= 2, d2++;
while (x % 5 == 0) x /= 5, d5++;
ans = ans * x % 10;
}
for (int i = 0; i < d2-d5; i++)
ans = ans * 2 % 10;
cout << ans;
return 0;
}
Week 4
滑雪场设计-枚举
思路
- 最优解中，所有的高度都在$[0, 100]$之间
- 只需枚举所有可能的区间
代码
#include <iostream>
#include <climits>
using namespace std;
const int N = 1005;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int ans = INT_MAX;
for (int l = 0; l <= 100-17; l++) {
int r = l+17, cost = 0;
for (int i = 0; i < n; i++)
if (a[i] < l) cost += (l-a[i])*(l-a[i]);
else if (a[i] > r) cost += (a[i]-r)*(a[i]-r);
ans = min(ans, cost);
}
cout << ans;
return 0;
}
整数集合划分-贪心
代码
#include <iostream>
#include <algorithm>
using namespace std;
int a[100005], res;
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
for (int i = 0; i < n; i++) {
if (i >= n >> 1) res += a[i];
else res -= a[i];
}
cout << n % 2 << ' ' << res;
return 0;
}
扩展题-双向搜索
思路
- 先搜索前
N/2个物品可以凑出来的所有重量，存到数组中去 - 对所有重量排序，判重
- 在搜索后一半物品可以凑出来的所有重量
y，在前一半物品搜索出来的重量二分出一个y，使得x+y<=w,x+y最大
- 先搜索前
优化
- 从大到小枚举所有重量，使得搜索到的和更快达到目标
- 均衡两次搜索时间
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
const int N = 46;
int n, w, g[N], k, cnt, wgt[1 << (23 + 2)];
void dfs_1(int x, int s) {
if (x == k) {
wgt[cnt++] = s;
return;
}
if (s * 1ll + g[x] <= w) dfs_1(x + 1, s + g[x]);
dfs_1(x + 1, s);
}
int ans;
void dfs_2(int x, int s) {
if (x == n) {
int l = 0, r = cnt - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (s * 1ll + wgt[mid] <= w) l = mid;
else r = mid - 1;
}
if (s * 1ll + wgt[l] <= w) ans = max(ans, s + wgt[l]);
return;
}
if (s * 1ll + g[x] <= w) dfs_2(x + 1, s + g[x]);
dfs_2(x + 1, s);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d%d", &w, &n);
for (int i = 0; i < n; i++) scanf("%d", &g[i]);
sort(g, g + n, greater<int>());
k = n / 2 + 2;
dfs_1(0, 0);
sort(wgt, wgt + cnt);
cnt = unique(wgt, wgt + cnt) - wgt;
dfs_2(k, 0);
cout << ans;
return 0;
}
合唱队形-LIS
思路
f[i]: 从前往后，以a[i]结尾的最长上升子序列的长度g[i]: 从后往前，以a[i]结尾的最长上升子序列的长度- $ ans = n - max(f[i]+g[i]) + 1$
代码
$ n^2 $
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int n, a[N];
int f[N], g[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++)
if (a[i] > a[j]) f[i] = max(f[i], f[j]+1);
}
for (int i = n; i >= 1; i--) {
g[i] = 1;
for (int j = n; j > i; j--)
if (a[i] > a[j]) g[i] = max(g[i], g[j]+1);
}
int ans = 0;
for (int k = 1; k <= n; k++) ans = max(ans, f[k] + g[k]);
cout << n - ans + 1;
return 0;
$ nlogn $
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int f[N], g[N], a[N], n;
int len1[N], len2[N];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int cnt = 0;
for (int i = 0; i < n; i++) {
auto it = lower_bound(f, f+cnt, a[i])-f;
if (it == cnt) f[cnt++] = a[i];
else f[it] = a[i];
len1[i] = cnt;
}
cnt = 0;
for (int i = n-1; i >= 0; i--) {
auto it = lower_bound(g, g+cnt, a[i])-g;
if (it == cnt) g[cnt++] = a[i];
else g[it] = a[i];
len2[i] = cnt;
}
int ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, len1[i]+len2[i]);
cout << n - ans + 1;
return 0;
}
火星人-排列
思路
实现next_permutation()
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10005;
int n, m, a[N];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
while (m--) {
int k = n-1;
while (a[k-1] > a[k]) k--;
k--;
int t = k;
while (t < n-1 && a[t+1] > a[k]) t++;
swap(a[t], a[k]);
reverse(a+k+1, a+n);
}
for (int i = 0; i < n; i++) cout << a[i] << ' ';
return 0;
}
星空之夜-Flood-fill
思路
- 判断形状是否相似
- 哈希：两两之间的距离之和
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
using P = pair<int, int>;
#define x first
#define y second
const int N = 105;
P c[N*N];
int cnt;
char g[N][N];
int n, m;
inline double get_dist(P a, P b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double get_hash() {
double s = 0;
for (int i = 0; i < cnt; i++)
for (int j = i+1; j < cnt; j++)
s += get_dist(c[i], c[j]);
return s;
}
char get_id(double d) {
static double hash[30];
static int idx = 0;
for (int i = 0; i < idx; i++) {
if (fabs(hash[i] - d) < 1e-8)
return 'a' + i;
}
hash[idx++] = d;
return 'a' + idx - 1;
}
void dfs(int i, int j) {
g[i][j] = '0';
c[cnt++] = {i, j};
for (int x = i-1; x <= i+1; x++)
for (int y = j-1; y <= j+1; y++) {
if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '0') continue;
dfs(x, y);
}
}
int main() {
cin >> m >> n;
for (int i = 0; i < n; i++) cin >> g[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (g[i][j] == '1') {
cnt = 0;
dfs(i, j);
auto d = get_hash();
auto id = get_id(d);
for (int k = 0; k < cnt; k++) g[c[k].x][c[k].y] = id;
}
}
for (int i = 0; i < n; i++) cout << g[i] << endl;
return 0;
}
摘花生-DP
思路
- 状态表示
- 集合：定义f[i][j]为从(1, 1)到达(i, j)的所有方案
- 属性：最大值
- 状态转移
- (i, j)从(i-1, j)即上方过来
- (i, j)从(i, j-1)即左方过来
- 空间压缩
- f[i][j]只需要用到这一层和上一层的f元素，所以可以压缩成滚动数组。在此之上，还可以直接压缩成一维数组。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 105;
int f[N];
int n, m, t;
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> t;
f[j] = max(f[j], f[j-1]) + t;
}
cout << f[m] << endl;
memset(f, 0, sizeof f);
}
}
最大的和-最大子矩形
思路
- 前缀和数组
A[i][j]表示 $ \sum_{i=1}^{n}{a[i][j]} $ - 枚举矩形上下边界
- 求最大连续子序列和
代码
package main
import (
"fmt"
)
var M [201][201]int
var n int
func main() {
fmt.Scanf("%d", &n)
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
fmt.Scanf("%d", &M[i][j])
M[i][j] += M[i-1][j]
}
}
ans := int(-1e9)
for i := 1; i <= n; i++ {
for j := i; j <= n; j++ {
s := 0
for k := 1; k <= n; k++ {
s = max(0, s) + M[j][k] - M[i-1][k]
ans = max(ans, s)
}
}
}
fmt.Println(ans)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
最大的和-线性DP
代码
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 50005;
int n, a[N], f[N], g[N]; // f[i]: 1~i最大连续子段和，g[i]:n~i最大连续子段和
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
fill(f, f+n+2, INT_MIN);
fill(g, g+n+2, INT_MIN);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int s = 0;
for (int i = 1; i <= n; i++) {
s = max(s, 0) + a[i];
f[i] = max(f[i-1], s);
}
s = 0;
for (int i = n; i >= 1; i--) {
s = max(s, 0) + a[i];
g[i] = max(g[i+1], s);
}
int ans = INT_MIN;
for (int i = 1; i < n; i++)
ans = max(ans, f[i] + g[i+1]);
cout << ans << endl;
}
return 0;
}
最大异或对-trie
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5, M = 3e6+5;
int a[N], son[M][2], idx, n;
void insert(int x) {
int p = 0;
for (int i = 30; ~i; i--) {
int t = x >> i & 1;
if (!son[p][t]) son[p][t] = ++idx;
p = son[p][t];
}
}
int query(int x) {
int p = 0, res = 0;
for (int i = 30; ~i; i--) {
int t = x >> i & 1;
if (son[p][!t]) {
res += 1 << i;
p = son[p][!t];
} else {
p = son[p][t];
}
}
return res;
}
int main() {
cin >> n;
int ans = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
insert(a[i]);
ans = max(ans, query(a[i]));
}
cout << ans;
return 0;
}
牛亦或-trie+前缀和
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5, M = 2e6+5;
int son[M][2], a[N], id[M], idx, n;
void insert(int x, int k) {
int p = 0;
for (int i = 20; ~i; i--) {
int t = x >> i & 1;
if (!son[p][t]) son[p][t] = ++idx;
p = son[p][t];
}
id[p] = k;
}
int query(int x) {
int p = 0;
for (int i = 20; ~i; i--) {
int t = x >> i & 1;
if (son[p][!t]) {
p = son[p][!t];
} else {
p = son[p][t];
}
}
return id[p];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] ^= a[i-1];
}
insert(0, 0);
int ans = -1, l, r;
for (int i = 1; i <= n; i++) {
int k = query(a[i]);
int s = a[i] ^ a[k];
if (s > ans) {
ans = s;
l = k + 1, r = i;
}
insert(a[i], i);
}
cout << ans << " " << l << ' ' << r << endl;
return 0;
}
Week 5
开心的金明-01背包
代码
#include <iostream>
#include <algorithm>
using namespace std;
int f[30005];
int n, m;
int main() {
cin >> n >> m;
int v, w;
for (int i = 0; i < m; i++) {
cin >> v >> w;
for (int j = n; j >= v; j--)
f[j] = max(f[j], f[j-v]+w*v);
}
cout << f[n] << endl;
return 0;
}
K倍区间-前缀和
思路
求区间和，可以通过前缀和来求出。sum[r]−sum[l−1]就是区间[l,r]的和。如果区间[l,r]的和是k的倍数则有(sum[r]−sum[l−1])，即sum[r]。因此，我们可以得到一个结论，对前缀和取模之后，两个相等的前缀和就能组成一个k倍区间。
有了这个结论之后，我们就可以使用两层for循环来计数k倍区间的个数，但是由于数据比较大，我们不能这样做。那么我们能不能在计算前缀和的过程中同时来统计k倍区间的个数呢？当然可以。我们可以用一个数组cnt，规定cnt[i]表示当前位置之前，前缀和取模后等于i的个数，以后每出现一次前缀和（取模后）和它相等，那么k倍区间就加上cnt[sum[i]]，然后cnt[sum[i]]++。这样似乎不容易理解，我们用样例举个例子。
对于数列 1 2 3 4 5，k = 2
对前1个数的和模k后为1，在此之前有0个前缀和取模后为1，总个数+0
对前2个数的和模k后为1，在此之前有1个前缀和取模后为1，总个数+1
对前3个数的和模k后为0，在此之前有0个前缀和取模后为0, 总个数+0
对前4个数的和模k后为0，在此之前有1个前缀和取模后为0，总个数+1
对前5个数的和模k后为1，在此之前有2个前缀和取模后为1，总个数+2
但是我们还忽略了一点，就是我们这样做我们少计算了区间·[0,i]构成的k倍区间，其个数为cnt[0]。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
int a[N], n, k, cnt[N];
int main() {
cin >> n >> k;
long ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] = (a[i] + a[i-1]) % k;
ans += cnt[a[i]];
cnt[a[i]]++;
}
cout << ans + cnt[0];
return 0;
}
数独检查-模拟
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 7;
int n, m;
int g[N*N][N*N];
bool st[N*N];
bool check_row() {
for (int i = 0; i < m; i++) {
memset(st, false, sizeof st);
for (int j = 0; j < m; j++) {
int t = g[i][j];
if (t < 1 || t > m) return false;
if (st[t]) return false;
st[t] = true;
}
}
return true;
}
bool check_col() {
for (int i = 0; i < m; i++) {
memset(st, false, sizeof st);
for (int j = 0; j < m; j++) {
int t = g[j][i];
if (t < 1 || t > m) return false;
if (st[t]) return false;
st[t] = true;
}
}
return true;
}
bool check_cell() {
for (int i = 0; i < m; i += n)
for (int j = 0; j < m; j += n) {
memset(st, false, sizeof st);
for (int dx = 0; dx < n; dx++)
for (int dy = 0; dy < n; dy++) {
int t = g[i+dx][j+dy];
if (t < 1 || t > m) return false;
if (st[t]) return false;
st[t] = true;
}
}
return true;
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> n;
m = n * n;
for (int i = 0; i < m; i++)
for (int j = 0; j < m; j++) cin >> g[i][j];
printf(check_row() && check_col() && check_cell() ? "Case #%d: Yes\n" : "Case #%d: No\n", t);
}
return 0;
}
最长公共子序列-LCS
思路
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int n, m, f[N][N];
char a[N], b[N];
int main() {
cin >> n >> m >> a + 1 >> b + 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i] == b[j]) f[i][j] = f[i-1][j-1] + 1;
else f[i][j] = max(f[i-1][j], f[i][j-1]);
cout << f[n][m];
return 0;
}
数独简单版-数独
#include <iostream>
#include <algorithm>
using namespace std;
char g[10][10];
bool row[10][10], col[10][10], cell[3][3][10];
bool dfs(int x, int y) {
if (y == 9) {
x++, y = 0;
}
if (x == 9) {
for (int i = 0; i < 9; i++) cout << g[i] << endl;
return true;
}
if (g[x][y] != '.') return dfs(x, y+1);
for (int i = 1; i <= 9; i++) {
if (!row[x][i] && !col[y][i] && !cell[x/3][y/3][i]) {
g[x][y] = i + '0';
row[x][i] = col[y][i] = cell[x/3][y/3][i] = true;
if (dfs(x, y+1)) return true;
row[x][i] = col[y][i] = cell[x/3][y/3][i] = false;
g[x][y] = '.';
}
}
return false;
}
int main() {
for (int i = 0; i < 9; i++) {
cin >> g[i];
for (int j = 0; j < 9; j++)
if (g[i][j] != '.') {
int t = g[i][j] - '0';
row[i][t] = col[j][t] = cell[i/3][j/3][t] = true;
}
}
dfs(0, 0);
}
献给阿尔吉侬的花束-BFS
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 205;
const int dx[]{-1, 0, 1, 0}, dy[]{0, 1, 0, -1};
char g[N][N];
int dist[N][N];
int r, c;
bool bfs(int x, int y) {
memset(dist, 0, sizeof dist);
queue<pair<int, int>> Q;
Q.push({x, y});
while (!Q.empty()) {
auto [tx, ty] = Q.front();
Q.pop();
if (g[tx][ty] == 'E') {
cout << dist[tx][ty] << endl;
return true;
}
for (int i = 0; i < 4; i++) {
int nx = tx + dx[i], ny = ty + dy[i];
if (nx < 0 || nx >= r || ny < 0 || ny >= c || g[nx][ny] == '#') continue;
Q.push({nx, ny});
if (g[nx][ny] != 'E')
g[nx][ny] = '#';
dist[nx][ny] = dist[tx][ty] + 1;
}
}
cout << "oop!" << endl;
return false;
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> r >> c;
for (int i = 0; i < r; i++) cin >> g[i];
bool is_break = false;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++)
if (g[i][j] == 'S') {
bfs(i, j);
is_break = true;
break;
}
if (is_break) break;
}
}
return 0;
}
a^b-位运算
代码
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
int main() {
ll a, b, p;
cin >> a >> b >> p;
ll res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
cout << res % p << endl;
return 0;
}
耍杂技的牛-贪心
代码
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 50005;
int n;
pair<int, int> a[N];
int main() {
cin >> n;
int w, s;
for (int i = 0; i < n; i++) {
cin >> w >> s;
a[i] = {w+s, w};
}
sort(a, a+n);
int ans = INT_MIN, sum_w = 0;
for (int i = 0; i < n; i++) {
w = a[i].second, s = a[i].first - w;
ans = max(ans, sum_w - s);
sum_w += w;
}
cout << ans;
return 0;
}
数列-二进制
思路
使用n的二进制表示
代码
#include <iostream>
#include <algorithm>
using namespace std;
int pow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
int main() {
int k, n;
cin >> k >> n;
int ans = 0;
for (int i = 0; i < 10; i++) {
if (n >> i & 1) ans += pow(k, i);
}
cout << ans << endl;
return 0;
}
借教室-二分&差分
代码
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
int r[N], d[N], s[N], t[N];
int n, m;
ll b[N];
bool check(int mid) {
for (int i = 1; i <= n; i++) b[i] = r[i] - r[i-1];
for (int i = 1; i <= mid; i++) {
b[s[i]] -= d[i];
b[t[i]+1] += d[i];
}
for (int i = 1; i <= n; i++) {
b[i] += b[i-1];
if (b[i] < 0) return false;
}
return true;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> r[i];
for (int i = 1; i <= m; i++) cin >> d[i] >> s[i] >> t[i];
int l = 0, r = m;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
if (l == m) puts("0");
else printf("-1\n%d", l + 1);
return 0;
}
关押罪犯-二分&染色法判断二分图
思路
- 二分答案，判断能否以当前答案大的点构成二分图
- 使用染色判断能否构成二分图
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20005, M = 200005;
int n, m;
int h[N], ne[M], e[M], w[M], idx;
int color[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int u, int c, int mid) {
color[u] = c;
for (int i = h[u]; ~i; i = ne[i]) {
if (w[i] <= mid) continue;
int v = e[i];
if (color[v]) {
if (color[v] == c)
return false;
} else if (!dfs(v, 3-c, mid)) return false;
}
return true;
}
bool check(int mid) {
memset(color, 0, sizeof color);
for (int i = 1; i <= n; i++)
if (!color[i])
if (!dfs(i, 1, mid)) return false;
return true;
}
int main() {
scanf("%d%d", &n, &m);
int a, b, c;
memset(h, -1, sizeof h);
while (m--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
int l = 0, r = 1e9;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d", l);
return 0;
}
Week 6
乌龟棋-线性DP
思路
状态表示：
f[b1,b2,b3,b4]表示所有第 i 种卡片使用了 bi 张的走法的最大分值。状态计算：将
f[b1,b2,b3,b4]表示的所有走法按最后一步选择哪张卡片分成四类：第 i 类为最后一步选择第 i 种卡片。比如 i=2，则这一类的最大分值是f[b1,b2−1,b3,b4]+score[b1+2b2+3b3+4b4]。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 45;
int f[N][N][N][N], b[4], w[355];
int n, m;
int main() {
cin >> n>> m;
for (int i = 0; i < n; i++) cin >> w[i];
while (m--) {
int t;
cin >> t;
b[t-1]++;
}
for (int A = 0; A <= b[0]; A++)
for (int B = 0; B <= b[1]; B++)
for (int C = 0; C <= b[2]; C++)
for (int D = 0; D <= b[3]; D++) {
int score = w[A * 1 + B * 2 + C * 3 + D * 4];
int &v = f[A][B][C][D];
v = score;
if (A) v = max(v, f[A-1][B][C][D] + score);
if (B) v = max(v, f[A][B-1][C][D] + score);
if (C) v = max(v, f[A][B][C-1][D] + score);
if (D) v = max(v, f[A][B][C][D-1] + score);
}
cout << f[b[0]][b[1]][b[2]][b[3]];
return 0;
}
比例简化-枚举
代码
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int A, B, L;
cin >> A >> B >> L;
int a, b;
double t = A * 1.0 / B;
double delta = 1e9;
for (int i = 1; i <= L; i++) {
for (int j = 1; j <= L; j++) {
if (gcd(i, j) == 1) {
double x = i * 1.0 / j;
if (x >= t && x - t < delta) {
delta = x - t;
a = i, b = j;
}
}
}
}
cout << a << " " << b;
return 0;
}
计算系数
思路
- 二项式定理：$ ans = C_k^n x^n y^m $
- Pascal公式：$ C_n^k = C_{n-1}^{k} + C_{n-1}^{k-1} $
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 10007;
const int N = 1005;
int C[N][N];
int pow(int a, int b) {
int res = 1;
a %= mod;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res % mod;
}
int main() {
int a, b, k, n, m;
cin >> a >> b >> k >> n >> m;
for (int i = 0; i <= k; i++)
for (int j = 0; j <= i; j++) {
if (!j) C[i][j] = 1;
else C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
}
cout << C[k][n] * pow(a, n) % mod * pow(b, m) % mod;
return 0;
}
合并果子
代码
#include <iostream>
#include <queue>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int>> Q;
int main() {
cin >> n;
int x;
while (n--) {
cin >> x;
Q.push(move(x));
}
int ans = 0;
while (Q.size() > 1) {
auto a = Q.top();
Q.pop();
auto b = Q.top();
Q.pop();
Q.push(a + b);
ans += a + b;
}
cout << ans;
return 0;
}
积木大赛-贪心&差分
思路
从后往前操作，如果当前的 bi>0，则将其减1，并将其后的某个负数加1。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
int n, h[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> h[i];
int res = 0;
for (int i = n; i >= 1; i--) res += max(0, h[i]-h[i-1]);
cout << res << endl;
return 0;
}
LeetCode-1755 最接近目标值的子序列和
思路
- generate sums for all subset: DP
- $ sum_i = sum_{i-1} \cup (sum_{i-1}+ nums[i]) $
- 将sum of subset分成两部分，遍历前一部分二分后一部分，并且排序
- 去重优化
代码
class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
const int n = nums.size();
int ans = abs(goal);
vector<int> t1{0}, t2{0};
t1.reserve(1 << (n / 2 + 1)), t2.reserve(1 << (n / 2 + 1));
for (int i = 0; i < n / 2; i++)
for (int j = t1.size() - 1; j >= 0; j--)
t1.push_back(nums[i] + t1[j]);
for (int i = n / 2; i < n; i++)
for (int j = t2.size() - 1; j >= 0; j--)
t2.push_back(nums[i] + t2[j]);
auto it = unique(begin(t1), end(t1));
t1.resize(distance(begin(t1), it));
sort(begin(t1), end(t1), greater<int>());
it = unique(begin(t2), end(t2));
t2.resize(distance(begin(t2), it));
sort(begin(t2), end(t2));
for (const auto &e : t1) {
auto it = lower_bound(begin(t2), end(t2), goal - e);
if (it != t2.end()) ans = min(ans, abs(goal - e - *it));
if (it != t2.begin()) ans = min(ans, abs(goal - e - *(--it)));
}
return ans;
}
};
Week 7
机器人跳跃问题-二分
思路
注意mid大于等于1e5时，一定可以完成游戏
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int h[N], n;
bool check(long mid) {
for (int i = 1; i <= n; i++) {
mid += mid - h[i];
if (mid > 1e5) return true;
if (mid < 0) return false;
}
return true;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> h[i];
int l = 0, r = 1e5;
while (l < r) {
const int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l;
return 0;
}
Z字形扫描
思路
- 下标之和为偶数，从下到上遍历
- 下标之和为奇数，从上到下遍历
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int g[N][N], n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) scanf("%d", &g[i][j]);
for (int i = 2; i <= 2 * n; i ++) {
if (i % 2 == 0) {
for (int j = i; j >= 1; j--) {
if (j >= 1 && j <= n && i - j >= 1 && i - j <= n)
printf("%d ", g[j][i-j]);
}
} else {
for (int j = 1; j <= n; j++) {
if (j >= 1 && j <= n && i - j >= 1 && i - j <= n)
printf("%d ", g[j][i-j]);
}
}
}
return 0;
}
动态求连续区间和-线段树
线段树-代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
struct node {
int l, r, sum;
} tree[N << 2];
int n, m, a[N];
void build(int u, int l, int r) {
if (l == r) tree[u] = {l, r, a[l]};
else {
const int mid = l + r >> 1;
build(u<<1, l, mid), build(u<<1|1, mid+1, r);
tree[u] = {l, r, tree[u<<1].sum + tree[u<<1|1].sum};
}
}
void update(int u, int i, int v) {
if (tree[u].l == i && tree[u].r == i) tree[u].sum += v;
else {
const int mid = tree[u].l + tree[u].r >> 1;
if (i <= mid) update(u<<1, i, v);
else update(u<<1|1, i, v);
tree[u].sum = tree[u<<1].sum + tree[u<<1|1].sum;
}
}
int query(int u, int l, int r) {
if (tree[u].l == l && tree[u].r == r) return tree[u].sum;
const int mid = tree[u].l + tree[u].r >> 1;
if (r <= mid) return query(u<<1, l, r);
else if (l > mid) return query(u<<1|1, l, r);
else return query(u<<1, l, mid) + query(u<<1|1, mid+1, r);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
int k, a, b;
while (m--) {
scanf("%d%d%d", &k, &a, &b);
if(!k) printf("%d\n", query(1, a, b));
else update(1, a, b);
}
return 0;
}
树状数组-代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int C[N], n, m;
void add(int x, int k) {
for (int i = x; i <= n; i += i & -i) C[i] += k;
}
int get_sum(int x) {
int s = 0;
for (int i = x; i >= 1; i -= i & -i) s += C[i];
return s;
}
int main() {
scanf("%d%d", &n, &m);
int t;
for (int i = 1; i <= n; i++) {
scanf("%d", &t);
add(i, t);
}
int k, a, b;
while (m--) {
scanf("%d%d%d", &k, &a, &b);
if (!k) printf("%d\n", get_sum(b) - get_sum(a-1));
else add(a, b);
}
return 0;
}
奇怪的数-组合计数
思路
- 划分为两类
- 0、1：$k$位, $ 2 \le k \le n - 2 $
- 2、3：$n-k$位
- 放0、1：第一位不能放, 剩下$n-1$位可以放$k$个0、1-> $ C_{n-1}^{k} $
- 0的个数：$1 \le cnt_0 \le k-1$, 共$k-1$种可能，2的个数：$1 \le cnt_2 \le n-k-1$，共$n-k-1$种可能
- $ ans = \sum_{k=2}^{n-2}{C_{n-1}^{k}(k-1)(n-k-1)} $
代码
#include <iostream>
using namespace std;
const int N = 1005;
int n, C[N][N];
const int mod = 1e9 + 7;
int main() {
cin >> n;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i; j++)
if (!j) C[i][j] = 1;
else C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
int ans = 0;
for (int k = 2; k <= n - 2; k++) {
ans = (ans + C[n-1][k] * 1ll * (k - 1) % mod * (n - k - 1)) % mod;
}
cout << ans;
return 0;
}
最优配餐-多源BFS
思路
将起点都入队列进行BFS
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1005;
int n, m, k, d, dist[N][N], w[N][N];
queue<pair<int, int>> Q;
void bfs() {
const int dx[]{-1, 0, 1, 0}, dy[]{0, 1, 0, -1};
while (!Q.empty()) {
auto [x, y] = Q.front();
Q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx <= 0 || nx > n || ny <= 0 || ny > n || dist[nx][ny] != -1) continue;
dist[nx][ny] = dist[x][y] + 1;
Q.push({nx, ny});
}
}
}
int main() {
scanf("%d%d%d%d", &n, &m, &k, &d);
memset(dist, -1, sizeof dist);
int x, y;
while (m--) {
scanf("%d%d", &x, &y);
Q.push({x, y});
dist[x][y] = 0;
}
int c;
for (int i = 0; i < k; i++) {
scanf("%d%d%d", &x, &y, &c);
w[x][y] += c;
}
for (int i = 0; i < d; i++) {
scanf("%d%d", &x, &y);
dist[x][y] = -2;
}
bfs();
long ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (w[i][j])
ans += w[i][j] * dist[i][j] * 1ll;
}
printf("%ld\n", ans);
return 0;
}
LeetCode-995 K 连续位的最小翻转次数
思路
差分数组d[i]表示i位置需要翻转的次数 - i-1位置需要翻转的次数
cnt表示当前位置需要翻转的次数
若A[i]+cnt是偶数则需要翻转：cnt++, d[i+k]++
若i+K > n则不可能
代码
class Solution {
public:
int minKBitFlips(vector<int>& A, int K) {
const int n = A.size();
vector<int> d(n + 1, 0);
int cnt = 0, ans = 0;
for (int i = 0; i < n; i++) {
cnt += d[i];
if (!((A[i] + cnt) & 1)) {
if (i + K > n) return -1;
++cnt;
++ans;
d[i+K]--;
}
}
return ans;
}
};
最小生成树
Prim
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
using P = pair<int, int>;
const int N = 2e5 + 5;
vector<P> g[N];
bool vis[N];
int n, m;
priority_queue<P> Q;
int main() {
scanf("%d%d", &n, &m);
int a, b, c;
while (m--) {
scanf("%d%d%d", &a, &b, &c);
g[a].push_back({b, c});
g[b].push_back({a, c});
}
Q.push({0, 1});
long ans = 0;
for (int i = 0; i < n; i++) {
while (true) {
auto [w, v] = Q.top();
Q.pop();
if (vis[v]) continue;
vis[v] = true;
ans += -w;
for (auto [_v, _w] : g[v]) {
if (vis[_v]) continue;
Q.push({-_w, _v});
}
break;
}
}
printf("%ld\n", ans);
return 0;
}
Kruskal
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
class UF {
vector<int> id, sz;
public:
UF(int N) {
id.resize(N);
sz.resize(N);
for (int i = 0; i < N; i++) {
id[i] = i;
sz[i] = 1;
}
}
int find(int p) {
while (p != id[p]) {
id[p] = id[id[p]];
p = id[p];
}
return p;
}
bool _union(int p, int q) {
int i = find(p), j = find(q);
if (i == j) return false;
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
return true;
}
};
struct node {
int w, u, v;
friend bool operator<(const node &a, const node& b) {
if (a.w == b.w) {
return make_pair(a.u, a.v) > make_pair(b.u, b.v);
}
return a.w > b.w;
}
};
int n, m;
priority_queue<node> Q;
int main() {
scanf("%d%d", &n, &m);
UF uf(n);
int a, b, c;
while (m--) {
scanf("%d%d%d", &a, &b, &c);
Q.push({c, a, b});
}
int cnt = 0;
long ans = 0;
while (!Q.empty() && cnt < n - 1) {
auto [w, u, v] = Q.top();
Q.pop();
if (uf._union(u-1, v-1)) {
ans += w;
++cnt;
}
}
printf("%ld\n", ans);
return 0;
}
单源最短路
代码
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
using P = pair<int, int>;
const int N = 2505, M = 12500;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int n, m, dist[N];
bool st[N];
priority_queue<P> Q;
void dijkstra(int s, int t) {
memset(dist, 0x3f, sizeof dist);
Q.push({0, s});
dist[s] = 0;
while (!Q.empty()) {
auto [d, u] = Q.top();
Q.pop();
if (st[u])
continue;
st[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (dist[v] > -d + w[i]) {
dist[v] = -d + w[i];
Q.push({-dist[v], v});
}
}
}
}
int main() {
memset(h, -1, sizeof h);
int s, t;
scanf("%d%d%d%d", &n, &m, &s, &t);
int a, b, c;
while (m--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
dijkstra(s, t);
printf("%d\n", dist[t]);
return 0;
}
网络延时-树形DP
思路
树形DP模板
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20005;
int h[N], e[N], ne[N], idx;
int n, m, f[N]; // f[u]: 表示u到最远叶节点的距离。显然如果u是节点，则f[u]=0
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int ans = 0;
void dfs(int u) { // 求以u为根节点到叶节点的最大距离
int a = 0, b = 0; // a记录u到最远叶节点的距离，b记录u到次远叶节点的距离
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
dfs(v); //求子节点j到最远叶节点的距离
int t = f[v] + 1; //u通过j能到的最远叶节点的距离
//更新a, b
if (t >= a) b = a, a = t;
else if (t > b) b = t;
}
f[u] = a;
// 最后的答案就是u所能到的最远叶节点距离和次远叶节点距离之和
ans = max(ans, a + b);
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
int j;
for (int i = 2; i <= n + m; i++) {
scanf("%d", &j);
add(j, i); // 因为是自根向下DP，所以建一条边即可
}
dfs(1);
cout << ans << endl;
return 0;
}
序列化二叉树
代码
class Solution:
def serialize(self, root):
ans = ""
def dfs_s(root):
nonlocal ans
if not root:
ans += 'None '
return
else:
ans += str(root.val) + ' '
dfs_s(root.left)
dfs_s(root.right)
dfs_s(root)
return ans
def deserialize(self, data):
A = data.split()
k = 0
def dfs_d():
nonlocal A, k
if k == len(A): return None
if A[k] == 'None':
k += 1
return None
root = TreeNode(int(A[k]))
k += 1
root.left = dfs_d()
root.right = dfs_d()
return root
return dfs_d()
最大亦或和-线性基
思路
- 构造线性基的方法如下：对于集合中的每个数
x转为二进制，从高位向低位扫，对于第i位是1的，如果p[i]不存在，那么p[i] = x结束扫描，如果存在，令x = x ^ p[i] - 查询集合内任意几个元素
xor最大值：从高位向低位扫，若xor上当前扫到的p[i]答案变大，就把答案xor上p[i] - 查询原集合内任意几个元素
xor的最小值，就是线性基集合所有元素中最小的那个
代码
#include <iostream>
#include <algorithm>
using namespace std;
using ull = unsigned long long;
ull p[65];
int n;
int main() {
scanf("%d", &n);
auto insert = [](ull x) {
for (int i = 63; ~i; i--) {
if (!(x >> i & 1)) continue;
if (!p[i]) {
p[i] = x;
break;
}
x ^= p[i];
}
};
ull x;
while (n--) {
scanf("%lld", &x);
insert(x);
}
ull ans = 0;
for (int i = 63; ~i; i--)
ans = max(ans, ans ^ p[i]);
printf("%lld", ans);
return 0;
}
通信网络-枚举+dfs
代码
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1005, M = 10005;
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int n, m;
bool st[N][N];
void dfs(int s, int u) {
st[s][u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (st[s][v]) continue;
dfs(s, v);
}
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
int a, b;
while (m--) {
scanf("%d%d", &a, &b);
add(a, b);
}
for (int i = 1; i <= n; i++)
dfs(i, i);
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if (st[i][j]) st[j][i] = true;
}
for (int i = 1; i <= n; i++) {
int j = 1;
for (; j <= n; j++)
if(!st[i][j]) break;
if (j > n) ++ans;
}
cout << ans;
return 0;
}
压缩编码-区间DP
思路
- 状态表示
f[i][j]- 集合：所有将
[i, j]合并成一堆的方案的集合 - 属性：最小值
- 集合：所有将
- 状态计算：
f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1])
代码
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 1005;
int n, f[N][N], s[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
s[i] += s[i-1];
}
for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
f[i][j] = INT_MAX;
for (int k = i; k < j; k++)
f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1]);
}
cout << f[1][n];
}
杂题记录
后序遍历
代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <functional>
using namespace std;
const int N = 30;
struct node {
char c;
node *l, *r;
node(char _c) : c(_c), l(nullptr), r(nullptr) {}
};
void print(node *root) {
if (!root) return;
print(root->l);
print(root->r);
printf("%c", root->c);
}
unordered_map<char, int> M;
string A, B;
node* dfs(int pl, int pr, int il, int ir) {
if (pl > pr) return nullptr;
auto it = M[A[pl]];
node *root = new node(A[pl]);
root->l = dfs(pl + 1, pl + 1 + it - il - 1, il, it - 1);
root->r = dfs(pl + 1 + it - il, pr, it + 1, ir);
return root;
};
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> A >> B;
const int n = A.size();
for (int i = 0; i < n; i++) M[B[i]] = i;
auto root = dfs(0, n - 1, 0, n - 1);
print(root);
return 0;
}
树的遍历-中序后序求层次
代码
package main
import "fmt"
type TreeNode struct {
val int
left, right *TreeNode
}
var n int
func main() {
fmt.Scan(&n)
after, in := make([]int, n), make([]int, n)
for i := range after {
fmt.Scan(&after[i])
}
for i := range in {
fmt.Scan(&in[i])
}
mp := make(map[int]int)
for i := range in {
mp[in[i]] = i
}
var dfs func(il, ir, al, ar int) (*TreeNode)
dfs = func(il, ir, al, ar int) (*TreeNode) {
if al > ar {
return nil
}
idx := mp[after[ar]]
root := &TreeNode{
val: after[ar],
left: dfs(il, idx-1, al, al+idx-il-1),
right: dfs(idx+1, ir, al+idx-il, ar-1),
}
return root
}
root := dfs(0, n-1, 0, n-1)
que := make([](*TreeNode), 0)
que = append(que, root)
for len(que) != 0 {
front := que[0]
fmt.Printf("%d ", front.val)
que = que[1:]
if front.left != nil {
que = append(que, front.left)
}
if front.right != nil {
que = append(que, front.right)
}
}
}
树中的最长路
代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <functional>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
int h[N], e[N], ne[N], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int n, f[N], ans;
void dfs(int u) {
int a = 0, b = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
dfs(v);
int t = f[v] + 1;
if (t >= a) b = a, a = t;
else if (t > b) b = t;
}
f[u] = a;
ans = max(ans, a + b);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
memset(h, -1, sizeof h);
cin >> n;
int a, b;
for (int i = 0; i < n - 1; i++) {
cin >> a >> b;
add(a, b);
}
dfs(1);
cout << ans << '\n';
return 0;
}
RMQ问题再临
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
struct node {
int l, r, minv;
} tree[N << 2];
int n, m, a[N];
void build(int u, int l, int r) {
if (l == r) tree[u] = {l, r, a[l]};
else {
const int mid = l + r >> 1;
build(u<<1, l, mid), build(u<<1|1, mid+1, r);
tree[u] = {l, r, min(tree[u<<1].minv, tree[u<<1|1].minv)};
}
}
void update(int u, int i, int v) {
if (tree[u].l == i && tree[u].r == i)
tree[u].minv = v;
else {
const int mid = tree[u].l + tree[u].r >> 1;
if (i <= mid) update(u<<1, i, v);
else update(u<<1|1, i, v);
tree[u].minv = min(tree[u<<1].minv, tree[u<<1|1].minv);
}
}
int query(int u, int l, int r) {
if (tree[u].l == l && tree[u].r == r) return tree[u].minv;
const int mid = tree[u].l + tree[u].r >> 1;
if (r <= mid) return query(u<<1, l, r);
else if (l > mid) return query(u<<1|1, l, r);
else return min(query(u<<1, l, mid), query(u<<1|1, mid+1, r));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
build(1, 1, n);
int a, b, c;
while (m--) {
cin >> a >> b >> c;
if (!a) cout << query(1, b, c) << endl;
else update(1, b, c);
}
return 0;
}
无间道之并查集
代码
#include <bits/stdc++.h>
using namespace std;
class UF {
vector<int> id, sz;
public:
UF(int N) {
id.resize(N), sz.resize(N);
for (int i = 0; i < N; i++)
id[i] = i, sz[i] = 1;
}
int find(int x) {
while (x != id[x]) {
id[x] = id[id[x]];
x = id[x];
}
return x;
}
bool is_connected(int p, int q) {
int i = find(p), j = find(q);
return i == j;
}
bool _union(int p, int q) {
int i = find(p), j = find(q);
if (i == j) return false;
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
return true;
}
};
unordered_map<string, int> M;
int idx;
int get_hash(const string &str) {
if (M.count(str)) return M[str];
else return M[str] = idx++;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n;
cin >> n;
UF uf(n);
int op;
string a, b;
while (n--) {
cin >> op >> a >> b;
int i = get_hash(a), j = get_hash(b);
if (!op) uf._union(i, j);
else {
puts(uf.is_connected(i, j) ? "yes" : "no");
}
}
return 0;
}
二分图判定
思路
染色法
代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <functional>
#include <cstring>
using namespace std;
const int N = 1e4 + 5, M = 1e5;
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int n, m, color[N];
bool dfs(int u, int c) {
color[u] = c;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (color[v]) {
if (color[v] == c) return false;
} else if (!dfs(v, 3 - c)) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
idx = 0;
memset(h, -1, sizeof h);
memset(color, 0, sizeof color);
cin >> n >> m;
int a, b;
while (m--) {
cin >> a >> b;
add(a, b);
add(b, a);
}
bool is_break = false;
for (int i = 1; i <= n; i++)
if (!color[i] && !dfs(i, 1)) {
is_break = true;
break;
}
puts(is_break ? "Wrong" : "Correct");
}
return 0;
}
猜字谜
代码
class Solution {
public:
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
unordered_map<int, int> mp;
vector<int> ans(puzzles.size());
for (const auto &e : words) {
int t = 0;
for (const auto &c : e)
t |= 1 << (c - 'a');
auto tmp = bitset<26>(t);
if (tmp.count() > 7) continue;
mp[t]++;
}
for (int i = 0; i < puzzles.size(); i++) {
string p = puzzles[i];
int mask = 0;
for (int i = 1; i < 7; i++)
mask |= 1 << (p[i] - 'a');
int subset = mask;
do {
int t = subset | (1 << (p[0] - 'a'));
if (mp.count(t)) ans[i] += mp[t];
subset = (subset - 1) & mask;
} while (subset != mask);
}
return ans;
}
};
至少有K个重复字符的最长子串
Code in Golang
func longestSubstring(s string, k int) (ans int) {
if s == "" {
return 0
}
cnt := [26]int{}
for _, v := range(s) {
cnt[v-'a']++
}
var split byte
for i, v := range(cnt) {
if (v > 0 && v < k) {
split = 'a' + byte(i)
break
}
}
if split == 0 {
return len(s)
}
for _, v := range strings.Split(s, string(split)) {
ans = max(ans, longestSubstring(v, k))
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Code in Python
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
if len(s) < k: return 0
for v in set(s):
if s.count(v) < k:
return max(self.longestSubstring(t, k) for t in s.split(v))
return len(s)
找到 K 个最接近的元素
堆-$nlogk$做法
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
priority_queue<pair<int, int>> Q;
for (const auto &e : arr) {
Q.push({abs(e - x), e});
if (Q.size() > k) Q.pop();
}
vector<int> ans(k);
int idx = 0;
while (!Q.empty()) {
ans[idx++] = Q.top().second;
Q.pop();
}
sort(ans.begin(), ans.end());
return ans;
}
};
二分+双指针-$logn+k$做法(Rust)
impl Solution {
pub fn find_closest_elements(arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
let n: i32 = arr.len() as i32;
let mut l: i32 = 0;
let mut r: i32 = n - 1;
while l < r {
let mid: usize = ((l + r) / 2) as usize;
if arr[mid] >= x {
r = mid as i32;
} else {
l = (mid + 1) as i32;
}
}
if r > 0 {
let a = (i32::abs(arr[(r-1) as usize] - x), arr[(r-1) as usize]);
let b = (i32::abs(arr[r as usize] - x), arr[r as usize]);
if a < b {
r -= 1;
}
}
let mut i: i32 = r;
let mut j: i32 = r;
for u in 0..k-1 {
if ((i - 1) < 0) {
j += 1;
} else if j + 1 >= n {
i -= 1;
} else {
let a = (i32::abs(arr[(i-1) as usize] - x), arr[(i-1) as usize]);
let b = (i32::abs(arr[(j+1) as usize] - x), arr[(j+1) as usize]);
if a < b {
i -= 1;
} else {
j += 1;
}
}
}
let mut ans = Vec::new();
for u in i..j+1 {
ans.push(arr[u as usize]);
}
return ans;
}
}
二维区域和检索 - 矩阵不可变
思路
二位前缀和
- 构造:
S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1] - 计算:
ans = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]
代码
class NumMatrix {
vector<vector<int>> C;
public:
NumMatrix(vector<vector<int>>& matrix) {
if (matrix.empty()) return;
const int n = matrix.size(), m = matrix[0].size();
C = vector<vector<int>>(n+1, vector<int>(m+1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
C[i][j] = matrix[i-1][j-1] + C[i-1][j] + C[i][j-1] - C[i-1][j-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int sum = C[row2+1][col2+1] - C[row1-1+1][col2+1] - C[row2+1][col1-1+1] + C[row1-1+1][col1-1+1];
return sum;
}
};
比特位计数-动态规划
思路
y=x & (x - 1): y为将x的最低设置位从1变成0之后的数- 状态定义：
f[i]: i的比特位中1的个数 - 状态计算:
f[i] = f[i & (i-1)]
代码
class Solution {
public:
vector<int> countBits(int num) {
vector<int> f(num+1);
for (int i = 1; i <= num; i++)
f[i] = f[i&(i-1)] + 1;
return f;
}
};
class Solution:
def countBits(self, num: int) -> List[int]:
f = [0] * (num + 1)
for i in range(1, num + 1):
f[i] = f[i & (i - 1)] + 1
return f
class Solution {
public int[] countBits(int num) {
int[] f = new int[num+1];
for (int i = 1; i <= num; i++)
f[i] = f[i & (i - 1)] + 1;
return f;
}
}
func countBits(num int) []int {
f := make([]int, num+1)
for i := 1; i <= num; i++ {
f[i] = f[i & (i - 1)] + 1
}
return f
}
俄罗斯套娃信封问题-LIS
解题思路
LIS变形
代码
$O(n^2)$
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& E) {
if (E.empty()) return 0;
sort(begin(E), end(E), [](vector<int> a, vector<int> b) {
return (a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]));
});
const int n = E.size();
vector<int> f(n);
for (int i = 0; i < n; i++) {
f[i] = 1;
for (int j = 0; j < i; j++) {
if (E[i][1] > E[j][1])
f[i] = max(f[i], f[j] + 1);
}
}
return *max_element(begin(f), end(f));
}
};
$O(nlogn)$
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& E) {
if (E.empty()) return 0;
sort(begin(E), end(E), [](vector<int> a, vector<int> b) {
return (a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]));
});
const int n = E.size();
vector<vector<int>> f;
for (int i = 0; i < n; i++) {
auto it = lower_bound(begin(f), end(f), E[i], [](vector<int> a, vector<int> b) {return a[1] < b[1];});
if (it == f.end()) f.push_back(E[i]);
else *it = E[i];
}
for (int i = 0; i < f.size(); i++)
cout << f[i][0] << " " << f[i][1] << endl;
return f.size();
}
};
用栈实现队列-双栈
思路
- 双栈实现队列
- 当
peek()和pop()时，如果输出栈为空，则将输入栈内容依次弹出，并压入输出栈 代码
- 当
代码
class MyQueue {
stack<int> _in, out;
void work() {
while (!_in.empty()) {
out.push(_in.top());
_in.pop();
}
}
public:
/** _initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
_in.push(x);
}
/** Removes the element from _in front of queue and returns that element. */
int pop() {
if (out.empty()) work();
auto res = out.top();
out.pop();
return res;
}
/** Get the front element. */
int peek() {
if (out.empty()) work();
auto res = out.top();
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
return _in.empty() && out.empty();
}
};
/**
* Your MyQueue object will be _instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* _int param_2 = obj->pop();
* _int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
下一个更大元素-单调栈
思路
- 单调栈内对应元素单调不增
- 当遇到一个比当前栈顶元素大的元素，则出栈，并且出栈元素下一个更大元素为当前元素
- 因为环，所以将下标映射至
1..2n-1
代码
C++
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
const int n = nums.size();
vector<int> ans(n, -1);
stack<int> the_stack;
for (int i = 0; i < 2 * n; i++) {
while (!the_stack.empty() && nums[i % n] > nums[the_stack.top()]) {
ans[the_stack.top()] = nums[i % n];
the_stack.pop();
}
the_stack.push(i % n);
}
return ans;
}
};
Java
class Solution {
public int[] nextGreaterElements(int[] nums) {
final var n = nums.length;
var ans = new int[n];
Arrays.fill(ans, -1);
Stack<Integer> S = new Stack<>();
for (int i = 0; i < 2 * n; i++) {
while (!S.isEmpty() && nums[S.peek()] < nums[i % n])
ans[S.pop()] = nums[i % n];
S.push(i % n);
}
return ans;
}
}
Python3
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [-1] * n
the_stack = []
for i in range(2 * n):
while the_stack and (nums[i % n] > nums[the_stack[-1]]):
ans[the_stack.pop()] = nums[i % n]
the_stack.append(i % n)
return ans
Golang
func nextGreaterElements(nums []int) []int {
n := len(nums)
ans := make([]int, n)
for i := range(ans) {
ans[i] = -1
}
stack := []int{}
for i := 0; i < 2 * n; i++ {
for len(stack) > 0 && nums[i % n] > nums[stack[len(stack)-1]] {
ans[stack[len(stack)-1]] = nums[i % n]
stack = stack[:len(stack)-1]
}
stack = append(stack, i % n)
}
return ans
}
分割回文串
思路
dfs + DP预处理
f[i][j] = f[i+1][j-1] && (s[i] == s[j])
代码
class Solution {
public:
vector<vector<string>> partition(string s) {
const int n = s.length();
vector<string> tmp;
vector<vector<string>> ans;
vector<vector<bool>> f(n, vector<bool>(n, true));
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++)
f[i][j] = f[i+1][j-1] && (s[i] == s[j]);
}
function<void(int)> dfs = [&](int i) {
if (i >= n) {
ans.push_back(tmp);
return;
}
for (int j = i; j < n; j++) {
if (f[i][j]) {
tmp.push_back(s.substr(i, j - i + 1));
dfs(j+1);
tmp.pop_back();
}
}
};
dfs(0);
return ans;
}
};
从第一个节点出发到最后一个节点的受限路径数-记忆化搜索
思路
单源最短路+记忆化搜索
代码
const int N = 2e4 + 5, M = 8e4 + 10;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
class Solution {
public:
int countRestrictedPaths(int n, vector<vector<int>>& edges) {
idx = 0;
memset(h, -1, sizeof h);
for (const auto &e : edges) {
add(e[0], e[1], e[2]);
add(e[1], e[0], e[2]);
}
vector<int> dist(n + 1, INT_MAX);
vector<bool> st(n + 1, false);
priority_queue<pair<int, int>> Q;
Q.push({0, n});
dist[n] = 0;
while (!Q.empty()) {
auto [wgt, u] = Q.top();
Q.pop();
if (st[u]) continue;
st[u] = true;
dist[u] = -wgt;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (-wgt + w[i] < dist[v]) {
dist[v] = -wgt + w[i];
Q.push({-dist[v], v});
}
}
}
const int mod = 1e9 + 7;
vector<int> f(n + 1, INT_MAX);
function<int(int)> dfs = [&](int u) {
if (u == n) return 1;
if (f[u] != INT_MAX) return f[u];
int ans = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (dist[u] > dist[v])
ans = (ans + dfs(v)) % mod;
}
return f[u] = ans;
};
return dfs(1);
}
};
公共钥匙盒-模拟
代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
const int N = 1005;
pair<int, int> T[N];
int n, k, a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
priority_queue<tuple<int, bool, int>> Q;
cin >> n >> k;
int w, s, c;
for (int i = 1; i <= n; i++)
a[i] = i;
while (k--) {
cin >> w >> s >> c;
T[w] = {s, c};
Q.push({ -s, false, -w});
Q.push({ -(s + c), true, -w});
}
while (Q.size()) {
auto it = Q.top();
auto t = get<0>(it);
auto b = get<1>(it);
auto w = get<2>(it);
Q.pop();
if (!b) {
for (int i = 1; i <= n; i++)
if (a[i] == -w) {
a[i] = 0;
break;
}
}
else {
for (int i = 1; i <= n; i++)
if (!a[i]) {
a[i] = -w;
break;
}
}
}
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
return 0;
}
基本计算器-栈
代码
class Solution {
public:
int calculate(string s) {
stack<int> sign;
sign.push(1);
int cur = 1;
int ans = 0;
const int n = s.length();
for (int i = 0; i < n; i++) {
if (s[i] == ' ') continue;
else if (s[i] == '+') cur = sign.top();
else if (s[i] == '-') cur = -sign.top();
else if (s[i] == '(') sign.push(cur);
else if (s[i] == ')') sign.pop();
else {
int sum = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') {
sum = sum * 10 + (s[i] - '0');
++i;
}
--i;
ans += sum * cur;
}
}
return ans;
}
};
基本计算器II-栈
思路
- 如果数字前是+, 将数字压栈
- 如果数字前是-, 将数字相反数压栈
- 如果数字前是*, 将栈顶元素乘以数字
- 如果数字前是/, 将栈顶元素除以数字
代码
func calculate(s string) int {
stack := []int{}
num := 0
pre := '+'
for i, v := range(s) {
if v >= '0' && v <= '9' {
num = num * 10 + int(v - '0')
}
if (!(v >= '0' && v <= '9') && v != ' ') || i == len(s)-1 {
switch pre {
case '+': stack = append(stack, num)
case '-': stack = append(stack, -num)
case '*': stack[len(stack)-1] *= num
case '/': stack[len(stack)-1] /= num
}
pre = v
num = 0
}
}
ans := 0
for _, v := range(stack) {
ans += v
}
return ans
}
验证二叉树的前序序列化
解题思路
遍历过程中：
- 根结点提供两个出度
- 除了根结点以外的非空结点提供一个入度数、两个出度
- 空结点提供一个入度
还没遍历结束时候满足：入度 < 出度
代码
func isValidSerialization(preorder string) bool {
if preorder == "#" {
return true
}
res := strings.Split(preorder, ",")
in, out := 0, 0
for i := range(res) {
if i == 0 {
if res[i] == "#" {
return false
}
out += 2
continue
}
if res[i] == "#" {
in++
} else {
in++
out += 2
}
if i != len(res)-1 && out <= in {
return false
}
}
return in == out
}
设计哈希集合
思路
拉链法
代码
C++
constexpr int N = 10007;
class MyHashSet {
int h[N], e[N], ne[N], idx;
public:
/** Initialize your data structure here. */
MyHashSet() {
idx = 0;
memset(h, -1, sizeof h);
}
void add(int key) {
if (!contains(key)) {
int k = key % N;
e[idx] = key;
ne[idx] = h[k];
h[k] = idx++;
}
}
void remove(int key) {
int k = key % N;
if (h[k] == -1) return;
if (e[h[k]] == key) // 第一个结点就是
h[k] = ne[h[k]];
for (int i = h[k]; ~i && ~ne[i]; i = ne[i]) {
if (e[ne[i]] == key) {
ne[i] = ne[ne[i]];
}
}
}
/** Returns true if this set contains the specified element */
bool contains(int key) {
int k = key % N;
for (int i = h[k]; ~i; i = ne[i]) {
if (e[i] == key) return true;
}
return false;
}
};
Golang
const N = 10007
type MyHashSet struct {
h []int
e []int
ne []int
idx int
}
/** Initialize your data structure here. */
func Constructor() MyHashSet {
t := make([]int, N)
for i := range(t) {
t[i] = -1
}
return MyHashSet{t, make([]int, N), make([]int, N), 0}
}
func (this *MyHashSet) Add(key int) {
if !this.Contains(key) {
k := (key % N + N) % N
this.e[this.idx] = key
this.ne[this.idx] = this.h[k]
this.h[k] = this.idx
this.idx++
}
}
func (this *MyHashSet) Remove(key int) {
k := (key % N + N) % N
if this.h[k] == -1 {
return
}
if this.e[this.h[k]] == key {
this.h[k] = this.ne[this.h[k]]
}
for i := this.h[k]; i != -1 && this.ne[i] != -1; i = this.ne[i] {
if this.e[this.ne[i]] == key {
this.ne[i] = this.ne[this.ne[i]]
}
}
}
/** Returns true if this set contains the specified element */
func (this *MyHashSet) Contains(key int) bool {
k := (key % N + N) % N
for i := this.h[k]; i != -1; i = this.ne[i] {
if this.e[i] == key {
return true
}
}
return false
}
设计哈希映射
思路
拉链法
代码
const N = 10007
type Pair struct {
k int
v int
}
type MyHashMap struct {
h []int
e []Pair
ne []int
idx int
}
/** Initialize your data structure here. */
func Constructor() MyHashMap {
h := make([]int, N)
for i := range(h) {
h[i] = -1
}
return MyHashMap{h, make([]Pair, N), make([]int, N), 0}
}
/** value will always be non-negative. */
func (this *MyHashMap) Put(key int, value int) {
if this.Get(key) == -1 {
k := (key % N + N) % N
this.e[this.idx] = Pair{key, value}
this.ne[this.idx] = this.h[k]
this.h[k] = this.idx
this.idx++
} else {
k := (key % N + N) % N
for i := this.h[k]; i != -1; i = this.ne[i] {
if this.e[i].k == key {
this.e[i].v = value
}
}
}
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func (this *MyHashMap) Get(key int) int {
k := (key % N + N) % N
for i := this.h[k]; i != -1; i = this.ne[i] {
if this.e[i].k == key {
return this.e[i].v
}
}
return -1
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func (this *MyHashMap) Remove(key int) {
k := (key % N + N) % N
if this.h[k] == -1 {
return
}
if this.e[this.h[k]].k == key {
this.h[k] = this.ne[this.h[k]]
}
for i := this.h[k]; i != -1 && this.ne[i] != -1; i = this.ne[i] {
if this.e[this.ne[i]].k == key {
this.ne[i] = this.ne[this.ne[i]]
}
}
}
不同的子序列-DP
思路
$$ f[i][j] = \begin{cases} f[i+1][j+1] + f[i+1][j], &s[i] = t[j]& \cr f[i+1][j], &s[i] \ne t[j] \end{cases} $$
代码
func numDistinct(s string, t string) int {
n, m := len(s), len(t)
if n < m {
return 0
}
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
f[i][m] = 1
}
for i := n-1; i >= 0; i-- {
for j := m-1; j >= 0; j-- {
if s[i] == t[j] {
f[i][j] = f[i+1][j+1] + f[i+1][j]
} else {
f[i][j] = f[i+1][j]
}
}
}
return f[0][0]
}
反转链表II
思路
- 创建头结点
a := m-1- 将
[m+1,n]指针反转 a->next->next = n+1a->next = n
代码
func reverseBetween(head *ListNode, left int, right int) *ListNode {
dummy := &ListNode{0, head}
a := dummy
for i := 0; i < left-1; i++ {
a = a.Next
}
pre, cur := a.Next, a.Next.Next
for i := 0; i < right-left; i++ {
tmp := cur.Next
cur.Next = pre
pre = cur
cur = tmp
}
a.Next.Next = cur
a.Next = pre
return dummy.Next
}
反转链表
迭代法
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
tmp := cur.Next
cur.Next = pre
pre = cur
cur = tmp
}
return pre
}
递归法
思路
- 首先我们先考虑 reverseList 函数能做什么，它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。
- 所以我们可以先递归处理 reverseList(head->next)，这样我们可以将以head->next为头节点的链表翻转，并得到原链表的尾节点tail，此时head->next是新链表的尾节点，我们令它的next指针指向head，并将head->next指向空即可将整个链表翻转，且新链表的头节点是tail
代码
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
tail := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return tail
}
表达式求值-栈
思路
- 使用两个栈，一个存操作数，另一个存运算符
- 遇到左括号入栈，遇到右括号进行计算直到栈顶为左括号
代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <stack>
using namespace std;
int main() {
string str;
cin >> str;
const int n = str.length();
stack<int> stk;
stack<char> op;
auto calculate = [&]() {
int a = stk.top();
stk.pop();
int b = stk.top();
stk.pop();
char c = op.top();
op.pop();
switch (c) {
case '+': stk.push(b + a); break;
case '-': stk.push(b - a); break;
case '*': stk.push(b * a); break;
case '/': stk.push(b / a); break;
}
};
unordered_map<char, int> mp = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
for (int i = 0; i < n; i++) {
auto c = str[i];
if (isdigit(c)) {
int j = i;
int num = 0;
while (j < n && isdigit(str[j])) {
num = num * 10 + str[j] - '0';
j++;
}
stk.push(num);
i = j - 1;
} else if (c == '(') {
op.push(c);
} else if (c == ')') {
while (op.size() && op.top() != '(') {
calculate();
}
op.pop();
} else {
while (op.size() && mp[op.top()] >= mp[c]) {
calculate();
}
op.push(c);
}
}
while (op.size()) {
calculate();
}
cout << stk.top() << endl;
return 0;
}
矩阵置零
思路
- 用两个变量记录第一行和第一列是否有0。
- 遍历整个矩阵，用矩阵的第一行和第一列记录对应的行和列是否有0。
- 把含有0的行和列都置成0。
代码
func setZeroes(matrix [][]int) {
n, m := len(matrix), len(matrix[0])
r0, c0 := 1, 1
// 第0行是否应该置为0
for i := 0; i < m; i++ {
if matrix[0][i] == 0 {
r0 = 0
}
}
// 第0列是否应该置为0
for i := 0; i < n; i++ {
if matrix[i][0] == 0 {
c0 = 0
}
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
if matrix[i][j] == 0 {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
// matrix[0][i]表示第i列是否该置为0
// matrix[i][0]表示第i行是否该置为0
// 把含有0的行和列都置成0 用第0行和第0列标记
for i := 1; i < m; i++ {
if matrix[0][i] == 0 {
for j := 1; j < n; j++ {
matrix[j][i] = 0
}
}
}
for i := 1; i < n; i++ {
if matrix[i][0] == 0 {
for j := 1; j < m; j++ {
matrix[i][j] = 0
}
}
}
if r0 == 0 {
for i := 0; i < m; i++ {
matrix[0][i] = 0
}
}
if c0 == 0 {
for i := 0; i < n; i++ {
matrix[i][0] = 0
}
}
}
不用加减乘除做加法
思路
- 两个整数做异或运算，得到不进位加法的运算结果
- 两个整数做与运算，然后左移一位，得到进位的运算结果
- 将上面得到的两个结果相加，即重复上述步骤直到进位的结果为0
代码
func add(num1 int, num2 int) int {
for num2 != 0 {
sum, carry := num1 ^ num2, (num1 & num2) << 1
num1, num2 = sum, carry
}
return num1
}
132模式-单调栈
思路
- 从右到左维护一个单调递减的栈
- 维护一个次大值(初始值为INT_MIN)
- 如果当前的值小于次大值则找到132子序列
代码
func find132pattern(nums []int) bool {
n := len(nums)
stk := make([]int, 0)
second := math.MinInt64
for i := n - 1; i >= 0; i-- {
if nums[i] < second {
return true
}
for len(stk) > 0 && stk[len(stk)-1] < nums[i] {
second = stk[len(stk)-1]
stk = stk[:len(stk)-1]
}
stk = append(stk, nums[i])
}
return false
}
直方图中最大矩形-单调栈
思路
单调栈可以解决：左边比当前值大或小的第一个数
代码
#include <iostream>
#include <algorithm>
using namespace std;
constexpr int N = 100005;
int n, h[N], l[N], r[N], stk[N];
void work() {
for (int i = 1; i <= n; i++)
scanf("%d", &h[i]);
// 设置边界为-1
h[0] = h[n+1] = -1;
// 寻找左边界
stk[0] = 0;
int tt = 0;
for (int i = 1; i <= n; i++) {
while (h[stk[tt]] >= h[i]) {
tt--;
}
l[i] = stk[tt];
stk[++tt] = i;
}
// 寻找左边界
stk[0] = n+1;
tt = 0;
for (int i = n; i >= 1; i--) {
while (h[stk[tt]] >= h[i]) {
tt--;
}
r[i] = stk[tt];
stk[++tt] = i;
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, h[i] * 1ll * (r[i]-l[i]-1));
}
printf("%lld\n", ans);
}
int main() {
while (scanf("%d", &n)) {
if (!n) return 0;
work();
}
return 0;
}
删除排序链表中的重复元素
思路
pre保存当前结点前驱结点- 找到右边第一个不相等的结点
right - 如果
cur.Next == right则不用删，否则pre.Next = right删除
代码
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
pre := &ListNode{0, head}
ans, cur := pre, head
for cur != nil {
right := cur
for right != nil && right.Val == cur.Val {
right = right.Next
}
if cur.Next == right {
pre = cur
} else {
pre.Next = right
}
cur = right
}
return ans.Next
}
可达性统计-拓扑排序
思路
- 从x出发能够到达的点，是从“x的各个后续节点y”出发能够到达的点的并集，再加上x点本身
- 可以求出拓扑序，按照拓扑序逆序进行计算
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
const int N = 30005;
int h[N], ne[N], e[N], idx, d[N];
int n, m;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int seq[N], cnt;
bitset<N> f[N];
void toposort() {
int que[N];
int hh = 0, tt = -1;
for (int i = 1; i <= n; i++)
if (!d[i]) que[++tt] = i;
while (hh <= tt) {
int front = que[hh++];
seq[cnt++] = front;
for (int i = h[front]; ~i; i = ne[i]) {
int j = e[i];
if (--d[j] == 0)
que[++tt] = j;
}
}
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
int a, b;
while (m--) {
scanf("%d%d", &a, &b);
add(a, b);
d[b]++;
}
toposort();
for (int i = n-1; ~i; i--) {
int j = seq[i];
f[j][j] = 1;
for (int k = h[j]; ~k; k = ne[k]) {
f[j] |= f[e[k]];
}
}
for (int i = 1; i <= n; i++)
printf("%lld\n", f[i].count());
return 0;
}
二叉树的下一个结点
思路
- 若当前结点有右儿子，则右子树中最左侧的结点就是当前结点的后继
- 如果当前没有右儿子，则要沿着
father域一直向上找，找到第一个是其father左儿子的结点，该结点的father就是当前结点的后继
代码
func inorderSuccessor(p *TreeNode) *TreeNode {
if p.Right != nil {
p = p.Right
for p.Left != nil {
p = p.Left
}
return p
}
for (p.Father != nil && p == p.Father.Right) {
p = p.Father
}
return p.Father
}
二叉搜索树迭代器-中序遍历非递归
思路
- 将根节点的左链入栈
- 当取出一个元素后，如果这个结点有右子树，则将其右子树的左链入栈
代码
type BSTIterator struct {
stk []*TreeNode
}
func Constructor(root *TreeNode) BSTIterator {
stk := make([](*TreeNode), 0)
for root != nil {
stk = append(stk, root)
root = root.Left
}
return BSTIterator{stk}
}
func (this *BSTIterator) Next() int {
root := this.stk[len(this.stk)-1]
this.stk = this.stk[:len(this.stk)-1]
ret := root.Val
root = root.Right
for root != nil {
this.stk = append(this.stk, root)
root = root.Left
}
return ret
}
func (this *BSTIterator) HasNext() bool {
return len(this.stk) > 0
}
翻转单词顺序
思路
- 将整个字符串翻转
- 翻转每个单词
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n)$ | $O(1)$ |
代码
class Solution {
public:
string reverseWords(string s) {
const int n = s.length();
reverse(begin(s), end(s));
for (int i = 0; i < n; i++) {
int j = i + 1;
while (j < n && s[j] != ' ') ++j;
reverse(begin(s) + i, begin(s) + j);
i = j;
}
return s;
}
};
搜索二维矩阵-二分
代码
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(log(n^2)) = O(logn)$ | $O(1)$ |
func searchMatrix(M [][]int, target int) bool {
n, m := len(M), len(M[0])
l, r := 0, n * m - 1
for l < r {
mid := (l + r + 1) >> 1
if M[mid/m][mid%m] <= target {
l = mid
} else {
r = mid - 1
}
}
return M[l/m][l%m] == target
}
二维数组中的查找
思路
我们可以发现：x左边的数都小于等于x，x下边的数都大于等于x
- 如果
x等于target，则说明我们找到了目标值，返回true； - 如果
x小于target，则x左边的数一定都小于target，我们可以直接排除当前一整行的数 - 如果
x大于target，则x下边的数一定都大于target，我们可以直接排序当前一整列的数
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(m+n)$ | $O(1)$ |
代码
func findNumberIn2DArray(M [][]int, target int) bool {
if len(M) == 0 {
return false
}
i, j := 0, len(M[0]) - 1
for i < len(M) && j >= 0 {
if M[i][j] == target {
return true
} else if (M[i][j] < target) {
i++
} else {
j--
}
}
return false
}
子集II
思路
- 先排序，把所有相同的元素放在一起，之后统计相同元素个数，对于每个相同元素可以选择的次数为0-t(t表示元素出现次数)
- 将所有元素的所有次数可能相互组合即可得到所有解集
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n2^n)$ | $O(n)$ |
代码
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
int n = nums.size();
sort(begin(nums), end(nums));
vector<int> tmp;
vector<vector<int>> ans;
function<void(int)> dfs = [&](int u){
if (u >= n) {
ans.emplace_back(tmp);
return;
}
int k = 0;
while (u + k < n && nums[u] == nums[u+k]) k++;
for (int i = 0; i <= k; i++) {
dfs(u + k);
tmp.emplace_back(nums[u]);
}
for (int i = 0; i <= k; i++)
tmp.pop_back();
};
dfs(0);
return ans;
}
};
递归实现组合型枚举
思路
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(2^n)$ | $O(n)$ |
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
int n, m;
int path[N];
// u是层数，start是起始值
void dfs(int u, int start) {
if (u > m) {
for (int i = 1; i <= m; i++)
cout << path[i] << " ";
cout << endl;
return;
}
for (int i = start; i <= n; i++) {
path[u] = i;
dfs(u + 1, i + 1);
path[u] = 0;
}
}
int main() {
cin >> n >> m;
dfs(1, 1);
return 0;
}
直方图的水量-单调栈|DP
单调栈
思路
- 维护一个单调栈（严格递减），那么一定有
height[t] > height[left](left是栈顶下面的元素) - 若
height[i] > height[t]则可形成一个盛水区域，宽度为i-left-1，高度为min(height[i], height[left])-height[t]
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n)$ | $O(n)$ |
代码
func trap(height []int) int {
stk := make([]int, 0)
ans := 0
for i := range height {
for len(stk) > 0 && height[i] >= height[stk[len(stk)-1]] {
top := stk[len(stk)-1]
stk = stk[:len(stk)-1]
if len(stk) <= 0 {
break
}
left := stk[len(stk)-1]
ans += (i - left - 1) * (min(height[i], height[left])-height[top])
}
stk = append(stk, i)
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
DP
思路
对于下标 i，水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的水的量等于下标 i 处的水能到达的最大高度减去 height[i]。
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n)$ | $O(n)$ |
代码
func trap(height []int) int {
n := len(height)
if n == 0 {
return 0
}
left, right := make([]int, n), make([]int, n)
left[0] = height[0]
for i := 1; i < n; i++ {
left[i] = max(left[i-1], height[i])
}
right[n-1] = height[n-1]
for i := n-2; i >= 0; i-- {
right[i] = max(right[i+1], height[i])
}
ans := 0
for i := range height {
ans += min(left[i], right[i]) - height[i]
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
雨-最短路变形
思路
- 将海水抽象为一个源点
- 求海水到每个点所经过的点的最大权值的最短路
代码
package main
import (
"fmt"
"container/heap"
)
type Node struct {
x int
y int
d int
}
type NodeHeap []Node
func (n NodeHeap) Len() int {
return len(n)
}
func (n NodeHeap) Swap(i, j int) {
n[i], n[j] = n[j], n[i]
}
func (n NodeHeap) Less(i, j int) bool {
return n[i].d < n[j].d
}
func (n *NodeHeap) Push(h interface{}) {
*n = append(*n, h.(Node))
}
func (n *NodeHeap) Pop() (x interface{}) {
x = (*n)[len(*n)-1]
*n = (*n)[:len(*n)-1]
return
}
func main() {
var T int
fmt.Scan(&T)
var n, m int
for C := 1; C <= T; C++ {
fmt.Scan(&n, &m)
h := make([][]int, n+1)
dist := make([][]int, n+1)
st := make([][]bool, n+1)
for i := 1; i <= n; i++ {
h[i] = make([]int, m+1)
st[i] = make([]bool, m+1)
dist[i] = make([]int, m+1)
for j := 1; j <= m; j++ {
fmt.Scan(&h[i][j])
dist[i][j] = int(^uint(0)>>1)
}
}
hp := &NodeHeap{}
heap.Init(hp)
for i := 1; i <= n; i++ {
heap.Push(hp, Node{i, 1, h[i][1]})
dist[i][1] = h[i][1]
heap.Push(hp, Node{i, m, h[i][m]})
dist[i][m] = h[i][m]
}
for i := 2; i <= m; i++ {
heap.Push(hp, Node{1, i, h[1][i]})
dist[1][i] = h[1][i]
heap.Push(hp, Node{n, i, h[n][i]})
dist[n][i] = h[n][i]
}
ans := 0
dx, dy := [4]int{-1, 0, 1, 0}, [4]int{0, 1, 0, -1}
for hp.Len() > 0 {
top := heap.Pop(hp).(Node)
st[top.x][top.y] = true
ans += top.d - h[top.x][top.y]
for i := range dx {
nx, ny := top.x + dx[i], top.y + dy[i]
if nx < 1 || nx > n || ny < 1 || ny > m || st[nx][ny] {
continue
}
if dist[nx][ny] > max(top.d, h[nx][ny]) {
dist[nx][ny] = max(top.d, h[nx][ny])
heap.Push(hp, Node{nx, ny, dist[nx][ny]})
}
}
}
fmt.Printf("Case #%d: %d\n", C, ans)
}
}
func max(a, b int) (x int) {
if a > b {
x = a
} else {
x = b
}
return
}
密码脱落-LCS
思路
求字符串及其翻转串的LCS长度
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n^2)$ | $O(n^2)$ |
代码
package main
import "fmt"
func reverse(s string) (res string) {
a := []rune(s)
n := len(a)
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
a[i], a[j] = a[j], a[i]
}
return string(a)
}
func main() {
var a, b string
fmt.Scanf("%s", &a)
n := len(a)
b = reverse(a)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
if a[i-1] == b[j-1] {
f[i][j] = f[i-1][j-1] + 1
} else {
f[i][j] = max(f[i-1][j], f[i][j-1])
}
}
}
fmt.Println(n - f[n][n])
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
森林中的兔子
思路
- 统计每种$x$出现的次数
- 若$x$出现了$k$次为了使得兔子数量最小，则兔子种类数为 $\lceil \frac{k}{x+1} \rceil$, 且每种兔子数量为$x+1$
- 则兔子总数为$\sum_i^n{ \lceil \frac{k_i}{x_i+1} \rceil \times (x_i+1)}$
- 例如有13只兔子回答5，则至少有六只同一种类兔子记为红色，还有六只另一种类记为蓝色，还剩下一只兔子回答5，则必然还有五只兔子与这一只兔子颜色相同记为白色。综上有$\lceil \frac{13}{5+1} \rceil \times (5+1) = 18$只兔子。
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n)$ | $O(n)$ |
代码
func numRabbits(answers []int) int {
mp := make(map[int]int)
for i := range answers {
mp[answers[i]]++
}
ret := 0
for k, v := range mp {
ret += (v + k) / (k + 1) * (k + 1);
}
return ret;
}
石子合并-区间DP
思路
- $f[i][j]$表示将表示将 $i$ 到 $j$ 合并成一堆的方案的集合，属性是最小值
- $f[i][j]=min_{i≤k≤j−1}\{f[i][k]+f[k+1][j]+s[j]−s[i−1]\}$
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n^3)$ | $O(n^2)$ |
代码
package main
import "fmt"
const N = 305
var n int
var s [N]int
var f [N][N]int
func main() {
fmt.Scan(&n)
for i := 1; i <= n; i++ {
fmt.Scan(&s[i])
s[i] += s[i-1]
}
for len := 2; len <= n; len++ {
for i := 1; i + len - 1 <= n; i++ {
j := i + len - 1
f[i][j] = int(^uint(0) >> 1)
for k := i; k < j; k++ {
f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1])
}
}
}
fmt.Println(f[1][n])
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
环形石子合并
思路
- 破环成链
- 求所有区间长度为n的链形石子合并
- 枚举长度为n的区间，取max
代码
package main
import "fmt"
const (
N = 405
INT_MAX = int(^uint(0) >> 1)
INT_MIN = -INT_MAX - 1
)
var (
n int
f [N][N]int
g [N][N]int
s [N]int
a [N]int
)
func main() {
fmt.Scan(&n)
for i := 1; i <= n; i++ {
fmt.Scan(&a[i])
a[i+n] = a[i]
}
for i := 1; i <= 2*n; i++ {
s[i] = s[i-1] + a[i]
}
for l := 2; l <= n; l++ {
for i := 1; i+l-1 <= 2*n; i++ {
j := i + l - 1
f[i][j], g[i][j] = INT_MAX, INT_MIN
for k := i; k < j; k++ {
f[i][j], g[i][j] = min(f[i][j], f[i][k]+f[k+1][j]+s[j]-s[i-1]), max(g[i][j], g[i][k]+g[k+1][j]+s[j]-s[i-1])
}
}
}
minv, maxv := INT_MAX, INT_MIN
for i := 1; i <= n; i++ {
minv = min(minv, f[i][i+n-1])
maxv = max(maxv, g[i][i+n-1])
}
fmt.Println(minv)
fmt.Println(maxv)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
合并两个有序数组
解题思路
- 指针从后往前移动
- 每次将较大值插到后面
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(m+n)$ | $O(1)$ |
代码
func merge(A []int, m int, B []int, n int) {
i, j := m-1, n-1
for k := m+n-1; k >= 0; k-- {
if i == -1 {
A[k] = B[j]
j--
} else if j == -1 {
A[k] = A[i]
i--
} else if A[i] > B[j] {
A[k] = A[i]
i--
} else {
A[k] = B[j]
j--
}
}
}
删除有序数组中的重复项II
思路
k指向新数组的末尾- 遍历数组，若当前元素不等于
nums[k-2]则插入新数组的末尾
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n)$ | $O(1)$ |
代码
func removeDuplicates(nums []int) int {
n := len(nums)
if n <= 2 {
return n
}
k := 2
for i := 2; i < n; i++ {
if nums[i] != nums[k-2] {
nums[k] = nums[i]
k++
}
}
return k
}
搜索旋转排序数组II-二分
思路
nums[l] == nums[mid]：不能确定哪一个区间是有序的，l++nums[l] < nums[mid]：左区间是有序的nums[l] > nums[mid]：右区间是有序的
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n)$ | $O(1)$ |
代码
func search(nums []int, target int) bool {
n := len(nums)
if n == 0 {
return false
}
l, r := 0, n-1
for l <= r {
mid := (l + r) >> 1
if nums[mid] == target {
return true
} else if nums[l] == nums[mid] {
l++
continue
} else if nums[l] < nums[mid] {
if nums[l] <= target && target < nums[mid] {
r = mid - 1
} else {
l = mid + 1
}
} else {
if nums[mid] < target && target <= nums[r] {
l = mid + 1
} else {
r = mid - 1
}
}
}
return false
}
0到n-1中缺失的数字-二分
思路
<img src=“https://cdn.acwing.com/media/article/image/2019/05/31/1_37a28f4683-%E7%BC%BA%E5%A4%B1%E6%95%B0%E5%AD%97.png" position=“center” style=“zoom: 80% ;”
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(logn)$ | $O(1)$ |
代码
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
const int n = nums.size();
if (!n) {
return 0;
}
if (nums[n-1] == n-1) {
return n;
}
int l = 0, r = n-1;
while (l < r) {
const int mid = (l + r) >> 1;
if (nums[mid] != mid) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};
移去K位数字-贪心
思路
- 如果字符串已经是有序的，则应该删除后$k$位
- 如果出现逆序，则应该把前一个元素删除
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n)$ | $O(1)$ |
代码
package main
import (
"fmt"
)
func main() {
var s string
var k int
fmt.Scan(&s, &k)
ans := "0"
for _, v := range s {
for k > 0 && ans[len(ans)-1] > byte(v) {
ans = ans[:len(ans)-1]
k--
}
ans += string(v)
}
for k > 0 {
ans = ans[:len(ans)-1]
k--
}
i := 0
for i < len(ans) - 1 && ans[i] == '0' {
i++
}
fmt.Println(ans[i:])
}
二叉搜索树节点最小距离
思路
二叉搜索树中序遍历有序
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n)$ | $O(1)$ |
代码
const MAX int = int(^uint(0) >> 1)
func minDiffInBST(root *TreeNode) (ans int) {
ans = MAX
var last int
is_first := false
var dfs func(root *TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
if (!is_first) {
is_first = true
} else {
ans = min(ans, root.Val - last)
}
last = root.Val
dfs(root.Right)
}
dfs(root)
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
实现Trie树
思路
- 字典树
代码
type Trie struct {
son [26]*Trie
isEnd bool
}
/** Initialize your data structure here. */
func Constructor() Trie {
return Trie{}
}
func (this *Trie) query(word string) (res *Trie) {
node := this
for _, v := range word {
t := v - 'a'
if node.son[t] == nil {
res = nil
return
}
node = node.son[t]
}
res = node
return
}
/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
node := this
for _, v := range word {
t := v - 'a'
if node.son[t] == nil {
node.son[t] = &Trie{}
}
node = node.son[t]
}
node.isEnd = true
}
/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
node := this.query(word)
return node != nil && node.isEnd
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
return this.query(prefix) != nil
}
前缀统计-Trie
链表代码
package main
import "fmt"
type Trie struct {
son [26]*Trie
isEnd bool
cnt int
}
func NewTrie() *Trie {
return &Trie{}
}
func (t *Trie) insert(word string) {
node := t
for _, v := range word {
c := v - 'a'
if node.son[c] == nil {
node.son[c] = NewTrie()
}
node = node.son[c]
}
node.cnt++
node.isEnd = true
}
func (t *Trie) query(word string) (ans int) {
node := t
for _, v := range word {
c := v - 'a'
if node.son[c] == nil {
return ans
}
node = node.son[c]
ans += node.cnt
}
return
}
func main() {
var n, m int
fmt.Scan(&n, &m)
var s string
t := NewTrie()
for i := 0; i < n; i++ {
fmt.Scan(&s)
t.insert(s)
}
for i := 0; i < m; i++ {
fmt.Scan(&s)
fmt.Println(t.query(s))
}
}
数组代码
package main
import "fmt"
const N = 1e6 + 5
var (
n, m int
son [N][26]int
idx int
cnt [N]int
)
func insert(word string) {
p := 0
for _, v := range word {
t := v - 'a'
if son[p][t] == 0 {
idx++
son[p][t] = idx
}
p = son[p][t]
}
cnt[p]++
}
func query(word string) (ans int) {
p := 0
for _, v := range word {
t := v - 'a'
if son[p][t] == 0 {
return
}
p = son[p][t]
ans += cnt[p]
}
return
}
func main() {
fmt.Scan(&n, &m)
var s string
for i := 0; i < n; i++ {
fmt.Scan(&s)
insert(s)
}
for i := 0; i < m; i++ {
fmt.Scan(&s)
fmt.Println(query(s))
}
}
打家劫舍II-DP
解题思路
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n)$ | $O(n)$ |
代码
func rob(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
f := make([][2]int, n)
f[0][0], f[0][1] = math.MinInt64, nums[0]
for i := 1; i < n; i++ {
f[i][0] = max(f[i-1][0], f[i-1][1])
f[i][1] = f[i-1][0] + nums[i]
}
res := f[n-1][0]
f[0][0], f[0][1] = 0, math.MinInt64
for i := 1; i < n; i++ {
f[i][0] = max(f[i-1][0], f[i-1][1])
f[i][1] = f[i-1][0] + nums[i]
}
return max(res, max(f[n-1][0], f[n-1][1]))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
扰乱字符串-DP
思路
- 状态表示
f[i][j][k]- 集合：
s1[i..i+k-1]和s2[j..j+k-1]所有匹配的方案的集合 - 属性：集合是否为空集
- 集合：
- 状态计算：
f[i][j][k]按s1第一段的长度划分成k-1类，有两种匹配方案f[i][j][u] && f[i+u][j+u][k-u]f[i][j+k-u][u] && f[i+u][j][k-u]
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n^4)$ | $O(n^3)$ |
代码
func isScramble(s1 string, s2 string) bool {
n := len(s1)
f := make([][][]bool, n)
for i := range f {
f[i] = make([][]bool, n)
for j := range f[i] {
f[i][j] = make([]bool, n+1)
}
}
for k := 1; k <= n; k++ {
for i := 0; i+k-1 < n; i++ {
for j := 0; j+k-1 < n; j++ {
if k == 1 {
if s1[i] == s2[j] {
f[i][j][k] = true
}
} else {
for u := 1; u < k; u++ {
if f[i][j][u] && f[i+u][j+u][k-u] ||
f[i][j+k-u][u] && f[i+u][j][k-u] {
f[i][j][k] = true
break
}
}
}
}
}
}
return f[0][0][n]
}
重复元素III-滑动窗口
思路
- 有序集合中查找大于等于
x - t的最小的元素y，如果y存在，且y <= x + t则存在 - 有序集合中元素数量超过了
k，将有序集合中最早被插入的元素删除即可
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(nlogk)$ | $O(k)$ |
代码
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<long> st;
const int n = nums.size();
for (int i = 0; i < n; i++) {
auto it = st.lower_bound(nums[i]*1l-t);
if (it != end(st) && *it <= nums[i]*1l+t) {
return true;
}
st.insert(nums[i]);
if (i-k >= 0)
st.erase(nums[i-k]);
}
return false;
}
};
解码方法-dp
思路
- 状态表示：$f[i]$表示前 $i$ 个数字共有多少种解码方式。
- 状态转移：
- 如果第 $i$ 个数字不是$0$，则 $i$ 个数字可以单独解码成一个字母，此时的方案数等于用前 $i−1$ 个数字解码的方案数，即 $f[i−1]$
- 如果第 $i−1$个数字和第 $i$个数字组成的两位数在 $10$ 到 $26$ 之间，则可以将这两位数字解码成一个字符，此时的方案数等于用前 $i−2$ 个数字解码的方案数，即 $f[i−2]$
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n)$ | $O(n)$ |
代码
func numDecodings(s string) int {
n := len(s)
f := make([]int, n+1)
f[0] = 1
for i := 1; i <= n; i++ {
if s[i-1] != '0' {
f[i] += f[i-1]
}
if i > 1 {
t := (s[i-2] - '0') * 10 + s[i-1] - '0'
if t >= 10 && t <= 26 {
f[i] += f[i-2]
}
}
}
return f[n]
}
矩形区域不超过 K 的最大数值和-前缀和
思路
- 二重循环枚举矩形的上边界和下边界，时间复杂度
O(n^2) - 在一维数组求和不超过K的最大子数组的和，我们可以在
O(nlogn)的时间复杂度内求解。我们知道可以使用前缀和求解子区间和：sum(A[i:j])=preSum[j]−preSum[i−1]。那么对于每一个preSum[j]，我们可以将遇到过的前缀后存入一个set中，再从set中找到一个大于等于preSum[j]−k的最小值，这样他们的差值就是小于等于kk的最大值。这种查找的时间复杂度是logn的，总共需要查找n次，所以总共的时间复杂度为O(nlogn)
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(m^2nlogn)$ | $O(n)$ |
代码
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& A, int k) {
const int m = A.size(), n = A[0].size();
int ans = INT_MIN;
for (int i = 0; i < m; i++) {
vector<int> sum(n);
for (int j = i; j < m; j++) {
for (int k = 0; k < n; k++) {
sum[k] += A[j][k];
}
set<int> st{0};
int s = 0;
for (const auto &e : sum) {
s += e;
auto it = st.lower_bound(s - k);
if (it != st.end()) {
ans = max(ans, s - *it);
}
st.insert(s);
}
}
}
return ans;
}
};
最大整除子集-dp
解题思路
- 前提：升序
- 状态集合：$f[i]$表示最大元素为$nums[i]$的有效解子集
- 属性：有效子集大小
- 状态计算：$f[i]=max(f[i], f[j]+1), j=0..i-1$
- 倒序遍历$f$找到集合元素
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(n^2)$ | $O(n)$ |
代码
func largestDivisibleSubset(nums []int) []int {
sort.Ints(nums)
n := len(nums)
f := make([]int, n)
for i := range f {
f[i] = 1
}
maxLen := 1
for i := range f {
for j := 0; j < i; j++ {
if nums[i] % nums[j] == 0 {
f[i] = max(f[i], f[j] + 1)
maxLen = max(maxLen, f[i])
}
}
}
ans := make([]int, maxLen)
end := true
for i := n-1; i >= 0 && maxLen > 0; i-- {
if f[i] == maxLen && (end || ans[maxLen] % nums[i] == 0) {
ans[maxLen-1] = nums[i]
end = false
maxLen--
}
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
整数拆分-完全背包
思路
完全背包
- 状态表示：$f[i]$表示$i$的不同拆分方式数
- 状态计算：$f[i]=f[j]+f[j-2^i], 0 \le 2^i \le n$
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(nlogn)$ | $O(n)$ |
代码
package main
import "fmt"
const (
N = 1e6 + 5
mod = 1e9
)
var (
n int
f [N]int
)
func main() {
fmt.Scan(&n)
f[0] = 1
for i := 0; 1<<i <= n; i++ {
for j := 1<<i; j <= n; j++ {
f[j] = (f[j] + f[j-1<<i]) % mod
}
}
fmt.Println(f[n])
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
组合总和IV-DP
思路
考虑顺序背包->先枚举体积，再枚举物品
| 时间复杂度 | 空间复杂度 |
|---|---|
| $O(mn)$ | $O(n)$ |
代码
func combinationSum4(nums []int, target int) int {
f := make([]int, target+1)
f[0] = 1
for i := 0; i <= target; i++ {
for _, v := range nums {
if i >= v {
f[i] += f[i-v]
}
}
}
return f[target]
}
最大的和-前缀和&滑动窗口
代码
package main
import "fmt"
const N = 1e5 + 5
var (
n int
k int
A [N]int
B [N]bool
)
func main() {
fmt.Scan(&n, &k)
for i := 0; i < n; i++ {
fmt.Scan(&A[i])
}
sum := 0
for i := 0; i < n; i++ {
fmt.Scan(&B[i])
if B[i] {
sum += A[i]
}
}
ans := 0
for i := 0; i < n; i++ {
if !B[i] {
sum += A[i]
}
if i >= k && !B[i-k] {
sum -= A[i-k]
}
ans = max(ans, sum)
}
fmt.Println(ans)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
八数码-A*
代码
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const string go = "urdl";
string s, t = "12345678x";
int get_f(const string &sts, int g) {
int f = g;
for (int i = 0; i < 9; i++) {
if (sts[i] != t[i]) {
f++;
}
}
return f;
}
unordered_map<string, int> mp;
priority_queue<pair<int, string>> que;
unordered_map<string, pair<char, string>> path;
int get_x(const string &sts) {
for (int i = 0; i < 9; i++) {
if (sts[i] == 'x')
return i;
}
return -1;
}
void dfs(const string &tmp) {
if (!path.count(tmp))
return;
dfs(path[tmp].second);
printf("%c", path[tmp].first);
}
bool check(const string &tmp) {
int cnt = 0;
for (int i = 0; i < 9; i++) {
if (tmp[i] == 'x')
continue;
for (int j = i + 1; j < 9; j++) {
if (tmp[j] != 'x' && tmp[i] > tmp[j])
cnt++;
}
}
return (cnt & 1) == 0;
}
void bfs() {
que.push({0, s});
mp[s] = 0;
if (!check(s)) {
puts("unsolvable");
return;
}
while (que.size()) {
auto [_, sts] = que.top();
que.pop();
if (sts == t) {
break;
}
auto idx = get_x(sts);
auto x = idx / 3, y = idx % 3;
for (int i = 0; i < 4; i++) {
auto cp = sts;
auto nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx <= 2 && ny >= 0 && ny <= 2) {
swap(cp[nx * 3 + ny], cp[idx]);
if (mp.count(cp))
continue;
path[cp] = {go[i], sts};
mp[cp] = mp[sts] + 1;
que.push({-get_f(cp, mp[cp]), cp});
}
}
}
dfs(t);
}
int main() {
char tmp;
for (int i = 0; i < 9; i++) {
cin >> tmp;
s += tmp;
}
bfs();
return 0;
}
最长递增子序列的个数-LIS
代码
func findNumberOfLIS(nums []int) int {
n := len(nums)
dp, cnt := make([]int, n), make([]int, n)
maxLen, ans := 0, 0
for i := range nums {
dp[i], cnt[i] = 1, 1
for j := 0; j < i; j++ {
if nums[i] > nums[j] {
if dp[j] + 1 > dp[i] {
dp[i] = dp[j] + 1
cnt[i] = cnt[j]
} else if dp[j] + 1 == dp[i] {
cnt[i] += cnt[j]
}
}
}
if maxLen < dp[i] {
maxLen = dp[i]
ans = cnt[i]
} else if maxLen == dp[i] {
ans += cnt[i]
}
}
return ans
}
牛的学术圈子I-二分
代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using std::cin;
int n, l;
std::vector<int> cite;
bool check(const int &mid) {
int cnt = 0;
for (const auto &e : cite) {
if (e >= mid) {
cnt++;
}
}
return cnt >= mid;
}
int binary_search(int l, int r) {
while (l < r) {
const auto mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
int main() {
cin >> n >> l;
cite.resize(n);
int max_cite = 0;
int min_cite = INT_MAX;
for (auto && e : cite) {
cin >> e;
max_cite = std::max(max_cite, e);
min_cite = std::min(min_cite, e);
}
auto res = binary_search(min_cite, max_cite);
sort(begin(cite), end(cite));
max_cite += l;
for (auto it = cite.rbegin(); it != cite.rend(); it++) {
if (l == 0)
break;
if (*it <= res) {
(*it)++;
l--;
}
}
res = binary_search(min_cite, max_cite);
printf("%d\n", res);
return 0;
}
牛年-同余
代码
#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <unordered_map>
using std::cin;
const std::unordered_map<std::string, int> zodiac_map = {
{"Ox", 0}, {"Tiger", 1}, {"Rabbit", 2}, {"Dragon", 3},
{"Snake", 4}, {"Horse", 5}, {"Goat", 6}, {"Monkey", 7},
{"Rooster", 8}, {"Dog", 9}, {"Pig", 10}, {"Rat", 11},
};
std::unordered_map<std::string, int> year;
int main() {
int n;
cin >> n;
year["Bessie"] = 0;
for (int i = 0; i < n; ++i) {
std::array<std::string, 8> strs;
for (auto &&str : strs) {
cin >> str;
}
if (strs[3] == "previous") {
const auto x = year[strs[7]];
const auto zodiac = zodiac_map.find(strs[4])->second;
auto r = ((x - zodiac) % 12 + 12) % 12;
if (r == 0) {
r = 12;
}
year[strs[0]] = x - r;
} else {
const auto x = year[strs[7]];
const auto zodiac = zodiac_map.find(strs[4])->second;
auto r = ((zodiac - x) % 12 + 12) % 12;
if (r == 0) {
r = 12;
}
year[strs[0]] = x + r;
}
}
printf("%d\n", std::abs(year["Elsie"]));
return 0;
}
找出缺失的观测数据
代码
impl Solution {
pub fn missing_rolls(rolls: Vec<i32>, mean: i32, n: i32) -> Vec<i32> {
let m = rolls.len() as i32;
let left = mean * (m + n) - rolls.iter().sum::<i32>();
let ave = left / n;
let remainder = left % n;
if ave <= 0 || ave > 6 || ave == 6 && remainder != 0 {
return vec![];
}
let mut res = vec![ave; n as usize];
for item in res.iter_mut().take(remainder as usize) {
*item += 1;
}
res
}
}
function missingRolls(rolls: number[], mean: number, n: number): number[] {
const m = rolls.length
const left = mean * (m + n) - rolls.reduce((a, b) => a + b)
const ave = Math.floor(left / n)
const remainder = left % n
if (ave <= 0 || ave > 6 || (ave === 6 && remainder !== 0))
return []
const missing = Array.from({ length: n }, (_, i) => ave + (remainder > i ? 1 : 0))
return missing
}
如果相邻两个颜色均相同则删除当前颜色
代码
class Solution {
public:
bool winnerOfGame(string colors) {
int freq[2] = {0, 0};
char cur = 'C';
int cnt = 0;
for (char c : colors) {
if (c != cur) {
cur = c;
cnt = 1;
} else if (cnt++; cnt >= 3) {
++freq[cur - 'A'];
}
}
return freq[0] > freq[1];
}
};
考试的最大困扰度
思路
双指针
- 枚举右指针，计算
answer_key[left, right]中另一个字符出现的次数 $s$ - 当 $s$ 大于 $k$，左端点右移
- 维护最大窗口长度
代码
impl Solution {
pub fn max_consecutive_answers(answer_key: String, k: i32) -> i32 {
let answer_key = answer_key.chars().collect::<Vec<char>>();
fn help(answer_key: &[char], k: i32, ch: char) -> i32 {
let mut s = 0;
let mut left = 0;
let mut max = 0;
for right in 0..answer_key.len() {
s += (answer_key[right] == ch) as i32;
while s > k {
s -= (answer_key[left] == ch) as i32;
left += 1;
}
max = max.max((right - left + 1) as i32);
}
max
}
help(&answer_key, k, 'T').max(help(&answer_key, k, 'F'))
}
}
区域和检索-数组可修改
思路
线段树裸题
代码
use std::ops::{Add, AddAssign};
/// This stucture implements a segmented tree that
/// can efficiently answer range queries on arrays.
pub struct SegmentTree<T: Default + Add + Copy> {
len: usize,
buf: Vec<T>,
}
impl<T: Default + Add<Output = T> + AddAssign + Copy> SegmentTree<T> {
/// function to build the tree
pub fn from_vec(arr: &[T]) -> Self {
let len = arr.len();
let mut buf: Vec<T> = vec![T::default(); 2 * len];
buf[len..(len + len)].clone_from_slice(&arr[0..len]);
for i in (1..len).rev() {
buf[i] = buf[2 * i] + buf[2 * i + 1];
}
SegmentTree { len, buf }
}
/// function to get sum on interval [l, r]
pub fn query(&self, mut l: usize, mut r: usize) -> T {
l += self.len;
r += self.len;
let mut res = T::default();
while l <= r {
if l % 2 == 1 {
res += self.buf[l];
l += 1;
}
if r % 2 == 0 {
res += self.buf[r];
r -= 1;
}
l /= 2;
r /= 2;
}
res
}
/// function to update a tree node
pub fn update(&mut self, mut idx: usize, val: T) {
idx += self.len;
self.buf[idx] = val;
idx /= 2;
while idx != 0 {
self.buf[idx] = self.buf[2 * idx] + self.buf[2 * idx + 1];
idx /= 2;
}
}
}
struct NumArray {
segment_tree: SegmentTree<i32>,
}
impl NumArray {
fn new(nums: Vec<i32>) -> Self {
let segment_tree = SegmentTree::from_vec(&nums);
NumArray { segment_tree }
}
fn update(&mut self, index: i32, val: i32) {
self.segment_tree.update(index as usize, val);
}
fn sum_range(&self, left: i32, right: i32) -> i32 {
self.segment_tree.query(left as usize, right as usize)
}
}
两棵二叉搜索树中的所有元素
思路
中序遍历 + 归并
代码
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn get_all_elements(
root1: Option<Rc<RefCell<TreeNode>>>,
root2: Option<Rc<RefCell<TreeNode>>>,
) -> Vec<i32> {
fn dfs(root: Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {
if let Some(node) = root {
dfs(node.borrow().left.clone(), res);
res.push(node.borrow().val);
dfs(node.borrow().right.clone(), res);
}
}
let mut res1 = vec![];
dfs(root1, &mut res1);
let mut res2 = vec![];
dfs(root2, &mut res2);
let mut merged = vec![0; res1.len() + res2.len()];
let mut i = 0;
let mut j = 0;
let mut k = 0;
while i < res1.len() && j < res2.len() {
if res1[i] < res2[j] {
merged[k] = res1[i];
i += 1;
} else {
merged[k] = res2[j];
j += 1;
}
k += 1;
}
while i < res1.len() {
merged[k] = res1[i];
i += 1;
k += 1;
}
while j < res2.len() {
merged[k] = res2[j];
j += 1;
k += 1;
}
merged
}
}
function getAllElements(root1: TreeNode | null, root2: TreeNode | null): number[] {
function dfs(root: TreeNode | null): number[] {
if (root === null) return []
const left = dfs(root.left)
const right = dfs(root.right)
return [...left, root.val, ...right]
}
const arr1 = dfs(root1)
const arr2 = dfs(root2)
const arr = []
let i = 0
let j = 0
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
arr.push(arr1[i])
i++
} else {
arr.push(arr2[j])
j++
}
}
while (i < arr1.length) {
arr.push(arr1[i])
i++
}
while (j < arr2.length) {
arr.push(arr2[j])
j++
}
return arr
}
最近的请求次数
思路
使用队列来维护最近 $3000$ 个请求的时间
代码
use std::collections::VecDeque;
struct RecentCounter {
pings: VecDeque<i32>,
}
impl RecentCounter {
fn new() -> Self {
Self {
pings: VecDeque::new(),
}
}
fn ping(&mut self, t: i32) -> i32 {
self.pings.push_back(t);
while let Some(x) = self.pings.front() {
if x + 3000 < t {
self.pings.pop_front();
} else {
break;
}
}
self.pings.len() as i32
}
}
class RecentCounter {
pings: number[] = []
constructor() { }
ping(t: number): number {
this.pings.push(t)
while (this.pings[0] < t - 3000) {
this.pings.shift()
}
return this.pings.length
}
}