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

function numTeams(rating: number[]): number {
    let count = 0;
    for (let i = 0; i < rating.length; i++) {
        let lSmaller = 0, lGreater = 0, rSmaller = 0, rGreater = 0;
        for (let j = 0; j < i; j++) {
            if (rating[j] < rating[i]) lSmaller++;
            if (rating[j] > rating[i]) lGreater++;
        }
        for (let j = i + 1; j < rating.length; j++) {
            if (rating[j] < rating[i]) rSmaller++;
            if (rating[j] > rating[i]) rGreater++;
        }
        count+= lSmaller * rGreater + lGreater * rSmaller;
    }
    return count;
};

class Solution:
    def numTeams(self, r: List[int]) -> int:
        n = len(r)
        ans = 0
        for i in range(n):
            left_less, left_greater, right_less, right_greater = 0,0,0,0
            for j in range(i):
                if r[j] < r[i]:
                    left_less += 1
                else:
                    left_greater += 1
            for k in range(i + 1, n):
                if r[k] < r[i]:
                    right_less += 1
                else:
                    right_greater += 1
            ans += left_less * right_greater + left_greater * right_less
        return ans

class Solution {
    public int numTeams(int[] rating) {
        int n = rating.length;
        int[] leftLess = new int[n];
        int[] leftGreater = new int[n];
        int[] rightLess = new int[n];
        int[] rightGreater = new int[n];
        
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (rating[j] < rating[i])
                    leftLess[i]++;
                else
                    leftGreater[i]++;
            }
        }
        for (int i = n - 2; i >= 0; i--)
        {
            for (int j = n - 1; j > i; j--)
             {
                if (rating[j] < rating[i])
                    rightLess[i]++;
                else
                    rightGreater[i]++;
             }
        }
        
        int ans = 0;
        for (int i = 1; i < n - 1; i++)
        {
            ans += leftLess[i] * rightGreater[i] + leftGreater[i] * rightLess[i];
        }
        return ans;
    }
}

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        def numTrio(nums):
            n = len(rating)
            ans = 0
            for i in range(1, n - 1):
                smallerCount = sum(nums[j] < nums[i] for j in range(i))
                largerCount = sum(nums[j] > nums[i] for j in range(i + 1, n))
                ans += smallerCount * largerCount
            return ans
        
        return numTrio(rating) + numTrio(rating[::-1])

def num_teams(rating)
  res = 0
  len = rating.length - 1
  len.times.each do |i|
    left_smaller, left_larger, right_smaller, right_larger = 0, 0, 0, 0
    (0..i).each do |j|
      left_larger += 1 if rating[i] < rating[j]
      left_smaller += 1 if rating[i] > rating[j]
    end

    (i+1..len).each do |k|
      right_smaller += 1 if rating[k] < rating[i]
      right_larger += 1 if rating[k] > rating[i]
    end

    res += (left_smaller * right_larger) + (left_larger * right_smaller)
  end

  res
end

class Solution {
    public int numTeams(int[] rating) {
        int n = rating.length;
        int ans = 0;

        int[] acs = new int[n];
        int[] decs = new int[n];

        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (rating[j] < rating[i]) {
                    ans += acs[j];
                    acs[i]++;
                } else if (rating[j] > rating[i]) {
                    ans += decs[j];
                    decs[i]++;
                }
            }
        }

        return ans;
    }
}

class Solution {
    public static final int INCREASE = -1;
    public static final int DECREASE = 1;

    public int numTeams(int[] rating) {
        return calculateTeam(rating, INCREASE) + calculateTeam(rating, DECREASE);
    }

    public int calculateTeam(int[] rating, int order) {
        int n = rating.length;
        int[] teamWith2MemberEndAt = new int[n];
        int[] teamWith3MemberEndAt = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ((rating[i] - rating[j]) * order > 0) {
                    teamWith2MemberEndAt[i]++;
                }
            }
        }

        int numTeams = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ((rating[i] - rating[j]) * order > 0) {
                    teamWith3MemberEndAt[i] += teamWith2MemberEndAt[j];
                }
            }
            numTeams += teamWith3MemberEndAt[i];
        }

        return numTeams;
    }
}

class Solution {
    public int numTeams(int[] rating) {
        int n = rating.length;
        int teams = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if ((rating[i] > rating[j] && rating[j] > rating[k]) ||
                        (rating[i] < rating[j] && rating[j] < rating[k])) {
                        teams++;
                    }
                }
            }
        }
        return teams;
    }
}

use std::ops::{ Add, Sub };

struct FenwickTree<T> {
    bit: Vec<T>
}

impl<T: Add<T, Output = T> + Sub<T, Output = T> + Copy> FenwickTree<T>
{
    pub fn new(data: Vec<T>) -> Self {
        let n = data.len();
        let mut bit = data;

        for i in 0..n {
            let pr = Self::parent(i);

            if pr < n {
                bit[pr] = bit[pr] + bit[i];
            }
        }

        Self {
            bit: bit
        }
    }

    pub fn sum(&self, mut i: usize) -> T {
        let mut result = self.bit[i];

        while Self::lower_bound(i) > 0 {
            i = Self::lower_bound(i) - 1;
            result = result + self.bit[i];
        }

        result
    }

    pub fn range_sum(&self, left: usize, right: usize) -> T {
        self.sum(right) - self.sum(left - 1)
    }

    pub fn add(&mut self, mut i: usize, delta: T) {
        let n = self.bit.len();

        while i < n {
            self.bit[i] = self.bit[i] + delta;
            i = Self::parent(i);
        }
    }

    #[inline(always)]
    fn lower_bound(i: usize) -> usize {
        i & (i + 1)
    }

    #[inline(always)]
    fn parent(i: usize) -> usize {
        i | (i + 1)
    }
}

impl Solution {
    pub fn num_teams(rating: Vec<i32>) -> i32 {
        let max =
            rating.iter().fold(i32::MIN, |max, &num| max.max(num)) as usize;

        let mut ft_left = FenwickTree::new(vec![0; max + 1]);
        let mut ft_right = FenwickTree::new(vec![0; max + 1]);

        for &r in &rating {
            ft_right.add(r as usize, 1);
        }

        let mut team_count = 0;
        for &r in &rating{
            ft_right.add(r as usize, -1);

            let (left_smaller, right_smaller) =
                (ft_left.sum(r as usize - 1), ft_right.sum(r as usize - 1));

            let (left_greater, right_greater) =
                (ft_left.range_sum(r as usize + 1, max), ft_right.range_sum(r as usize + 1, max));

            team_count += left_smaller * right_greater + left_greater * right_smaller;

            ft_left.add(r as usize, 1);
        }

        team_count
    }
}

impl Solution {
    pub fn num_teams(rating: Vec<i32>) -> i32 {
        let n = rating.len();
        if n < 3 || n > 1000 {
            unsafe { core::hint::unreachable_unchecked() }
        }
        let mut left_lower_count;
        let left_lower_count = {
            left_lower_count = vec![0; n];
            left_lower_count.as_mut_slice()
        };
        let mut left_higher_count;
        let left_higher_count = {
            left_higher_count = vec![0; n];
            left_higher_count.as_mut_slice()
        };
        let mut team_count = 0;
        for i in 1..n {
            for j in 0..i {
                if rating[j] < rating[i] {
                    team_count += left_lower_count[j];
                    left_lower_count[i] += 1;
                } else if rating[j] > rating[i] {
                    team_count += left_higher_count[j];
                    left_higher_count[i] += 1;
                }
            }
        }
        team_count
    }
}