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

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] list = new ListNode[k];
        ListNode curr = head;
        int len = 0;
        while(curr!=null){
            len++;
            curr = curr.next;
        }
        curr = head;
        ListNode prev = curr;
        int n = len/k;
        int r = len%k;
        for(int i = 0;i<k;i++){
            int size = i<r? n+1:n;
            list[i] = curr;
            for(int j = 0; j<size;j++){
                prev = curr;
                curr = curr.next;
                if(j==size-1)
                    prev.next = null;                   
            }
        }
        return list;
    }
}

class Solution {
   public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        vector<ListNode*> res;
        ListNode* tmp = head;
        int n = 0;
        while (tmp) ++n, tmp = tmp->next;
        int div = n / k, mod = n % k;

        while (k) {
            tmp = head;
            for (int i = 1; i < div + (mod > 0); ++i) tmp = tmp->next;
            res.push_back(head);
            if (tmp) head = tmp->next, tmp->next = nullptr;
            --mod, --k;
        }

        return res;
    }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode[]}
 */
var splitListToParts = function(head, k) {
    const ans = [];
    let n = (() => {
        let t = head, len = 0;
        while (t) {
            len++;
            t = t.next;
        }
        return len;
    })();
    while (k > 0) {
        const t = new ListNode();
        let tt = t, sz = 0;
        for (; sz * k < n;) {
            tt.next = head;
            head = head.next;
            tt = tt.next;
            tt.next = null;
            sz++;
        }
        ans.push(t.next);
        k--;
        n -= sz;
    }
    return ans;
};

/**
 * 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[] splitListToParts(ListNode head, int k) {
        int len = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        while (head != null) {
            len++;
            queue.offer(head.val);
            head = head.next;
        }
        int div = len / k;
        int mod = len % k;
        ListNode[] heads = new ListNode[k];
        if (len < k) {
            for (int i = 0; i < k; i++) {
                int el = div;
                ListNode root = new ListNode();
                ListNode temp = root;
                while (el >= 0 && !queue.isEmpty()) {
                    temp.next = new ListNode(queue.poll());
                    temp = temp.next;
                    el--;
                }
                heads[i] = root.next;
            }
            return heads;
        }
        for (int i = 0; i < k; i++) {
            int el = div;
            ListNode root = new ListNode();
            ListNode temp = root;
            while (el > 0 && !queue.isEmpty()) {
                temp.next = new ListNode(queue.poll());
                temp = temp.next;
                el--;
            }
            if (mod > 0) {
                temp.next = new ListNode(queue.poll());
                temp = temp.next;
                mod--;
            }
            heads[i] = root.next;
        }
        return heads;
    }
}

type Node = Box<ListNode>;
impl Solution {
    pub fn split_list_to_parts(mut head: Option<Node>, k: i32) -> Vec<Option<Node>> {
        let (mut n, k) = (0, k as usize);
        let mut result: Vec<Option<Node>> = vec![];
        let mut p = head.as_ref();

        while let Some(node) = p {
            p = node.next.as_ref();
            n += 1;
        }

        let (q, r) = (n / k, n % k);

        fn build_sublist(mut head: Option<Node>, length: usize) -> (Option<Node>, Option<Node>) {
            let mut sentinel = Some(Box::new(ListNode::new(0)));
            let mut tail = sentinel.as_mut();

            for j in 0..length {
                if let Some(mut node) = head {
                    head = node.next.take();
                    tail =
                        tail.map(|tail| {
                            tail.next = Some(node);
                            tail
                        });
                    tail = tail.and_then(|tail| tail.next.as_mut());
                }
            }

            let subhead = sentinel.and_then(|mut sen| sen.next.take());

            (head, subhead)
        }

        for i in 0..r {
            let (new_head, subhead) = build_sublist(head.take(), q + 1);
            head = new_head;

            result.push(subhead);
        }

        for i in r..k {
            let (new_head, subhead) = build_sublist(head.take(), q);
            head = new_head;

            result.push(subhead);
        }

        result
    }
}

impl Solution {
    fn len(head: &Option<Box<ListNode>>) -> i32 {
        let (mut current, mut n) = (head, 0);
        while let Some(node) = current {
            n += 1;
            current = &node.next;
        }
        n
    }
    pub fn split_list_to_parts(head: Option<Box<ListNode>>, k: i32) -> Vec<Option<Box<ListNode>>> {
        let (n, mut current) = (Self::len(&head), head);
        let (q, r) = (n / k, n % k);
        let parts = &mut Vec::new();
        for i in 0..k {
            let mut head = current.take();
            let mut tail = &mut head;
            let part_len = if i < r { q + 1 } else { q };
            for _ in 0..(part_len - 1) {
                if tail.is_some() {
                    tail = &mut tail.as_mut().unwrap().next;    
                }
            }
            if tail.is_some() {
                current = tail.as_mut().unwrap().next.take();
            }
            parts.push(head);
        }
        parts.to_owned()
    }
}

class Solution {
    public int maxPossibleScore(int[] start, int d) {
        int n = start.length;
    
        //boundary: min = 0, max = start[max]+d - start[min];
        Arrays.sort(start);
    
        int l =0;
        int r = start[n-1]+d-start[0];
    
        while(l<r){
            int mid=(int)Math.ceil(l + (double)(r-l)/2);
            if(condition(start, d,mid)){
                l = mid;
            }
            else{
                r=mid-1;
            }
        }
        return r;
    }
    private boolean condition(int[] start, int d, int num){
    
        long last_chosen = start[0];
        for(int i =1 ;i < start.length;i++){
            long in_range = last_chosen + num;
            if(in_range <= start[i]) {
                last_chosen = start[i];
            }
            else if(in_range<=(long)start[i]+d){
                last_chosen = in_range;
            }
            else return false;
        }
        return true;
    }
}

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int n = 0;
        ListNode curr = head;
        while (curr != null) {
            n++;
            curr = curr.next;
        }

        ListNode[] res = new ListNode[k];
        int idx = 0, temp = k;
        curr = head;
        while (idx < k) {
            res[idx++] = curr;

            int count = (n - 1) / temp + 1;
            for (int i = 1; i < count; i++) {
                if (curr != null) {
                    curr = curr.next;
                }
            }
            if (curr != null) {
                ListNode next = curr.next;
                curr.next = null;
                curr = next;
            }
            n -= count;
            temp--;
        }
        return res;
    }
}