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

impl Solution {
    pub fn find_the_winner(n: i32, k: i32) -> i32 {
        fn g(n: i32, k: i32) -> i32 {
            match n {
                1 => 0,
                _ => (g(n - 1, k) + k) % n
            }
        }

        g(n, k) + 1
    }
}

public class Solution {
    public int FindTheWinner(int n, int k) {
        Queue<int> q = new Queue<int>();
        for(int i = 1; i <= n; i++)
            q.Enqueue(i);
        int temp = 0;
        while(q.Count > 1)
        {
            temp++;
            if(temp == k)
            {
                temp = 0;
                q.Dequeue();
            }
            else
                q.Enqueue(q.Dequeue());
        }
        return q.Dequeue();
    }
}

impl Solution {
    pub fn find_the_winner(n: i32, k: i32) -> i32 {
        if n == 1 {
            1
        } else {
            (Self::find_the_winner(n - 1, k) + k - 1) % n + 1
        }
    }
}

impl Solution {
    pub fn find_the_winner(n: i32, k: i32) -> i32 {
        (1..n).fold(1, |a, i| {
            (a + k - 1) % (i + 1) + 1
        })
    }
}

// Problem: https://leetcode.com/problems/find-the-winner-of-the-circular-game/
class Solution {
    // solution 2: using array with a little imagination
    func findTheWinner(_ n: Int, _ k: Int) -> Int {
        var nums = Array(1...n)
        var step = 0
        while nums.count > 1 {
            step = (step + k - 1) % nums.count
            nums.remove(at: step)
        }
        return nums[0]
    }
}

public class Solution
{
    public int FindTheWinner(int n, int k)
    {
        Node root = new();
        root.val = 1;
        Node prev = null;
        Node current = root;
        for (int i = 1; i <= n; i++)
        {
            if (current == null)
            {
                current = new();
            }
            current.val = i % (n + 1);

            if (prev != null)
            {
                current.prev = prev;
                prev.next = current;
            }

            prev = current;
            current = current.next;
        }
        prev.next = root;
        root.prev = prev;
        
        Node pointer = root;
        for (int i = n; 1 < i; i--)
        {
            Node remove = null;
            int travel = k % i - 1;
            if (travel == -1)
            {
                remove = pointer.prev;
                goto Remove;
            }
            
            for (int j = 0; j < travel; j++)
            {
                pointer = pointer.next;
            }
            remove = pointer;
            pointer = pointer.next;

            Remove:
            remove.prev.next = pointer;
            pointer.prev = remove.prev;
            remove.prev = null;
            remove.next = null;
        }

        return pointer.val;
    }

    public class Node
    {
        public int val;
        public Node prev;
        public Node next;
    }
}

class Solution {
    public int findTheWinner(int n, int k) {
        ArrayList<Integer> nums = new ArrayList<>();
        for(int i =1;i<=n;i++) nums.add(i);
        int index = 0;
        while(nums.size()!=1){
            int size = nums.size();
            index = (index+k)%size-1;
            if(index<0) index+=size;
            nums.remove(index);
        }
        return nums.get(0);
    }
}

class Solution {
public:
    int findTheWinner(int n, int k) {
        queue<int> q;
        for(int i = 1; i<=n; i++) q.push(i);
        while(q.size() > 1){
            int turn = k - 1;
            while(turn--){
                q.push(q.front());
                q.pop();
            }
            q.pop();
        }
        return q.front();
    }
};

function findTheWinner(n: number, k: number): number {
    let res = 0;
    for (let i = 2; i <= n; i++){
        res = (res + k) % i;
    }
    return res + 1;
};

use std::rc::Rc;
use std::cell::RefCell;
use std::mem;

struct Codec {}

type Elem = (i32, usize, usize);
type Node = Rc<RefCell<TreeNode>>;

impl Codec {
    fn new() -> Self {
        Codec {}
    }

    fn serialize(&self, root: Option<Node>) -> String {
        struct Id(usize);

        impl Id {
            pub fn new(start: usize) -> Self {
                Id(start)
            }

            pub fn get(&self) -> usize {
                self.0
            }

            pub fn increase(&mut self) {
                self.0 += 1;
            }
        }

        fn count(node: Option<&Node>) -> usize {
            match node {
                Some(node) => {
                    let mut result = 1;

                    result += count(node.borrow().left.as_ref());
                    result += count(node.borrow().right.as_ref());

                    result
                },
                None => 0
            }
        }

        fn build(node: Option<Node>, serialized: &mut Vec<Elem>, id_struct: &mut Id) -> usize {
            match node {
                Some(node) => {
                    let (id, val, mut left_id, mut right_id) = (id_struct.get(), node.borrow().val, 0, 0);

                    id_struct.increase();

                    node.borrow_mut().left.take().map(|left| {
                        left_id = build(Some(left), serialized, id_struct);
                    });

                    node.borrow_mut().right.take().map(|right| {
                        right_id = build(Some(right), serialized, id_struct);
                    });

                    serialized[id] = (val, left_id, right_id);

                    id
                },
                None => 0
            }
        }

        let n = count(root.as_ref());

        let (mut serialized, mut id_struct) = (vec![(0, 0, 0); n], Id::new(0));

        build(root, &mut serialized, &mut id_struct);

        unsafe {
            let (og_len, og_cap, og_size) = (serialized.len(), serialized.capacity(), mem::size_of::<Elem>());
            let ptr_serialized = mem::ManuallyDrop::new(serialized).as_mut_ptr();
            let bytes = Vec::from_raw_parts(ptr_serialized as *mut u8, og_len * og_size, og_cap * og_size);

            String::from_utf8_unchecked(bytes)
        }
    }

    fn deserialize(&self, data: String) -> Option<Node> {
        let bytes = data.into_bytes();

        let serialized =
            unsafe {
                let (len, cap, og_size) = (bytes.len(), bytes.capacity(), mem::size_of::<Elem>());
                let ptr_serialized = mem::ManuallyDrop::new(bytes).as_mut_ptr();

                Vec::from_raw_parts(ptr_serialized as *mut Elem, len / og_size, cap / og_size)
            };

        fn build_tree(id: usize, serialized: &Vec<Elem>) -> Node {
            let (val, left_id, right_id) = serialized[id];

            let mut node = TreeNode::new(val);

            if left_id != 0 {
                node.left = Some(build_tree(left_id, serialized));
            }

            if right_id != 0 {
                node.right = Some(build_tree(right_id, serialized));
            }

            Rc::new(RefCell::new(node))
        }

        if serialized.len() > 0 {
            Some(build_tree(0, &serialized))
        } else {
            None
        }
    }
}

class Solution {
    public int findTheWinner(int n, int k) {
        Queue<Integer> fencies = IntStream.rangeClosed(1, n).boxed().collect(Collectors.toCollection(LinkedList::new));

        while (fencies.size() > 1) {
            IntStream.range(0, k - 1).forEach(i -> fencies.offer(fencies.poll()));
            fencies.poll();
        }

        return fencies.poll();
    }
}

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        # original:      0 1   2   ... k-1 k k+1 ... i   ... n-1
        # delete k:      0 1   2   ... k-1   k+1 ... i   ... n-1
        # reroot at k+1: -k 1-k 2-k ... -1    0   ... i-k ... n-1-k

        def winner(n):
            if n == 1:
                return 0
            return (k + winner(n - 1)) % n
        return winner(n) + 1

impl Solution {
    pub fn find_the_winner(n: i32, k: i32) -> i32 {
        let mut winner_index = 0;
        for i in 1..=n {
            winner_index = (winner_index + k) % i;
        }
        winner_index + 1
    }
}

class Solution {
public:
    int findTheWinner(int n, int k) {
        queue <int> nums;
        for(int i = 1; i <= n; i++) nums.push(i);
        while (nums.size() > 1){
            int steps = k - 1;
            while(steps--) {
                nums.push(nums.front());
                nums.pop();
            }
            nums.pop();
        }
        return nums.front();
    }
};

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        q = deque()
        for i in range(1 , n + 1): q.append(i)

        while len(q) > 1:
            for i in range(k - 1):
                num = q.popleft()
                q.append(num)

            q.popleft()
       
        return q[0]

class Solution {
public:
    double averageWaitingTime(vector<vector<int>>& customers) {
        int time = 0;
        double ans = 0;
        ans += customers[0][1];
        time += customers[0][0] + customers[0][1];
        if(customers.size() == 1)
            return ans;
        cout << "time: " << time << " ans: " << ans << '\n';
        for(int i = 1; i < customers.size(); i++) {
            if(customers[i][0] <= time) {
                ans += (time - customers[i][0] + customers[i][1]);
            }
            else {
                ans += customers[i][1];
            }
            time = customers[i][1] + max(time, customers[i][0]);
            cout << "time: " << time << " ans: " << ans << '\n';
        }
        return ans / customers.size();
    }
};

function averageWaitingTime(c: number[][]): number {
    let total = 0, cur = c[0][0], n = c.length;
    for (const [u, v] of c) {
        if (cur < u) cur = u + v;
        else cur+= v;
        total+= cur - u;
    }
    return total / n
};