[C language brush leetcode] 1604. Warn people who use the same employee card more than or equal to three times within an hour (m)

【

All the employees in Li Kou company use employee cards to open the office door . Every time an employee uses his employee card , The security system records the name and time of use of the employee . If an employee uses the employee card more than or equal to three times in an hour , The system will automatically release a Warning  .

Here's an array of strings  keyName  and  keyTime , among  [keyName[i], keyTime[i]]  Corresponding to a person's name and where he is   One day The time of using the employee card in .

The format of using time is 24 hourly  , Form like  "HH:MM" , For example  "23:51" and  "09:49" .

Please return the name of the employee who received the system warning after de duplication , Press them Dictionary order, ascending order   Sort and return .

Please note that  "10:00" - "11:00"  Within an hour , and  "23:51" - "00:10"  Not considered within an hour , Because the system records the usage in a certain day .

Example 1：

Input ：keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output ：["daniel"]
explain ："daniel" Used in an hour 3 Second employee card （"10:00","10:40","11:00"）.
Example 2：

Input ：keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output ：["bob"]
explain ："bob" Used in an hour 3 Second employee card （"21:00","21:20","21:30"）.
Example 3：

Input ：keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]
Output ：[]
Example 4：

Input ：keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]
Output ：["clare","leslie"]
 

Tips ：

1 <= keyName.length, keyTime.length <= 105
keyName.length == keyTime.length
keyTime The format is  "HH:MM" .
Guarantee  [keyName[i], keyTime[i]]  The binary pair formed   Different from each other  .
1 <= keyName[i].length <= 10
keyName[i]  Only lowercase letters .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

】

This problem is really complicated , no UT-HASH I'm not sure , Skill points involved ：
1. String manipulation ： String comparison strcmp; String copy strcpy 

2. Time is converted into seconds
3. UTHASH String operation of ; Add and find ; And then there was HASH_SORT Sort ;HASH_ITER Traverse ;

4. Sort twice ,HASH_SORT and qsort

5. Condition judgment of swiping the card three times ：if (cur->ktime[i] - cur->ktime[i - 2] <= 60), Start traversing directly from the third time .

Ideas ：
First save everyone and clock in time UTHASH, The person's name is key, The time array size is set to 1000
Then sort by name
Then traverse the hash
Sort everyone's opening time
Calculate whether it meets the meaning of the question , Opened three times in an hour

typedef struct {
    char kname[11];
    int ktime[1000];
    int cnt;
    UT_hash_handle hh;
} UT_HASH;

int Getsec(char *str) {
    int hour, sec, ret;
    sscanf(str, "%d:%d", &hour, &sec);
    ret = hour * 60 + sec;
    return ret;
}

int Cmphash(UT_HASH *a, UT_HASH *b) {
    return strcmp(a->kname, b->kname);
}

int Cmpq(const void *a, const void *b) {
    int x = *(int *)a;
    int y = *(int *)b;
    return x - y;
}

char ** alertNames(char ** keyName, int keyNameSize, char ** keyTime, int keyTimeSize, int* returnSize){
    UT_HASH *mymap = NULL;
    char **retarr = (char **)malloc(sizeof(char *) * keyNameSize);
    int idx = 0;
    int i;

    for (i = 0; i < keyNameSize; i++) { //  Initialize array 
        retarr[i] = (char *)malloc(sizeof(char) * 11);
        memset(retarr[i], 0, sizeof(char) * 11);
    }

    for (i = 0; i < keyNameSize; i++) { //  Deposit in UTHASH
        UT_HASH *find = NULL;
        HASH_FIND_STR(mymap, keyName[i], find);
        if (find != NULL) {
            int tmpsec = Getsec(keyTime[i]);
            find->ktime[find->cnt++] = tmpsec;
        } else {
            UT_HASH *new = (UT_HASH *)malloc(sizeof(UT_HASH));
            strcpy(new->kname, keyName[i]);
            new->ktime[0] = Getsec(keyTime[i]);
            new->cnt = 1;
            HASH_ADD_STR(mymap, kname, new);
        }
    }

    HASH_SORT(mymap, Cmphash); //  By name hash Sort 

    UT_HASH *cur, *tmp;
    HASH_ITER(hh, mymap, cur, tmp) {  //  Traverse hash surface 
        if (cur->cnt < 3) {
            break; //  Open less than three times , immediate withdrawal 
        }
        qsort(cur->ktime, cur->cnt, sizeof(int), Cmpq);

        for (i = 2; i < cur->cnt; i++) {
            if (cur->ktime[i] - cur->ktime[i - 2] <= 60) { //  I swiped my card three times in an hour 
                strcpy(retarr[idx++], cur->kname);
                break;
            }
        }
    }

    *returnSize = idx;
    return retarr;
}

/*
 This problem is really complicated , no UT-HASH  I'm not sure , Skill points involved ：
1.  String comparison strcmp; String copy strcpy; Time is converted into seconds ;
2. UTHASH String operation of ; Add and find ; And then there was HASH_SORT Sort ;HASH_ITER Traverse ;

 Ideas ：
 First save everyone and clock in time UTHASH, The person's name is key, The time array size is set to 1000
 Then sort by name 
 Then traverse the hash 
 Sort everyone's opening time 
 Calculate whether it meets the meaning of the question , Opened three times in an hour 
*/