C语言 | Leetcode C语言题解之第399题除法求值

题目：

题解：

/*** Note: The returned array must be malloced, assume caller calls free().*/typedef struct hash_node_t
{char *key;double val;int distinguish_flag; // 用于区分不同的关系struct hash_node_t *p_next;
}HASH_NODE_T;typedef struct hash_t
{HASH_NODE_T **hash_arr;int size;
}HASH_T;HASH_T *hash_init(int size)
{HASH_T *hash_head = (HASH_T *)malloc(1 * sizeof(HASH_T));hash_head->hash_arr = (HASH_NODE_T **)calloc(26, sizeof(HASH_NODE_T *));hash_head->size = size;return hash_head;
}bool hash_compare(HASH_T *hash_head, char *key, char *key1)
{int distinguish_flag = 0, distinguish_flag1 = 0;int pos = key[0] % hash_head->size;int pos1 = key1[0] % hash_head->size;HASH_NODE_T *now_node = hash_head->hash_arr[pos];HASH_NODE_T *now_node1 = hash_head->hash_arr[pos1];while(now_node){if(!strcmp(now_node->key, key)){distinguish_flag = now_node->distinguish_flag;break;}now_node = now_node->p_next;}while(now_node1){if(!strcmp(now_node1->key, key1)){distinguish_flag1 = now_node1->distinguish_flag;break;}now_node1 = now_node1->p_next;}if(distinguish_flag == distinguish_flag1){return true;}return false;
}HASH_NODE_T *hash_find(HASH_T *hash_head, char *key)
{int pos = key[0] % hash_head->size;HASH_NODE_T *now_node = hash_head->hash_arr[pos];while(now_node){if(!strcmp(now_node->key, key)){break;}now_node = now_node->p_next;}return now_node;
}void hash_put(HASH_T *hash_head, char *key, double val, int distinguish_flag)
{int pos = key[0] % hash_head->size;HASH_NODE_T *now_node = hash_head->hash_arr[pos];HASH_NODE_T *new_node = NULL;if(NULL == hash_find(hash_head, key)) // 哈希表没有这个键值{new_node = (HASH_NODE_T *)malloc(1 * sizeof(HASH_NODE_T));new_node->key = key;new_node->val = val;new_node->distinguish_flag = distinguish_flag;new_node->p_next = now_node;hash_head->hash_arr[pos] = new_node;}
}void deal_flag_arr(char*** equations, int equationsSize, double* values, int *flag_arr, int index, HASH_T *hash_head, int distinguish_flag) // 优先处理后续有相关关系的方程
{double hash_val_0 = 0, hash_val_1 = 0; // 用于充当当前键值for(int i = 1; i < equationsSize; i++){if(flag_arr[i]){continue;}if(!strcmp(equations[i][0], equations[index][0])){hash_val_0 = hash_find(hash_head, equations[index][0])->val;hash_val_1 = hash_val_0 / values[i];}else if(!strcmp(equations[i][0], equations[index][1])){hash_val_0 = hash_find(hash_head, equations[index][1])->val;hash_val_1 = hash_val_0 / values[i];}else if(!strcmp(equations[i][1], equations[index][0])){hash_val_1 = hash_find(hash_head, equations[index][0])->val;hash_val_0 = hash_val_1 * values[i];}else if(!strcmp(equations[i][1], equations[index][1])){hash_val_1 = hash_find(hash_head, equations[index][1])->val;hash_val_0 = hash_val_1 * values[i];}else{continue;}flag_arr[i] = 1;hash_put(hash_head, equations[i][0], hash_val_0, distinguish_flag);hash_put(hash_head, equations[i][1], hash_val_1, distinguish_flag);deal_flag_arr(equations, equationsSize, values, flag_arr, i, hash_head, distinguish_flag); // 寻找后续是否存在已有的对应关系}
}double hash_node_val(HASH_T *hash_head, char *equations)
{double hash_val = 0;HASH_NODE_T *now_node = hash_find(hash_head, equations); // 当前哈希节点if(now_node){hash_val = now_node->val;}else{hash_val = -1;}return hash_val;
}double* calcEquation(char*** equations, int equationsSize, int* equationsColSize, double* values, int valuesSize, char*** queries, int queriesSize, int* queriesColSize, int* returnSize) {HASH_T *hash_head = hash_init(26);double *return_arr = (double *)malloc(queriesSize * sizeof(double));double hash_val_0 = 0, hash_val_1 = 0; // 用于充当当前键值int *flag_arr = (int *)calloc(equationsSize, sizeof(int)); // 用于记录该对应关系是否已经判断过*returnSize = queriesSize;int distinguish_flag = 0; // 用于区分不同的关系bool equation_flag = false; // 用于区分不同的关系for(int i = 0; i < equationsSize; i++) // 把所有已知对应关系放入哈希表{if(flag_arr[i]) // 跳过已经使用过的对应关系{continue;}distinguish_flag++;hash_val_0 = hash_node_val(hash_head, equations[i][0]);hash_val_1 = hash_node_val(hash_head, equations[i][1]);if(-1 == hash_val_0 && -1 == hash_val_1) // 键值计算{hash_val_1 = distinguish_flag;hash_val_0 = hash_val_1 * values[i];}else if(-1 == hash_val_0 && -1 != hash_val_1){distinguish_flag = hash_find(hash_head, equations[i][1])->distinguish_flag;hash_val_0 = hash_val_1 * values[i];}else if(-1 != hash_val_0 && -1 == hash_val_1){distinguish_flag = hash_find(hash_head, equations[i][0])->distinguish_flag;hash_val_1 = hash_val_0 / values[i];}hash_put(hash_head, equations[i][0], hash_val_0, distinguish_flag);hash_put(hash_head, equations[i][1], hash_val_1, distinguish_flag);deal_flag_arr(equations, equationsSize, values, flag_arr, i, hash_head, distinguish_flag); // 寻找后续是否存在已有的对应关系}for(int i = 0; i < queriesSize; i++) // 开始计算查询数据结果{equation_flag = hash_compare(hash_head, queries[i][0], queries[i][1]); // 比对二者是否处于同一个关系对应体系中if(!equation_flag){return_arr[i] = -1;continue;}hash_val_0 = hash_node_val(hash_head, queries[i][0]);hash_val_1 = hash_node_val(hash_head, queries[i][1]);if(-1 == hash_val_0 || -1 == hash_val_1) // 结果计算{return_arr[i] = -1;}else{return_arr[i] = hash_val_0 / hash_val_1;}}return return_arr;
}