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;
}

时间优化

  1. $ 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]] $
  2. $ f[i][j-v] = f[i-1][j-w[i]]+f[i-1][j-2w[i]]+…+f[i-1][j-kw[i]] $
  3. 由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

题目链接

思路

  1. 状态表示
    • 集合:定义f[i][j]为从(1, 1)到达(i, j)的所有方案
    • 属性:最大值
  2. 状态转移
    • (i, j)从(i-1, j)即上方过来
    • (i, j)从(i, j-1)即左方过来
  3. 空间压缩
    • 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]答案变大,就把答案xorp[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+1
  • a->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;
}

二叉树的下一个结点

题目链接

思路

  1. 若当前结点有右儿子,则右子树中最左侧的结点就是当前结点的后继
  2. 如果当前没有右儿子,则要沿着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
}

翻转单词顺序

题目链接

思路

  1. 将整个字符串翻转
  2. 翻转每个单词
时间复杂度空间复杂度
$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左边的数都小于等于xx下边的数都大于等于x

  1. 如果 x 等于target,则说明我们找到了目标值,返回true
  2. 如果 x 小于target,则 x 左边的数一定都小于target,我们可以直接排除当前一整行的数
  3. 如果 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

题目链接

思路

  1. k指向新数组的末尾
  2. 遍历数组,若当前元素不等于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类,有两种匹配方案
    1. f[i][j][u] && f[i+u][j+u][k-u]
    2. 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$ 个数字共有多少种解码方式。
  • 状态转移:
    1. 如果第 $i$ 个数字不是$0$,则 $i$ 个数字可以单独解码成一个字母,此时的方案数等于用前 $i−1$ 个数字解码的方案数,即 $f[i−1]$
    2. 如果第 $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'))