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

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

image.png

3 分 - 访问所有点的最小时间
4 分 - 统计参与通信的服务器
4 分 - 搜索推荐系统
6 分 - 停在原地的方案数

展开讨论
力扣 (LeetCode)发起于 2019-11-24

先占坑,贴一下 code 好了:
访问所有点的最小时间

两点之间最优方案是固定的,计算横纵坐标差的最大值,就是需要的步数,剩下的贪心就可以了时间复杂度 O(n)O(n)

    class Solution(object):
        def minTimeToVisitAllPoints(self, points):
            """
            :type points: List[List[int]]
            :rtype: int
            """
            def get_ans(X1,X2):
                x1,y1 = X1
                x2,y2 = X2
                
                dx = abs(x2-x1)
                dy = abs(y2-y1)
                return max(dx,dy)
            ans = 0
            for i in range(1,len(points)):
                ans += get_ans(points[i-1],points[i])
            return ans

统计参与通信的服务器

思考下什么位置的机器是不能和其他机器通讯的,那就是该机器的行和列都只有他自己,所以行和列都只有一个机器。所以对于每个机器,我们判断其对应的行和列是不是只有该机器就可以了。时间复杂度 O(n2)O(n^2)

    class Solution(object):
        def countServers(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            n = len(grid)
            m = len(grid[0])
            import numpy as np
            sumr = np.sum(grid,0)
            sumc = np.sum(grid,1)
            
            r_index_1 = np.where(sumr==1)[0]
            c_index_1 = np.where(sumc==1)[0]
            ans = 0
            for ridx in r_index_1:
                for cidx in c_index_1:
                    if grid[cidx][ridx] == 1:
                        ans += 1
            return np.sum(grid) - ans

搜索推荐系统

Trie 树模拟,我们把词典中所有单词都存到一个 trie 树上,trie 树上每个节点存经过这个节点的所有单词。最后查询的时候,我们将每个经过的节点中的单词排序取前三就可以了。

如果要优化内存的话,每个节点用堆存字典序最小的三个元素即可,但是这题不优化也可过。

时间复杂度 O(nmlog(n))O(nmlog(n))nn 为所有字符总数量,mm 为平均每个单词的字符数量。

    class Node(object):
        def __init__(self):
            self.words = []
            self.mp = {}
    def make_trie(root,word):
        node = root
        for c in word:
            node.words.append(word)
            if not c in node.mp:
                node.mp[c] = Node()
            node = node.mp[c]
        node.words.append(word)
        
    class Solution(object):
        def suggestedProducts(self, products, searchWord):
            """
            :type products: List[str]
            :type searchWord: str
            :rtype: List[List[str]]
            """
            root = Node()
            for word in products:
                make_trie(root,word)
            ans = []
            for c in searchWord:
                if root is None or (not c in root.mp):
                    root = None
                else:
                    root = root.mp[c]
                if root is None:
                    ans.append([])
                else:
                    ret = sorted(root.words)
                    if len(ret) > 3:
                        ret = ret[:3]
                    ans.append(ret)
            return ans

停在原地的方案数

动态规划,dp[i][j] 表示第 i 步,当前指针在 j 的总方案数。那么 dp[i][j] = sum(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]), 需要特殊处理一下数组边界。

有一个优化是因为我们最多 500 步,所以不可能到达 500 更大的数组下标,枚举j的时候只需要枚举到 step+1 就可以了。这样总体时间复杂度 O(step2)O(step^2)

同样满足矩阵快速幂性质,可以用矩阵快速幂优化到 O(arrLen3log(step))O(arrLen^3log(step))

    long long ans[510][510];
    class Solution {
    public:
        int numWays(int steps, int arrLen) {
            long long mod = 1000000007;
            memset(ans,0,sizeof(ans));
            arrLen = min(arrLen,steps+1);
            ans[0][0] = 1;
            for ( int i = 1 ; i <= steps+1 ; i ++){
                for ( int j = 0 ; j < arrLen ; j ++){
                    ans[i][j] = ans[i-1][j];
                    if (j != 0)
                        ans[i][j] += ans[i-1][j-1];
                    if (j != arrLen-1)
                        ans[i][j] += ans[i-1][j+1];
                    ans[i][j] %= mod;
                }
            }
            return ans[steps][0]%mod;
        }
    };
    ```
9
展开全部 15 讨论