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

class Solution {
    fun maxDistance(position: IntArray, m: Int): Int {
        position.sort()

        val ok = { f: Int ->
            var c = 1
            var lastpos = position.first()
            for (p in position) {
                if (p - lastpos < f) continue

                c += 1
                lastpos = p
            }
            c >= m
        }

        var l = 1
        var h = (position.last() - position.first()) / (m - 1)
        while (l < h) {
            val mid = (l + h) / 2 + 1
            if (ok(mid)) l = mid else h = mid - 1
        }

        return l
    }
}

use std::{cmp::Ordering, ops::Range};

trait BinarySearch<F, Idx>
where
    F: FnMut(Idx) -> Ordering
{
    fn binary_search_by(&self, f: F) -> Result<Idx, Idx>;

    fn binary_search_min_by(&self, f: F) -> Idx;

    fn binary_search_max_by(&self, f: F) -> Idx;
}

macro_rules! impl_binary_search_for_range {
    ($($t:ty)*) => ($(
        impl<F> BinarySearch<F, $t> for Range<$t>
        where F: FnMut($t) -> Ordering,
        {
            fn binary_search_by(&self, mut f: F) -> Result<$t, $t> {
                let mut left = self.start;
                let mut right = self.end;

                while left < right {
                    let middle = left + (right - left) / 2;

                    match f(middle) {
                        Ordering::Equal => return Ok(middle),
                        Ordering::Less => left = middle + 1,
                        Ordering::Greater => right = middle
                    }
                }

                Err(left)
            }

            fn binary_search_min_by(&self, mut f: F) -> $t {
                let search_result =
                    Self::binary_search_by(&self, |index| {
                        match f(index) {
                            Ordering::Equal => Ordering::Greater,
                            other => other
                        }
                    });

                search_result.unwrap_or_else(|i| i)
            }

            fn binary_search_max_by(&self, mut f: F) -> $t {
                let search_result =
                    Self::binary_search_by(&self, |index| {
                        match f(index) {
                            Ordering::Equal => Ordering::Less,
                            other => other
                        }
                    });

                search_result.unwrap_or_else(|i| i)
            }
        }
    )*)
}

impl_binary_search_for_range!{ i32 }

impl Solution {
    pub fn max_distance(mut position: Vec<i32>, m: i32) -> i32 {
        position.sort_unstable();
        let n = position.len();
        let max_pos = position[n - 1];
        let hi = (max_pos / (m - 1)) + (max_pos % (m - 1) != 0) as i32 + 1;
        let mut answer = 0;

        (1..hi).binary_search_max_by(|min_dist| {
            let mut ball_count = 1;
            let mut last_ball_pos = position[0];

            for &pos in position.iter().skip(1) {
                if pos - last_ball_pos >= min_dist {
                    ball_count += 1;
                    last_ball_pos = pos;
                }
            }

            if ball_count >= m {
                answer = min_dist;
            }

            m.cmp(&ball_count)
        });

        answer
    }
}

 while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (canMakeBouquets(bloomDay, m, k, mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    while (low <= high) {
        const mid = low + Math.floor((high - low) / 2);
        if (can(mid)) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        def check(k):
            count, prev = 1, position[0]
            for pos in position[1:]:
                if pos - prev >= k:
                    count += 1
                    if count >= m:
                        return True
                    prev = pos
        l,h = 0, position[-1] - position[0] + 1
        while l < h - 1:
            pivot = l + (h-l+1)//2
            if check(pivot):
                l = pivot
            else:
                h = pivot
        return l

public class Solution {
    public bool IsValid(int[] position, int mid, int m)
    {
        int count = 1;
        int previous = position[0];
        for(int i = 1; i<position.Length; i++)
        {
            if(position[i] - previous >= mid)
            {
                count++;
                previous = position[i];
            }
            if(count == m)
                return true;
        }
        return false;
    }

    public int MaxDistance(int[] position, int m) {
        int left = 0;
        int right = position.Max(p => p);
        int mid = 0;
        int result = 0;
        Array.Sort(position);
        while(left <= right)
        {
            mid = (left + right)/2;
            if(IsValid(position, mid, m))
            {
                left = mid + 1;
                result = mid;
            }
            else
            {
                right = mid - 1;
            }
        }
        return result;
    }
}

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        l , r = 0 , position[-1] - position[0]

        def check(x):
            cnt = 0
            prev = position[0]
            for i in range(1 , len(position)):
                if position[i] - prev >= x:
                    cnt += 1
                    prev = position[i]
                if cnt + 1 == m: return True

            return False

        res = -1
        while l <= r:
            mid = (l + r) // 2
            if check(mid):
                res = mid
                l = mid + 1
            else: r = mid - 1
        
        return res