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

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

image.png

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

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

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

第一题:

阅读理解题

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
展开全部 15 讨论