力扣(LeetCode)刷题,简单+中等题(第31期)

举报
不脱发的程序猿 发表于 2021/02/05 23:23:09 2021/02/05
【摘要】 目录 第1题:同构字符串 第2题:最后一块石头的重量 第3题:最小路径和 第4题:键盘行 第5题:存在重复元素 II 第6题:两数相加 第7题:三个数的最大乘积 第8题:等价多米诺骨牌对的数量 第9题:公平的糖果棒交换 第10题:替换后的最长重复字符 力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案...

目录

第1题:同构字符串

第2题:最后一块石头的重量

第3题:最小路径和

第4题:键盘行

第5题:存在重复元素 II

第6题:两数相加

第7题:三个数的最大乘积

第8题:等价多米诺骨牌对的数量

第9题:公平的糖果棒交换

第10题:替换后的最长重复字符


力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

第1题:同构字符串

试题要求如下:

回答(C语言):


  
  1. #define MAX_NUM 128
  2. bool isIsomorphic(char * s, char * t){
  3. int sLen = 0;
  4. int tLen = 0;
  5. int *hash1 = NULL;
  6. int *hash2 = NULL;
  7. sLen = strlen(s);
  8. tLen = strlen(t);
  9. // 特殊处理
  10. if (sLen != tLen) {
  11. return false;
  12. }
  13. // 分配空间
  14. hash1 = malloc(sizeof(int) * MAX_NUM);
  15. memset(hash1, 0, sizeof(int) * MAX_NUM);
  16. hash2 = malloc(sizeof(int) * MAX_NUM);
  17. memset(hash2, 0, sizeof(int) * MAX_NUM);
  18. // 统计字符串出现的次数
  19. for (int i = 0; i < sLen; i++) {
  20. if (hash1[s[i]] == 0) {
  21. hash1[s[i]] = t[i];
  22. }
  23. if (hash2[t[i]] == 0) {
  24. hash2[t[i]] = s[i];
  25. }
  26. if (hash1[s[i]] != t[i] || hash2[t[i]] != s[i]) {
  27. return false;
  28. }
  29. }
  30. return true;
  31. }

运行效率如下所示:


第2题:最后一块石头的重量

试题要求如下:

回答(C语言):


  
  1. int cmp(const void* _a, const void* _b){
  2. int a = *(int*)_a;
  3. int b = *(int*)_b;
  4. return b-a;
  5. }
  6. int lastStoneWeight(int* stones, int stonesSize){
  7. if(stonesSize <=1){
  8. return stones[0];
  9. }
  10. qsort(stones,stonesSize,sizeof(int),cmp);
  11. while(stones[1] != 0){
  12. stones[0] = stones[0] - stones[1];
  13. stones[1] = 0;
  14. qsort(stones,stonesSize,sizeof(int),cmp);
  15. }
  16. return stones[0];
  17. }

运行效率如下所示:


第3题:最小路径和

试题要求如下:

回答(C语言):


  
  1. int minPathSum(int** grid, int gridSize, int* gridColSize) {
  2. int rows = gridSize, columns = gridColSize[0];
  3. if (rows == 0 || columns == 0) {
  4. return 0;
  5. }
  6. int dp[rows][columns];
  7. dp[0][0] = grid[0][0];
  8. for (int i = 1; i < rows; i++) {
  9. dp[i][0] = dp[i - 1][0] + grid[i][0];
  10. }
  11. for (int j = 1; j < columns; j++) {
  12. dp[0][j] = dp[0][j - 1] + grid[0][j];
  13. }
  14. for (int i = 1; i < rows; i++) {
  15. for (int j = 1; j < columns; j++) {
  16. dp[i][j] = fmin(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  17. }
  18. }
  19. return dp[rows - 1][columns - 1];
  20. }

运行效率如下所示:


第4题:键盘行

试题要求如下:

解题思路:

1、先在 a 空间中,将3行键盘的下标分别记为1,2,3;

2、遍历数组,如果不在同一行就退出;

3、如果是正常退出的,将单词记录。

回答(C语言):


  
  1. /**
  2. * Note: The returned array must be malloced, assume caller calls free().
  3. */
  4. char ** findWords(char ** words, int wordsSize, int* returnSize){
  5. *returnSize=0;
  6. char **res=(char**)malloc(sizeof(char*)*wordsSize);
  7. char *a=(char*)calloc(59,sizeof(char));
  8. for(int i=0;i<58;i++){
  9. 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)
  10. a[i]=1;
  11. 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)
  12. a[i]=2;
  13. else
  14. a[i]=3;
  15. }
  16. int i,j;
  17. for(i=0;i<wordsSize;i++){
  18. for(j=1;j<strlen(words[i]);j++){
  19. char t=a[words[i][0]-65];
  20. if(t!=a[words[i][j]-65])
  21. break;
  22. }
  23. if(j==strlen(words[i])){
  24. res[*returnSize]=(char*)calloc(strlen(words[i])+1,1);
  25. strcpy(res[*returnSize],words[i]);
  26. (*returnSize)++;
  27. }
  28. }
  29. return res;
  30. }

运行效率如下所示:


第5题:存在重复元素 II

试题要求如下:

回答(C语言):


  
  1. bool containsNearbyDuplicate(int* nums, int numsSize, int k){
  2. if(numsSize==0)
  3. return false;
  4. int mark[numsSize];//Hash表
  5. memset(mark,-1,sizeof(int)*numsSize);
  6. for(int i = 0, tmp = 0; i < numsSize; i++)
  7. {
  8. tmp=nums[i]%numsSize;//Hash函数
  9. if(tmp<0)//转换为正数
  10. tmp+=(numsSize-1);
  11. if(mark[tmp]==-1)//没有存数
  12. mark[tmp]=i;//存下数组下标
  13. else//已经存数
  14. {
  15. while(nums[mark[tmp]]!=nums[i])//发生冲突
  16. {
  17. tmp++;tmp%=numsSize;
  18. if(mark[tmp]==-1)//没有存数
  19. mark[tmp]=i;//存下数组下标
  20. }
  21. //已经存过该数
  22. if(i!=mark[tmp])
  23. if(i-mark[tmp]<=k)//求差值
  24. return true;
  25. else
  26. mark[tmp]=i;
  27. }
  28. }
  29. return false;
  30. }

运行效率如下所示:


第6题:两数相加

试题要求如下:

回答(C语言):


  
  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. * int val;
  5. * struct ListNode *next;
  6. * };
  7. */
  8. struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
  9. struct ListNode* pre = (struct ListNode*)malloc(sizeof(struct ListNode));
  10. pre->val = 0;
  11. pre->next = NULL;
  12. struct ListNode* cur = pre;
  13. int carry = 0;
  14. int sum = 0;
  15. while(l1 != NULL || l2 != NULL){
  16. int x = (l1 == NULL) ? 0:l1->val;
  17. int y = (l2 == NULL) ? 0:l2->val;
  18. sum = x + y + carry;
  19. carry = sum / 10;
  20. struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
  21. p->val = sum % 10;
  22. p->next = NULL;
  23. cur->next = p;
  24. cur = cur->next;
  25. if(l1 != NULL){
  26. l1 = l1->next;
  27. }
  28. if(l2 != NULL){
  29. l2 = l2->next;
  30. }
  31. }
  32. if(carry == 1){
  33. struct ListNode* ca = (struct ListNode*)malloc(sizeof(struct ListNode));
  34. ca->val = carry;
  35. ca->next = NULL;
  36. cur->next = ca;
  37. }
  38. return pre->next;
  39. }

运行效率如下所示:


第7题:三个数的最大乘积

试题要求如下:

解题思路:

假设若使用排序法。

如果数组中全是非负数,则排序后最大的三个数相乘即为最大乘积;如果全是非正数,则最大的三个数相乘同样也为最大乘积。

如果数组中有正数有负数,则最大乘积既可能是三个最大正数的乘积,也可能是两个最小负数(即绝对值最大)与最大正数的乘积。

所以,根据此规律,使用线性扫描法实现。

回答(C语言):


  
  1. int maximumProduct(int* nums, int numsSize) {
  2. // 最小的和第二小的
  3. int min1 = INT_MAX, min2 = INT_MAX;
  4. // 最大的、第二大的和第三大的
  5. int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
  6. for (int i = 0; i < numsSize; i++) {
  7. int x = nums[i];
  8. if (x < min1) {
  9. min2 = min1;
  10. min1 = x;
  11. } else if (x < min2) {
  12. min2 = x;
  13. }
  14. if (x > max1) {
  15. max3 = max2;
  16. max2 = max1;
  17. max1 = x;
  18. } else if (x > max2) {
  19. max3 = max2;
  20. max2 = x;
  21. } else if (x > max3) {
  22. max3 = x;
  23. }
  24. }
  25. return fmax(min1 * min2 * max1, max1 * max2 * max3);
  26. }

运行效率如下所示:


第8题:等价多米诺骨牌对的数量

试题要求如下:

回答(C语言):


  
  1. int numEquivDominoPairs(int** dominoes, int dominoesSize, int* dominoesColSize) {
  2. int num[100];
  3. memset(num, 0, sizeof(num));
  4. int ret = 0;
  5. for (int i = 0; i < dominoesSize; i++) {
  6. int val = dominoes[i][0] < dominoes[i][1] ? dominoes[i][0] * 10 + dominoes[i][1] : dominoes[i][1] * 10 + dominoes[i][0];
  7. ret += num[val];
  8. num[val]++;
  9. }
  10. return ret;
  11. }

运行效率如下所示:


第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语言):


  
  1. /**
  2. * Note: The returned array must be malloced, assume caller calls free().
  3. */
  4. int cmp(const void *a, const void *b) {
  5. return *(int *)a - *(int *)b;
  6. }
  7. int* fairCandySwap(int* A, int ASize, int* B, int BSize, int* returnSize){
  8. *returnSize = 0;
  9. int *res = (int *)malloc(2 * sizeof(int));
  10. /* 判断是否动态内存是否申请成功*/
  11. if (res == NULL) {
  12. return NULL;
  13. }
  14. *returnSize = 2;
  15. int sumA = 0, sumB = 0, diff = 0;
  16. /* 求数组 A 和 B 的和*/
  17. for (int i = 0; i < ASize; ++i) {
  18. sumA += A[i];
  19. }
  20. for (int j = 0; j < BSize; ++j) {
  21. sumB += B[j];
  22. }
  23. diff = sumA - sumB;
  24. /* 排序,为后面进行二分查找做准备 */
  25. qsort(A, ASize, sizeof(int), cmp);
  26. for (int k = 0; k < BSize; ++k) {
  27. /* 二分查找的目标元素 */
  28. int target = diff / 2 + B[k];
  29. int l = 0, r = ASize - 1;
  30. /* 二分查找 */
  31. while (l <= r) {
  32. int m = l + (r - l)/2;
  33. if (A[m] > target) {
  34. r = m - 1;
  35. } else if (A[m] < target) {
  36. l = m + 1;
  37. /* 查找到目标元素,对数组元素赋值并返回 */
  38. } else {
  39. res[0] = target;
  40. res[1] = B[k];
  41. return res;
  42. }
  43. }
  44. }
  45. return NULL;
  46. }

运行效率如下所示:


第10题:替换后的最长重复字符

试题要求如下:

解题思路:

1、定义一个长度为 26 的整型数组(字符串仅包含大写英文字母),用于模拟哈希表(记录重复字母出现次数);

2、分别定义两个指针(字符下标),用于遍历字符串,两个指针组成的区间构成一个滑动窗口,当它们之间的间距大于字母当前出现最大频次加上 k 时,代表替换 k 次仍不能使得这个窗口之间的字母全是相同,此时需要将向右移动(缩小窗口的大小),同时将频次递减(增大了左边界);否则 r 向右移动增大窗口。

回答(C语言):


  
  1. int characterReplacement(char * s, int k){
  2. int maxCnt = 0;
  3. int l = 0, r = 0; // 滑动窗口[l, r)
  4. int freq[26] = {0}; // 记录重复字符出现频次
  5. int lenS = strlen(s);
  6. while (r < lenS) {
  7. freq[s[r] - 'A']++; // 计算当前字符出现频次
  8. maxCnt = fmax(maxCnt, freq[s[r++] - 'A']); // 计算当前字符出现的最大频次
  9. if (r - l > maxCnt + k) { // 滑动窗口大小大于字母最大频次加上能替换的次数
  10. freq[s[l++] - 'A']--; // l 右移动减少滑动窗口大小,同时频次减减
  11. }
  12. }
  13. return r - l;
  14. }

运行效率如下所示:

文章来源: blog.csdn.net,作者:不脱发的程序猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/m0_38106923/article/details/111861391

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。