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

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

image.png

3 分 - 按既定顺序创建目标数组
4 分 - 四因数
5 分 - 检查网格中是否存在有效路径
6 分 - 最长快乐前缀

展开讨论
力扣 (LeetCode)发起于 2020-03-22
共 41 个讨论

纪念人生第一次全AC 太不容易了啊啊啊!!!

第一题查了一下API直接调了

第二题上手写了个从1遍历到根号num,结果把根号num转int忘了+1,半天过不了。 一怒之下写了个从1遍历到num的,结果超时了OTZ ... 又回头写根号num的...第二题写了二十分钟

第三题看了一眼太复杂,大概想了想应该是DFS吧,然后跳过

第四题看完题目笑出声,昨天刚看过KMP,直接默写。 结果忘记了KMP求next时是求当前位置前一位的最长前缀和后缀,我当成当前位置写了半天,WA好几次...最后才发现这个问题,给原串最后加了一个字符,然后再提交就AC了。。。

然后回头写第三题...二十分钟写完,写了150行。。体力活

12

**吧最后一题,C++写了半天,各种优化过不了,一看通过那么多,点开评论区一看各种暴力能过,一看常用语言Python

换Python三行暴力就过了

LeetCode是歧视C++用户吗

8

第四题,kmp求next串,最短代码

class Solution {
public:
    string longestPrefix(string s) 
    {
        int len=s.length();
        vector<int> ne(len,-1);
        for(int i=1,j=-1;i<len;i++)
        {
            while(j>=0 && s[i]!=s[j+1]) j=ne[j];
            if(s[i]==s[j+1]) j++;
            ne[i]=j;
        }
        int res=ne[len-1];
        if(res>=0) return s.substr(0,res+1);
        return "";
    }
};
5

纪念一下自己第二次参加竞赛。。
制作出来两道题,小白之路漫漫,加油

4

第三题会构成环吗 (开头会是4吗)

3
class Solution(object):
    def longestPrefix(self, s):
        """
        :type s: str
        :rtype: str
        """
        index = []
        for i in range(len(s)-1):
            if s[i]==s[-1]:
                index.append(i)
        for i in range(len(index)-1, -1, -1):
            if s[:index[i]]==s[len(s)-index[i]-1:-1]:
                return s[:index[i]+1]
        return ''

最后一题真就把我吓到了,难顶,在第三题上花了好长时间服了

2

第二题暴力遍历超时,有大佬分享优化方案吗

2

第二题第四题疯狂超时...到底该怎么优化 求大佬请教```

class Solution {
    int count=0;
    public int sumFourDivisors(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            int a=IsTarget(nums[i]);
            if(count==3){
                sum+=a;
            }
        }
        return sum;
    }
    public int IsTarget(int n){
        count=0;
        int sum=0;
        for(int i=1;i<=n/2;i++){
            if(n%i==0){
                count++;
                sum+=i;
            }
        }
        return sum+n;
    }
}
2

第三题可以dfs,两个方向,用两个大小的数组就行,判断a能不能去b,只要满足a->b可以,b->a也可以那就说明a可以去b了,同时注意下访问过的不再访问就行,比赛时提交通过,性能没看,估计会有点慢

    private int[][] dr = new int[][]{
            {}, {0, 0}, {-1, 1}, {0, 1}, {0, 1}, {0, -1}, {0, -1}
    };
    private int[][] dc = new int[][]{
            {}, {-1, 1}, {0, 0}, {-1, 0}, {1, 0}, {-1, 0}, {1, 0}
    };

    public boolean hasValidPath(int[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        return dfs(grid, 0, 0, visited);
    }

    private boolean dfs(int[][] grid, int startRow, int startCol, boolean[][] visited) {
        if (startRow == grid.length - 1 && startCol == grid[0].length - 1) {
            return true;
        }
        int d = grid[startRow][startCol];
        visited[startRow][startCol] = true;
        int[] nr = dr[d];
        int[] nc = dc[d];
        for (int i = 0; i < 2; i++) {
            int nextRow = startRow + nr[i];
            int nextCol = startCol + nc[i];
            if (nextRow < 0 || nextRow > grid.length - 1 || nextCol < 0 || nextCol > grid[0].length - 1) {
                continue;
            }
            if (visited[nextRow][nextCol]) {
                continue;
            }
            //保证next也能到这里才是有效的
            int nd = grid[nextRow][nextCol];
            int[] nr2 = dr[nd];
            int[] nc2 = dc[nd];
            boolean can = false;
            for (int j = 0; j < 2; j++) {
                int goRow = nextRow + nr2[j];
                int goCol = nextCol + nc2[j];
                if (goRow == startRow && goCol == startCol) {
                    can = true;
                    break;
                }
            }

            if (can) {
                if (dfs(grid, nextRow, nextCol, visited)) {
                    return true;
                }
            }


        }
        visited[startRow][startCol] = false;
        return false;
    }
1

第一题: 开始想着插入是O(n),想了半天没找到好的解决......直接就暴力插入了. 过了.
第二题: 遍历 1 到 平方根+1 位置, 能整除就加入集合, 如果集合个数超过4,就Break, 否则就检查集合个数是否刚好4个. res += sum(set)
第三题: DFS一直卡递归层数, 加了设置为4000层,卡内存...... 加了 @lu_cache, 还是不行, 试试改成BFS......一次过......我了个去......
第四题: 倒着遍历(pre,当前缀), 逐个比较,一旦符合,就是最长的.
唉........被第三题搞太久了......第4题没时间了......就差了2分钟......哈哈哈哈哈哈
还是要多练练~~

1