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

class Solution {
  public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;
    if (head.next == null) return new TreeNode(head.val);
    ListNode fast=head, slow=head;
    while (true) {
      fast = fast.next.next;
      if (fast == null || fast.next == null) break;
      slow = slow.next;
    }

    ListNode root = slow.next;
    slow.next = null;
    TreeNode node = new TreeNode(root.val);
    node.left = sortedListToBST(head);
    node.right = sortedListToBST(root.next);
    return node;
  }
}

function sortedListToBST(head: ListNode | null): TreeNode | null {
    if (head == null) return null;
    if (head.next == null) return new TreeNode(head.val);
    let fast = head, slow = head, pre = null;
    while (fast && fast.next) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    pre.next = null;
    return new TreeNode(slow.val, sortedListToBST(head), sortedListToBST(slow.next));
};

class Node:
    def __init__(self, head):
        self.head = head
    
    def __repr__(self):
        return head.next.val
    
    def __lt__(self, other):
        return self.head.next.val < other.head.next.val
    
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0:
            return None
        
        heap = []
        for ll in lists:
            if ll is None:
                continue
            head = ListNode()
            head.next = ll
            heap.append(Node(head))
      
        heapq.heapify(heap)
        head = ListNode()
        node = head
        
        while len(heap) > 0:
            minnHead = heapq.heappop(heap)
            
            node.next = minnHead.head.next
            minnHead.head.next = minnHead.head.next.next
            
            node = node.next
            
            if minnHead.head.next is None:
                continue
            
            heapq.heappush(heap, minnHead)
        
        return head.next

class Solution {
  public ListNode mergeKLists(ListNode[] ls) {
    ListNode h = new ListNode();
    ListNode h1 = h;
    var pq = new PriorityQueue<int[]>((l,r) -> l[0]-r[0]);

    for (int i = 0; i < ls.length; ++i) {
      if (ls[i] == null) continue;
      pq.add(new int[]{ls[i].val, i});
    }

    while (!pq.isEmpty()) {
      int[] n = pq.poll();
      int idx = n[1];
      h.next = ls[idx];
      h = ls[idx];
      ls[idx] = ls[idx].next;
      if (ls[idx] != null) pq.add(new int[]{ls[idx].val, idx});
    }
    return h1.next;
  }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        ListNode result = null;
        ListNode next = null;
        for (int i= 0; i<lists.length; i++) {
            while (lists[i] != null) {
                minHeap.add(lists[i].val);
                lists[i] = lists[i].next;
            }
        }
        
        while (minHeap.size() > 0) {
            if (result == null) {
                result = new ListNode(minHeap.poll());
                next = result;
            } else {
                next.next = new ListNode(minHeap.poll());
                next = next.next;
            }
        }
        return result;
    }
}

class Solution {
public:
    ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
        ListNode *h = new ListNode(), *c = h;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                c->next = l1;
                c = l1;
                l1 = l1->next;
            } else {
                c->next = l2;
                c = l2;
                l2 = l2->next;
            }
        }
        c->next = l2 == nullptr ? l1 : l2;
        ListNode *hh = h->next;
        delete h;
        return hh;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        while (n > 1) {
            for (int i = 0, j = n - 1; i < j; i++, j--) {
                lists[i] = merge2Lists(lists[i], lists[j]);
            }
            n = (n >> 1) + (n & 1);
        }
        return n ? lists[0] : nullptr;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length <= 0){
            return null;
        }
        while(lists.length > 1){
            ArrayList<ListNode> tmp = new ArrayList<>();
            for(int i = 0; i < lists.length; i += 2){
                ListNode temp1 = lists[i];
                ListNode temp2 = (i + 1 < lists.length) ? lists[i + 1] : null;
                tmp.add(this.merge(temp1, temp2));
            }
            lists = tmp.toArray(new ListNode[tmp.size()]);
        }
        return lists[0];
    }
    public ListNode merge(ListNode list1, ListNode list2){
        ListNode result = new ListNode();
        ListNode ptr = result;
        while(list1 != null && list2 != null)
        {
            if(list2 != null && list1.val < list2.val)
            {
                ptr.next = list1;
                list1 = list1.next;
            }
            else
            {
                ptr.next = list2;
                list2 = list2.next;
            }
            ptr = ptr.next;
        }
        while(list1 != null)
        {
            ptr.next = list1;
            list1 = list1.next;
            ptr = ptr.next;
        }
        while(list2 != null)
        {
            ptr.next = list2;
            list2 = list2.next;
            ptr = ptr.next;
        }
        return result.next;
    }
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    const queue = new MinPriorityQueue({ priority: x => x.val })

    for (const list of lists) {
        if (list) {
            queue.enqueue(list)
        }
    }

    let ans = new ListNode(), head = ans;

    while (!queue.isEmpty()) {
        const { val, next } = queue.dequeue().element

        ans.next = new ListNode(val)
        ans = ans.next

        if (next) {
            queue.enqueue(next)
        }
    }

    return head.next
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  const nums = [];
  for (let list of lists) {
    while (list) {
      nums.push(list.val);
      list = list.next;
    }
  }
 
  nums.sort((u, v) => u - v);
  const root = new ListNode()
  nums.reduce((prev, cur) => {
    prev.next = new ListNode(cur);
    return prev.next;
  }, root);
 
  return root.next;
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

        for (ListNode list : lists) {
            if (list != null)  pq.add(list);
        }

        ListNode sentinel = new ListNode();
        ListNode cur= sentinel;

        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            cur.next = node;
            cur = cur.next;
            if (node.next != null) {
                pq.add(node.next);
            }
        }

        return sentinel.next;
    }
}

class Solution {
    public int findValidSplit(int[] nums) {
        Map<Integer, Integer>[] cache = new Map[nums.length];
        boolean[] sieve = new boolean[1001];
        Arrays.fill(sieve, true);
        // sieve
        for (int i = 2; i < sieve.length; i++) {
            if (sieve[i] == false) continue;
            for (int j = i + i; j < 1001; j += i) {
                sieve[j] = false;
            }
        }

        Map<Integer, Integer> pFreq = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            cache[i] = new HashMap<>();
            for (int j = 2; j < 1001; j++) {
                if (num < j) break;
                if (sieve[j] == false) continue;
                while (num % j == 0) {
                    num /= j;
                    cache[i].put(j, cache[i].getOrDefault(j,0) + 1);
                    pFreq.put(j, pFreq.getOrDefault(j, 0) + 1);
                }
            }
            if (num > 1000) {
                cache[i].put(num, cache[i].getOrDefault(num,0) + 1);
                pFreq.put(num, pFreq.getOrDefault(num, 0) + 1);
            }
        }

        int cntNotFull = 0;
        Map<Integer, Integer> curFreq = new HashMap<>();
       
        for (int i = 0; i < nums.length - 1; i++) {
            for (int num : cache[i].keySet()) {
                // if (cache[i].getOrDefault(num, 0) == 0) continue;
                boolean firstTime = curFreq.getOrDefault(num, 0) == 0;
                if (curFreq.getOrDefault(num, 0) + cache[i].get(num) < pFreq.get(num) && firstTime) {
                    cntNotFull++;
                }
                if (curFreq.getOrDefault(num, 0) + cache[i].get(num) == pFreq.get(num) && !firstTime) {
                    cntNotFull--;
                }
                curFreq.put(num, curFreq.getOrDefault(num, 0) + cache[i].get(num));
            }
            if (cntNotFull == 0) return i;
        }

        return -1;
    }
}

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root: return False
        def helper(node1, node2):
            if node1 and not node2: return False
            if node2 and not node1: return False
            if not node1 and not node2: return True
            if node1.val == node2.val:
                return helper(node1.left, node2.right) and helper(node1.right, node2.left)

        return helper(root.left, root.right)

/**
 * 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 isSymmetric(root: TreeNode | null): boolean {
    const helper = (left: TreeNode | null, right: TreeNode | null) => {
        if (left === null || right === null) {
            return left === right;
        }
       
        return left.val === right.val
            && helper(left.left, right.right)
            && helper(left.right, right.left);
    };

    return root === null || helper(root.left, root.right);
};

template <size_t N>
constexpr auto firstNprimes() {
    array<unsigned, N> res{2};
    for (size_t i = 1; i != N; ++i) {
        for (unsigned k = res[i - 1] | 1; !res[i]; k += 2) {
            bool isPrime = true;
            for (size_t j = 0; j < i && isPrime; ++j)
                if (k % res[j] == 0) isPrime = false;
            if (isPrime) res[i] = k;
        }
    }
    return res;
}

struct Solution {
    int findValidSplit(vector<int>& nums) {
        auto forEachPrimeFactor = [](int n, auto&& yield) { // thượng đẳng yield như Python
            constexpr auto primes = firstNprimes<168>(); // thượng đẳng tính số nt ở compile time
            for (int p : primes) {
                if (n % p == 0) yield(p);
                while (n % p == 0) n /= p;
            }
            if (n > 1) yield(n);
        };

        unordered_map<int, int> primeMaxIndex;
        for (int i = 0; i < nums.size(); ++i)
            forEachPrimeFactor(nums[i], [&](int p){ primeMaxIndex[p] = i; });

        for (int i = 0, res = 0; i < nums.size(); ++i) {
            if (i > res) return res; // i > res nghĩa là bên trái hết prime factor
            forEachPrimeFactor(nums[i], [&](int p){ res = max(res, primeMaxIndex[p]); }); // ăn gian ở đây: nếu p ko có trong primeMaxIndex thì primeMaxIndex[p] trả về default của int là 0, max(res, 0) sẽ luôn trả về res vì res >= 0
        }
        return -1;
    }
};

/**
 * 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 boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        return helper(root.left, root.right);
    }

    public boolean helper(TreeNode rootA, TreeNode rootB) {
        if (rootA == null && rootB == null) return true;

        if (rootA !=null && rootB != null) {
            if (rootA.val == rootB.val) return helper(rootA.left, rootB.right) && helper(rootA.right, rootB.left);
        }

        return false;
    }
}

var isSymmetric = root => !root || (verify = (a, b) => a?.val === b?.val && (!a || verify(a.left, b.right) && verify(a.right, b.left)))(root.left, root.right);

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        queue = deque([root.left, root.right])
        
        while len(queue) > 0:           
            left = queue.popleft()
            right = queue.popleft()
            
            if left and right:
                if left.val != right.val:
                    return False
                
                queue.append(left.left)
                queue.append(right.right)
                queue.append(left.right)
                queue.append(right.left)
            elif left != right:
                return False
            
        return True

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        self.lefts = []
        self.inorder(root.left, 0)
        return self.reverseInorderCheck(root.right, 0, 0)[0]
    
    def inorder(self, node, level):
        if node is None:
            self.lefts.append((node, level))
            return
        
        self.inorder(node.left, level+1)
        self.lefts.append((node.val, level))
        self.inorder(node.right, level+1)
    
    def reverseInorderCheck(self, node, idx, level):
        if idx >= len(self.lefts):
            return [False, idx]
        
        if node is None and node == self.lefts[idx][0]:
            return [level == self.lefts[idx][1], idx+1]
        
        res, idx = self.reverseInorderCheck(node.right, idx, level+1)
        
        if not res:
            return [res, idx]
        
        check = self.lefts[idx]
        
        if check[0] != node.val or check[1] != level:
            return [False, idx]
        
        idx += 1
        
        return self.reverseInorderCheck(node.left, idx, level+1)