LeetCode第5场双周赛题解

红太狼 2021-11-16 16:02 306阅读 0赞

竞赛链接：[https://leetcode-cn.com/contest/biweekly-contest-5][https_leetcode-cn.com_contest_biweekly-contest-5]

**1.最大唯一数**

给你一个整数数组 `A`，请找出并返回在该数组中仅出现一次的最大整数。

如果不存在这个只出现一次的整数，则返回 -1。

**示例 1：**

输入：[5,7,3,9,4,9,8,3,1]
    输出：8
    解释： 
    数组中最大的整数是 9，但它在数组中重复出现了。而第二大的整数是 8，它只出现了一次，所以答案是 8。

**示例 2：**

输入：[9,9,8,8]
    输出：-1
    解释： 
    数组中不存在仅出现一次的整数。

**提示：**

1.  `1 <= A.length <= 2000`
2.  `0 <= A[i] <= 1000`

**思路：**

**开一个足够大的dp数组专门存放整数每个整数出现的次数，遍历一遍数组，找到出现次数为1（dp\[i\]==1）的所有整数中最大的那个即可。**

**上AC代码：**

class Solution {
    public:
        int dp[1001];
        int largestUniqueNumber(vector<int>& A) {
            memset(dp,0,sizeof(dp));
            int i;
            int len=A.size();
            for(i=0;i<len;i++)
            {
                dp[A[i]]++;
            }
            int ret=-1;
            for(i=0;i<len;i++)
            {
                if(dp[A[i]]==1)
                {
                    if(A[i]>ret)
                    {
                        ret=A[i];
                    }
                }
            }
            return ret;
        }
    };

**2.阿姆斯特朗数**

假设存在一个 `k` 位数 `N`，其每一位上的数字的 `k` 次幂的总和也是 `N`，那么这个数是阿姆斯特朗数。

给你一个正整数 `N`，让你来判定他是否是阿姆斯特朗数，是则返回 `true`，不是则返回 `false`。

**示例 1：**

输入：153
    输出：true
    示例： 
    153 是一个 3 位数，且 153 = 1^3 + 5^3 + 3^3。

**示例 2：**

输入：123
    输出：false
    解释： 
    123 是一个 3 位数，且 123 != 1^3 + 2^3 + 3^3 = 36。

**思路：**

**解析出整个数的每一位上的数字，将其入栈，统计出一共有多少位（整型变量len），将len方和sum初始化为0，然后一个一个出栈，设出栈的数字为now，每次出栈都sum+=pow(now,len)。最后判断sum与N是不是相等，若相等返回true，不相等返回false。**

**上AC代码：**

class Solution {
    public:
        bool isArmstrong(int N) {
            int len=0;
            int p=N;
            stack<int> s;
            while(p)
            {
                len++;
                s.push(p%10);
                p/=10;
            }
            bool ret=false;
            int sum=0;
            while(!s.empty())
            {
                int now=s.top();
                s.pop();
                sum+=pow(now,len);
            }
            if(N==sum)
                ret=true;
            return ret;
        }
    };

**3.最低成本联通所有城市**

想象一下你是个城市基建规划者，地图上有 `N` 座城市，它们按以 `1` 到 `N` 的次序编号。

给你一些可连接的选项 `conections`，其中每个选项 `conections[i] = [city1, city2, cost]` 表示将城市 `city1` 和城市 `city2` 连接所要的成本。（**连接是双向的**，也就是说城市 `city1` 和城市 `city2` 相连也同样意味着城市 `city2` 和城市 `city1` 相连）。

返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为 1 的）最小成本。该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务，则请你返回 -1。

**示例 1：**

![aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE5LzA3LzI3LzEzMTRfZXgyLnBuZw][]

输入：N = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
    输出：6
    解释：
    选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。

**示例 2：**

![aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE5LzA3LzI3LzEzMTRfZXgxLnBuZw][]

输入：N = 4, conections = [[1,2,3],[3,4,4]]
    输出：-1
    解释： 
    即使连通所有的边，也无法连接所有城市。

**提示：**

1.  `1 <= N <= 10000`
2.  `1 <= conections.length <= 10000`
3.  `1 <= conections[i][0], conections[i][1] <= N`
4.  `0 <= conections[i][2] <= 10^5`
5.  `conections[i][0] != conections[i][1]`

**思路：**

**并查集+最小生成树。**

关于最小生成树算法：最小生成树问题（MST）是为了解决以最低的花费连接所有的点（使图的连通分量的数目为1）而提出的。

这里采用并查集+Kruskal算法：用边结构体存储图的信息，如下：

struct edge

int from;

int to;

int cost;

先**将边按cost从小到大排序****，**然后遍历所有的边，每遍历到一条边，就使用并查集的Find函数**判断一下from和to是否在同一个连通分量里，如果原本就在同一个连通分量里，说明加上当前遍历的边就要形成环；所以只有from和to不在同一个连通分量的时候，才能f\[Find(from)\]=Find(to),然后让总花费sum+=cost。**遍历完全部的边就得到了最小花费。

**上AC代码：**

struct edge
    {
        int from;
        int to;
        int cost;
    };
    bool cmp(edge a,edge b)
    {
        return a.cost<b.cost;
    };
    class Solution {
    public:
        edge e[10001];
        bool vis[10001];
        int f[10001];
        int Find(int x)
        {
            if(f[x]==x)
                return x;
            else
                return f[x]=Find(f[x]);
        }
        int minimumCost(int N, vector<vector<int>>& conections) {
            int ret=-1;
            int cnt=0;
            int len=conections.size();
            int i;
            //初始化并查集
            for(i=0;i<=N;i++)
            {
                f[i]=i;
            }
            //初始化地图
            for(i=0;i<len;i++)
            {
                int a=conections[i][0];
                int b=conections[i][1];
                int c=conections[i][2];
                e[cnt].from=a;
                e[cnt].to=b;
                e[cnt].cost=c;
                cnt++;
            }
            //地图初始化完成
            sort(e,e+cnt,cmp);
            int sum=0;
            for(i=0;i<cnt;i++)
            {
                int a=e[i].from;
                int b=e[i].to;
                int c=e[i].cost;
                if(Find(a)==Find(b))
                {
                    //成环
                    continue;
                }
                else
                {
                    f[Find(a)]=Find(b);
                    sum+=c;
                }
            }
            int num=0;
            memset(vis,0,sizeof(vis));
            for(i=1;i<=N;i++)
            {
                if(vis[Find(i)]==false)
                {
                    vis[Find(i)]=true;
                    num++;
                }
            }
            if(num==1)
                ret=sum;
            return ret;
        }
    };

**4.平行课程**

已知有 `N` 门课程，它们以 `1` 到 `N` 进行编号。

给你一份课程关系表 `relations[i] = [X, Y]`，用以表示课程 `X` 和课程 `Y` 之间的先修关系：课程 `X` 必须在课程 `Y` 之前修完。

假设在一个学期里，你可以学习任何数量的课程，但前提是你已经学习了将要学习的这些课程的所有先修课程。

请你返回学完全部课程所需的最少学期数。

如果没有办法做到学完全部这些课程的话，就返回 `-1`。

**示例 1：**

**![aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE5LzA3LzI3LzEzMTZfZXgxLnBuZw][]**

输入：N = 3, relations = [[1,3],[2,3]]
    输出：2
    解释：
    在第一个学期学习课程 1 和 2，在第二个学期学习课程 3。

**示例 2：**

**![aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE5LzA3LzI3LzEzMTZfZXgyLnBuZw][]**

输入：N = 3, relations = [[1,2],[2,3],[3,1]]
    输出：-1
    解释：
    没有课程可以学习，因为它们相互依赖。

**提示：**

1.  `1 <= N <= 5000`
2.  `1 <= relations.length <= 5000`
3.  `relations[i][0] != relations[i][1]`
4.  输入中没有重复的关系

**思路：**

**DAG拓扑排序+数据结构上的dp。**

**这里采用邻接矩阵存储图，先初始化图和图中点的入度，先遍历所有的点找到入度为0的点，将其入队，并将其深度（所需学期数）初始化为1，然后就可以边出队边dp了。每出队一个点，就要将该点指向的点的入度都减1，并将减完之后入度为0的点入队，更新刚刚入队的点的深度dp\[i\]=max(dp\[now\]+1,dp\[i\])。还需要判断有没有修完全部的课程，可以通过统计入队的点的个数cnt是否等于N来判定，等于N则说明能修完所有的课程，返回dp数组中最大的数；否则返回-1。**

**此外，由于该题目设定的图的边比较稀疏，采用邻接表存储图效率会更高。**

**上AC代码：**

class Solution {
    public:
        int indegree[5001];
        int dp[5001];
        bool mp[5001][5001];
        int minimumSemesters(int N, vector<vector<int>>& relations) {
            int len=relations.size();
            memset(mp,0,sizeof(mp));
            memset(indegree,0,sizeof(indegree));
            memset(dp,0,sizeof(dp));
            int i;
            for(i=0;i<len;i++)
            {
                int a=relations[i][0];
                int b=relations[i][1];
                mp[a][b]=true;
                indegree[b]++;
            }
            queue<int> que;
            int cnt=0;
            for(i=1;i<=N;i++)
            {
                if(indegree[i]==0)
                {
                    cnt++;
                    que.push(i);
                    dp[i]=1;
                }
            }
            while(!que.empty())
            {
                int now=que.front();
                que.pop();
                for(i=1;i<=N;i++)
                {
                    if(mp[now][i]==true&&--indegree[i]==0)
                    {
                        cnt++;
                        que.push(i);
                        dp[i]=max(dp[now]+1,dp[i]);
                    }
                }
            }
            int ret=-1;
            if(cnt==N)
            {
                for(i=1;i<=N;i++)
                {
                    if(dp[i]>ret)
                    {
                        ret=dp[i];
                    }
                }
            }
            return ret;
        }
    };

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[https_leetcode-cn.com_contest_biweekly-contest-5]: https://leetcode-cn.com/contest/biweekly-contest-5
[aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE5LzA3LzI3LzEzMTRfZXgyLnBuZw]: /images/20211116/5af8ee13e788472982e027bb442fc2e8.png
[aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE5LzA3LzI3LzEzMTRfZXgxLnBuZw]: /images/20211116/a549f76ae7e545428913eba905b105ac.png
[aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE5LzA3LzI3LzEzMTZfZXgxLnBuZw]: /images/20211116/5b63bd62e10b4d8fb7f752c8e6d2b0c3.png
[aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE5LzA3LzI3LzEzMTZfZXgyLnBuZw]: /images/20211116/7a543dd1a9cc4d8cb02c10acdc86b25e.png
[20200227123106884.jpg]: /images/20211116/a89bf97c07d04ec3968aa199d2e6bea9.png