力扣上C语言编程题

  一. 简介

本文简单记录一下力扣上 C语言编程题。作为自己做题笔记。

二. 力扣上 C 语言编程题

1. 从数组中找到两个元素之和，等于一个 target目标值

具体题目说明：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

C语言实现如下：

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int i, j;int* ret_buf = (int*)malloc(2 * sizeof(int));for(i = 0; i < numsSize; i++) {for(j = i+1; j < numsSize; j++) {if((nums[i] + nums[j]) == target) {ret_buf[0] = i;ret_buf[1] = j;*returnSize = 2;return ret_buf;}}}*returnSize = 0;return NULL;
}

2. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

题目分析：

(1) 什么是字母异位词？

字母异位词指的是由相同字母重新排列组合而成的不同单词或短语。

(2) 解题思路：

字母异位词排序后的字符串是相同的，可以利用排序后的字符串相同进行分组。

排序后的字符串作为哈希表中某一个桶的标志。

具体方法如下：

1) 创建节点结构体和哈希表

2）对每个字符串进行排序，再逐个插入哈希表中（排序后的字符串作为哈希表中的键，对应的字符串作为值）；

3）遍历哈希表，获取哈希表中桶数量，即位所输出的二维数组的元素数目returnSize ；

4）将哈希表中元素逐个拷贝到返回值 buf 中，将二维数组中每个组的元素数目也拷贝到返回值中 returnColumnSizes；

代码实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>//定义字符串最大长度
#define  STR_LENGTH  200
//定义哈希表大小
#define  HASH_SIZE  10005typedef struct hash_node{//key为桶的标志（排序后的字符串作为key）char key[STR_LENGTH]; //存放键值key对应的字符串（因为一个key对应多个字符串，所以需要二维数组）char** group;  //group中字符串的个数 int group_size;//创建链表用（为了解决不同key映射到同一个位置时的冲突）struct hash_node* next;
} hash_node;hash_node* hash_table[HASH_SIZE];//对字符串进行排序，排序后的字符串作为哈希表的key
int str_sort(const void* a, const void* b) {const char* tmp_a = (const char*)a;const char* tmp_b = (const char*)b;return *tmp_a - *tmp_b;
}//计算哈希值的函数
int hash_function(const char* key) {int ch = 0;//数学证明这个数字更难发生冲突unsigned int hash_value = 5381;while(ch = *key++) {hash_value = ((hash_value << 5) + hash_value) % HASH_SIZE;}return hash_value;
}int insert_hash(char* key, char* str) {if(!key || !str) {return -1;}//通过哈希函数计算哈希值int position = hash_function(key);hash_node* node = hash_table[position];//判断键值key在哈希表中是否已存在while(node) {if(strcmp(node->key, key) == 0) {node->group[node->group_size] = str;node->group_size++;return 0;}node = node->next;}//key在哈希表中不存在，则创建新节点并进行插入（头插入法）    hash_node* new_node = (hash_node*)malloc(sizeof(hash_node));strncpy(new_node->key, key, STR_LENGTH);new_node->group = (char**)malloc(1000 * sizeof(char*));new_node->group[0] = str;new_node->group_size = 1;new_node->next = hash_table[position];hash_table[position] = new_node;return 0;
}//释放哈希表内存
void free_hashtable_memory(void) {int i = 0;for(i = 0; i < HASH_SIZE; i++) {hash_node* node = hash_table[i];while(node) {hash_node* tmp_node = node->next;free(node->group);free(node);node = tmp_node;}}
}/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {int i = 0;memset(hash_table, 0, sizeof(hash_table));//对每个字符串进行排序，再将字符串逐个插入哈希表中for(i = 0; i < strsSize; i++) {char* ptr = strs[i];char key[STR_LENGTH];strncpy(key, ptr, STR_LENGTH);qsort(key, strlen(key), sizeof(char), str_sort);insert_hash(key, ptr);}*returnSize = 0;//遍历哈希表，获取哈希表中桶数量（即获取returnSize）for(i = 0; i < HASH_SIZE; i++) {hash_node* node = hash_table[i];while(node) {(*returnSize)++;node = node->next;}}printf("*returnSize: %d\n", *returnSize);//获取返回数组，获取 returnColumnSizes（returnColumnSizes为每个group的字符串个数）char*** result = (char***)malloc((*returnSize) * sizeof(char**));*returnColumnSizes = (int*)malloc((*returnSize) * sizeof(int));int index = 0;for(i = 0; i < HASH_SIZE; i++) {hash_node* tmp_node = hash_table[i];while(tmp_node) {//把tmp_node的二维数组放到三维数组result的对应位置//为result的每个指针开辟指向二维数组空间result[index] = (char**)malloc(tmp_node->group_size * sizeof(char*)); for(int n = 0; n < tmp_node->group_size; n++) {result[index][n] = tmp_node->group[n];}(*returnColumnSizes)[index] = tmp_node->group_size;index++;tmp_node = tmp_node->next;}}//释放哈希表内存资源free_hashtable_memory();return result;
}

以上的代码已经过编译运行（力扣网），可实现预期效果。