【代码随想录算法训练营第42期第六天 | LeetCode242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和】

代码随想录算法训练营第42期第六天 | LeetCode242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

一、242.有效的字母异位词

解题代码C：

bool isAnagram(char* s, char* t) {int len1 = strlen(s);int len2 = strlen(t);int al[26] = {0};int bl[26] = {0};for(int i = 0; i < len1; i ++)al[s[i] - 'a'] ++;for(int i = 0; i < len2; i ++)bl[t[i] - 'a'] ++;for(int i = 0; i < 26; i ++)if(al[i] != bl[i])return false;return true;
}

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

二、349. 两个数组的交集

解题代码C：

int* intersection1(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int nums1Cnt[1000] = {0};int lessSize = nums1Size < nums2Size ? nums1Size : nums2Size;int * result = (int *) calloc(lessSize, sizeof(int));int resultIndex = 0;int* tempNums;int i;/* Calculate the number's counts for nums1 array */for(i = 0; i < nums1Size; i ++) {nums1Cnt[nums1[i]]++;}/* Check if the value in nums2 is existing in nums1 count array */for(i = 0; i < nums2Size; i ++) {if(nums1Cnt[nums2[i]] > 0) {result[resultIndex] = nums2[i];resultIndex ++;/* Clear this count to avoid duplicated value */nums1Cnt[nums2[i]] = 0;}}* returnSize = resultIndex;return result;
}

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

三、202. 快乐数

解题代码C：

int get_sum(int n) {int sum = 0;div_t n_div = { .quot = n };while (n_div.quot != 0) {n_div = div(n_div.quot, 10);sum += n_div.rem * n_div.rem;}return sum;
}// (版本1)使用数组
bool isHappy(int n) {// sum = a1^2 + a2^2 + ... ak^2// first round:// 1 <= k <= 10// 1 <= sum <= 1 + 81 * 9 = 730// second round:// 1 <= k <= 3// 1 <= sum <= 36 + 81 * 2 = 198// third round:// 1 <= sum <= 81 * 2 = 162// fourth round:// 1 <= sum <= 81 * 2 = 162uint8_t visited[163] = { 0 };int sum = get_sum(get_sum(n));int next_n = sum;while (next_n != 1) {sum = get_sum(next_n);if (visited[sum]) return false;visited[sum] = 1;next_n = sum;};return true;
}// (版本2)使用快慢指针
bool isHappy(int n) {int slow = n;int fast = n;do {slow = get_sum(slow);fast = get_sum(get_sum(fast));} while (slow != fast);return (fast == 1);
}

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

四、1. 两数之和

解题代码C：

/*** Note: The returned array must be malloced, assume caller calls free().*/// leetcode 支持 ut_hash 函式庫typedef struct {int key;int value;UT_hash_handle hh; // make this structure hashable} map;map* hashMap = NULL;void hashMapAdd(int key, int value){map* s;// key already in the hash?HASH_FIND_INT(hashMap, &key, s);if(s == NULL){s = (map*)malloc(sizeof(map));s -> key = key;HASH_ADD_INT(hashMap, key, s);}s -> value = value;}map* hashMapFind(int key){map* s;// *s: output pointerHASH_FIND_INT(hashMap, &key, s);   return s;}void hashMapCleanup(){map* cur, *tmp;HASH_ITER(hh, hashMap, cur, tmp){HASH_DEL(hashMap, cur);free(cur);}}void hashPrint(){map* s;for(s = hashMap; s != NULL; s=(map*)(s -> hh.next)){printf("key %d, value %d\n", s -> key, s -> value);}}int* twoSum(int* nums, int numsSize, int target, int* returnSize){int i, *ans;// hash find resultmap* hashMapRes; hashMap = NULL;ans = malloc(sizeof(int) * 2);for(i = 0; i < numsSize; i++){// key 代表 nums[i] 的值，value 代表所在 index;hashMapAdd(nums[i], i);}hashPrint();for(i = 0; i < numsSize; i++){hashMapRes = hashMapFind(target - nums[i]);if(hashMapRes && hashMapRes -> value != i){ans[0] = i;ans[1] = hashMapRes -> value ;*returnSize = 2;return ans;}}hashMapCleanup();return NULL;
}