23.03.29 学习

Kruskal = quicksort + 并查集，并查集真忘了，也不想写重载运算符，就用cmp比较rule吧
复习一下并查集
6600/52000，一道题提交前进200，把图论补完恐怕进不去前6000，还是要补完数论ToT

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m;
int p[N];

struct Edge {
    int a, b, w;
}edges[M];

static bool cmp(Edge& a, Edge& b) {
    return a.w < b.w;
}

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
    sort(edges, edges + m, cmp);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int sum = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if (find(a) != find(b)) {
            p[find(a)] = find(b);
            cnt ++ ;
            sum += w;
        }
    }

    if (cnt != n - 1) return INF;
    else return sum;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    int res = kruskal();

    if (res == INF) cout << "impossible" << endl;
    else cout << res << endl;

    return 0;
}

23.03.29学习

确实和dijsktra算法很像，思路代码风格都是

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], dist[N];
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    int res = 0;

    for (int i = 0; i < n; i ++ ) {
        int t = -1;
        for (int j = 1; j <= n; j ++ ) 
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;
        st[t] = true;
        if (i) res += dist[t];

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f3f3f3f, sizeof g);
    while (m -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);  // 去掉重边的无向图
    }

    int t = prim();

    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}

这版提前初始化dist[1]=0，把起点的距离初始化，省去两个if(i)的判断

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], dist[N];
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int res = 0;

    for (int i = 0; i < n; i ++ ) {
        int t = -1;
        for (int j = 1; j <= n; j ++ ) 
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (dist[t] == INF) return INF;
        st[t] = true;
        res += dist[t];

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);  // 去掉重边的无向图
    }

    int t = prim();

    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}

23.03.28 学习

算法基础课补完计划开始

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1e5 + 10, M = N;
int n, m;
int h[N], e[M], ne[M], idx;
int d[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void topsort() {
    queue<int> q;
    int top[N], cnt = 0;
    for (int i = 1; i <= n; i ++ ) {
        if (d[i] == 0) {
            q.push(i);
            cnt ++ ;
            top[cnt] = i;
        }
    }
    // bfs,删除每个点的入度找拓扑序
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j] -- ;
            if (d[j] == 0) {
                q.push(j);
                cnt ++ ;
                top[cnt] = j;
            }
        }
    }
    // 判断
    if (cnt != n) cout << -1 << endl;
    else {
        for (int i = 1; i <= n; i ++ ) cout << top[i] << ' ';
        cout << endl;
    }
}

int main()
{

    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++ ;
    }

    topsort();

    return 0;
}

23.03.24 学习

纪念，力扣Hot100正式刷完，前前后后刷了一个多月，虽然慢但是也完事了，之前基本就刷的差不多了面试够用就没再着急刷，下一目标把算法基础课的数论部分刷完，COYG!!!

还是看wzc大佬的题解，思路非常好，而且和LeetCode84.最大的矩形 思路高度联通，把一维问题扩展到二维，或许不是最快的，但是思路很好想。

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size(), res = 0;
        vector<int> heights(m, 0);
        heights.push_back(-1);

        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < m; j ++ ) {
                if (matrix[i][j] == '0') heights[j] = 0;
                else heights[j] ++ ;
            }
            // for (auto x : heights) cout << x << ' ';
            // cout << endl;

            // 对于每一层的heights都计算一遍res，遍历完m层最大的res就出来了
            stack<int> stk;
            for (int i = 0; i <= m; i ++ ) {
                while (!stk.empty() && heights[i] < heights[stk.top()]) {
                    auto cur = stk.top();
                    stk.pop();

                    if (stk.empty()) res = max(res, heights[cur] * i);
                    else res = max(res, heights[cur] * (i - stk.top() - 1));
                }
                stk.push(i);
            }
        }

        return res;
    }
};

23.03.24 学习

这个题打断点多模拟一下吧，看大佬题解https://www.acwing.com/solution/content/140/

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size(), res = 0;
        heights.push_back(-1);
        stack<int> stk;

        for (int i = 0; i <= n; i ++ ) {
            while (!stk.empty() && heights[i] < heights[stk.top()]) {
                auto cur = stk.top();
                stk.pop();

                if (stk.empty()) res = max(res, heights[cur] * i);  // 左边没有比他低的柱子
                else res = max(res, heights[cur] * (i - stk.top() - 1)); 
            }
            stk.push(i);
        }

        return res;
    }
};

23.03.24 学习

题解太牛了，好难想，也不想用树状数组…，直接&O(n^2)&吧

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b) {
        if (a[0] != b[0]) return a[0] > b[0];
        return a[1] < b[1];
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);

        vector<vector<int>> res;
        for(auto p:people) res.insert(res.begin()+p[1],p);

        return res;
    }
};

23.03.23 学习

这个单调递减栈，有点东西

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> stk;
        vector<int> res(T.size());
        for (int i = T.size() - 1; i >= 0; i -- ) {
            while (stk.size() && T[i] >= T[stk.top()]) stk.pop();
            if (stk.size()) res[i] = stk.top() - i;
            stk.push(i);
        }
        return res;
    }
};

23.03.23 学习

wzc1995大佬太强了，同样的人，向他学习

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> t(26, 0);
        for (auto c : tasks) 
            t[c - 'A'] ++ ;

        priority_queue<int> heap;
        for (auto c : t) 
            if (c != 0) 
                heap.push(c);

        int res = 0;
        int interval = n + 1;
        while (true) {
            vector<int> tmp;
            for (int i = 0; i < interval; i ++ ) {
                if (!heap.empty()) {
                    tmp.push_back(heap.top() - 1);
                    heap.pop();
                }
            }

            for (auto x : tmp) {
                if (x)
                    heap.push(x);
            }

            if (heap.empty()) {
                res += tmp.size();
                break;
            } else {
                res += n + 1;
            }
        }

        return res;
    }
};

23.03.22 学习

和最长回文子串一个路数，那个是取最大，这个是统计总数

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0, n = s.size();
        for (int i = 0; i < s.size(); i ++ ) {
            for (int j = i, k = i; j >= 0 && k < n; j -- , k ++ ) {
                if (s[j] != s[k]) break;
                res ++ ;
            }

            for (int j = i, k = i + 1; j >= 0 && k < n; j -- , k ++ ) {
                if (s[j] != s[k]) break;
                res ++ ;
            }
        }

        return res;
    }
};

23.03.22 学习

简单遍历第一棵树，不用dfs也蛮好想的

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* r1, TreeNode* r2) {
        if (!r1 && !r2) return NULL;
        if (r1 && !r2) return r1;
        if (!r1 && r2) return r2;

        r1->val += r2->val;
        r1->left = mergeTrees(r1->left, r2->left);
        r1->right = mergeTrees(r1->right, r2->right);
        return r1;
    }
};