第1题：同构字符串
第2题：最后一块石头的重量
第3题：最小路径和
第4题：键盘行
第5题：存在重复元素 II
第6题：两数相加
第7题：三个数的最大乘积
第8题：等价多米诺骨牌对的数量
第9题：公平的糖果棒交换
第10题：替换后的最长重复字符
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：同构字符串试题要求如下：
回答（C语言）：
#define MAX_NUM 128
bool isIsomorphic(char * s, char * t){
int sLen = 0;
int tLen = 0;
int *hash1 = NULL;
int *hash2 = NULL;
sLen = strlen(s);
tLen = strlen(t);
// 特殊处理
if (sLen != tLen) {
return false;
}
// 分配空间
hash1 = malloc(sizeof(int) * MAX_NUM);
memset(hash1, 0, sizeof(int) * MAX_NUM);
hash2 = malloc(sizeof(int) * MAX_NUM);
memset(hash2, 0, sizeof(int) * MAX_NUM);
// 统计字符串出现的次数
for (int i = 0; i < sLen; i++) {
if (hash1[s[i]] == 0) {
hash1[s[i]] = t[i];
}
if (hash2[t[i]] == 0) {
hash2[t[i]] = s[i];
}
if (hash1[s[i]] != t[i] || hash2[t[i]] != s[i]) {
return false;
}
}
return true;
}运行效率如下所示：
试题要求如下：
回答（C语言）：
int cmp(const void* _a, const void* _b){
int a = *(int*)_a;
int b = *(int*)_b;
return b-a;
}
int lastStoneWeight(int* stones, int stonesSize){
if(stonesSize next = NULL;
cur->next = p;
cur = cur->next;
if(l1 != NULL){
l1 = l1->next;
}
if(l2 != NULL){
l2 = l2->next;
}
}
if(carry == 1){
struct ListNode* ca = (struct ListNode*)malloc(sizeof(struct ListNode));
ca->val = carry;
ca->next = NULL;
cur->next = ca;
}
return pre->next;
}运行效率如下所示：
试题要求如下：
解题思路：
假设若使用排序法。
如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。
如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
所以，根据此规律，使用线性扫描法实现。
回答（C语言）：
int maximumProduct(int* nums, int numsSize) {
// 最小的和第二小的
int min1 = INT_MAX, min2 = INT_MAX;
// 最大的、第二大的和第三大的
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
for (int i = 0; i < numsSize; i++) {
int x = nums[i];
if (x < min1) {
min2 = min1;
min1 = x;
} else if (x < min2) {
min2 = x;
}
if (x > max1) {
max3 = max2;
max2 = max1;
max1 = x;
} else if (x > max2) {
max3 = max2;
max2 = x;
} else if (x > max3) {
max3 = x;
}
}
return fmax(min1 * min2 * max1, max1 * max2 * max3);
}运行效率如下所示：
试题要求如下：
回答（C语言）：
int numEquivDominoPairs(int** dominoes, int dominoesSize, int* dominoesColSize) {
int num[100];
memset(num, 0, sizeof(num));
int ret = 0;
for (int i = 0; i < dominoesSize; i++) {
int val = dominoes[i][0] < dominoes[i][1] ? dominoes[i][0] * 10 + dominoes[i][1] : dominoes[i][1] * 10 + dominoes[i][0];
ret += num[val];
num[val]++;
}
return ret;
}运行效率如下所示：
试题要求如下：
解题思路：
假设数组 A 和 B 的元素之和分别为 sumA 和 sumB，待交换的元素分别为 x 和 y，则按照题目的要求必然存在以下等式成立：sumA - x + y = sumB + x - y
将等式 sumA - x + y = sumB + x - y 进一步简化，可得 x = (sumA - sumB) / 2 + y，即在数组 A 中必须存在一个值为 (sumA - sumB) / 2 + y 的元素。
此时，这个问题就简化为：在数组中查找一个元素的值等于目标值 target 了。
回答（C语言）：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int* fairCandySwap(int* A, int ASize, int* B, int BSize, int* returnSize){
*returnSize = 0;
int *res = (int *)malloc(2 * sizeof(int));
/* 判断是否动态内存是否申请成功*/
if (res == NULL) {
return NULL;
}
*returnSize = 2;
int sumA = 0, sumB = 0, diff = 0;
/* 求数组 A 和 B 的和*/
for (int i = 0; i < ASize; ++i) {
sumA += A[i];
}
for (int j = 0; j < BSize; ++j) {
sumB += B[j];
}
diff = sumA - sumB;
/* 排序，为后面进行二分查找做准备 */
qsort(A, ASize, sizeof(int), cmp);
for (int k = 0; k < BSize; ++k) {
/* 二分查找的目标元素 */
int target = diff / 2 + B[k];
int l = 0, r = ASize - 1;
/* 二分查找 */
while (l target) {
r = m - 1;
} else if (A[m] < target) {
l = m + 1;
/* 查找到目标元素，对数组元素赋值并返回 */
} else {
res[0] = target;
res[1] = B[k];
return res;
}
}
}
return NULL;
}运行效率如下所示：
试题要求如下：
解题思路：
1、定义一个长度为 26 的整型数组（字符串仅包含大写英文字母），用于模拟哈希表（记录重复字母出现次数）；
2、分别定义两个指针（字符下标），用于遍历字符串，两个指针组成的区间构成一个滑动窗口，当它们之间的间距大于字母当前出现最大频次加上 k 时，代表替换 k 次仍不能使得这个窗口之间的字母全是相同，此时需要将向右移动（缩小窗口的大小），同时将频次递减（增大了左边界）；否则 r 向右移动增大窗口。
回答（C语言）：
int characterReplacement(char * s, int k){
int maxCnt = 0;
int l = 0, r = 0; // 滑动窗口[l, r)
int freq[26] = {0}; // 记录重复字符出现频次
int lenS = strlen(s);
while (r < lenS) {
freq[s[r] - 'A']++; // 计算当前字符出现频次
maxCnt = fmax(maxCnt, freq[s[r++] - 'A']); // 计算当前字符出现的最大频次
if (r - l > maxCnt + k) { // 滑动窗口大小大于字母最大频次加上能替换的次数
freq[s[l++] - 'A']--; // l 右移动减少滑动窗口大小，同时频次减减
}
}
return r - l;
}运行效率如下所示：
