力扣(LeetCode)刷题，简单+中等题(第31期)
【摘要】 目录
第1题：同构字符串
第2题：最后一块石头的重量
第3题：最小路径和
第4题：键盘行
第5题：存在重复元素 II
第6题：两数相加
第7题：三个数的最大乘积
第8题：等价多米诺骨牌对的数量
第9题：公平的糖果棒交换
第10题：替换后的最长重复字符
力扣(LeetCode)定期刷题，每期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;
-
}
运行效率如下所示：
第2题：最后一块石头的重量
试题要求如下：
回答（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 <=1){
-
return stones[0];
-
}
-
-
qsort(stones,stonesSize,sizeof(int),cmp);
-
-
while(stones[1] != 0){
-
stones[0] = stones[0] - stones[1];
-
stones[1] = 0;
-
qsort(stones,stonesSize,sizeof(int),cmp);
-
}
-
-
return stones[0];
-
}
运行效率如下所示：
第3题：最小路径和
试题要求如下：
回答（C语言）：
-
int minPathSum(int** grid, int gridSize, int* gridColSize) {
-
int rows = gridSize, columns = gridColSize[0];
-
-
if (rows == 0 || columns == 0) {
-
return 0;
-
}
-
-
int dp[rows][columns];
-
dp[0][0] = grid[0][0];
-
-
for (int i = 1; i < rows; i++) {
-
dp[i][0] = dp[i - 1][0] + grid[i][0];
-
}
-
for (int j = 1; j < columns; j++) {
-
dp[0][j] = dp[0][j - 1] + grid[0][j];
-
}
-
for (int i = 1; i < rows; i++) {
-
for (int j = 1; j < columns; j++) {
-
dp[i][j] = fmin(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
-
}
-
}
-
-
return dp[rows - 1][columns - 1];
-
}
运行效率如下所示：
第4题：键盘行
试题要求如下：
解题思路：
1、先在 a 空间中，将3行键盘的下标分别记为1，2，3；
2、遍历数组，如果不在同一行就退出；
3、如果是正常退出的，将单词记录。
回答（C语言）：
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
char ** findWords(char ** words, int wordsSize, int* returnSize){
-
*returnSize=0;
-
char **res=(char**)malloc(sizeof(char*)*wordsSize);
-
char *a=(char*)calloc(59,sizeof(char));
-
-
for(int i=0;i<58;i++){
-
if(i=='Q'-65||i=='W'-65||i=='E'-65||i=='R'-65||i=='T'-65||i=='Y'-65||i=='U'-65||i=='I'-65||i=='O'-65||i=='P'-65||i=='q'-65||i=='w'-65||i=='e'-65||i=='r'-65||i=='t'-65||i=='y'-65||i=='u'-65||i=='i'-65||i=='o'-65||i=='p'-65)
-
a[i]=1;
-
else if(i=='A'-65||i=='S'-65||i=='D'-65||i=='F'-65||i=='G'-65||i=='H'-65||i=='J'-65||i=='K'-65||i=='L'-65||i=='a'-65||i=='s'-65||i=='d'-65||i=='f'-65||i=='g'-65||i=='h'-65||i=='j'-65||i=='k'-65||i=='l'-65)
-
a[i]=2;
-
else
-
a[i]=3;
-
}
-
-
int i,j;
-
-
for(i=0;i<wordsSize;i++){
-
for(j=1;j<strlen(words[i]);j++){
-
char t=a[words[i][0]-65];
-
if(t!=a[words[i][j]-65])
-
break;
-
}
-
if(j==strlen(words[i])){
-
res[*returnSize]=(char*)calloc(strlen(words[i])+1,1);
-
strcpy(res[*returnSize],words[i]);
-
(*returnSize)++;
-
}
-
}
-
-
return res;
-
}
运行效率如下所示：
第5题：存在重复元素 II
试题要求如下：
回答（C语言）：
-
bool containsNearbyDuplicate(int* nums, int numsSize, int k){
-
if(numsSize==0)
-
return false;
-
int mark[numsSize];//Hash表
-
memset(mark,-1,sizeof(int)*numsSize);
-
-
for(int i = 0, tmp = 0; i < numsSize; i++)
-
{
-
tmp=nums[i]%numsSize;//Hash函数
-
if(tmp<0)//转换为正数
-
tmp+=(numsSize-1);
-
if(mark[tmp]==-1)//没有存数
-
mark[tmp]=i;//存下数组下标
-
else//已经存数
-
{
-
while(nums[mark[tmp]]!=nums[i])//发生冲突
-
{
-
tmp++;tmp%=numsSize;
-
if(mark[tmp]==-1)//没有存数
-
mark[tmp]=i;//存下数组下标
-
}
-
//已经存过该数
-
if(i!=mark[tmp])
-
if(i-mark[tmp]<=k)//求差值
-
return true;
-
else
-
mark[tmp]=i;
-
}
-
}
-
-
return false;
-
}
运行效率如下所示：
第6题：两数相加
试题要求如下：
回答（C语言）：
-
/**
-
* Definition for singly-linked list.
-
* struct ListNode {
-
* int val;
-
* struct ListNode *next;
-
* };
-
*/
-
-
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
-
struct ListNode* pre = (struct ListNode*)malloc(sizeof(struct ListNode));
-
pre->val = 0;
-
pre->next = NULL;
-
-
struct ListNode* cur = pre;
-
int carry = 0;
-
int sum = 0;
-
-
while(l1 != NULL || l2 != NULL){
-
int x = (l1 == NULL) ? 0:l1->val;
-
int y = (l2 == NULL) ? 0:l2->val;
-
-
sum = x + y + carry;
-
carry = sum / 10;
-
-
struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
-
p->val = sum % 10;
-
p->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;
-
}
运行效率如下所示：
第7题：三个数的最大乘积
试题要求如下：
解题思路：
假设若使用排序法。
如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。
如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
所以，根据此规律，使用线性扫描法实现。
回答（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);
-
}
运行效率如下所示：
第8题：等价多米诺骨牌对的数量
试题要求如下：
回答（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;
-
}
运行效率如下所示：
第9题：公平的糖果棒交换
试题要求如下：
解题思路：
假设数组 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 <= r) {
-
int m = l + (r - l)/2;
-
if (A[m] > target) {
-
r = m - 1;
-
} else if (A[m] < target) {
-
l = m + 1;
-
/* 查找到目标元素，对数组元素赋值并返回 */
-
} else {
-
res[0] = target;
-
res[1] = B[k];
-
return res;
-
}
-
}
-
}
-
-
return NULL;
-
}
运行效率如下所示：
第10题：替换后的最长重复字符
试题要求如下：
解题思路：
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;
-
}
运行效率如下所示：
文章来源: handsome-man.blog.csdn.net，作者：不脱发的程序猿，版权归原作者所有，如需转载，请联系作者。
原文链接：handsome-man.blog.csdn.net/article/details/111861391
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）