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

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

image.png

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

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

先占坑,贴一下 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

这次的题真水,都怀疑看错了。
全部暴力解决,都没做多少优化。

8

今天没打,不过题解照样写

第一题:

阅读理解题

class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int ret = 0;
        for (int i = 1;i < points.length;i++) {
            ret += Math.max(Math.abs(points[i][0] - points[i - 1][0]),
                           Math.abs(points[i][1] - points[i - 1][1]));
        }
        return ret;
    }
}

第二题:

阅读理解题

class Solution {
    public int countServers(int[][] grid) {
        int[] row = new int[grid.length];
        int[] col = new int[grid[0].length];
        
        Arrays.fill(row, 0);
        Arrays.fill(col, 0);
        
        for (int i = 0;i < grid.length;i++) {
            for (int j = 0;j < grid[0].length;j++) {
                if (grid[i][j] == 1) {
                    row[i]++;
                    col[j]++;
                }
            }
        }
        
        int ret = 0;
        for (int i = 0;i < grid.length;i++) {
            for (int j = 0;j < grid[0].length;j++) {
                if (grid[i][j] == 1 && (row[i] > 1 || col[j] > 1)) {
                    ret++;
                }
            }
        }
        return ret;
    }
}

第三题:

前缀树和二分什么都太麻烦了。

这里给一个简单思路

products数组排完序之后,我们定义一个数组prefix[i]表示products[i]跟searchWords匹配的最长前缀
比如说,mobile跟mouse匹配的最长前缀是2

显然,prefix是一个单峰数组,就是非严格递增然后非严格递减

然后我们可以对searchWords每个前缀进行搜索,假设我们搜索到第k个前缀,products中跟第k个前缀匹配的位置在p,那么我们搜索第k+1个前缀的时候,只需要从p开始继续搜索

复杂度,o(Σ products[i].length)

class Solution {
    
    private int findPrefix(String a, String b) {
        int index = 0;
        while (index < a.length() && index < b.length() && a.charAt(index) == b.charAt(index)) {
            index++;
        }
        return index;
    }
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        int[] len = new int[products.length];
        Arrays.sort(products);
        for (int i = 0;i < products.length;i++) {
            len[i] = findPrefix(products[i], searchWord);
        }
        List<List<String>> ret = new ArrayList();
        int res = 0;
        for (int i = 0;i < searchWord.length();i++) {
            List<String> sub = new ArrayList();
            while (res < products.length && len[res] < i + 1) {
                res++;
            }
            for (int j = 0;j < 3 && res + j < products.length && len[res + j] >= i + 1;j++) {
                sub.add(products[res + j]);
            }
            ret.add(sub);
        }
        return ret;
    }
}

写了一版trie树

class Solution {

    class Node {
        Node[] next;
        List<String> val;

        public Node() {
            next = new Node[26];
            val = new ArrayList<>();
        }
    }

    void insert(String str, Node root) {
        Node cur = root;
        for (int i = 0;i < str.length();i++) {
            if (cur.next[str.charAt(i) - 'a'] == null) {
                cur.next[str.charAt(i) - 'a'] = new Node();
            }
            cur = cur.next[str.charAt(i) - 'a'];
            if (cur.val.size() < 3) {
                cur.val.add(str);
            }
        }
    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Node root = new Node();
        Arrays.sort(products);
        for (String str: products) {
            insert(str, root);
        }
        List<List<String>> ret = new ArrayList<>();
        Node cur = root;
        for (int i = 0;i < searchWord.length();i++) {
            if (cur == null || cur.next[searchWord.charAt(i) - 'a'] == null) {
                cur = null;
                ret.add(new ArrayList<>());
            } else {
                cur = cur.next[searchWord.charAt(i) - 'a'];
                ret.add(cur.val);
            }
        }
        return ret;
    }
}

第四题:

题目的数据范围很有迷惑性,len高达10610^6是没用,step最大才500,就算是每次都向右走,最大才走到500这个位置

动态规划入门题啊,用dp[i][j]表示第i轮正好走到位置j的方案数,那么有转移方程:
dp[i][j]=dp[i1][j1]+dp[i1][j]+dp[i1][j+1]dp[i][j]= dp[i-1][j-1] + dp[i -1][j] + dp[i-1][j+1]

这种题,看完题意之后首先想到是搜索,回溯,搜索的过程中,比如说第7轮第8个位置,是从第6轮第7个位置搜索过来的,同样也是第6轮第8个位置,第9个位置可以搜过过来,于是有很多重复的搜索过程,这些重复的搜索过程想办法只算一次,就可以大量压缩搜索空间。

动态规划其实是搜索题中的记忆化版本。这其实说的也不严谨,记忆化是一种实现方式,而动态规划就是一种思想,一种把大量搜索状态空间的搜索,转化成拥有大量重复搜索状态,并且可以增量更新的做法。

我们脑子里面其实没有动态规划的概念,一个题拿出来首先是用模拟的方式来想一遍,想办法把搜索空间压缩,这样就会出现很多算法思想。二分,动态规划,贪心,其实是搜索题优化出来的一种固定题型。而刷题,一来了解不多的题型,下次遇到可以直接套,二来,锻炼思维速度

import java.util.Arrays;

class Solution {

    static int MOD = 1000000007;

    public int numWays(int steps, int arrLen) {
        int[] dp = new int[Math.min(steps + 1, arrLen)];
        int[] dp1 = new int[dp.length];

        Arrays.fill(dp, 0);
        dp[0] = 1;
        for (int i = 1;i <= steps;i++) {
            System.arraycopy(dp, 0, dp1, 0, dp.length);
            for (int j = 0;j < dp.length;j++) {
                if (j != 0) {
                    dp1[j] = (dp1[j] + dp[j - 1]) % MOD;
                }
                if (j != dp.length - 1) {
                    dp1[j] = (dp1[j] + dp[j + 1]) % MOD;
                }
            }
            System.arraycopy(dp1, 0, dp, 0, dp.length);
        }
        return dp[0];
    }
}
8

image.png
意思是能推荐重复物品? 题目也没说清楚呀

6

来纪念下自己第一次完赛……
不过这次可能确实略简单一些,最后一道也只是动态规划,前面都只是略优化的暴力而已……

5

第二题
这个[[1,0,0,1,0],[0,0,0,0,0],[0,0,0,1,0]]预期为啥是3

1

同分同时排名咋算。。。

大佬们能帮忙看看第一题吗,死活过不去

    public int minTimeToVisitAllPoints(int[][] points) {
        if (points == null || points.length == 0)
            return 0;
        int steps = 0;
        for (int i = 0; i < points.length - 1; i++) {
            int x = Math.abs(points[i + 1][0] - points[i][0]);
            int y = Math.abs(points[i + 1][1] - points[i][0]);
            steps += Math.max(x, y);
        }
        return steps;
    }

扔个python3的题解:
https://www.bilibili.com/read/cv4032039

为啥我第一题总是会花费好长时间而且经常会有bug,这次好不容易最后一题有思路,写着写着就没时间了
image.png