1090. 受标签影响的最大值/ 698. 划分为k个相等的子集

1090. 受标签影响的最大值

• 相关标签 ： 贪心 哈希表

/*

1. 
qsort(labels , ... , cmp(values))
qsort(values, )

2. 
res = 0
idx = 0

findNext(labels, &idx)
    return next

curLabel

for (int )
{

}

while (num_wanted--) {

    curLabel = labels[idx]
    while ( labels[idx] == curLabel && use_limit-- ) {
        res += values[idx++]
    }
    if (labels[idx] == curLabel) {
        findNext(labels, &idx)
    }
}

*/

// void swap(int *a, int *b) 
// {
//     *a^=*b; 
//     *b^=*a; 
//     *a^=*b; 
// }

void swap(int *a, int *b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 

int partition(int *arr, int low , int high, int *labels)
{
    // i, j 
    int pi = arr[high];
    int i = low - 1;
    // [j ... low ... high -1] ---->  [ j > pi]pi[ j  < pi]
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] > pi) { // 把大的 swap 到 pivot 前面去 [low ... i] > pi 
            i++;
            swap(&arr[i], &arr[j]);
            swap(&labels[i], &labels[j]);
        }
    }
    // i + 1  < pi  --> swap 
    swap(&arr[i + 1], &arr[high]);
    swap(&labels[i +1], &labels[high]);
    return i + 1;
}

void quickSort(int *arr, int low , int high, int *labels)
{
    int pivot = 0;
    if (low < high) {
        pivot = partition(arr, low ,high, labels);
        quickSort(arr, low, pivot - 1, labels);
        quickSort(arr, pivot + 1, high, labels);   
    }
}

#define LABELHM 20001

int largestValsFromLabels(int* values, int valuesSize, int* labels, int labelsSize, int num_wanted, int use_limit){
    quickSort(values, 0, valuesSize -1, labels);
    // for (int i = 0; i < valuesSize; i++) {
    //     printf("%d-%d\n", values[i], labels[i]);
    // }
    int max = 0;
    int curLabel = 0;
    int idx = 0;
    int hmlabel[LABELHM] = {0};
    
    curLabel = -1;
    while (num_wanted && idx < valuesSize) {
        printf("idx:%d, label:%d hmlabel %d\n",idx, labels[idx], hmlabel[labels[idx]]);
        if (labels[idx] != curLabel) { // 遇到 新 label 就 吃 use_limit 个
            curLabel = labels[idx];
            for (int j = 0; j < use_limit && labels[idx] == curLabel && hmlabel[curLabel] < use_limit; j++) {
                printf("idx: %d - %d\n", idx, values[idx]);
                max += values[idx++];
                
                hmlabel[curLabel] += 1; //累计次数 
                num_wanted--;
                if (num_wanted == 0 || idx > valuesSize - 1) {
                    return max;
                }
            }
        } else {
            idx++;
        }
        
    }
    
    return max;
}

698. 划分为k个相等的子集

• 相关标签 ： 递归 动态规划

/*
1. qsort

2. 
sum 
1 2 2 3  不是个双指针 是个递归 

3. 一般递归会超时 

需要剪枝 


*/

int cmp(const void *a, const void *b)
{
    return *(int *)b - *(int *)a; // increase
}


bool rec(int* nums, int numsSize, int k, int *subsets, int cur, int subSum, int remain)
{
    if (cur == numsSize || remain == 0) {
        return true;
    }

    for (int i = 0; i < k; i++) { // 找坑
        
        if (subsets[i] + nums[cur] <= subSum) {
            subsets[i]  +=  nums[cur];
            if (rec(nums, numsSize, k, subsets, cur + 1, subSum, remain - nums[cur])) {
                return true;
            }
            subsets[i]  -=  nums[cur]; 
        }
    }
    return false;
}

bool canPartitionKSubsets(int* nums, int numsSize, int k){
    
    qsort(nums, numsSize, sizeof(int), cmp);
    
    int sum  = 0;
    int subSum = 0;
    for(int i =0; i < numsSize; i++) {
        printf("%d ", nums[i]);
        sum += nums[i];
    }
    if (sum % k != 0) {
        return false;
    }

    subSum = sum / k;
    // 递归 把 K个 集合填满
    int subsets[50] = {0};
    int cur = 0;
    while (nums[cur] == subSum && cur < numsSize) {
        cur++;
        k--;
    }
    return rec(nums, numsSize, k, subsets, cur, subSum, sum);
}