2022-01-25每日刷题打卡

力扣——每日一题

1688. 比赛中的配对次数

给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：

如果当前队伍数是 偶数 ，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
如果当前队伍数为 奇数 ，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
返回在比赛中进行的配对次数，直到决出获胜队伍为止。

示例 1：

输入：n = 7
输出：6
解释：比赛详情：

• 第 1 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。
• 第 2 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
• 第 3 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
  总配对次数 = 3 + 2 + 1 = 6

这题说人话就是，每次配对操作后，计数器加上n/2的值，只不过如果n是偶数的话就把n对半分就好，如果是奇数，则对半分后还要加一。直到n==1时结束配对。

class Solution {
public:
    int numberOfMatches(int n) {
        int ans=0;
        while(n!=1)
        {
            if(n%2==0)
            {
                ans+=n/2;
                n/=2;
            }
            else
            {
                ans+=n/2;
                n/=2;
                n++;
            }
        }
        return ans;
    }
};

542. 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

广度搜索，这题大致就是，让我们创建一个和他给的矩阵大小一样的矩阵，（这里给的3*3，我们创建的也是3 *3），我们创建的矩阵中的值，是原矩阵中到达数字0所需步数，比如题目给的，除了最后一排中间的，其它都是一步到0，所以，其它1对应矩阵都是1，除了最后一排中间那个是2。标准的走迷宫问题，准备一个大小一样的矩阵，所有元素都初始化为0，然后遍历原矩阵，当遍历到的元素为1时，以那个点为起点进行广度搜索，计算这个点到距离最近的0要几步。

但，测试样例过了，提交却说超时了。

class Solution {
public:
    typedef pair<int,int>PII;
    int n,m;
    PII que[10005];
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        n=mat.size(),m=mat[0].size();
        vector<vector<int>>v(n,vector<int>(m,0));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(mat[i][j]==1)
                {
                    bfs(i,j,mat,v);
                }
        return v;
    }
    void bfs(int x,int y,vector<vector<int>>& mat,vector<vector<int>>& v)
    {
        vector<vector<int>>ans(n,vector<int>(m,0));
        que[0]={x,y};
        ans[x][y]=1;
        int hh=0,tt=0;
        while(hh<=tt)
        {
            auto t=que[hh++];
            for(int i=0;i<4;i++)
            {
                int a=t.first+dx[i],b=t.second+dy[i];
                if(a>=0&&a<n&&b>=0&&b<m&&ans[a][b]==0)
                {
                    ans[a][b]=ans[t.first][t.second]+1;
                    if(mat[a][b]==0)
                    {
                        v[x][y]=ans[a][b]-1;
                        return;
                    }
                    que[++tt]={a,b};
                }
            }
        }
    }
};

后来想，我这种写法每有一个1就要来一遍广度搜索，实在太慢因为一次只能给一个格子赋值。

优化一下，我们不以1为起点，而是一开始就记录下所有0的坐标，以那些坐标开始广搜，这样不是0的格子就都会赋值了。

class Solution {
public:
    typedef pair<int,int>PII;
    int n,m;
    PII que[10005];
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        n=mat.size(),m=mat[0].size();
        int hh=0,tt=0;
        vector<vector<int>>v(n,vector<int>(m,-1));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(mat[i][j]==0)
                {
                    v[i][j]=0;
                    que[tt++]={i,j};
                }
        while(hh<=tt)
        {
            auto t=que[hh++];
            for(int i=0;i<4;i++)
            {
                int a=t.first+dx[i],b=t.second+dy[i];
                if(a>=0&&a<n&&b>=0&&b<m&&v[a][b]==-1)
                {
                    v[a][b]=v[t.first][t.second]+1;
                    que[tt++]={a,b};
                }
            }
        }
        return v;
    }
};

623. 在二叉树中增加一行

给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。

添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。

将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。

如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。

示例 1:

输入:
二叉树如下所示:
4
/
2 6
/ \ /
3 1 5

v = 1

d = 2

输出:
4
/
1 1
/
2 6
/ \ /
3 1 5

深度搜索，记录每次到达的层数，当层数等于深度值d时，用题目给的val值创建两个节点，接到当前节点的左节点和右节点，并将原本的左节点右节点成为新左节点的左节点和新右节点的右节点。

/**
 * 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* addOneRow(TreeNode* root, int val, int depth) {
        if(depth==1)
        {
            TreeNode* p=new TreeNode(val);
            p->left=root;
            return p;
        }
        dfs(root,val,depth,1);
        return root;
    }
    void dfs(TreeNode*& root, int val, int depth,int u)
    {
        if(!root)return ;
        if(u==depth-1)
        {
            TreeNode *p=new TreeNode(val);
            TreeNode *q=new TreeNode(val);
            TreeNode *l=root->left,*r=root->right;
            root->left=p;
            p->left=l;
            root->right=q;
            q->right=r;
        }
        else
        {
            dfs(root->left,val,depth,u+1);
            dfs(root->right,val,depth,u+1);
        }
    }
};

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

遍历矩阵，当遍历到的点为1时，以那个为起点广度搜索，每走过一个点，计数器ans++，并且把走过的点都改为0。在多次广度搜索中维护最大值，最后返回最大值。

class Solution {
public:
    typedef pair<int,int>PII;
    PII que[10000];
    int n,m;
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max_ans=0;
        n=grid.size(),m=grid[0].size();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(grid[i][j]==1)
                {
                    max_ans=max(max_ans,bfs(i,j,grid));
                }
        return max_ans;
    }
    int bfs(int x,int y,vector<vector<int>>& grid)
    {
        int ans=1;
        que[0]={x,y};
        grid[x][y]=0;
        int hh=0,tt=0;
        while(hh<=tt)
        {
            auto t=que[hh++];
            for(int i=0;i<4;i++)
            {
                int a=t.first+dx[i],b=t.second+dy[i];
                if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==1)
                {
                    ans++;
                    que[++tt]={a,b};
                    grid[a][b]=0;
                }
            }
        }
        return ans;
    }
};

733. 图像渲染

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例 1:

输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析:
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

记录它所给坐标位置上的颜色，然后把那个位置染成newColor，以那个点为起点开始广度搜索，把所有和它联通的，并且颜色等于初始颜色的点都染成newColor，要注意的一点是，我们要额外准备一个数组，记录我们走过的位置，不然如果初始颜色和newColor一样的话，会使得我们一直在一个地点内转圈，所以我们要记录走过的地方，当我们广度搜索时，如果下一个地块已经走过了就不走了。

class Solution {
public:
    typedef pair<int,int>PII;
    PII que[10000];
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor)
    {
        int n=image.size(),m=image[0].size();
        int tt=0,hh=0,color=image[sr][sc];
        que[0]={sr,sc};
        image[sr][sc]=newColor;
        vector<vector<int>>v(n,vector<int>(m,0));
        v[sr][sc]=1;
        while(hh<=tt)
        {
            auto t=que[hh++];
            for(int i=0;i<4;i++)
            {
                int a=t.first+dx[i],b=dy[i]+t.second;
                if(a>=0&&a<n&&b>=0&&b<m&&image[a][b]==color&&v[a][b]==0)
                {
                    image[a][b]=newColor;
                    v[a][b]=1;
                    que[++tt]={a,b};
                }
            }
        }
        return image;
    }
};

690. 员工的重要性

给定一个保存员工信息的数据结构，它包含了员工 唯一的 id ，重要度 和 直系下属的 id 。

比如，员工 1 是员工 2 的领导，员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工 1 的数据结构是 [1, 15, [2]] ，员工 2的 数据结构是 [2, 10, [3]] ，员工 3 的数据结构是 [3, 5, []] 。注意虽然员工 3 也是员工 1 的一个下属，但是由于 并不是直系 下属，因此没有体现在员工 1 的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。

示例：

输入：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出：11
解释：
员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。

提示：

一个员工最多有一个 直系 领导，但是可以有多个 直系 下属
员工数量不超过 2000 。

准备一个哈希表，以员工的id为key，员工的整个信息为val创建哈希表，首先遍历员工数组，把员工的信息存入哈希表中，然后准备一个计数器ans=0，计算员工的重要度。以题目给的员工id为起点开始广度遍历，每次遍历员工的下属数组（结构体中的subordinates），然后根据数组中的员工id，继续遍历那个员工的下属数组，直到所有的下属数组都遍历完为止。同时，每遍历一个员工，就把这个员工的重要度加到ans上。广度搜索结束后返回ans即可。

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    unordered_map<int,Employee*>mymap;
    int ans=0;
    int getImportance(vector<Employee*> employees, int id) {
        int n=employees.size();
        for(int i=0;i<n;i++)
        {
            mymap[employees[i]->id]=employees[i];
        }
        ans+=mymap[id]->importance;
        vector<vector<int>>v;
        v.push_back(mymap[id]->subordinates);
        int hh=0;
        while(hh<v.size())
        {
            for(int i=0;i<v[hh].size();i++)
            {
                ans+=mymap[v[hh][i]]->importance;
                v.push_back(mymap[v[hh][i]]->subordinates);
            }
            hh++;
        }
        return ans;
    }
};