thảo luận [Học Tập] Topic thuật toán

func numTeams(rating []int) int {
    total := len(rating)
    if total < 3 {
        return 0
    }
    
    teams := 0
    for i, rate := range rating {
        // travel left and right
        for l := 0; l < i; l++ {
            for r := i + 1; r < total; r ++ {
                // check cond 1
                if rating[l] < rate && rate < rating[r] {
                    teams ++
                }
                // check cond 2
                if rating[l] > rate && rate > rating[r] {
                    teams ++
                }
            }
        }
    }
    
    return teams
}

//Chạy bằng hàm này
function countSolution(){
    var arr = //dãy số bạn nhập vào;
    var target = //đơn giản là target;
    var sum = 0;
    arr.forEach(i=> sum +=i);
    if((sum - target) % 2 != 0){
        return 0;
    }
    target = (sum - target) / 2;
    var groups = groupNumber(arr);
    var resolutionCount = 0;
    arrResInitial = [];
    res = evaluate(groups, groups.length - 1, target, arrResInitial, resolutionCount);
    return res;
}

//hàm biến chuỗi ban đầu thành 1 dạng chuỗi thống kê
function groupNumber(arr){
    var groups = {};
    for (var i of arr){
        if(groups[i]){
            groups[i] ++;
        }else{
            groups[i] = 1;
        }
    }
    var res = []
    for(var i in groups){
        res.push({num: parseInt(i), count: groups[i]});
    }
    return res;
}

//hàm xác định xem phương án có khả thi hay không
function evaluate(groups, index, target, arrResInitial, resolutionCount){
    var num = groups[index].num;
    var max =  Math.floor(target/num);
    var count = groups[index].count < max ? groups[index].count : max;
    for(var i = 0; i<=count; i++){
        actionCount++
        var arrRes = JSON.parse(JSON.stringify(arrResInitial));
        multiRes = i*num;
        arrRes.push({num:num, multiplier: i, pop: groups[index].count});
        if(multiRes == target){
            resolutionCount += multiplyPosibilities(arrRes);
        }else if(multiRes < target){
            if(index > 0){
                resolutionCount += evaluate(groups, index - 1, target - num*i, arrRes, resolutionCount);
            }
        }
    }
    return resolutionCount;
}

//hàm nhân mấy cái tổ hợp
function multiplyPosibilities(arrRes){
    var res = 1;
    for(var item of arrRes){
        res = res * quickMath(item.pop, item.multiplier);
    }
    return res;
}

//hàm tính số lượng các tổ hợp. Naming luôn là 1 vấn đề đau đầu
function quickMath(pop, picked){
    var small = picked > (pop - picked) ? picked : (pop - picked);
    if(small == pop){
        return 1;
    }
    var leftOver = pop - small;
    var res = 1;
    for(var i = small + 1; i <= pop; i++){
        res *= i;
    }
    for(var i = 1; i <= leftOver; i++){
        res = res / i;
    }
    return res;
}