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

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        for u, v in pairwise(range(n)):
            graph[u].append(v)

        def bfs(node, src):
            q = deque([node])
            visited = {node}
            cnt = 0

            while q:
                cnt += 1
                for _ in range(len(q)):
                    curr = q.popleft()

                    for nei in graph[curr]:
                        if nei not in visited:
                            q.append(nei)
                            visited.add(nei)

                        if nei == src:
                            return cnt

        res = []
        for u, v in queries:
            graph[u].append(v)
            res.append(bfs(0, n-1))

        return res

public class Solution
{
    public int[] ShortestDistanceAfterQueries(int n, int[][] queries)
    {
        var dis = new int[n];
        var res = new int[queries.Length];
        var qr = new List<int>[n];
        for (int i = 0; i < n; i++)
        {
            dis[i] = i;
            qr[i] = [];
        }

        for (int i = 0; i < queries.Length; i++)
        {
            var q = queries[i];
            qr[q[1]].Add(q[0]);
            dis[q[1]] = Math.Min(dis[q[0]] + 1, dis[q[1]]);
            for (int j = q[1] + 1; j < n; j++)
            {
                var d = dis[j];
                foreach (var s in qr[j])
                {
                    d = Math.Min(dis[s] + 1, d);
                }
                d = Math.Min(dis[j-1] + 1, d);
                dis[j] = d;
            }

            res[i] = dis[^1];
        }

        return res;
    }
}

var shortestDistanceAfterQueries = function (n, queries) {
    const ans = [],
        d = Array(n).fill().map((_, i) => i),
        p = Array(n).fill().map((_, i) => [i > 0 ? i - 1 : 0]),
        memo = [];
    const calc = (i) => {
        if (!i) {
            return 0;
        }
        return (memo[i] ??= _.min(p[i].map(calc)) + 1);
    };
    for (const [u, v] of queries) {
        p[v].push(u);
        memo.length = 0;
        ans.push(calc(n - 1));
    }
    return ans;
};

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                dp[i][j] = j - i;
            }
        }
        
        vector<int> ret;
        ret.reserve(queries.size());
        
        for (auto &q: queries) {
            for (int i = 0; i <= q[0]; ++i) {
                for (int j = q[1]; j < n; ++j) {
                    dp[i][j] = min(dp[i][j], dp[i][q[0]] + 1 + dp[q[1]][j]);
                }
            }
            ret.push_back(dp[0][n-1]);
        }
        return ret;
    }
};

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        d = [[i - 1] if i else [] for i in range(n)]
        f = cache(lambda i: 0 if i == 0 else min(map(f, d[i])) + 1)
        return [f.cache_clear() or d[v].append(u) or f(n - 1) for u, v in queries]

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        d = defaultdict(list)
        for i in range(n - 1):
            d[i].append(i + 1)
        def bfs():
            queue = [0]
            dist = {0 : 0}
            while queue:
                node = queue.pop(0)
                for i in d[node]:
                    if i not in dist:
                        dist[i] = dist[node] + 1
                        queue.append(i)
            
            return dist[n - 1]
        
        res = []
        for x , y in queries:
            d[x].append(y)
            res.append(bfs())
        
        return res

class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        boolean[] visited = new boolean[n];
        List<List<Integer>> outDegree = new ArrayList();
        int times = 0;
        int index = 0;
        int[] res = new int[queries.length];
        for(int i = 0;i<n-1;i++){
            outDegree.add(new ArrayList());
            outDegree.get(i).add(i+1);
        }
        for(int[] q:queries){
            outDegree.get(q[0]).add(q[1]);
            Arrays.fill(visited,false);
            times = -1;
            Queue<Integer> queue = new LinkedList();
            queue.add(0);
            while(!queue.isEmpty()){
                times++;
                int size = queue.size();
                for(int i = 0;i<size;i++){
                    int node = queue.remove();
                    if(node == n-1){
                        res[index] = times;
                        break;
                    }
                    if(visited[node])
                        continue;
                    visited[node] = true;
                    for(int k:outDegree.get(node))
                        queue.add(k);
                }
                if(res[index]!=0){
                    index++;
                    break;
                }
            }
        }
        return res;
    }
}

class Solution:
    def findMaximumScore(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [-1] * n
        stack = [0]

        for i in range(1, len(nums)):
            while stack and nums[i] > nums[stack[-1]]:
                j = stack.pop()
                dp[j] = i

            stack.append(i)
  
        @cache
        def f(i):
            if i >= n - 1:
                return 0
            if dp[i] == -1:
                return nums[i] * (n - 1 - i)
            else:
                return nums[i] * (dp[i] - i) + f(dp[i])
          
        return f(0)