讨论/题目交流/🏆2019 力扣杯 - 全国秋季编程大赛/
🏆2019 力扣杯 - 全国秋季编程大赛

image.png

你来写我来送: 欢迎大家在本条讨论下分享和编写本次 🏆 力扣杯大赛的解题思路 / 题解

在「圈子」内撰写题解文章的同学也可以将文章链接贴在本条讨论下,力扣君将在 2019 年 10 月 10 日下午 16:00 精选 两篇优质内容,分别送出 1 本 《程序员面试金典》。
1821567415874_.pic_hd.jpg

展开讨论

我来分享一下我的代码和思路,自我感觉还是比较清晰的
来自菜鸡的题解

第一题 主要是拼手速

class Solution {
public:
    int game(vector<int>& guess, vector<int>& answer) {
        int num = 0;
        for(int i=0; i<3; i++)
            if(guess[i] == answer[i]) num++;
        return num;
    }
};

第二题 主要是根据公式进行计算,然后化简即可

可以看出每次去计算的时候都有

Snipaste_2019-09-27_22-14-34.jpg
计算后,反转一下 分子 分母 并化简,然后继续获得新的 b 重复操作
至于这三个字母为什么是这个顺序,主要是当时比赛的时候随便写的,23333

class Solution {
public:
    // 传入引用,同步更改传入的实参
    void simp(int &a, int &b) {
        // __gcd 是 C++ 封装好的求最大公约数的函数,直接调用即可
        int g = __gcd(a, b);
        a /= g, b /= g;
    }
    vector<int> fraction(vector<int>& cont) {
        int a = cont.back(), b, c = 1;
        for(int i=cont.size()-2; i>=0; i--) {
            b = cont[i];
            if(b == 0) swap(a, c);
            else {
                int tem = a;
                a = a*b + c;
                c = tem;
                simp(a, c);
            }
        }
        simp(a, c);
        return {a, c};
    }
};

第三题

主要需要把机器人的一轮操作记录一下,形成一个范围,
然后把障碍物以及终点根据距离相应地映射到这个范围内比较一下

class Solution {
public:
    bool robot(string co, vector<vector<int>>& ob, int x, int y) {
        int len = co.size(), a = 0, b = 0, m, n;
        // 根据坐标点的 x+y 大小把障碍点排序
        sort(ob.begin(), ob.end(), [](vector<int> &a, vector<int> &b) {return a[0]+a[1] < b[0]+b[1];});
        // 通过一个哈希表来记录 记录一轮操作走过的范围
        unordered_set<int> hashSet;
        hashSet.insert(0);
        for(auto &ch:co) {
            if(ch == 'U') b++;
            else a++;
            // 字符串最长不超过 1000 
            hashSet.insert(a*1000 + b);
        }
        // 把终点映射到机器人的一轮操作范围内,查看机器人能够经过终点
        m = x - (x + y) / len * a;
        n = y - (x + y) / len * b;
        // 到达不了终点
        if(hashSet.find(m*1000 + n) == hashSet.end()) return false;
        for(int i=0; i<ob.size(); i++) {
            // 终点前面的障碍都碰不到
            // 当前障碍的距离大于终点,说明已经到了终点
            if(ob[i][0] + ob[i][1] > x + y) return true;
            m = ob[i][0] - (ob[i][0] + ob[i][1]) / len * a;
            n = ob[i][1] - (ob[i][0] + ob[i][1]) / len * b;
            // 提前碰到障碍
            if(hashSet.find(m*1000 + n) != hashSet.end()) return false;
        }
        return true;
    }
};

第四题

比赛的时候并没有 AC
赛后看了大佬的代码以及 二分匹配的匈牙利算法 后写的 AC 代码

class Solution {
public:
    bool dfs(int u, vector<bool> &rep, vector<vector<int>> &G, vector<int> &mat) {
        for(int i=0; i<G[u].size(); i++) {
            int v = G[u][i];
            if(!rep[v]) { // 结点如果没有在交替路径中
                rep[v] = true;
                // 如果当前结点没有匹配,就进行匹配,或者交替路径交换
                if(mat[v] == -1 || dfs(mat[v], rep, G, mat)) {
                    mat[u] = v; // 进行匹配点的记录
                    mat[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    void getRes(int &res, int N, vector<vector<int>> &G) {
        // 初始化匹配点都是-1
        vector<int> mat(N, -1);
        for(int i=0; i<N; i++) 
            if(mat[i] == -1) {
                vector<bool> rep(N, false);
                // 每一次增广路径遍历之后,使得匹配点的对数加1
                if(dfs(i, rep, G, mat)) res++;
            }
    }
    int domino(int n, int m, vector<vector<int>>& b) {
        int N = n*m, u, v, res = 0;
        vector<vector<int>> G(N);
        vector<vector<bool>> used(n, vector<bool>(m, false));
        for(auto &it:b)
            used[it[0]][it[1]] = true;
        
        for(int i=0; i<n; i++) 
            for(int j=0; j<m; j++) 
                if(!used[i][j]) {
                    u = i*m+j;
                    if(j+1 < m && !used[i][j+1]) {
                        v = i*m + j + 1;
                        G[u].push_back(v);
                        G[v].push_back(u);
                    }
                    if(i+1 < n && !used[i+1][j]) {
                        v = i*m + m + j;
                        G[u].push_back(v);
                        G[v].push_back(u);
                    }
                }
        getRes(res, N, G);
        return res;
    }
};

第五题

这一题,我的代码复杂度相当高,所以代码看起来比较精简,属于卡着线过的 704ms
这一题,我查询的复杂度为 O(1)O(1),整加一个人的钱数的复杂度为 O(M)O(M),M 为最深的层数
增加一群人的钱数的复杂度为 O(M∗N)O(M * N),N 为人数

class Solution {
public:
    const int mod = 1e9 +7;
    void dfs(vector<vector<int>>& gr, vector<int>& fa, vector<long long> &res, int x, int y) {
        // 增加当前点的每个人以及对应上司的奖金
        up(gr, fa, res, x, y);
        for(int i=0; i<gr[x].size(); i++)
            // 递归遍历每个点
            dfs(gr, fa, res, gr[x][i], y);
    }
    void up(vector<vector<int>>& gr, vector<int>& fa, vector<long long> &res, int cur, int mon) {
        // 增加每个人以及对应上司的奖金
        while(cur != 0) {
            res[cur] = (res[cur] + mon) % mod;
            cur = fa[cur];
        }
    }
    vector<int> bonus(int n, vector<vector<int>>& le, vector<vector<int>>& op) {
        // 建立基于邻接表的图,因为没有环,所以其实是棵树
        vector<vector<int>> graph(n+1);
        // 每个节点以及子节点的奖金值
        vector<long long> res(n+1, 0);
        // 保存每个节点的父节点
        vector<int> fa(n+1, 0);
        // 建立连接,以及更新父节点
        for(auto &it:le) graph[it[0]].push_back(it[1]), fa[it[1]] = it[0];
        vector<int> ret;
        for(auto &it:op) {
            // 根据命令不同,进行对应操作
            if(it[0] == 1) up(graph, fa, res, it[1], it[2]);
            else if(it[0] == 2) dfs(graph, fa, res, it[1], it[2]);
            else ret.push_back(res[it[1]] % mod);
        }
        return ret;
    }
};
17
展开全部 23 讨论