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

Phó GOAT · 10/1/24

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public static int amountOfTime(TreeNode root, int start) {
        int time = 0;
        Set<Integer> visited = new HashSet<>();
        Map<Integer, Set<Integer>> map = new HashMap<>();
        dfs(root, 0, map);
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                int curr = queue.poll();
                for (int n : map.get(curr)) {
                    if (!visited.contains(n)) {
                        visited.add(n);
                        queue.add(n);
                    }
                }
                size--;
            }
            time++;
        }
        return time - 1;
    }

    public static void dfs(TreeNode root, int val, Map<Integer, Set<Integer>> map) {
        if (root == null) {
            return;
        }
        if (!map.containsKey(root.val)) {
            map.put(root.val, new HashSet<>());
        }
        if (val != 0) {
            map.get(root.val).add(val);
        }
        if (root.left != null) {
            map.get(root.val).add(root.left.val);
        }
        if (root.right != null) {
            map.get(root.val).add(root.right.val);
        }
        dfs(root.left, root.val, map);
        dfs(root.right, root.val, map);
    }
}

Java:

class Solution {
  private int ans;

  public int amountOfTime(TreeNode root, int start) {
    dfs(root, start);
    return ans;
  }

  public int dfs(TreeNode root, int start) {
    if (root == null) return 0;

    int leftDepth = dfs(root.left, start);
    int rightDepth = dfs(root.right, start);

    if (root.val == start) {
      ans = Math.max(leftDepth, rightDepth);
      return -1;
    } else if (leftDepth >= 0 && rightDepth >= 0) {
      return Math.max(leftDepth, rightDepth) + 1;
    } else {
      ans = Math.max(ans, Math.abs(leftDepth - rightDepth));
      return Math.min(leftDepth, rightDepth) - 1;
    }
  }
}

Violet_7 · 10/1/24

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        start_deep = 0

        def dfs(root):
            if root is None:
                return -1, -1

            left_time, left_distance = dfs(root.left)
            right_time, right_distance = dfs(root.right)
            curr_distance = 0 if root.val == start else -1

            if left_distance != -1:
                curr_distance = left_distance + 1
                left_time = max(left_time, curr_distance)
                if right_time >= 0:
                    right_time += curr_distance
            else:
                left_time += 1

            if right_distance != -1:
                curr_distance = right_distance + 1
                right_time = max(right_time, curr_distance)
                if left_time >= 0:
                    left_time += curr_distance
            else:
                right_time += 1

            return max(left_time, right_time), curr_distance

        result, _ = dfs(root)
        return result

Ngồi hì hục mãi cái one pass

Violet_7 · 10/1/24

freedom.9 đã nói:

Co cach nao chi can dung 1 dfs ko nhi

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        graph = {}

        def buildGraph(root):
            if not root.val in graph:
                graph[root.val] = []
           
            if root.left != None:
                if root.left.val not in graph:
                    graph[root.left.val] = []
                graph[root.val].append(root.left.val)
                graph[root.left.val].append(root.val)
                buildGraph(root.left)

            if root.right != None:
                if root.right.val not in graph:
                    graph[root.right.val] = []
                graph[root.val].append(root.right.val)
                graph[root.right.val].append(root.val)
                buildGraph(root.right)

        buildGraph(root)
        queue = []
        # current, parent, distance
        queue.append((start, -1, 0))
        while queue:
            item = queue.pop(0)
            for neigbor in graph[item[0]]:
                if neigbor == item[1]:
                    continue
               
                queue.append((neigbor, item[0], item[2] + 1))

            if len(queue) == 0:
                return item[2]

        return -1

có bác

, mà hơi nhiều if else :pudency:

seastar · 10/1/24

Violet_7 đã nói:
có bác , mà hơi nhiều if else

T if-else có mấy phát chứ mấy, :matrix:

seastar đã nói:

10/01/2024: loay hoay mãi cũng làm đc cái dfs mà chỉ cần 1 lần duyệt, :beauty:

.

C++:

class Solution {
public:
    int amountOfTime(TreeNode* root, int start) {
        return amountOfTimeDFS(root, start).first;
    }

    pair<int,int> amountOfTimeDFS(TreeNode* root, int start) {
        if (!root) return {0, -1};
        auto [l, l_d] = amountOfTimeDFS(root->left, start);
        auto [r, r_d] = amountOfTimeDFS(root->right, start);
        if (root->val == start) return { max(l, r), 0};
        if (l_d < 0 && r_d < 0) return { 1 + max(l, r), -1};
        if (l_d >= 0) return {max(l, r + l_d + 1), l_d + 1};
        return {max(l + r_d + 1, r), r_d + 1};
    }
};

Xem tệp đính kèm 2281168

freedom.9 · 10/1/24

EzLink đã nói:

e code logic giống bác, C# bị stackoverflow ở case này :beat_brick:

e code cái C# logic giống bác mà bị stackoverflow sáng h, case nó đây :beat_brick:

Xem tệp đính kèm 2281304

C#:

public class Solution {
    public int AmountOfTime(TreeNode root, int start) {
        var map = new Dictionary<int, int[]>();
        map[root.val] = new int[3];
        DFS(root);
        var queue = new Queue<(int, int, int)>();
        var ans = 0;

        queue.Enqueue((start, -1, 0));
        while(queue.Count>0){
            var (cur_node, parent, cur_time) = queue.Dequeue();
            foreach(int next in map[cur_node]){
                if(next == 0 || next == parent){
                    continue;
                }
                queue.Enqueue((next, cur_node, cur_time+1));
            }
            ans = cur_time;
        }
        return ans;

        void DFS(TreeNode node){
            if(node.left!=null){
                map[node.val][1] = node.left.val;
                map[node.left.val] = new int[3];
                map[node.left.val][0] = node.val;
                DFS(node.left);
            }
            if(node.right!=null){
                map[node.val][2] = node.right.val;
                map[node.right.val] = new int[3];
                map[node.right.val][0] = node.val;
                DFS(node.right);
            }
        }

    }
}

Hàm build map của bác nó bị đè lên kìa, phải check có hay k thì mới new chứ.
À đọc lộn, chắc bác code có bug rồi :shame:

via theNEXTvoz for iPhone

Kroosm4 · 10/1/24

EzLink đã nói:

e code logic giống bác, C# bị stackoverflow ở case này :beat_brick:

e code cái C# logic giống bác mà bị stackoverflow sáng h, case nó đây :beat_brick:

Xem tệp đính kèm 2281304

C#:

public class Solution {
    public int AmountOfTime(TreeNode root, int start) {
        var map = new Dictionary<int, int[]>();
        map[root.val] = new int[3];
        DFS(root);
        var queue = new Queue<(int, int, int)>();
        var ans = 0;

        queue.Enqueue((start, -1, 0));
        while(queue.Count>0){
            var (cur_node, parent, cur_time) = queue.Dequeue();
            foreach(int next in map[cur_node]){
                if(next == 0 || next == parent){
                    continue;
                }
                queue.Enqueue((next, cur_node, cur_time+1));
            }
            ans = cur_time;
        }
        return ans;

        void DFS(TreeNode node){
            if(node.left!=null){
                map[node.val][1] = node.left.val;
                map[node.left.val] = new int[3];
                map[node.left.val][0] = node.val;
                DFS(node.left);
            }
            if(node.right!=null){
                map[node.val][2] = node.right.val;
                map[node.right.val] = new int[3];
                map[node.right.val][0] = node.val;
                DFS(node.right);
            }
        }

    }
}

Khử đệ quy thui thím. Lần đầu làm leetcode thấy bị overflow :beat_brick:

.

lechuck · 11/1/24

Hơi dài, optimize nữa chắc cũng được mà beats 99.44% nên thôi khỏi :smile:

Python:

from collections import deque
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        startNode = None
        p = {}
        def find(node, parent):
            nonlocal startNode
            if not node:
                return
            if parent:
                p[node] = parent
            if node.val == start:
                startNode = node
                return
            find(node.left, node)
            find(node.right, node)
        find(root, None)
        min = 0
        queue = deque()
        queue.append(startNode)
        visited = set()
        visited.add(startNode)
        while queue:
            count = len(queue)
            for _ in range(count):
                curNode = queue.popleft()
                if curNode in p and p[curNode] not in visited:
                    queue.append(p[curNode])
                    visited.add(p[curNode])
                if not curNode:
                    continue
                if curNode.left and curNode.left not in visited:
                    queue.append(curNode.left)
                    visited.add(curNode.left)
                if curNode.right and curNode.right not in visited:
                    queue.append(curNode.right)
                    visited.add(curNode.right)
            min += 1
        return min -1

freedom.9 · 11/1/24

A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.
Đề kiểu muốn chửi à, đếch hiểu cái ancestor này là gì cả :beat_brick:

pikachu_1 · 11/1/24

freedom.9 đã nói:
A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.
Đề kiểu muốn chửi à, đếch hiểu cái ancestor này là gì cả

Thì cứ dịch nôm ra, tổ tiên bố hoặc là ông hoặc là cụ.

aNotHeRNo0b · 11/1/24

Java:

import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maximumValue;

    public int maxAncestorDiff(TreeNode root) {
        maximumValue = 0;
        dfsWithParent(root, new ArrayList<Integer>());
        return maximumValue;
    }

    public void dfsWithParent(TreeNode root, List<Integer> ancesstorValue) {
        if (root == null) {
            return;
        }

        for (int i = 0; i < ancesstorValue.size(); i++) {
            System.err.println(ancesstorValue);
            maximumValue = Math.max(maximumValue, Math.abs(root.val - ancesstorValue.get(i)));
        }

        ancesstorValue.add(root.val);
        dfsWithParent(root.left, ancesstorValue);
        dfsWithParent(root.right, ancesstorValue);
        ancesstorValue.remove(ancesstorValue.size() - 1);
    }
}

Java:

class Solution {
    public int maximumValue;

    public int maxAncestorDiff(TreeNode root) {
        minValue(root);
        maxValue(root);
        return maximumValue;
    }

    public int minValue(TreeNode root) {
        if (root == null) {
            return -1;
        }

        int minLeft = minValue(root.left);
        int minRight = minValue(root.right);

        if (minLeft == -1) minLeft = root.val;
        if (minRight == -1) minRight = root.val;

        maximumValue = Math.max(maximumValue, Math.abs(root.val - Math.min(minLeft, minRight)));

        return Math.min(root.val, Math.min(minLeft, minRight));
    }
   
    public int maxValue(TreeNode root) {
        if (root == null) {
            return -1;
        }

        int maxLeft = maxValue(root.left);
        int maxRight = maxValue(root.right);
        if (maxLeft == -1) maxLeft = root.val;
        if (maxRight == -1) maxRight = root.val;

        maximumValue = Math.max(maximumValue, Math.abs(root.val - Math.max(maxRight, maxLeft)));

        return Math.max(root.val, Math.max(maxRight, maxLeft));
    }
}

Nhìn đề nghĩ pass hết ancestor value cho node con check thì sẽ là O(n^2) nhưng hóa ra là O(n^3)

cherry5 · 11/1/24

C#:

public class Solution {
    int maxD;
    public int MaxAncestorDiff(TreeNode root) {
        maxD = 0;
        recursion(root, root.val, root.val);
        return maxD;
    }

    public void recursion(TreeNode node, int min, int max) {
        if(node == null) return;
        
        min = Math.Min(min, node.val);
        max = Math.Max(max, node.val);
        maxD = Math.Max(maxD, max - min);

        recursion(node.left, min, max);
        recursion(node.right, min, max);
    }
}

Aluminum21 · 11/1/24

C#:

public class Solution
{
    public int MaxAncestorDiff(TreeNode root)
    {
        return DFS(root, root.val, root.val);
    }

    private int DFS(TreeNode node, int min, int max)
    {
        if (node == null)
        {
            return max - min;
        }

        max = Math.Max(max, node.val);
        min = Math.Min(min, node.val);

        int maxLeft = DFS(node.left, min, max);
        int maxRight = DFS(node.right, min, max);

        return Math.Max(maxLeft, maxRight);
    }
}

anoldvozer1710.v2 · 11/1/24

Tìm max và min trong từng subtree :doubt:

JavaScript:

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxAncestorDiff(root: TreeNode | null): number {
    const go = (node: TreeNode, curMax: number, curMin: number) => {
        if (!node) return curMax - curMin;
        curMax = Math.max(curMax, node.val);
        curMin = Math.min(curMin, node.val);
        return Math.max(go(node.left, curMax, curMin), go(node.right, curMax, curMin));
    }
    return go(root, root.val, root.val);

};

cherry5 · 11/1/24

aNotHeRNo0b đã nói:
O(n^2) nhưng hóa ra là O(n^3)

Hình như vẫn O(n^2) thôi bác, em bỏ println submit vẫn accepted

freedom.9 · 11/1/24

Ý tưởng là ở mỗi dfs trả về min và max thôi. Lúc đầu thì nghĩ sẽ phải trả về 1 list các node nhưng nghĩ lại chỉ có min và max contribute vô cái kết quả thôi.
Đm cái đề sida đọc muốn chửi chứ làm thì ko có gì đặc biệt :tire:

Kẹp câu giải thích đúng ngu ngục

via theNEXTvoz for iPhone

anoldvozer1710.v2 · 11/1/24

freedom.9 đã nói:
Ý tưởng là ở mỗi dfs trả về min và max thôi. Lúc đầu thì nghĩ sẽ phải trả về 1 list các node nhưng nghĩ lại chỉ có min và max contribute vô cái kết quả thôi.
Đm cái đề sida đọc muốn chửi chứ làm thì ko có gì đặc biệt
Kẹp câu giải thích đúng ngu ngục

via theNEXTvoz for iPhone

fence hiểu quá phức tạp thôi, nhìn đề là hiểu tính min max trong từng subtree rồi :angry:

pikachu_1 · 11/1/24

freedom.9 đã nói:
Ý tưởng là ở mỗi dfs trả về min và max thôi. Lúc đầu thì nghĩ sẽ phải trả về 1 list các node nhưng nghĩ lại chỉ có min và max contribute vô cái kết quả thôi.
Đm cái đề sida đọc muốn chửi chứ làm thì ko có gì đặc biệt
Kẹp câu giải thích đúng ngu ngục

via theNEXTvoz for iPhone

Sao nhiều người đọc lần đầu hiểu mà. Người ta gọi đó là trình độ fen ạ

freedom.9 · 11/1/24

anoldvozer1710.v2 đã nói:
fence hiểu quá phức tạp thôi, nhìn đề là hiểu tính min max trong từng subtree rồi

Mình ko hiểu đề đó fence vì ko hiểu cái ancestor là gì, mà đó là though process thôi chứ code thì là code tìm min max thôi :beauty:

via theNEXTvoz for iPhone

freedom.9 · 11/1/24

pikachu_1 đã nói:
Sao nhiều người đọc lần đầu hiểu mà. Người ta gọi đó là trình độ fen ạ

Thường leetcode nó có trò kiểu như a string is beautiful if ...
Nên rút kinh nghiệm ko dựa vô nghĩa của cái từ đó mà dựa vô giải thích :tire:

via theNEXTvoz for iPhone

thanbaiks · 11/1/24

JavaScript:

var maxAncestorDiff = function(root) {
    let ans = 0;

    const dfs = node => {
        if (!node) {
            return null
        }

        let min = node.val, max = node.val;

        [node.left, node.right].filter(Boolean).forEach(n => {
            [mi, ma] = dfs(n);
            min = Math.min(min, mi);
            max = Math.max(max, ma);
        });
        ans = Math.max(ans, node.val - min, max - node.val);

        return [min, max];
    }

    dfs(root);

    return ans;
};

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

Senior Member

Member

Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Junior Member

Junior Member

Senior Member

Junior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này