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

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        dummy=ListNode(next=head)
        cur=head
        last_s=dummy    #keep track of last small node
        last_b=dummy    #keep track of last big node
        while cur:
            next_node=cur.next
            if cur.val<x:         
                if cur!=last_s.next:    # move current node to next of last small
                    tmp=last_s.next
                    last_s.next=cur
                    last_b.next=cur.next   
                    cur.next=tmp
                last_s=cur
            else:   
                last_b=cur
            cur=next_node
        return dummy.next

// https://www.internalpointers.com/post/writing-custom-iterators-modern-cpp
struct Iterator
{
    using iterator_category = std::forward_iterator_tag;
    using difference_type   = std::ptrdiff_t;
    using value_type        = int;
    using pointer           = int*;
    using reference         = int&;
 
 
    Iterator(ListNode* ptr) : m_ptr(ptr) {}
 
    reference operator*() const { return m_ptr->val; }
    pointer operator->() { return &m_ptr->val; }

    // Prefix increment
    Iterator& operator++() { m_ptr = m_ptr->next; return *this; }

    // Postfix increment
    Iterator operator++(int) { Iterator tmp = *this; ++(*this); return tmp; }

    friend bool operator== (const Iterator& a, const Iterator& b) { return a.m_ptr == b.m_ptr; };
    friend bool operator!= (const Iterator& a, const Iterator& b) { return a.m_ptr != b.m_ptr; };  

    ListNode* m_ptr;
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        std::stable_partition<Iterator>(head, nullptr, [x](int n) { return n < x; });
        return head;
    }
};

public class Solution {
    public IList<int> CountSmaller(int[] nums) {
        SortedSet<int> set = new ();
        foreach (var num in nums)
            set.Add(num);
      
        Dictionary<int, int> indexes = new ();
        int len = 0;
        foreach (var num in set)
        {
            indexes[num] = len++;
        }
      
        int[] BIT = new int[len+1];
        int[] ret = new int[nums.Length];
        for (var i = nums.Length - 1; i >= 0; i--)
        {
            int index = indexes[nums[i]];
            ret[i] = sum(BIT, index-1);
            update(BIT, index, 1);
        }
      
        return ret;
    }
  
    void update(int[] BIT, int index, int val)
    {
        index = index + 1;
        while (index < BIT.Length)
        {
            BIT[index] += val;
            index += index & (-index);
        }
    }
  
    int sum(int[] BIT, int index)
    {
        int sum = 0;
        index = index + 1;
        while (index > 0)
        {
            sum += BIT[index];
            index -= index & (-index);
        }
        return sum;
    }
}