商业网站建站,检测站点是否使用wordpress,白云网站 建设信科网络,.net空网站做九九乘法表目录 3. 无重复字符的最长子串 题目描述
解题思路
代码实现
349. 两个数组的交集
题目描述
解题思路
代码实现
454. 四数相加 II
题目描述
解题思路
代码实现
242. 有效的字母异位词
题目描述
解题思路
代码实现
438. 找到字符串中所有字母异位词
题目…目录 3. 无重复字符的最长子串 题目描述
解题思路
代码实现
349. 两个数组的交集
题目描述
解题思路
代码实现
454. 四数相加 II
题目描述
解题思路
代码实现
242. 有效的字母异位词
题目描述
解题思路
代码实现
438. 找到字符串中所有字母异位词
题目描述
解题思路
代码实现
202. 快乐数
题目描述
解题思路
代码实现
383. 赎金信
题目描述
解题思路
代码实现
387. 字符串中的第一个唯一字符
题目描述
解题思路
代码实现 3. 无重复字符的最长子串 题目描述 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串的长度。
示例 1:
输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。 示例 2:
输入: s bbbbb 输出: 1 解释: 因为无重复字符的最长子串是 b所以其长度为 1。 示例 3:
输入: s pwwkew 输出: 3 解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。 提示
0 s.length 5 * 104 s 由英文字母、数字、符号和空格组成 解题思路
使用滑动窗口的算法并结合哈希表来快速判断某个字符是否已被访问过。
1.初始化
获取字符串s的长度len。如果字符串为空len 0则最长无重复字符子串的长度显然为0直接返回0。
定义左指针left和右指针right都初始化为0。这两个指针用于定义当前考虑的子串范围。定义maxLen用于记录当前找到的最长无重复字符子串的长度初始化为0。
定义哈希表hash大小为256并全部初始化为0。哈希表的索引对应字符的ASCII值值对应字符的访问状态0表示未访问1表示已访问。
2.遍历字符串
使用while循环遍历字符串直到右指针right达到字符串的末尾。
3.检查字符状态
在每次循环中检查当前右指针right指向的字符s[right]的访问状态
如果hash[s[right]]为0表示该字符在当前考虑的子串中还未出现过将hash[s[right]]设置为1标记该字符为已访问。更新maxLen为当前子串长度right - left 1和maxLen中的较大值。右指针right右移一位继续考虑下一个字符。
如果hash[s[right]]为1表示该字符在当前考虑的子串中已经出现过为了找到最长无重复字符子串需要移动左指针left并重置左指针及其左侧所有字符的访问状态在hash中对应位置设置为0。左指针left右移一位。
4.返回结果
当遍历完整个字符串后maxLen中保存的就是最长无重复字符子串的长度将其作为结果返回。
代码实现
int lengthOfLongestSubstring(char* s) {int len strlen(s);if (len 0)return 0;int left 0, right 0;int maxLen 0;int hash[256] {0};while (right len) {// 如果当前字符没有被访问过if (hash[s[right]] 0) {hash[s[right]] 1; // 标记当前字符为已访问maxLen (right - left 1) maxLen ? (right - left 1): maxLen; // 更新最大长度right; // 右指针右移} else {// 如果当前字符已经被访问过则移动左指针并重置左指针及其左侧所有字符的访问状态hash[s[left]] 0;left;}}return maxLen;
}
349. 两个数组的交集 题目描述 给定两个数组 nums1 和 nums2 返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1
输入nums1 [1,2,2,1], nums2 [2,2] 输出[2] 示例 2
输入nums1 [4,9,5], nums2 [9,4,9,8,4] 输出[9,4] 解释[4,9] 也是可通过的
提示
1 nums1.length, nums2.length 1000 0 nums1[i], nums2[i] 1000 解题思路 1.初始化哈希表和结果数组
创建一个大小为1005的哈希表 hash用于记录数组 nums1 中元素的出现次数。分配一个足够大的数组 result 来存储交集结果。这个数组的大小根据两个数组中较小的一个来确定因为交集的大小不会超过较小的数组的大小。
2.记录 nums1 中元素的出现次数
遍历数组 nums1将每个元素作为索引在哈希表 hash 中对应的位置增加计数。这样哈希表就记录了 nums1 中每个元素的出现次数。
3.查找交集并填充结果数组
遍历数组 nums2对于每个元素检查它在哈希表 hash 中对应的计数是否大于0。如果大于0说明这个元素也出现在 nums1 中因此它是交集的一部分。将这个交集元素添加到结果数组 result 中并更新结果数组的索引 resultIndex。将哈希表中该元素对应的计数置为0以避免重复添加同一个元素到结果数组中。
4.返回结果
通过指针参数 returnSize 返回结果数组 result 的大小并返回指向结果数组 result 的指针。
代码实现
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size,int* returnSize) {// 创建一个大小为 1005 的哈希表初始值全部为 0int hash[1005] {0};// lessSize// 存储两个数组中较小的那个数组的大小这样可以确保结果数组的大小足够存放交集int lessSize nums1Size nums2Size ? nums1Size : nums2Size;// 分配足够空间来存储可能的交集结果并用 calloc 初始化为 0int* result (int*)calloc(lessSize, sizeof(int));// resultIndex 用于记录结果数组中当前的位置int resultIndex 0;// 遍历第一个数组将每个元素出现的次数记录在哈希表中for (int i 0; i nums1Size; i) {hash[nums1[i]];}// 遍历第二个数组查找与第一个数组有交集的元素for (int i 0; i nums2Size; i) {// 如果哈希表中对应位置的值大于 0说明该元素在第一个数组中出现过if (hash[nums2[i]] 0) {// 将交集元素添加到结果数组中result[resultIndex] nums2[i];// 更新结果数组中的位置索引resultIndex;// 将哈希表中对应位置的值置为 0表示该元素已被找到过一次hash[nums2[i]] 0;}}// 通过指针参数返回交集数组的大小*returnSize resultIndex;// 返回指向交集数组的指针return result;
}
454. 四数相加 II 题目描述
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 i, j, k, l n nums1[i] nums2[j] nums3[k] nums4[l] 0 示例 1
输入nums1 [1,2], nums2 [-2,-1], nums3 [-1,2], nums4 [0,2] 输出2 解释 两个元组如下 1. (0, 0, 0, 1) - nums1[0] nums2[0] nums3[0] nums4[1] 1 (-2) (-1) 2 0 2. (1, 1, 0, 0) - nums1[1] nums2[1] nums3[0] nums4[0] 2 (-1) (-1) 0 0 示例 2
输入nums1 [0], nums2 [0], nums3 [0], nums4 [0] 输出1 提示
n nums1.length n nums2.length n nums3.length n nums4.length 1 n 200 -228 nums1[i], nums2[i], nums3[i], nums4[i] 228 解题思路
观察发现如果可以找到两个数对来自不同数组它们的和互为相反数那么它们就可以组成一个满足条件的四元组。因此问题可以转化为对于每一对来自nums1和nums2的数找到多少对来自nums3和nums4的数它们的和与这对数的和互为相反数。
1.使用哈希表
哈希表是一种以平均常数时间复杂度进行插入、删除和查找的数据结构。在这个问题中可以使用哈希表来存储nums1和nums2中所有两数之和及其出现的次数。
2.遍历并构建哈希表
遍历nums1和nums2的所有组合计算每对数的和ikey。
检查哈希表中是否已经存在这个键两数之和。
如果不存在则创建一个新的哈希表项键为两数之和值为1表示这个和第一次出现。
如果已经存在则增加该键对应的值表示这个和又出现了一次。
3.利用哈希表查找
遍历nums3和nums4的所有组合计算每对数的和的相反数-ikey。
在哈希表中查找这个相反数。
如果找到了则将哈希表中该键对应的值累加到结果变量中因为这个值表示在nums1和nums2中有多少对数的和与当前nums3和nums4中的数对的和互为相反数。
4.返回结果
遍历完成后结果变量中存储的就是所有满足条件的四元组的个数返回这个结果。 代码实现 struct hashTable { int key; // 哈希表项的键用于存储nums1[i] nums2[j]的和 int val; // 哈希表项的值用于存储键出现的次数 UT_hash_handle hh; // uthash库提供的数据结构用于处理哈希表的相关操作
}; // 计算四数之和为零的元组个数
int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size) { struct hashTable* hashtable NULL; // 初始化哈希表为空 // 遍历nums1和nums2的所有组合计算两数之和并更新哈希表 for (int i 0; i nums1Size; i) { for (int j 0; j nums2Size; j) { int ikey nums1[i] nums2[j]; // 计算两数之和 struct hashTable* tmp; HASH_FIND_INT(hashtable, ikey, tmp); // 在哈希表中查找键ikey if (tmp NULL) { // 如果没找到则新建一个哈希表项 struct hashTable* tmp malloc(sizeof(struct hashTable)); tmp-key ikey; tmp-val 1; // 初始值为1表示找到了一对数的和为ikey HASH_ADD_INT(hashtable, key, tmp); // 将新项添加到哈希表中 } else { // 如果找到了则增加该键对应的值表示又找到了一对数的和为ikey tmp-val; } } } int ans 0; // 初始化结果变量为0 // 遍历nums3和nums4的所有组合计算两数之和的相反数并在哈希表中查找该相反数 for (int i 0; i nums3Size; i) { for (int j 0; j nums4Size; j) { int ikey -nums3[i] - nums4[j]; // 计算两数之和的相反数 struct hashTable* tmp; HASH_FIND_INT(hashtable, ikey, tmp); // 在哈希表中查找该相反数 if (tmp ! NULL) { // 如果找到了则将该键对应的值累加到结果变量中 // 因为对于nums3和nums4中的每一对数的和如果哈希表中存在相反数 // 则说明在nums1和nums2中存在另一对数的和与该相反数相等从而四数之和为零 ans tmp-val; } } }
return ans//返回结果
} 242. 有效的字母异位词
题目描述
给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。
注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。 示例 1:
输入: s anagram, t nagaram
输出: true示例 2:
输入: s rat, t car
输出: false 提示:
1 s.length, t.length 5 * 104s 和 t 仅包含小写字母
解题思路
初始化 创建一个大小为26的整数数组 record并初始化所有元素为0。数组的每个索引对应一个小写字母例如record[0] 对应字母 a。获取字符串 s 和 t 的长度分别存储在 slength 和 tlength 中。长度检查 如果两个字符串的长度不同它们显然不可能是异位词因为异位词要求字符完全相同只是顺序不同。因此直接返回 false0。计算字符频率 遍历字符串 s 中的每个字符将对应字母在 record 数组中的计数加1。这是通过计算字符与 a 的ASCII码差值并用该差值作为数组索引来实现的。同时遍历字符串 t 中的每个字符将对应字母在 record 数组中的计数减1。如果 s 和 t 是异位词那么 record 数组中的每个索引都应该最终为0因为每个字符在 s 中出现的次数与在 t 中出现的次数应该相同。检查记录数组 遍历 record 数组检查是否有任何非零值。如果发现任何非零值说明 s 和 t 不是变位词因为这意味着至少有一个字符在两个字符串中的出现次数不同。因此返回 false0。返回结果 如果 record 数组中的所有值都是0说明 s 和 t 是异位词因为它们的字符组成完全相同只是顺序不同。因此返回 true1。
代码实现
bool isAnagram(char* s, char* t) {int record[26] {0}, slength strlen(s), tlength strlen(t);int i;if (slength ! tlength)return 0;for (i 0; i slength; i) {record[s[i] - a] 1;record[t[i] - a] - 1;}for (i 0; i 26; i) {if (record[i] ! 0) {return 0;}}return 1;
}
438. 找到字符串中所有字母异位词
题目描述 给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串包括相同的字符串。
示例 1:
输入: s cbaebabacd, p abc 输出: [0,6] 解释: 起始索引等于 0 的子串是 cba, 它是 abc 的异位词。 起始索引等于 6 的子串是 bac, 它是 abc 的异位词。 示例 2:
输入: s abab, p ab 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 ab, 它是 ab 的异位词。 起始索引等于 1 的子串是 ba, 它是 ab 的异位词。 起始索引等于 2 的子串是 ab, 它是 ab 的异位词。
提示:
1 s.length, p.length 3 * 104 s 和 p 仅包含小写字母 解题思路 利用哈希表来记录字符频率并使用滑动窗口的方法来遍历字符串s。
1.初始化
首先获取字符串s和p的长度并检查p的长度是否大于s的长度。如果大于那么s中不可能有与p构成异位词的子串所以直接返回空数组。
初始化两个哈希表shash和phash用于存储s和p中字符出现的次数。因为题目中说s 和 p 仅包含小写字母所以哈希表的大小为26。
2.计算p中字符的出现次数
遍历p中的每个字符并在phash中对应的位置增加计数。
3.初始化结果数组和滑动窗口
分配内存给结果数组ans大小为slen - plen 1。这是因为最多可能有slen - plen 1个与p等长的子串存在于s中。
初始化计数器count为0用于记录找到的异位词子串的数量。
初始化滑动窗口的左边界left为0。
4.使用滑动窗口遍历s
使用变量right作为滑动窗口的右边界从0开始遍历s。
在每次迭代中更新shash中对应s[right]字符的计数。
当滑动窗口的大小达到p的长度时检查shash和phash是否相等。可以通过memcmp函数实现它比较两个内存区域的内容。
如果哈希值匹配说明找到了一个与p构成异位词的子串将左边界的索引left添加到结果数组ans中并增加计数器count。
然后移动滑动窗口的左边界即将left右移一位并更新shash中对应s[left]字符的计数。
5.返回结果
设置结果数组的大小为count。
返回结果数组ans。
【补充】C 库string.h函数 - memcmp()
作用把存储区 str1 和存储区 str2 的前 n 个字节进行比较。
函数声明int memcmp(const void *str1, const void *str2, size_t n)
参数str1 -- 指向内存块的指针。
str2 -- 指向内存块的指针。
n -- 要被比较的字节数。
返回值
如果str1 小于 str2返回值 0。
如果str1 大于 str2返回值 0。
如果str1 等于 str2返回值 0。
代码实现
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* findAnagrams(char * s, char * p, int* returnSize){int slen strlen(s), plen strlen(p); // 如果p的长度大于s的长度直接返回空数组if (plen slen) { *returnSize 0; return NULL; } // 初始化两个哈希表用于存储p和s中字符出现的次数int shash[26] {0}, phash[26] {0}; // 计算p中字符出现的次数for (int i 0; i plen; i) { phash[p[i] - a]; } // 为结果数组分配内存int *ans (int*)malloc(sizeof(int) * (slen - plen 1)); // 初始化结果数组的计数器和滑动窗口的左边界int count 0, left 0; // 遍历字符串sfor (int right 0; right slen; right) { // 维护滑动窗口的哈希值shash[s[right] - a]; // 当窗口大小达到p的长度时开始检查哈希值是否匹配if (right - left 1 plen) { // 如果哈希值匹配将左边界的索引添加到结果数组中if (memcmp(shash, phash, sizeof(phash)) 0) { ans[count] left; } // 移动窗口左边界并更新哈希值shash[s[left] - a]--; left; } } // 设置结果数组的大小*returnSize count; // 返回结果数组return ans;
}
202. 快乐数
题目描述
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true 不是则返回 false 。 示例 1
输入n 19
输出true
解释
12 92 82
82 22 68
62 82 100
12 02 02 1示例 2
输入n 2
输出false提示
1 n 231 - 1
解题思路
定义一个辅助函数 getSum这个函数用于计算一个整数的各位数字的平方和。 通过循环每次取整数 n 的最后一位数字n % 10计算其平方然后累加到 sum 中。接着将 n 除以 10去掉已经处理过的最后一位数字。当 n 为 0 时循环结束返回 sum。定义主函数 isHappy用于判断一个数是否为快乐数。 首先调用 getSum 函数计算输入数 n 的各位数字的平方和 sum。定义一个哈希表 hash用于记录已经出现的 sum 值。初始时所有元素都设为 0。进入一个循环当 sum 不等于 1 时继续循环 如果 sum 在哈希表中已经出现过即 hash[sum] 1则返回 false表示 n 不是快乐数。否则将 hash[sum] 的值设为 1表示 sum 已经出现过。再次调用 getSum 函数更新 sum 的值为其各位数字的平方和。如果循环正常结束即 sum 等于 1则返回 true表示 n 是快乐数。
代码实现
int getSum(int n) {int sum 0;while (n) {sum (n % 10) * (n % 10);n / 10;}return sum;
}
bool isHappy(int n) {int sum getSum(n);int hash[1005] {0};while (sum ! 1) {if (hash[sum] 1) {return false;} else {hash[sum];}sum getSum(sum);}return true;
}
383. 赎金信
题目描述
给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以返回 true 否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。 示例 1
输入ransomNote a, magazine b
输出false示例 2
输入ransomNote aa, magazine ab
输出false示例 3
输入ransomNote aa, magazine aab
输出true提示
1 ransomNote.length, magazine.length 105ransomNote 和 magazine 由小写英文字母组成
解题思路
初始化哈希表 创建一个大小为26的整数数组hash用于存储每个小写字母出现的次数。数组的每个索引对应一个小写字母例如hash[0]对应字母ahash[1]对应字母b以此类推。将hash数组的所有元素初始化为0。统计magazine中字符的出现次数 遍历magazine字符串中的每个字符。对于每个字符将其对应的哈希表索引增加1。这是通过计算字符与a的ASCII码差值来实现的例如字符b会对应索引1因为b - a 1。减少ransomNote中字符的出现次数 遍历ransomNote字符串中的每个字符。对于每个字符将其对应的哈希表索引减少1。检查哈希表 遍历整个哈希表。如果发现任何索引的值小于0这意味着ransomNote中的某个字符在magazine中的出现次数不足以满足其需求。因此函数返回0表示无法用magazine构造ransomNote。返回结果 如果哈希表中所有索引的值都大于等于0这意味着magazine中的字符足够用来构造ransomNote。因此函数返回1。
代码实现
bool canConstruct(char* ransomNote, char* magazine) {int hash[26] {0}, i 0;for (i 0; magazine[i] ! \0; i) {hash[magazine[i] - a];}for (i 0; ransomNote[i] ! \0; i) {hash[ransomNote[i] - a]--;}for (i 0; i26; i) {if (hash[i] 0)return 0;}return 1;
}
387. 字符串中的第一个唯一字符
题目描述
给定一个字符串 s 找到 它的第一个不重复的字符并返回它的索引 。如果不存在则返回 -1 。 示例 1
输入: s leetcode
输出: 0示例 2:
输入: s loveleetcode
输出: 2示例 3:
输入: s aabb
输出: -1提示:
1 s.length 105s 只包含小写字母
解题思路
初始化: 定义一个 hashTable 结构体它包含两个整型成员key 和 val以及一个 UT_hash_handle 类型的成员 hh。这个结构体用于存储字符和其出现的频率。使用 UT_hash_handle 是因为代码中使用了 uthash 这个库它是一个用于 C 语言的轻量级哈希表库。计算频率: 创建一个空的哈希表 frequency。遍历字符串 s 中的每个字符 对于每个字符将其 ASCII 值作为键ikey在哈希表中查找。如果找不到该键tmp NULL则创建一个新的 hashTable 结构体实例并设置其 key 为当前字符的 ASCII 值val 为 1然后将它添加到哈希表中。如果找到了该键则将对应结构体的 val 值加 1表示该字符的出现频率增加。查找第一个只出现一次的字符: 再次遍历字符串 s 中的每个字符 对于每个字符使用其 ASCII 值在哈希表中查找。如果找到了该键并且其对应的 val 值为 1即该字符只出现了一次则返回当前字符的索引 i。返回结果: 如果在字符串 s 中没有找到只出现一次的字符则返回 -1。
代码实现
struct hashTable {int key;int val;UT_hash_handle hh;
};int firstUniqChar(char* s) {struct hashTable* frequency NULL;int n strlen(s);for (int i 0; i n; i) {int ikey s[i];struct hashTable* tmp;HASH_FIND_INT(frequency, ikey, tmp);if (tmp NULL) {tmp malloc(sizeof(struct hashTable));tmp-key ikey;tmp-val 1;HASH_ADD_INT(frequency, key, tmp);} else {tmp-val;}}for (int i 0; i n; i) {int ikey s[i];struct hashTable* tmp;HASH_FIND_INT(frequency, ikey, tmp);if (tmp ! NULL tmp-val 1) {return i;}}return -1;
