23.02.11 Today’s Leetcode

1129. Shortest Path with Alternating Colors (medium)

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        Map<Integer, List<List<Integer>>> adj = new HashMap<>();
        for (int[] redEdge : redEdges) {
            adj.computeIfAbsent(redEdge[0], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(redEdge[1], 0));
        }

        for (int[] blueEdge : blueEdges) {
            adj.computeIfAbsent(blueEdge[0], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(blueEdge[1], 1));
        }

        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        boolean[][] visit = new boolean[n][2];
        Queue<int[]> q = new LinkedList<>();

        // Start with node 0, with number of steps as 0 and undefined color -1.
        q.offer(new int[] { 0, 0, -1 });
        answer[0] = 0;
        visit[0][1] = visit[0][0] = true;

        while (!q.isEmpty()) {
            int[] element = q.poll();
            int node = element[0], steps = element[1], prevColor = element[2];

            if (!adj.containsKey(node)) {
                continue;
            }

            for (List<Integer> nei : adj.get(node)) {
                int neighbor = nei.get(0);
                int color = nei.get(1);
                if (!visit[neighbor][color] && color != prevColor) {
                    if (answer[neighbor] == -1)
                        answer[neighbor] = 1 + steps;
                    visit[neighbor][color] = true;
                    q.offer(new int[] { neighbor, 1 + steps, color });
                }
            }
        }
        return answer;
    }
}

내 풀이는 다음과 같다. 그런데 colors[x]를 list형식으로 바꾸어서 red, blue인지 혹은 둘 다 인지 저장해서 구현해야 정상적으로 작동할 것 같다.

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        r_tree = defaultdict(list)
        b_tree = defaultdict(list)
        for u, v in redEdges:
            r_tree[u].append(v)

        for u, v in blueEdges:
            b_tree[u].append(v)
        
        visited = [-1] * n
        visited[0] = 0
        colors = [-1] * n
        colors[0] = 2

        # 0: red, 1: blue, 2: any
        que, temp = [0], []
        dist = 1
        while que:
            cur = que.pop()
            color = colors[cur]
            if color == 1 or color == 2:
                for node in r_tree[cur]:
                    if visited[node] == -1:
                        visited[node] = dist
                        colors[node] = 0
                        temp.append(node)
            if color == 0 or color == 2:
                for node in b_tree[cur]:
                    if visited[node] == -1:
                        visited[node] = dist
                        colors[node] = 1
                        temp.append(node)
            if len(que) == 0 and len(temp) > 0:
                que = temp
                temp = []
                dist += 1
        
        return visited

36. Valid Sudoku (medium)

class Solution {
    public boolean checkLine(char[] line) {
        Set<Character> set = new HashSet<>();
        for(char c : line)
            if (!set.contains(c)) {
                if (c != '.') {
                    set.add(c);
                }
            } else {
                return false;
            }
        return true;
    }

    public boolean checkSection(char[][] board, int i, int j) {
        Set<Character> set = new HashSet<>();
        for (int a = 3 * i; a < 3 * (i + 1); a++) {
            for (int b = 3 * j; b < 3 * (j + 1); b++) {
                char c = board[a][b];
                if (!set.contains(c)) {
                    if (c != '.') {
                        set.add(c);
                    }
                } else {
                    return false;
                }
            }
        }
        return true;
    }


    public boolean isValidSudoku(char[][] board) {

        // check horizontal line
        for (char[] chars : board) {
            if (!checkLine(chars))
                return false;
        }

        // check vertical line
        for (int j = 0; j < board[0].length; j++) {
            char[] chars = new char[9];
            for (int i = 0; i < board.length; i++) {
                chars[i] = board[i][j];
            }
            if(!checkLine(chars))
                return false;
        }

        // check sections
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(!checkSection(board, i, j))
                    return false;
            }
        }

        return true;
    }
}

74. Search a 2D Matrix (medium)

Binary Search in 2D matrix

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        row_i, row_j = 0, m - 1
        row = -1
        while row_j > row_i:
            row_avg = (row_i + row_j) // 2
            if target > matrix[row_avg][-1]:
                row_i = row_avg + 1
            elif target < matrix[row_avg][0]:
                row_j = row_avg - 1
            else:
                row = row_avg
                break
        row = (row_i + row_j) // 2

        col_i, col_j = 0, n - 1
        col = -1
        while col_j > col_i:
            col_avg = (col_i + col_j) // 2
            if target > matrix[row][col_avg]:
                col_i = col_avg + 1
            elif target < matrix[row][col_avg]:
                col_j = col_avg - 1
            else:
                col = col_avg
                break
        col = (col_i + col_j) // 2

        # print(row, col)

        return matrix[row][col] == target