1
力扣 (LeetCode) 刷题，简单 + 中等题 (第 30 期)
发布于: 2021 年 03 月 02 日
力扣(LeetCode)定期解题，每期 10 道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第 1 题：单词规律
试题要求如下：
回答（C 语言）：
bool wordPattern(char * pattern, char * str){ char **hash = (char **)malloc(26 * sizeof(char*)); for (int i = 0; i < 26; ++i) { hash[i] = (char*)malloc(64 * sizeof(char)); memset(hash[i], 0, 64 * sizeof(char)); } int len = strlen(pattern); for (int i = 0; i < len; ++i) { char *p = str; while (p && *p != 0 && *p != ' ') ++p; if (' ' == *p) *p++ = 0; if (strlen(str) == 0) return false; int pos = pattern[i] - 'a'; if (strlen(hash[pos]) == 0) { for (int j = 0; j < 26; ++j) { if (j != pos && strlen(hash[j]) > 0) { if (strcmp(hash[j], str) == 0) return false; } } strcpy(hash[pos], str); } else { if (strcmp(hash[pos], str) != 0) return false; } str = p; } if (strlen(str) > 0) return false; return true;}复制代码
运行效率如下所示：
第 2 题：找不同
试题要求如下：
解题思路：
回答（C 语言）：
char findTheDifference(char* s, char* t) { int n = strlen(s), m = strlen(t); int as = 0, at = 0; for (int i = 0; i < n; i++) { as += s[i]; } for (int i = 0; i < m; i++) { at += t[i]; } return at - as;}复制代码
运行效率如下所示：
第 3 题：在排序数组中查找元素的第一个和最后一个位置
试题要求如下：
回答（C 语言）：
int* searchRange(int* nums, int numsSize, int target, int* returnSize){ int *ret=(int *)malloc(sizeof(int)*2); ret[0]=-1; ret[1]=-1; *returnSize=2; if(numsSize==0||target<nums[0]||target>nums[numsSize-1]){ return ret; } int left=0, right=numsSize-1, mid=0, head=0, tail=0; while(left<=right){ mid=(left+right)/2; if(nums[mid]>=target){ right=mid-1; } else{ left=mid+1; //mid存的就是第一个>=target的那个值的索引 } } head=left; left=0, right=numsSize-1, mid=0; while(left<=right){ mid=(left+right)/2; if(nums[mid]<=target){ left=mid+1; } else{ right=mid-1; } } tail=right; if(nums[head]==target){ //存在这个数 ret[0]=head; ret[1]=tail; } return ret;}复制代码
运行效率如下所示：
第 4 题：使用最小花费爬楼梯
试题要求如下：
回答（C 语言）：
int minCostClimbingStairs(int* cost, int costSize) { int prev = 0, curr = 0; for (int i = 2; i <= costSize; i++) { int next = fmin(curr + cost[i - 1], prev + cost[i - 2]); prev = curr; curr = next; } return curr;}复制代码
运行效率如下所示：
第 5 题：寻找峰值
试题要求如下：
回答（C 语言）：
int findPeakElement(int *nums, int numsSize){ if (!nums || numsSize < 1) { return 0; } if (numsSize == 1) { return 0; } if (nums[0] > nums[1]) { return 0; } if (nums[numsSize - 1] > nums[numsSize - 2]) { return numsSize - 1; } for (int i = 1; i < numsSize - 1; i++) { if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) { return i; } } return -1;}复制代码
运行效率如下所示：
第 6 题：字符串中的第一个唯一字符
试题要求如下：
解题思路：
两次遍历，一次记录字符出现次数，一次找出第一个出现一次的索引。
回答（C 语言）：
int firstUniqChar(char * s){ if(s == NULL || strlen(s) == 0) return -1; int len = strlen(s); if(len == 1) return 0; int recode[26] = {0}; //记录字符出现次数 for(int i=0;i<len;i++){ recode[s[i]-'a']++; } //找出第一个出现一次的索引 for(int i=0;i<len;i++){ if(recode[s[i]-'a'] == 1){ return i; } } return -1;}复制代码
运行效率如下所示：
第 7 题：两个数组的交集 II
试题要求如下：
回答（C 语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */struct cell{ int value; int times1; int times2;};int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){ int i = 0, cur, mapSize = nums1Size + nums2Size, *ret = (int *)malloc(sizeof(int) * (nums1Size + nums2Size)); *returnSize = 0; struct cell *hashMap = (struct cell *)memset(malloc(sizeof(struct cell) * mapSize), 0, sizeof(struct cell) * mapSize); for (i = 0; i < nums1Size; i++) { cur = (nums1[i] > 0 ? 1 : -1) * (nums1[i] % mapSize); while((hashMap[cur].times1 || hashMap[cur].times2) && hashMap[cur].value != nums1[i]) { cur++; cur = cur == mapSize ? 0 : cur; } if (hashMap[cur].times1 == 0 && hashMap[cur].times2 == 0) hashMap[cur].value = nums1[i]; hashMap[cur].times1++; } for (i = 0; i < nums2Size; i++) { cur = (nums2[i] > 0 ? 1 : -1) * (nums2[i] % mapSize); while((hashMap[cur].times1 || hashMap[cur].times2) && hashMap[cur].value != nums2[i]) { cur++; cur = cur == mapSize ? 0 : cur; } if (hashMap[cur].times1 == 0 && hashMap[cur].times2 == 0) hashMap[cur].value = nums2[i]; hashMap[cur].times2++; } for (i = 0; i < mapSize; i++) while ((hashMap[i].times2--) && (hashMap[i].times1--)) ret[(*returnSize)++] = hashMap[i].value; return ret;}复制代码
运行效率如下所示：
第 8 题：分发饼干
试题要求如下：
回答（C 语言）：
int compare(const void * a, const void * b){ return ( *(int*)b - *(int*)a );} int findContentChildren(int* g, int gSize, int* s, int sSize){ int count=0; qsort (g, gSize, sizeof(int), compare); qsort (s, sSize, sizeof(int), compare); for(int i = 0, j = 0; i < gSize && j < sSize; i++, j++) { if(s[j] >= g[i]) count++; else j--; } return count;}复制代码
运行效率如下所示：
第 9 题：旋转图像
试题要求如下：
回答（C 语言）：
void rotate(int** matrix, int matrixSize, int* matrixColSize) { int matrix_new[matrixSize][matrixSize]; for (int i = 0; i < matrixSize; i++) { for (int j = 0; j < matrixSize; j++) { matrix_new[i][j] = matrix[i][j]; } } for (int i = 0; i < matrixSize; ++i) { for (int j = 0; j < matrixSize; ++j) { matrix[j][matrixSize - i - 1] = matrix_new[i][j]; } }}复制代码
运行效率如下所示：
第 10 题：矩阵置零
试题要求如下：
回答（C 语言）：
void setZeroes(int** matrix, int matrixSize, int* matrixColSize){ int i = 0; int j = 0; int iRow = matrixSize; int iCol = matrixColSize[0]; int row[iRow]; int col[iCol]; memset(row, 0x00, sizeof(int) * iRow); memset(col, 0x00, sizeof(int) * iCol); //1,遍历一遍，找出所有为0的元素，并在行，列数组中标记 for (i = 0; i < iRow; i++) { for (j = 0; j < iCol; j++) { if (matrix[i][j] == 0) { row[i] = 1; col[j] = 1; } } } //2,遍历数组，按照行，列中的结果修改矩阵 for (i = 0; i < iRow; i++) { for (j = 0; j < iCol; j++) { if (row[i] == 1) { matrix[i][j] = 0; } if (col[j] == 1) { matrix[i][j] = 0; } } }}复制代码
运行效率如下所示：
划线
评论
复制
发布于: 2021 年 03 月 02 日阅读数: 11
版权声明: 本文为 InfoQ 作者【不脱发的程序猿】的原创文章。
原文链接:【http://xie.infoq.cn/article/2c09838197efd96a85862a19b】。文章转载请联系作者。
不脱发的程序猿
关注
【研究方向】物联网、嵌入式、AI、Python 2018.02.09 加入
【公众号】美男子玩编程
评论