当前位置：首页 > news >正文

1679. K 和数对的最大数目-自定义哈希表解决

news 来源：原创 2024/4/29 0:33:21

1679. K 和数对的最大数目-自定义哈希表解决

给你一个整数数组 nums 和一个整数 k 。

每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。

返回你可以对数组执行的最大操作数。

示例 1：

输入：nums = [1,2,3,4], k = 5
输出：2
解释：开始时 nums = [1,2,3,4]：

移出 1 和 4 ，之后 nums = [2,3]
移出 2 和 3 ，之后 nums = []
不再有和为 5 的数对，因此最多执行 2 次操作。

示例 2：

输入：nums = [3,1,3,4,3], k = 6
输出：1
解释：开始时 nums = [3,1,3,4,3]：

移出前两个 3 ，之后nums = [1,4,3]
不再有和为 6 的数对，因此最多执行 1 次操作。

博主感觉今天有点倒霉，题目都好复杂，解题代码如下：

#define size 1000
struct hash{
    int val;
  int count;
    struct hash *next;
};
void hash_add(struct hash *h,int val,int count){
    struct hash *p=(struct hash *)malloc(sizeof(struct hash));
    p->val=val;
     p->count=count;
  
    p->next=h->next;
    h->next=p;
}


bool  hash_find(struct hash *h,int val){
     struct hash *p=h->next;
     while(p){
         if(p->val==val&&p->count>=1)return true;
         p=p->next;
     }
     return false;
}
bool  hash_find2(struct hash *h,int val){
     struct hash *p=h->next;
     while(p){
         if(p->val==val)return true;
         p=p->next;
     }
     return false;
}
void  hash_count_add(struct hash *h,int val){
     struct hash *p=h->next;
     while(p){
         if(p->val==val){
              p->count++;
              break;

         }
        
         p=p->next;
     }
     return false;
}

void  hash_count_sub(struct hash *h,int val){
     struct hash *p=h->next;
     while(p){
         if(p->val==val){
              p->count--;
              break;

         }
        
         p=p->next;
     }
   
}

int maxOperations(int* nums, int numsSize, int k){
      struct hash *h=(struct hash *)malloc(sizeof(struct hash)*size);
      int i,j;
    
   
    for(i=0;i<size;i++){
       (h+i)->next=NULL;
    }
    int re=0;
    for(int i=0;i<numsSize;i++){
        if(nums[i]<=k){
         //   printf("* ");
            if(hash_find(h+(k-nums[i])%size,k-nums[i])){
                re++;
                hash_count_sub(h+(k-nums[i])%size,k-nums[i]);
                  continue;

            }
          
         }
        if(!hash_find2(h+nums[i]%size,nums[i])){
            hash_add(h+nums[i]%size,nums[i],1);
          //  printf("%d ",nums[i]);

        }
        else{
             hash_count_add(h+nums[i]%size,nums[i]);

        }

    }

    for(i=0;i<size;i++){
        struct hash *p=(h+i)->next;
        while(p){
            printf("%d ",p->val);
            p=p->next;
        }
    }
return re;
}