「微爱思扣 以 Code 会友」专场竞赛

比赛链接

A-下载插件

小扣打算给自己的 $VS code$ 安装使用插件，初始状态下带宽每分钟可以完成 $1 $个插件的下载。假定每分钟选择以下两种策略之一:

• 使用当前带宽下载插件；

• 将带宽加倍（下载插件数量随之加倍）。

请返回小扣完成下载 $n$ 个插件最少需要多少分钟。$(1\le n \le 10^5)$

注意：实际的下载的插件数量可以超过 $n$​ 个。

---

这个题我们可以这样想，如果$n$是$2$的次幂，即$n = 2^k$，则连续加倍$k$次，然后下载一次需要$k + 1$分钟。而如果我们仅连续加倍$k - 1$次，则需要下载两次，最后还是$k + 1$分钟。不过我们再减小，只连续加倍$k - 2$ 次，我们就需要下载$4$次了。由此我们可以看出，在$n = 2^k$的情况下，一直加倍直到可以一次下载完是最优的。

那么其他情况呢？显然对于任意一个数$n$，我们都可以找到一个合适的$ k \\in N$使得$n \\in [2^k,2^{k+1}]$，则根据红字，我们至少有了一种在$k + 2$分钟下载完$n$个插件的方案。那么还能更快么？ 答案是不能，道理也同上，减少加倍的次数，会使得下载次数增多的更多，故而无法使答案更优。

所以我们只需要把$n$转换为不小于自己的最小的$2^k$，则答案就是$k + 2$。

复杂度$O(log(n))$。

public class Solution 
{
    public int LeastMinutes(int n) 
    {
        int Ans = 0, val = 1;
        while(val < n)
        {
            val <<= 1;
            Ans++;
        }        
        return Ans + 1;
    }
}

B-完成一半题目

有 $N$ 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了$ 2\\times N$ 道题目，整型数组 $questions$ 中每个数字对应了每道题目所涉及的知识点类型。若每位扣友选择不同的一题，请返回被选的$ N$ 道题目至少包含多少种知识点类型。$(1\le N \le 5 \times 10^4)$

大体意思可以抽象为，给你一个有$2\times N$个正整数的数组，让你从中选$N$​个数，问至少会有多少不同的数。

---

做法也很简单，按照数的数目排个序，从最多的开始取即可(贪心嘛)。

inline int cmp(int x, int y){ return x > y; }

class Solution 
{
public:
    int halfQuestions(vector<int>& questions) 
    {
        int MaxN = 0;
        int n = questions.size();

        for (int i = 0; i < n; i++)
            MaxN = max(MaxN, questions[i]);

        int *vis = new int[MaxN + 1]; 
        memset(vis, 0, sizeof(int) * (MaxN + 1));
        for (int i = 0; i < n; i++)
            vis[questions[i]]++; 

        sort(vis + 1, vis + 1 + MaxN, cmp);
        
        int person = questions.size() >> 1;
        int Ans = 0;
        for (int i = 1; i <= MaxN; i++)
        {
            if (vis[i])
            {
                Ans++;
                while (vis[i])
                {
                    vis[i]--;
                    person--;
                    if (person == 0)
                        return Ans;
                }
            }
        }

        return Ans;
    }
};

C-主题空间

给你一个$n \times m$的矩阵，每个元素的值都是$0 \sim5$的整数。相邻且数字一样的格子我们认为是同一个主题空间。$0$表示走廊，矩阵外面认为全是走廊。现在要求不和走廊相邻的面积最大的主题空间。

例如上图为$4\times 11$的矩阵，其中不与走廊相邻的主题空间有5个，分别用不同的颜色标记在下图：

其大小分别为$3,1,1,1,2$​。故最大的为$3$​。$(1\le n,m\le 500)$​

---

对于这个数据范围，我们可以大胆的使用$BFS$搜索，枚举每一个不在边上且不是道路的格子，并向四周搜索。在搜索过程中记录当前扩展的面积为多大，并且判断相邻的格子是不是走廊。

不过有些需要考虑的点：

• 开一个二维数组$vis$记录每个格子有没有被访问过，从而防止重复访问同样的格子。

• 每次$BFS$的时候，将当前主题空间的所有格均在$vis$中标记为$1$，防止同一主题空间的格多次开启$BFS$。

public class Solution 
{
    private int row, col;
    private int[] dx = new int[]{0, 1, -1, 0, 0};
    private int[] dy = new int[]{0, 0, 0, 1, -1};
    private int[,] vis;

    private int Bfs(int x, int y, string[] grid)
    {
        Queue<int> qX = new Queue<int>();
        Queue<int> qY = new Queue<int>();
        qX.Enqueue(x);
        qY.Enqueue(y);
        vis[x, y] = 1;
        
        int tempVal = 0, flag = 0;
        while (qX.Count() != 0)
        {
            int nowX = qX.Dequeue(), nowY = qY.Dequeue();
            tempVal++;

            for (int i = 1; i <= 4; i++)
            {
                int nextX = nowX + dx[i], nextY = nowY + dy[i];
            	
                //超出范围
                if (nextX < 0 || nextX > row - 1 || nextY < 0 || nextY > col - 1)
                    continue;

                //标记一下这次bfs的主题空间是和走廊接壤的
                if (grid[nextX][nextY] == '0')
                {   
                    flag = 1;
                    continue;
                }
                
                if (grid[nextX][nextY] == grid[nowX][nowY])
                {
                    //同上，标记一下这个主题空间是和走廊接壤的
                    if (nextX == 0 || nextX == row - 1 || nextY == 0 || nextY == col - 1)
                        flag = 1;

                    if (vis[nextX, nextY] == 0)
                    {
                        qX.Enqueue(nextX);
                        qY.Enqueue(nextY);
                        vis[nextX, nextY] = 1;
                    }
                }
            }
        }

        return (flag == 1) ? 0 : tempVal;
    }

    public int LargestArea(string[] grid) 
    {
        row = grid.Length;
        col = grid[0].Length;

        vis = new int[row, col];

        int Ans = 0;
        for (int i = 1; i < row - 1; i++)
            for (int j = 1; j < col - 1; j++)
                if (vis[i, j] == 0 && grid[i][j] != '0')
                    Ans = Math.Max(Ans, Bfs(i, j, grid));

        return Ans;
    }
}