thảo luận Leetcode mỗi ngày

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dirs = [(0,1), (0,-1), (1,0), (-1,0)]
        def dfs(i, j):
            nonlocal visit
            if (
                (i, j) in visit or
                i < 0 or i >= m or
                j < 0 or j >= n or
                grid[i][j] == 0
            ): return 0
            if i == 0 or i == m-1 or j == 0 or j == n-1:
                return float('inf')
            visit.add((i,j))
            cnt = 1
            for di, dj in dirs:
                ni, nj = i + di, j + dj
                cnt += dfs(ni, nj)
            return cnt

        visit = set()
        ans = 0
        for i in range(m):
            for j in range(n):
                if (i,j) not in visit and grid[i][j] == 1:
                    res = dfs(i, j)
                    if res != float('inf'):
                        ans += res
        return ans

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return

        def clone(node):
            new_node = Node(node.val)
            return new_node
        
        def dfs(node):
            nonlocal visited, map
            if not node: return
            visited.add(node)
            new_node = clone(node)
            map[node] = new_node
            new_neighbors = []
            for ne in node.neighbors:
                if ne not in visited:
                    new_neighbors.append(dfs(ne))
                else:
                    print(ne.val, map[ne])
                    new_neighbors.append(map[ne])
            new_node.neighbors = new_neighbors
            # print(new_node.val, [(n.val, n) for n in new_node.neighbors])
            return new_node
            # print(node.val, [(n.val, n) for n in node.neighbors])
        visited = set()
        map = {}
        dfs(node)
        return map[node]

class Solution:
    def __init__(self):
        self.nodes = {}
        
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        
        if node.val in self.nodes:
            return self.nodes[node.val]
    
        newNode = Node(node.val)
        self.nodes[node.val] = newNode
        
        for neigh in node.neighbors:
            newNode.neighbors.append(self.cloneGraph(neigh))
        
        return newNode

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if (!node) {
        return null;
    }

    const edges = Array(101).fill().map(() => Array(101));
    const visited = Array(101).fill(false);
    const nodes = Array(101).fill().map((_, idx) => new Node(idx));

    const find = n => {
        if (visited[n.val]) {
            return;
        }

        visited[n.val] = true;

        for (const m of n.neighbors) {
            if (!edges[n.val][m.val] && !edges[m.val][n.val]) {
                edges[n.val][m.val] = edges[m.val][n.val] = true;
                nodes[n.val].neighbors.push(nodes[m.val]);
                nodes[m.val].neighbors.push(nodes[n.val]);
            }
            find(m);
        }
    };

    find(node);

    return nodes[node.val];
};

function cloneGraph(node: Node | null): Node | null {

    const map: Map<Node, Node> = new Map();
        if (!node) {
        return;
    }

    const dfs = (node: Node): Node | null => {
        const clone = new Node(node.val);
        const neighbors: Node[] = []
        map.set(node, clone);
        for (const neigh of node.neighbors) {
            if (map.has(neigh)) {
                neighbors.push(map.get(neigh))
            } else {
                neighbors.push(dfs(neigh))
            }
        }
        clone.neighbors = neighbors
        return clone
    }

    if (node.neighbors.length === 0) {
        return (new Node(node.val))
    }
    return dfs(node);

};

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Integer, Node> map = new HashMap<>();
        Map<Integer, Set<Integer>> adjList = new HashMap<>();
        Set<Integer> visited = new HashSet<>();
        
        Node ret = new Node(node.val);

        map.put(node.val, ret);

        Queue<Node> q = new LinkedList<>();
        visited.add(node.val);
        q.add(node);

        while(!q.isEmpty()) {
            Node cur = q.poll();
            adjList.putIfAbsent(cur.val, new HashSet<>());
            for (Node neighbor : cur.neighbors) {
                // System.out.println(neighbor.val);
                map.putIfAbsent(neighbor.val, new Node(neighbor.val));
                adjList.get(cur.val).add(neighbor.val);
                if (!visited.contains(neighbor.val)) {
                    q.add(neighbor);
                    visited.add(neighbor.val);
                }
            }
        }
        
        for (int nodeVal : adjList.keySet()) {
            Node cur = map.get(nodeVal);
            for (int neighborVal : adjList.get(nodeVal)) {
                cur.neighbors.add(map.get(neighborVal));
            }
        }

        // System.out.println(visited);
        // System.out.println(adjList.get(4));
        return ret;
    }
}

class Solution {
  List<List<Integer>> graph = new ArrayList<>();
  int[][] dp;
  int ans = 1;
  String colors;
  boolean[] v = new boolean[100_001];
  public int largestPathValue(String colors, int[][] edges) {
    this.colors = colors;
    int N = colors.length();
    for (int i = 0; i++ < N;) {
      graph.add(new ArrayList<>());
    }
    for (var e: edges) {
      graph.get(e[0]).add(e[1]);
    }
    dp = new int[N][];
    for (int i = 0; i < N; ++i) {
      if (dfs(i) == null) return -1;
    }
    return ans;
  }

  int[] dfs(int node) {
    if (v[node]) return null;
    if (dp[node] != null) return dp[node];
    v[node] = true;
    int[] curr = new int[26];
    for (int n: graph.get(node)) {
      int[] r = dfs(n);
      if (r == null) return null;
      for (int i = 0; i < 26; ++i) {
        curr[i] = Math.max(curr[i], r[i]);
      }
    }
    v[node] = false;
    char c = colors.charAt(node);
    curr[c-'a']++;
    ans = Math.max(ans, curr[c-'a']);
    dp[node] = curr;
    return dp[node];
  }
}

/**
 * @param {string} colors
 * @param {number[][]} edges
 * @return {number}
 */
var largestPathValue = function(colors, edges) {
    const n = colors.length;
    const parents = Array.from({ length: n }, () => []);

    for (const [u, v] of edges) {
        parents[v].push(u);
    }

    const go = ch => {
        const scores = [];
        const scoreOf = idx => {
            if (scores[idx] === undefined) {
                scores[idx] = -1;
                let tmp = 0;

                for (const p of parents[idx]) {
                    if (scoreOf(p) === -1) {
                        return -1;
                    }
                    tmp = Math.max(tmp, scoreOf(p));
                }


                scores[idx] = tmp + (colors[idx] === ch ? 1 : 0);
            }

            return scores[idx];
        };

        let t = 0;
        for (let i = 0; i < n; i++) {
            if (scoreOf(i) < 0) {
                return -1;
            }

            t = Math.max(t, scoreOf(i));
        }

        return t;
    };

    let ans = 0;
    for (let ch = 'a'; ch <= 'z'; ch = String.fromCharCode(ch.charCodeAt(0) + 1)) {
        const t = go(ch);
        if (t < 0) {
            return t;
        }

        ans = Math.max(ans, t);
    }

    return ans;
};

function largestPathValue(colors: string, edges: number[][]): number {
        const n = colors.length;
        const map: Map<number, number[]> = new Map()
        const indegree = Array(n).fill(0);

        for (const edge of edges) {
            if (map.has(edge[0])) {
                const val = map.get(edge[0]);
                val.push(edge[1]);
                map.set(edge[0], val)
            } else {
                map.set(edge[0], [edge[1]])
            }
            indegree[edge[1]]++;
        }

        const count: number[][] = [];
        for (let i = 0; i < n; i++) {
            count.push([])
            for (let j = 0; j < 26; j++) {
                count[i].push(0)
            }
        }
        const queue: number[] = [];

        for (let i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.push(i);
            }
        }

        let res = 1, seenNodes = 0;
        while (queue.length) {
            const node = queue.shift();
            res = Math.max(res, ++count[node][colors[node].charCodeAt(0) - 'a'.charCodeAt(0)]);
            seenNodes++;

            if (!map.has(node)) {
                continue;
            }

            for (const neighbor of map.get(node)) {
                for (let i = 0; i < 26; i++) {
                    count[neighbor][i] = Math.max(count[neighbor][i], count[node][i]);
                }

                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.push(neighbor);
                }
            }
        }

        return seenNodes < n ? -1 : res;
};

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        from collections import defaultdict
        G = defaultdict(list)
        for a, b in edges:
            G[a].append(b)
        
        def dfs(node):
            nonlocal visit, ans
            if node in path:
                return float('inf')
            if node in visit:
                return 0
            visit.add(node)
            path.add(node)
            color_index = ord(colors[node]) - ord('a')
            counts[node][color_index] = 1
            for nei in G[node]:
                if dfs(nei) == float('inf'):
                    return float('inf')
                for c in range(26):
                    counts[node][c] = max(
                        counts[node][c],
                        (1 if c == color_index else 0) + counts[nei][c]
                    )
            path.remove(node)
            return max(counts[node])

        ans = 0
        visit, path = set(), set()
        counts = [[0 for _ in range(26)] for _ in range(len(colors))]
        for node in range(len(colors)):
            ans = max(ans, dfs(node))
        return ans if ans != float('inf') else -1

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] cs = s.toCharArray();
        Set<Character> open = new HashSet<>();
        Set<Character> close = new HashSet<>();
        open.add('(');
        open.add('{');
        open.add('[');
        close.add(')');
        close.add('}');
        close.add(']');

        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
        for (char c : cs) {
            if (open.contains(c)) {
                stack.push(c);
            } else if (close.contains(c)) {
                if (stack.isEmpty()) return false;
                if (map.get(stack.peek()) == c) stack.pop();
                else return false;
            }
        }

        return stack.isEmpty();
    }
}

function isValid(s: string): boolean {
    const map = {
        "(": ")",
        "{": "}",
        "[": "]",
    }
    let stack: string[] = [];

    for(let i = 0; i < s.length; i++){
        if(map[s[i]]){
            stack.push(map[s[i]]);
            continue;
        }

        if(stack.pop() !== s[i]){
            return false;
        }
    }

    return stack.length == 0;
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const map = Object.fromEntries('()|{}|[]'.split('|').map(s => [s[1], s[0]]));
    const stack = [];

    for (const ch of s) {
        if (map[ch]) {
            if (map[ch] !== stack.pop()) {
                return false;
            }
        } else {
            stack.push(ch);
        }
    }

    return stack.length === 0;
};

class Solution {
  public boolean isValid(String str) {
    char[] stack = new char[str.length()/2 + 2];
    int head = 0;
    char[] sym = new char[]{'(', ')', '[', ']', '{', '}'};
    char[] s = str.toCharArray();
    for (int i = 0; i < s.length; ++i) {
      if (s.length - i < head) return false;
      char c = s[i];
      int idx = c / 50;
      if (c == sym[idx*2+1]) {
        if (head == 0) return false;
        if (stack[head--] != sym[idx*2]) return false;
      } else {
        stack[++head] = c;
      }
    }
    return head == 0;
  }
}

function removeStars(s: string): string {
    let stack: string[] = []
    for (let i = 0; i < s.length; i++) {
        if (s[i] == '*') {
            stack.pop();
        } else {
            stack.push(s[i])
        }
    }
    return stack.join('')
};

class Solution {
    public String removeStars(String s) {
        StringBuilder sb = new StringBuilder();
        ArrayDeque<Character> deque = new ArrayDeque<>();
        for (char c : s.toCharArray()){
            if (c != '*') {
                deque.add(c);
            }else {
                deque.removeLast();
            }
        }

        while (!deque.isEmpty()){
            sb.append(deque.pollFirst());
        }

        return sb.toString();
    }
}

function removeStars(s: string): string {
    const stack: string[] = [];

    for (const c of s) {
        if (c !== '*') {
            stack.push(c);
        } else {
            stack.pop();
        }
    }

    return stack.join('');
};

function removeStars(s: string): string {
    let skip = 0;
    let result = '';

    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === '*') {
            skip++;
        } else {
            if (skip > 0) {
                skip--;
            } else {
                result += s[i];
            }
        }
    }

    return [...result].reverse().join('');
};

class Solution {
public:
    string removeStars(string& s) {
        int j = 0;
        for(char& c : s)
            if(c == '*') --j;
            else s[j++] = c;
        return s.substr(0, j);
    }
};