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

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

image.png

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

第三题可以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
展开全部 41 讨论