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

impl Solution {
    pub fn num_of_strings(patterns: Vec<String>, word: String) -> i32 {
        let mut cnt = 0;
        for pattern in patterns{
            if word.contains(pattern){
                cnt += 1;
            }
        }
        cnt
    }
}

function numberOfSubstrings(s: string): number {
    let map = { 'a': 0, 'b': 0, 'c': 0 };
    let l = 0, res = 0;

    for (let r = 0; r < s.length; r++) {
        map[s[r]]++;

        while (map['a'] > 0 && map['b'] > 0 && map['c'] > 0) {
            res += s.length - r;
            map[s[l]]--;
            l++;
        }
    }

    return res;
};

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        l, res = 0, 0
        cnt = {c:0 for c in "abc"}
        
        for r in range(len(s)):
            cnt[s[r]] += 1
            while all(cnt.values()):
                cnt[s[l]] -= 1
                l += 1
            res += l
        return res

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n=len(grid)
        dist=[[-1]*n for _ in range(n)]
        queue=deque()
        for r in range(n):
            for c in range(n):
                if grid[r][c]==1:
                    queue.append((r,c))
                    dist[r][c]=0
        dirs=[(0, 1),(1, 0),(0, -1),(-1, 0)]
        while queue:
            r,c=queue.popleft()
            for dr,dc in dirs:
                nr,nc=r+dr,c+dc
                if 0<=nr<n and 0<=nc<n and dist[nr][nc]==-1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
        def can_reach(limit):
            if dist[0][0]<limit or dist[n-1][n-1]<limit:
                return False
            q = deque([(0, 0)])
            visited = [[False] * n for _ in range(n)]
            visited[0][0] = True
            while q:
                r,c=q.popleft()
                if r==n-1 and c==n-1:
                    return True
                for dr,dc in dirs:
                    nr,nc =r+dr,c+dc
                    if 0 <=nr<n and 0 <=nc<n and not visited[nr][nc]:
                        if dist[nr][nc]>=limit:
                            visited[nr][nc] = True
                            q.append((nr, nc))
            return False
        low=0
        high=min(dist[0][0],dist[n-1][n-1])
        ans=0
        while low <= high:
            mid = (low + high) // 2
            if can_reach(mid):
                ans=mid
                low= mid+1 
            else:
                high=mid-1
        return ans

function findSafeWalk(grid: number[][], health: number): boolean {
    const m = grid.length,
        n = grid[0].length;
    const arr = Array.from({ length: m }, () =>
        new Array(n).fill(-1),
    );
    const dirs = [[0, 1],[1, 0],[-1, 0],[0, -1]];

    const pq = new MinPriorityQueue<[number, number, number]>({compare: (a, b ) => a[0] - b[0]});
    pq.enqueue([grid[0][0], 0, 0]);

    while (!pq.isEmpty()) {
        const [val, xx, yy] = pq.dequeue();
        if (arr[xx][yy] >= 0) {
            continue;
        }
        arr[xx][yy] = val;

        for (const [dx, dy] of dirs) {
            const nx = xx + dx;
            const ny = yy + dy;

            if (nx < 0 || ny < 0 || nx >= m || ny >= n || arr[nx][ny] >= 0) {
                continue;
            }

            pq.enqueue([val + grid[nx][ny], nx, ny]);
        }
    }

    return arr[m - 1][n - 1] < health;
}

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        m,n=len(grid),len(grid[0])
        damage=[[float('inf')]*n for _ in range(m)]
        q=deque([(0,0)])
        dirs=[(0,1),(1,0),(0,-1),(-1,0)]
        damage[0][0]=grid[0][0]
        while q:
            r,c=q.popleft()
            if r==m-1 and c==n-1:
                break
            for dr,dc in dirs:
                nr,nc=r+dr,c+dc
                if 0<=nr<m and 0<=nc<n:
                    new_damage=damage[r][c]+grid[nr][nc]
                    if new_damage<damage[nr][nc]:
                        damage[nr][nc]=new_damage
                        if grid[nr][nc]==0:
                            q.appendleft((nr,nc))
                        else:
                            q.append((nr,nc))
        return health>damage[m-1][n-1]

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        adj = defaultdict(dict)
        for u, v, w in roads:
            adj[u][v] = adj[v][u] = w
       
        result = 100_001
        q = deque([1])
        visited = [False for _ in range(n + 1)]
        while q:
            u = q.popleft()
            for v, score in adj[u].items():
                if not visited[v]:
                    q.append(v)
                    visited[v] = True
                result = min(result, score)
               
        return result

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        adj=defaultdict(list)
        for u,v,dis in roads:
            adj[u].append((v,dis))
            adj[v].append((u,dis))
        min_score=float('inf')
        visited=set()
        q=deque([1])
        visited.add(1)
        while q:
            u=q.popleft()
            for v,dis in adj[u]:
                min_score=min(min_score,dis)
                if v not in visited:
                    q.append(v)
                    visited.add(v)
        return min_score

from collections import defaultdict
class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        def compare(cur_node,prev_node,score):
            res = cur_node
            if prev_node[1]>0:
                if prev_node[0]+score>cur_node[0]:
                    res = (prev_node[0]+score,prev_node[1])
                elif prev_node[0]+score==cur_node[0]:
                    res = (cur_node[0],(cur_node[1]+prev_node[1])%modulo)
            return res
        modulo = 10**9 + 7
        n = len(board)
        m = len(board[0])
        cur = [(0,0)]*m
        cur[m-1]=(0,1)
        for i in range(m-2,-1,-1):
            if board[n-1][i]!='X':
                if board[n-1][i]=='E':
                    score = 0
                else:
                    score = int(board[n-1][i])
                cur[i]=compare(cur[i],cur[i+1],score)
        prev = cur
        for j in range(n-2,-1,-1):
            cur = [(0,0)]*m
            for i in range(m-1,-1,-1):
                if board[j][i]!='X':
                    if board[j][i]=='E':
                        score = 0
                    else:
                        score = int(board[j][i])
                    cur[i]=compare(cur[i],prev[i],score)
                    if i+1<m:
                        cur[i]=compare(cur[i],cur[i+1],score)
                        cur[i]=compare(cur[i],prev[i+1],score)
            prev = cur
        return list(cur[0])

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda interval: (interval[0], -interval[1]))
        x, y = intervals[0][0], intervals[0][1]
        cnt = 0
        for i in range(1, len(intervals)):
            x2, y2 = intervals[i][0], intervals[i][1]

            if y2 <= y:
                cnt += 1
            else:
                x, y = x2, y2
        
        return len(intervals) - cnt

function removeCoveredIntervals(intervals: number[][]): number {
    intervals.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
    const n = intervals.length;
    let res = 0;
    let x = intervals[0][0], y = intervals[0][1];
    for (let i = 1; i < intervals.length; i++) {
        const x1 = intervals[i][0], y1 = intervals[i][1];
        if (x1 >= x && y1 <= y) res++
        else x = x1, y = y1
    }
    return n - res;
};

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1]))
        ans=0
        prev_l,prev_r=-1,-1
        for l,r in intervals:
            if prev_l<l and prev_r<r:
                ans+=1
                prev_l=l
                prev_r=r
        return ans

class Solution {
    public long sumAndMultiply(int n) {
        int sum = 0;
        long x = 0, offset = 1;

        while (n > 0) {
            int val = n % 10;
            if (val != 0) {
                x = x + val * offset;
                offset *= 10;
                sum += val;
            }
            n /= 10;
        }

        return x * sum;
    }
}

function pathExistenceQueries(n: number, nums: number[], maxDiff: number, queries: number[][]): boolean[] {
    const arr = new Array<number>(n);
    let cur = 0;
    arr[0] = cur;

    for (let i = 1; i < n; i++) {
        if (nums[i] - nums[i - 1] > maxDiff) {
            cur++;
        }
        arr[i] = cur;
    }
    return queries.map(([u, v]) => arr[u] === arr[v]);
}