讨论/题目交流/🏆 第 178 场力扣周赛/
🏆 第 178 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 有多少小于当前数字的数字
4 分 - 通过投票对团队排名
5 分 - 二叉树中的列表
7 分 - 使网格图至少有一条有效路径的最小代价

展开讨论
共 21 个讨论

第一题
第一眼还以为要排序去重,第二眼发现数据量小,直接暴力

class Solution(object):
    def smallerNumbersThanCurrent(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = []
        
        for v in nums:
            cnt = 0
            for t in nums:
                if t<v:
                    cnt += 1
            ans.append(cnt)
        
        return ans

第二题
就是自定义cmp函数,统计每个字母每种名次的数量,从高到低依次比较,如果都相同,再比较字典序
python不会写sort的自定义cmp,所以就手写插入排序了

class Solution(object):
    def rankTeams(self, votes):
        """
        :type votes: List[str]
        :rtype: str
        """
        Dict = dict() # rank可能更加合适,记录各个rank的数量
        n = len(votes[0])
        
        for v in votes[0]:
            Dict[v] = [0] * n # 初始化cnt
        
        for v in votes:
            for i in range(n):
                Dict[v[i]][i] += 1 # 统计各个名次的数量
        
        Ans = ""
        
        # 插入排序,每次选当前rank最高的,v记录rank最高的,选完后加入Ans,然后把Dict里该元素去掉
        for i in range(n):
            v = 0
            for j in range(n):
                if self.compare(votes[0][v], votes[0][j], Dict):
                    v = j
            Dict[votes[0][v]] = [0] * n
            Ans = Ans + votes[0][v]
            
        return Ans
    # 自定义cmp函数,先比较rank,都一样则比较字典序
    def compare(self, a, b, Dict):
        n = len(Dict[a])
        for i in range(n):
            if Dict[a][i] < Dict[b][i]:
                return True
            if Dict[a][i] > Dict[b][i]:
                return False
        return a > b

第三题:
类似于字符串匹配题,昨天刚做的leetcode 139,140,如果139和140会做这道题应该就很简单了,区别在于这道题可以从任意位置开始匹配,所以先把树的所有结点取出来,但由于只需要向下匹配一次,所以相比较而言又更加容易一点。

class Solution(object):
    def isSubPath(self, head, root):
        """
        :type head: ListNode
        :type root: TreeNode
        :rtype: bool
        """
        
        tree = [root]
        x = 0
        
        # 取出所有树节点
        while x < len(tree):
            if tree[x].left != None:
                tree.append(tree[x].left)
            if tree[x].right != None:
                tree.append(tree[x].right)    
            x += 1
        
        # 等价于从所有树节点开始匹配,每次失配的丢掉,匹配的留下,如果没有可以匹配的,则返回false,否则循环结束返回true
        while head != None:
            new_tree = []
            for v in tree:
                if v != None and v.val == head.val:
                    new_tree.append(v.left)
                    new_tree.append(v.right)
            if len(new_tree) == 0:
                return False
            tree = new_tree
            head = head.next
            
        return True

第四题
题目写得很唬人,“有效路径”其实本质还是最短路,可以把箭头对应的路径当作“捷径”,类似于游戏中的“传送门”,如果按箭头走,则时间为0,反之,不按箭头走时间为1(修改箭头),为了简化代码,按箭头走也可以加一条时间为1的路径(可以不选择“传送门”),这样就不需要特判了,把图构造好然后就是spfa了。

class Solution(object):
    def minCost(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)
        m = len(grid[0])
        
        # 边
        edge = dict()
        
        for i in range(n*m):
            edge[i] = []
        
        # 四个方向
        direct = [[0,1], [0,-1], [1,0], [-1,0]]
        
        for i in range(n):
            for j in range(m):
                p = i*m+j
                d = direct[grid[i][j]-1]
                ni = i+d[0]
                nj = j+d[1]
                # 箭头边,边权为0
                if ni >= 0 and ni < n and nj >= 0 and nj < m:
                    q = ni*m+nj
                    edge[p].append([q, 0])
                # 非箭头边,边权为1,为了简便,箭头方向也加了一条,反正最短路会选箭头边,所以不影响
                for k in range(4):
                    d = direct[k]
                    ni = i+d[0]
                    nj = j+d[1]
                
                    if ni >= 0 and ni < n and nj >= 0 and nj < m:
                        q = ni*m+nj
                        edge[p].append([q, 1])
        
        # spfa模板
        dist = [n*m] * (n*m)
        dist[0] = 0
        vis = [0] * (n*m)
        q = [0]
        while len(q) > 0:
            x = q[0]
            q = q[1:]
            vis[x] = 0
            for y, d in edge[x]:
                if dist[x]+d < dist[y]:
                    dist[y] = dist[x]+d
                    if vis[y] == 0:
                        vis[y] = 1
                        q.append(y)
        
        return dist[n*m-1]

中间第二题提交的时候断网了几分钟,不然还能再进一名,气

21

来写一下 T4. 使网格图至少有一条有效路径的最小代价 的题解

很容易转化成一个最短路的模型,我们从 (0, 0) 点开始做最短路,到达每一个格子如果顺着箭头走代价为 0,反之代价为 1,计算到达 (n - 1, m - 1) 的最短路。每个格子只能修改一次的条件在最小代价的情况下一定天然符合,因为到达某个格子绕一圈回来再改它完全没有必要。

这道题目有一点特殊,因为他的边权为 0 / 1,可以使用 01BFS,在 O(nm+4nm)O(n * m + 4 * n * m) 的复杂度内求解,即 O(点数+边数)O(点数 + 边数)
通常的 BFS 边权均为 1,每次我们从队首取出一个节点的时候,一定能保证他是当前未向外扩展且 dist 值最小的节点,我们用它继续扩展新的节点并加入队尾,依旧能保证这个性质,这才成了宽度优先遍历。

但是如果出现了边权为 0 的情况,按照 BFS 处理就不行了,因为从边权为 0 的边扩展出去的新节点加入队列位尾部后,不能保证未来从队首取用节点一定是当前未向外扩展且 dist 值最小的节点
考虑当前队首节点 dist 值位 x,那么队列中的节点的元素 dist 值可能是这样的:

x,x,,x,x+1,,x+1x, x, \cdots, x, x+1, \cdots, x+1

考虑取队首节点开始扩展新的节点,那么新的节点的 dist 值位 xxx+1x+1,直接加入队尾将导致问题:

x,x,,x,x+1,,x+1x,x+1x, x, \cdots, x, x+1, \cdots, x+1 \leftarrow x, x+1

解决方法就是维护一个双端队列,如果从边权为 0 的边扩展的新的点从队首加入,从边权为 1 的点扩展的新点从队尾加入,这样就会变成这个样子:

xx,x,,x,x+1,,x+1x+1x \rightarrow x, x, \cdots, x, x+1, \cdots, x+1 \leftarrow x+1

那么,我们就可以继续放心取用队首元素做 BFS 了。

代码大致长这个样子:

const int MAXN = 150;
int dist[MAXN][MAXN];
bool inQue[MAXN][MAXN];
deque<pair<int, int> > que;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        
        memset(dist, -1, sizeof(dist));
        memset(inQue, false, sizeof(inQue));
        while(!que.empty()) que.pop_back();
        dist[0][0] = 0; que.push_back(make_pair(0, 0));
        
        while(!que.empty()){
            pair<int, int> cur = que.front(); que.pop_front();
            int x = cur.first, y = cur.second;
            
            if (inQue[x][y]) continue;
            inQue[x][y] = true;
            
            for (int k = 0; k < 4; k++){
                int tx = x + dx[k], ty = y + dy[k], cost = dist[x][y] + (grid[x][y] - 1 == k ? 0 : 1);
                if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
                if (dist[tx][ty] == -1 || dist[tx][ty] > cost){
                    dist[tx][ty] = cost;
                    if (dist[x][y] == dist[tx][ty]){
                        que.push_front(make_pair(tx, ty));
                    }else que.push_back(make_pair(tx, ty));
                }
            }
        }
        
        return dist[n - 1][m - 1];
    }
};

最后说一下吧,假设本题的点数为 nn,边数为 mm,那么时间复杂度为 O(n+m)O(n + m),也就是说数据范围可以再大一些,比如让点数等于 1e6。
这道题目本质是个最短路,用最短路算法也是没有问题的,用堆优化的 Dijkstra 复杂度为 O(nlogn)O(n log n) ,通过是合理的。但是 SPFA 嘛……如果想让 T4 更加完善一点,可以修改一下数据范围的限制方式,从限制网格图长宽,变为限制图中总格子数,然后卡一下 SPFA 和没有优化的 Dijkstra。

10

只会一题

4

这次因为回来晚了就没打。

看了一下题, 主要难点在T4.

这个题首先看上去想dp, 但是因为它不是最短路线, 因此状态不好设计。 存疑。

感觉可以转化成一个图论模型。

  1. 每个点和相邻的点连边。 如果是原来的方向, 边权为0, 否则为1;
  2. 以左上角为起点, 右下角为终点求最短路。

这个图至多会有1万个点, 接近4万条边, 需要注意效率。 Dijkstra最短路算法应该可以。 不过需要注意是否需要优化。 毕竟感觉刚好卡在是不是T的那个点上。

3

妈耶,大神真多,压哨交题。
说下对T4的思路,主要是BFS + DFS。
以样例一举例:grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]],图可以自己看题。
基本思路:
1、每个格子有方向,就代表着,跟着格子路径走所到达的一系列格子的损耗都为0。也就是说该路径上所有格子最小代价都为f. (用DFS做)
2、与该路径相邻的未访问过的格子,其有效路径为f+1. (BFS思想,其一定为最优解)
3、将2所述所有相邻格子入队
4、对队列中每个节点进行1、2、3步操作,直到队列为空. (BFS框架)。

上面第三步比较难处理,即获取路径上所有相邻节点。
我的想法是:用dfs每走到一个格子把它上下左右所有格子都入队。
在出队的时候判断该格子是否访问即可。

ac源代码:

struct node{
    node(int xx,int yy,int ff){
        x =xx;
        y=yy;  
        f=ff;  // 有效路径
    }
  int x,y,f;  
};
class Solution {
public:
    queue<node> que;
    vector<vector<int>> vis;
    int m,n;

    void biao(int x,int y, int f){  // 标记路径相邻格子
        if(x<0|| x >= m)return;
        if(y<0|| y >= n)return;
        que.push( node(x,y,f) );
        return;
    }

    void dfs(int x, int y, vector<vector<int>>& grid, int f){
        // 回溯条件
        if(x<0|| x >= m)return;
        if(y<0|| y >= n)return;
        if(vis[x][y] != -1)return;

        // 访问标记
        vis[x][y] = f;

        // 将上下左右都入队
        biao(x,y+1,f+1);
        biao(x,y-1,f+1);
        biao(x+1,y,f+1);
        biao(x-1,y,f+1);

        if(grid[x][y]==1)dfs(x, y+1, grid,f);
        else if(grid[x][y]==2)dfs(x, y-1, grid,f);
        else if(grid[x][y]==3)dfs(x+1, y, grid,f);
        else if(grid[x][y]==4)dfs(x-1, y, grid,f);    
    }  

    int minCost(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        vis.resize(m);
        for(int i=0;i<m;i++){
            vis[i].resize(n);
            for(int j=0;j<n;j++)vis[i][j]=-1;
        }
        
        que.push(node(0,0,0));
        
       while(!que.empty()){
            node temp = que.front();
            que.pop();
            int x = temp.x;
            int y = temp.y;
            int f = temp.f;
            if(vis[x][y]!=-1)continue;
            dfs(x,y,grid,f);
        }
        return vis[m-1][n-1];
    }
};
2

有多少小于当前数字的数字

思路

  1. 统计个数
  2. 用小于当前数字的个数替换统计个数
  3. 转成答案格式

答题

vector<int> smallerNumbersThanCurrent(vector<int>& nums) 
{
    map<int, int> count;
    for (auto& n : nums)
    {
        count[n]++;
    }
    int t = 0;
    for (auto& p : count)
    {
        swap(t, p.second);
        t += p.second;
    }
    for (auto& n : nums)
    {
        n = count[n];
    }
    return nums;
}

通过投票对团队排名

思路

  1. 阅读理解错误,通过 WA WA 用例审题,耗时 75 分
  2. 此处跳过

二叉树中的列表

思路

  1. 使用 bfs 找到起点
  2. 使用 dfs 匹配

答题

bool dfs(ListNode* head, TreeNode* root)
{
    if (head == nullptr) return true;
    if (root == nullptr) return false;
    if (root->val != head->val) return false;
    return dfs(head->next, root->left) || dfs(head->next, root->right);
}

bool isSubPath(ListNode* head, TreeNode* root) 
{
    queue<TreeNode*> que;
    que.push(root);

    while (!que.empty())
    {
        auto q = que.front();
        que.pop();
        if (q == nullptr) continue;

        if (q->val == head->val)
        {
            if (dfs(head, q)) return true;
        }
        que.push(q->left);
        que.push(q->right);
    }
    return false;
}

使网格图至少有一条有效路径的最小代价

思路

  1. 使用 bfs ,找到最短路径
  2. 有箭头的方向相当于步数 +0
  3. 其他方向相当于步数 +1
  4. 将 +0 的格子加入到本次队列
  5. 将 +1 的格子加入到下次队列

答题

int minCost(vector<vector<int>>& grid)
{
    vector<vector<int>> dd = { {}, {0, 1}, {0, -1}, {1, 0}, {-1, 0} };  // 方向数组
    vector<vector<int>> vi(grid.size(), vector<int>(grid[0].size(), INT_MAX));  // 使用步数作为 visited 标准
    queue<vector<int>> cq;  // 本次队列 curr queue
    queue<vector<int>> nq;  // 下次队列 next queue
    int ans = 0;
    cq.push({ 0, 0 });
    vi[0][0] = 0;

    while (!cq.empty() || !nq.empty())
    {
        while (!cq.empty())
        {
            auto q = cq.front();
            cq.pop();
            int x = q[0];
            int y = q[1];
            if (vi[x][y] < ans) continue;
            if (x == grid.size() - 1 && y == grid[0].size() - 1) return ans;

            for (int i = 1; i < dd.size(); i++)
            {
                int dx = x + dd[i][0];
                int dy = y + dd[i][1];
                if ((dx < 0 || dx >= grid.size()) || (dy < 0 || dy >= grid[0].size())) continue;
                if (vi[dx][dy] <= ans) continue;

                // 将箭头所指格子加入当前队列,其他加入下次队列
                auto& sq = (i == grid[x][y]) ? cq : nq;
                sq.push({ dx, dy });
                vi[dx][dy] = (i == grid[x][y]) ? ans : ans + 1;
            }
        }
        swap(cq, nq);
        ans++;
    }
    return ans;
}

致谢

上周卡 T1 ,这周卡 T2 ,求进步!

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

我的leetcode

2

只剩下最后一道。。。。but没有思路。。。。

1

第四题不知道按什么顺序dp,从左到右,从右到左,从上到下,从下到上,循环十遍竟然过了。。。

2

大家好,我的博客是: http://erik-chen.github.io/,欢迎交流!

第一题. 有多少小于当前数字的数字

思路

维护一个字典,用来储存每个num和它的排序(注意并列的情况)

代码

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        nums2 = sorted(nums)    # 对nums排序
        mapping = {}            # mapping储存num和其序号的键值对
        for i, num in enumerate(nums2):         # 遍历排序后的数组
            if i > 0 and nums2[i] == nums2[i-1]:# 如果某一位跟前一位的值相等,那么它的序号跟前一位一样(并列)
                mapping[nums2[i]] = mapping[nums2[i-1]]
            else:                               # 如果某一位跟前一位的值不等,那么以index为序号
                mapping[nums2[i]] = i
        res = []
        for num in nums:
            res.append(mapping[num])            # res用来储存返回值
        return res

第二题. 通过投票对团队排名

解题思路

其实就是对votes[0]里的每一个字母进行排序,关键是排序的依据是什么?Python有现成的sort函数,那么参数key是什么呢?

  1. 比较字母A比字母B在所有str的第1位,哪个出现次数多
  2. 如果字母A和字母B在所有str的前k位出现次数都一样多,那么比较第k+1位,哪个出现次数多
  3. 如果都一样多,就以字典序排序

所以怎么利用以上的规则,把key表示出来呢?
这里采取了把出现字数压缩成chr值的办法,然后依据字典序的方法来排序

  1. 如果字母A在所有str的第1位出现5次,B出现4次,那么我们把A标记为chr(1000-5)B标记为chr(1000-4)。因为chr(1000-5) < chr(1000-4),所以A排在B的前面
  2. 如果字母AB在前k位都是一样的,那么前面k个chr值都一样。如果第k+1位,AB多,那么依照上面的法则,A排在B的前面。
  3. 如果都一样,我们就在chr值后面加上字母本身,因为A<B,所以A排在B的前面

代码

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        mapping = {}                                        # mapping储存key值
        for word in votes:
            for i, letter in enumerate(word):
                if letter not in mapping:
                    mapping[letter] = [1000] * len(word)    # 初始化key值
                mapping[letter][i] -= 1                     # 如果A在第i位多出现一次,就在第i位的chr值-=1,提高其比较的优先级
        for letter in mapping:
            mapping[letter] = ''.join((chr(x) for x in mapping[letter])) + letter   # 为了利用字典序,须转换为字符串
        return ''.join(sorted(votes[0], key=lambda x: mapping[x]))                  # 进行排序

第三题. 二叉树中的列表

解题思路

  1. 外层递归解决链表的头和tree的某个node匹配的问题
  2. 内层递归解决链表的每个node和tree的每层node匹配的问题

代码

class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if root:
            if head.val == root.val:
                if self.f(head, root):
                    return True
            return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
        return False
    
    def f(self, node, root):
        if not node.next:
            return True
        if root.left and root.left.val == node.next.val and self.f(node.next, root.left):
            return True
        if root.right and root.right.val == node.next.val and self.f(node.next, root.right):
            return True
        return False

第四题. 使网格图至少有一条有效路径的最小代价

解题思路

  1. 因为需要计算改变数,因此想到BFS
  2. queue储存所有当前这步可以search到的地方
  3. visited储存所有历史上search过的地方
  4. new_queue储存当前的基础上,改变一个箭头,可以search到的地方
  5. 用new_queue代替queue,同时用count记数,进行BFS
  6. 当search到右下角,返回count

代码

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0
        queue = [(0, 0)]
        visited = {(0, 0)}
        while True:
            for i, j in queue:
                if grid[i][j] == 1:
                    if j+1 < n and (i,j+1) not in visited:
                        queue.append((i,j+1))
                        visited.add((i,j+1))
                elif grid[i][j] == 2:
                    if j-1 >=0 and (i,j-1) not in visited:
                        queue.append((i,j-1))
                        visited.add((i,j-1))
                elif grid[i][j] == 3:
                    if i+1 < m and (i+1,j) not in visited:
                        queue.append((i+1,j))
                        visited.add((i+1,j))
                else:
                    if i-1 >=0 and (i-1,j) not in visited:
                        queue.append((i-1,j))
                        visited.add((i-1,j))
            if (m-1, n-1) in visited:
                return count
            count += 1
            new_queue = []
            for i,j in queue:
                for p, q in zip((i-1,i+1,i,i),(j,j,j-1,j+1)):
                    if (p, q) not in visited and 0<=p<m and 0<=q<n:
                        new_queue.append((p,q))
                        visited.add((p,q))
            queue = new_queue
1