专栏首页ACM算法日常LeetCode 第 210 场周赛 解题报告

LeetCode 第 210 场周赛 解题报告

5535. 括号的最大嵌套深度

「知识点:栈」

从前向后遍历字符串,只考虑 ()

  • 如果遇到 (,则入栈。
  • 如果遇到 ),则从栈中弹出一个 (

那么在遍历过程中,栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的),即那些嵌套的(

class Solution {
public:
    int maxDepth(string s) {
        int depth = 0; // 并不需要一个 std::stack,只维护一下元素数量就可以了。
        int anw = 0; // 记录一下 depth 的最大值。
        for(auto c : s) {
            if(c == '(') {
                depth ++;
            } else if(c == ')') {
                depth --;
            }
            anw = max(anw, depth);
        }
        return anw;
    }
};

5536. 最大网络秩

「知识点:容斥」

设与点p直接相连边的数量为

d(p)

枚举所有点对

(u,v)

,其秩为

对于

d(p)

,可以通过遍历一次 roads 搞定~

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        int anw = 0;
        vector<vector<int>> cnt(n, vector<int>(n, 0));
        vector<int> cl(n, 0), cr(n, 0);
        for(const auto &r : roads) {
            cnt[r[0]][r[1]]++; // 标记是否存在边(u,v)
            cnt[r[1]][r[0]]++;
            cl[r[0]]++;   // 预处理与 p 直接相连边的数量
            cl[r[1]]++;
            cr[r[0]]++;
            cr[r[1]]++;
        }
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                anw = max(anw, cl[i] + cr[j] - cnt[i][j]);
            }
        }
        return anw;
    }
};

5537. 分割两个字符串得到回文串

「知识点:回文串」

设字符串长度为 l。如果 A,B 分割后可拼接为回文串,则必然存在

n ∈ [0, l)

,满足下述两个要求:

  • A中长度为n的 前缀和B中长度为n的 后缀互为镜像, 或者,A中长度为n的 后缀和B中长度为n的 前缀互为镜像
  • A中长度为 l-2n的中间部分是一个回文串, 或者,B中长度为 l-2n的中间部分是一个回文串。

可以先找出符合上述要求的最大的 n,然后判断剩下的长度为 l-2n 的中间部分是否为回文串。

class Solution {
public:
    bool isPalindrome(const std::string &a, int l, int r) {
        // 判断中间部分是否为回文串
        while(l < r) {
            if(a[l] != a[r]) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
    
    bool check(const string &a, const string &b) {
        // 从 a 中选取前缀, 从 b 中选取后缀
        for(int i = 0, j = a.size()-1; i < j; i++, j--) {
            if(a[i] != b[j]) {
                if(isPalindrome(a, i, j) || isPalindrome(b, i, j)) {
                    return true;
                } else {
                    break;
                }
            }
            if(j-i <= 2) { // 中间部分为空字符串或者为单字符的情况
                return true;
            }
        }
        
        // 从 b 中选取前缀, 从 a 中选取后缀
        for(int i = 0, j = a.size()-1; i < j; i++, j--) {
            if(b[i] != a[j]) {
                return isPalindrome(a, i, j) || isPalindrome(b, i, j);
            }
            if(j-i <= 2) {  // 中间部分为空字符串或者为单字符的情况
                return true;
            }
        }
        return true;
    }
    bool checkPalindromeFormation(string a, string b) {
        return check(a, b);
    }
};

5538. 统计子树中城市之间最大距离

「知识点:状态压缩,树的遍历」

首先,借助状态压缩的技巧,枚举点的子集s。其次,检查s是否可以组成一颗子树。最后,计算s对应子树的直径,即城市之间的最大距离。

计算树的直径:因为数据量比较小,直接暴力搞吧,详见代码。(比较高级的做法是树形DP,老铁可以自行百度)。

class Solution {
public:
    vector<int> vec[20];
    vector<int> anw;
    bool getPath(int s, int pre, int t, vector<int> &path) {
        if(s == t) {
            return true;
        }
        for(auto c : vec[s]) {
            if(c == pre) {
                continue;
            }
            if(getPath(c, s, t, path)) {
                path.push_back(s);
                return true;
            }
        }
        return false;
    }
    int getDis(int s, int t, int status) {
        vector<int> path;
        // dfs 获取 (s, t) 之间的路径
        getPath(s, -1, t, path);
        
        // 判断路径上的点是否都在点集内
        for(auto c : path) {
            if((status&(1<<(c-1))) == 0) {
                return -1;
            }
        }
        return path.size();
    }
    int get(int n, int status) {
        int maxDis = 0;
        for(int i = 1, bi = 1; i <= n; i++, bi <<= 1) {
            if((bi&status) == 0) {
                continue;
            }
            for(int j = i+1, bj = bi<<1; j <= n; j++, bj <<= 1) {
                // 两层 for 循环,枚举点对 (i,j)
                if((bj&status) == 0) {
                    continue;
                }
                // 获取 (i,j)之间的路径长度,并判断路径上的点是否都在该点集内。
                int tmpDis = getDis(i, j, status);
                
                // tmpDis 不超过 0,说明status不能构成一棵子树
                if(tmpDis <= 0) {
                    return 0;
                }
                maxDis = max(maxDis, tmpDis);
            }
        }
        return maxDis;
    }
    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
        // 先搞个邻接表
        for(const auto &pair : edges) {
            vec[pair[0]].push_back(pair[1]);
            vec[pair[1]].push_back(pair[0]);
        }
        // 初始化答案
        anw.resize(n-1);
        //因为至少应该包含两个点,所以从 3 开始枚举
        
        for(int i = 3, mask = 1<< n; i < mask; i++) {
            int dis = get(n, i);
            //利用 dis <= 0 表示点集不能构成子树
            if(dis <= 0) {
                continue;
            }
            anw[dis-1] ++;
        }
        return anw;
    }
};

本文分享自微信公众号 - ACM算法日常(acm-clan)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常
  • Leetcode 周赛题解 220

    给你一个字符串形式的电话号码 number 。number 由数字、空格 ' '、和破折号 '-' 组成。

    ACM算法日常
  • 图论建图

    图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。

    ACM算法日常
  • [LightOJ-1356] Prime Independence 二分图+素数分解

    数据大,需要用优化的二分图,对每个数求出素因数,不独立的两个数之间就差一个素因数,若 a 去掉这个素因数得到b

    用户2965768
  • 指针详解(一)

    C语言可谓是因为指针而拥有了其他的语言所不拥有的作用,但是却又因为指针导致它对于初学者而言是一个很难克服的难题。接下来我们直切主体——指针。

    石的三次方
  • Leetcode 周赛题解 220

    给你一个字符串形式的电话号码 number 。number 由数字、空格 ' '、和破折号 '-' 组成。

    ACM算法日常
  • 一套帮助你理解C语言的测试题(转)

          原文链接:http://www.nowamagic.net/librarys/veda/detail/775

    xuyaowen
  • 洛谷P1043 数字游戏

    题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

    attack
  • C语言实现计算器(指针+函数)

    输入两个整数a和b,及+,-,*,/中的任意一字符。根据输入字符对整数a和b做相应的算术运算,如输入+,程序就给出a与b之和,输入-,就给出a和b之差,输入*,...

    小Bob来啦
  • HDU 1573 X问题

    Problem Description 求在小于等于N的正整数中有多少个X满足: Input 输入数据的第一行为一个正整数T,表示有T组测试数据。每组测...

    attack

扫码关注云+社区

领取腾讯云代金券