LeetCode第178场周赛

BFS不熟悉。。排名 291 / 3304

Contents

1 第一题：有多少小于当前数字的数字
2 第二题：通过投票对团队排名
3 第三题：二叉树中的列表
4 第四题：使网格图至少有一条有效路径的最小代价

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

　　给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
　　
　　换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
　　
　　以数组形式返回答案。
　　
　　示例 1：
　　输入：nums = [8,1,2,2,3]
　　输出：[4,0,1,1,3]
　　解释：
　　对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
　　对于 nums[1]=1 不存在比它小的数字。
　　对于 nums[2]=2 存在一个比它小的数字：（1）。
　　对于 nums[3]=2 存在一个比它小的数字：（1）。
　　对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。
　　
　　示例 2：
　　输入：nums = [6,5,4,8]
　　输出：[2,1,0,3]
　　
　　示例 3：
　　输入：nums = [7,7,7,7]
　　输出：[0,0,0,0]

思路：
　　因为相同的数字对应的比它小的数字是一样多的，因此用一个dict来记录。为了节省时间，将nums排序后遍历一次即可。时间复杂度为排序的复杂度O(nlogn)。

代码：

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        if len(nums) == 0:
            return []
        sort = sorted(nums)
        ans = {sort[0]: 0}
        c = 0
        for i in range(1, len(sort)):
            c += 1
            if sort[i] == sort[i-1]:
                pass
            elif sort[i] > sort[i-1]:
                ans[sort[i]] = c

        return [ans[i] for i in nums]

class Solution:

def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:

if len(nums) == 0:

return []

sort = sorted(nums)

ans = {sort[0]: 0}

c = 0

for i in range(1, len(sort)):

c += 1

if sort[i] == sort[i-1]:

pass

elif sort[i] > sort[i-1]:

ans[sort[i]] = c

return [ans[i] for i in nums]

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

　　现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。
　　
　　排名规则如下：
　　
　　参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
　　如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。
　　给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。
　　
　　请你返回能表示按排名系统排序后的所有团队排名的字符串。
　　
　　示例 1：
　　输入：votes = [“ABC”,”ACB”,”ABC”,”ACB”,”ACB”]
　　输出：”ACB”
　　解释：A 队获得五票「排位第一」，没有其他队获得「排位第一」，所以 A 队排名第一。
　　B 队获得两票「排位第二」，三票「排位第三」。
　　C 队获得三票「排位第二」，两票「排位第三」。
　　由于 C 队「排位第二」的票数较多，所以 C 队排第二，B 队排第三。
　　
　　示例 2：
　　输入：votes = [“WXYZ”,”XYZW”]
　　输出：”XWYZ”
　　解释：X 队在并列僵局打破后成为排名第一的团队。X 队和 W 队的「排位第一」票数一样，但是 X 队有一票「排位第二」，而 W 没有获得「排位第二」。
　　
　　示例 3：
　　输入：votes = [“ZMNAGUEDSJYLBOPHRQICWFXTVK”]
　　输出：”ZMNAGUEDSJYLBOPHRQICWFXTVK”
　　解释：只有一个投票者，所以排名完全按照他的意愿。
　　
　　示例 4：
　　输入：votes = [“BCA”,”CAB”,”CBA”,”ABC”,”ACB”,”BAC”]
　　输出：”ABC”
　　解释：
　　A 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
　　B 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
　　C 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
　　完全并列，所以我们需要按照字母升序排名。
　　
　　示例 5：
　　输入：votes = [“M”,”M”,”M”,”M”]
　　输出：”M”
　　解释：只有 M 队参赛，所以它排名第一。

思路：
　　这题就是对n+1个关键字依次进行sort，python中正好支持这样的特性。先统计每个队伍第1、第2、第3、。。。第n的票数，分别作为第1、第2、。。。第n关键词降序排序。由于票数都相同时按字母序排，因此把字母ascii码的相反数作为第n+1个关键词(为了统一成降序排列，ascii码大的要排在后面)。

　　如votes = ["WXYZ","XYZW"]，票数votes_dict = {'W':[1, 0, 0, 1], 'X':[1, 1, 0, 0], 'Y':[0, 1, 1, 0], 'Z': [0, 0, 1, 1]}。

代码：

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        allletters = set()  # 所有出现字母的集合
        l = len(votes[0])
        ranks = []
        for place in range(l):
            votes_dict = {}
            for vote in votes:
                who = vote[place]
                allletters.add(who)
                if who not in votes_dict:
                    votes_dict[who] = 1  # 统计次数
                else:
                    votes_dict[who] += 1
            ranks.append(votes_dict)

        ans = []
        for c in allletters:
            ans.append([])
            for i in range(len(ranks)):
                rank = ranks[i]
                if c in rank:
                    ans[-1].append(rank[c])
                else:
                    ans[-1].append(0)
            ans[-1].append(90-ord(c))  # 加入ascii码的相反数
            ans[-1].append(c)

        ans = sorted(ans, key=lambda kv: [kv[i] for i in range(l+1)], reverse=True)
        ans = [i[-1] for i in ans]
        r = ''
        for i in ans:
            r += i
        return r

class Solution:

def rankTeams(self, votes: List[str]) -> str:

allletters = set() # 所有出现字母的集合

l = len(votes[0])

ranks = []

for place in range(l):

votes_dict = {}

for vote in votes:

who = vote[place]

allletters.add(who)

if who not in votes_dict:

votes_dict[who] = 1 # 统计次数

else:

votes_dict[who] += 1

ranks.append(votes_dict)

ans = []

for c in allletters:

ans.append([])

for i in range(len(ranks)):

rank = ranks[i]

if c in rank:

ans[-1].append(rank[c])

else:

ans[-1].append(0)

ans[-1].append(90-ord(c)) # 加入ascii码的相反数

ans[-1].append(c)

ans = sorted(ans, key=lambda kv: [kv[i] for i in range(l+1)], reverse=True)

ans = [i[-1] for i in ans]

r = ''

for i in ans:

r += i

return r

第三题：二叉树中的列表

　　给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
　　
　　如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
　　
　　一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
　　
　　示例 1：
　　
　　输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
　　输出：true
　　解释：树中蓝色的节点构成了与链表对应的子路径。
　　
　　示例 2：
　　
　　
　　输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
　　输出：true
　　
　　示例 3：
　　输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
　　输出：false
　　解释：二叉树中不存在一一对应链表的路径。

思路：
　　先遍历一遍二叉树找出所有和链表第一个节点相同的节点。然后再从每个节点开始遍历一次，如果能将链表匹配完毕，则返回true。

代码：

class Solution {
public:
    vector<TreeNode*> roots;
    void dfs(TreeNode* root, int n){  // 先遍历一遍二叉树，找出和链表头节点相同的节点 
        if (!root) return;
        if (root->val == n) roots.push_back(root);
        if (root->left){
            dfs(root->left, n);
        }
        if (root->right){
            dfs(root->right, n);
        }    
    }
    bool dfs2(ListNode* head, TreeNode* root){  // 从每个节点开始遍历匹配

        if (!head) return true;  // 链表已匹配完毕，返回true
        if (!root) return false;
        // cout<< root->val;
        if (head->val != root->val) return false;
        if (root->left){
            if (dfs2(head->next, root->left)) return true;
        }
        if (root->right){
            if (dfs2(head->next, root->right)) return true;
        }    
        if (!head->next) return true;
        return false;

    }
    bool isSubPath(ListNode* head, TreeNode* root) {
        if (!head || !root)
            return false;
        dfs(root, head->val);
        for (int i = 0;i <roots.size();i++){
            if (dfs2(head, roots[i])) return true;  // 从每个节点开始遍历一次
        }

        return false;
    }
};

class Solution {

public:

vector<TreeNode*> roots;

void dfs(TreeNode* root, int n){ // 先遍历一遍二叉树，找出和链表头节点相同的节点

if (!root) return;

if (root->val == n) roots.push_back(root);

if (root->left){

dfs(root->left, n);

}

if (root->right){

dfs(root->right, n);

}

bool dfs2(ListNode* head, TreeNode* root){ // 从每个节点开始遍历匹配

if (!head) return true; // 链表已匹配完毕，返回true

if (!root) return false;

// cout<< root->val;

if (head->val != root->val) return false;

if (root->left){

if (dfs2(head->next, root->left)) return true;

}

if (root->right){

if (dfs2(head->next, root->right)) return true;

}

if (!head->next) return true;

return false;

}

bool isSubPath(ListNode* head, TreeNode* root) {

if (!head || !root)

return false;

dfs(root, head->val);

for (int i = 0;i <roots.size();i++){

if (dfs2(head, roots[i])) return true; // 从每个节点开始遍历一次

}

return false;

}

};

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

　　给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
　　
　　1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
　　2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
　　3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
　　4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]
　　注意网格图中可能会有无效数字，因为它们可能指向 grid 以外的区域。
　　
　　一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条有效路径为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径不需要是最短路径。
　　
　　你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字只能修改一次。
　　
　　请你返回让网格图至少有一条有效路径的最小代价。
　　
　　示例 1：
　　
　　输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
　　输出：3
　　解释：你将从点 (0, 0) 出发。
　　到达 (3, 3) 的路径为： (0, 0) –> (0, 1) –> (0, 2) –> (0, 3) 花费代价 cost = 1 使方向向下 –> (1, 3) –> (1, 2) –> (1, 1) –> (1, 0) 花费代价 cost = 1 使方向向下 –> (2, 0) –> (2, 1) –> (2, 2) –> (2, 3) 花费代价 cost = 1 使方向向下 –> (3, 3)
　　总花费为 cost = 3.
　　
　　示例 2：
　　
　　
　　输入：grid = [[1,1,3],[3,2,2],[1,1,4]]
　　输出：0
　　解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。
　　
　　示例 3：
　　
　　
　　输入：grid = [[1,2],[4,3]]
　　输出：1
　　
　　示例 4：
　　输入：grid = [[2,2,2],[2,2,2]]
　　输出：3
　　
　　示例 5：
　　输入：grid = [[4]]
　　输出：0
　　

思路：
　　BFS，这题也可以用Dijkstra或者SPFA。
　　思路为维护一个队列，能按箭头走到的位置代价为0，越过箭头走不到的位置代价为1。队列初始为(0, 0)，初始步数count = 0，先将队列中的所有位置按箭头走一次，然后步数count += 1，搜索所有count - 1步时能走到位置的周围未访问过的位置，并将它置为新的队列。集合visited记录已经访问过的位置，搜索到(m - 1, n - 1)时候退出。

代码：

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
        m, n = len(grid), len(grid[0])
        count = 0
        q = [(0, 0)]
        visited = {(0, 0)}

        def can_go(x, y):
            if x < 0 or y < 0 or x >= m or y >= n:
                return False
            return (x, y) not in visited

        while True:
            for i, j in q:
                for di, d in enumerate(directions):
                    if grid[i][j] == di + 1:  # 箭头的方向
                        x = i + d[0]
                        y = j + d[1]
                        if can_go(x, y):
                            q.append((x, y))
                            print(x, y)
                            visited.add((x, y))

            if (m - 1, n - 1) in visited:
                return count

            count += 1

            new_q = []
            for i, j in q:
                for di, d in enumerate(directions):
                    x = i + d[0]
                    y = j + d[1]
                    if (x, y) not in visited and can_go(x, y):
                        new_q.append((x, y))
                        visited.add((x, y))

            del q
            q = new_q

class Solution:

def minCost(self, grid: List[List[int]]) -> int:

directions = ((0, 1), (0, -1), (1, 0), (-1, 0))

m, n = len(grid), len(grid[0])

count = 0

q = [(0, 0)]

visited = {(0, 0)}

def can_go(x, y):

if x < 0 or y < 0 or x >= m or y >= n:

return False

return (x, y) not in visited

while True:

for i, j in q:

for di, d in enumerate(directions):

if grid[i][j] == di + 1: # 箭头的方向

x = i + d[0]

y = j + d[1]

if can_go(x, y):

q.append((x, y))

print(x, y)

visited.add((x, y))

if (m - 1, n - 1) in visited:

return count

count += 1

new_q = []

for i, j in q:

for di, d in enumerate(directions):

x = i + d[0]

y = j + d[1]

if (x, y) not in visited and can_go(x, y):

new_q.append((x, y))

visited.add((x, y))

del q

q = new_q