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

目录

第1题:单词规律

第2题:找不同

第3题:在排序数组中查找元素的第一个和最后一个位置

第4题:使用最小花费爬楼梯

第5题:寻找峰值

第6题:字符串中的第一个唯一字符

第7题:两个数组的交集 II

第8题:分发饼干

第9题:旋转图像

第10题:矩阵置零


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

第1题:单词规律

试题要求如下:

回答(C语言):


  
  1. bool wordPattern(char * pattern, char * str){
  2. char **hash = (char **)malloc(26 * sizeof(char*));
  3. for (int i = 0; i < 26; ++i)
  4. {
  5. hash[i] = (char*)malloc(64 * sizeof(char));
  6. memset(hash[i], 0, 64 * sizeof(char));
  7. }
  8. int len = strlen(pattern);
  9. for (int i = 0; i < len; ++i)
  10. {
  11. char *p = str;
  12. while (p && *p != 0 && *p != ' ') ++p;
  13. if (' ' == *p) *p++ = 0;
  14. if (strlen(str) == 0)
  15. return false;
  16. int pos = pattern[i] - 'a';
  17. if (strlen(hash[pos]) == 0)
  18. {
  19. for (int j = 0; j < 26; ++j)
  20. {
  21. if (j != pos && strlen(hash[j]) > 0)
  22. {
  23. if (strcmp(hash[j], str) == 0)
  24. return false;
  25. }
  26. }
  27. strcpy(hash[pos], str);
  28. }
  29. else
  30. {
  31. if (strcmp(hash[pos], str) != 0)
  32. return false;
  33. }
  34. str = p;
  35. }
  36. if (strlen(str) > 0)
  37. return false;
  38. return true;
  39. }

运行效率如下所示:


第2题:找不同

试题要求如下:

解题思路:

回答(C语言):


  
  1. char findTheDifference(char* s, char* t) {
  2. int n = strlen(s), m = strlen(t);
  3. int as = 0, at = 0;
  4. for (int i = 0; i < n; i++) {
  5. as += s[i];
  6. }
  7. for (int i = 0; i < m; i++) {
  8. at += t[i];
  9. }
  10. return at - as;
  11. }

运行效率如下所示:


第3题:在排序数组中查找元素的第一个和最后一个位置

试题要求如下:

回答(C语言):


  
  1. int* searchRange(int* nums, int numsSize, int target, int* returnSize){
  2. int *ret=(int *)malloc(sizeof(int)*2);
  3. ret[0]=-1;
  4. ret[1]=-1;
  5. *returnSize=2;
  6. if(numsSize==0||target<nums[0]||target>nums[numsSize-1]){
  7. return ret;
  8. }
  9. int left=0, right=numsSize-1, mid=0, head=0, tail=0;
  10. while(left<=right){
  11. mid=(left+right)/2;
  12. if(nums[mid]>=target){
  13. right=mid-1;
  14. }
  15. else{
  16. left=mid+1; //mid存的就是第一个>=target的那个值的索引
  17. }
  18. }
  19. head=left;
  20. left=0, right=numsSize-1, mid=0;
  21. while(left<=right){
  22. mid=(left+right)/2;
  23. if(nums[mid]<=target){
  24. left=mid+1;
  25. }
  26. else{
  27. right=mid-1;
  28. }
  29. }
  30. tail=right;
  31. if(nums[head]==target){ //存在这个数
  32. ret[0]=head;
  33. ret[1]=tail;
  34. }
  35. return ret;
  36. }

运行效率如下所示:


第4题:使用最小花费爬楼梯

试题要求如下:

回答(C语言):


  
  1. int minCostClimbingStairs(int* cost, int costSize) {
  2. int prev = 0, curr = 0;
  3. for (int i = 2; i <= costSize; i++) {
  4. int next = fmin(curr + cost[i - 1], prev + cost[i - 2]);
  5. prev = curr;
  6. curr = next;
  7. }
  8. return curr;
  9. }

运行效率如下所示:


第5题:寻找峰值

试题要求如下:

回答(C语言):


  
  1. int findPeakElement(int *nums, int numsSize)
  2. {
  3. if (!nums || numsSize < 1) {
  4. return 0;
  5. }
  6. if (numsSize == 1) {
  7. return 0;
  8. }
  9. if (nums[0] > nums[1]) {
  10. return 0;
  11. }
  12. if (nums[numsSize - 1] > nums[numsSize - 2]) {
  13. return numsSize - 1;
  14. }
  15. for (int i = 1; i < numsSize - 1; i++) {
  16. if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
  17. return i;
  18. }
  19. }
  20. return -1;
  21. }

运行效率如下所示:


第6题:字符串中的第一个唯一字符

试题要求如下:

解题思路:

两次遍历,一次记录字符出现次数,一次找出第一个出现一次的索引。

回答(C语言):


  
  1. int firstUniqChar(char * s){
  2. if(s == NULL || strlen(s) == 0) return -1;
  3. int len = strlen(s);
  4. if(len == 1) return 0;
  5. int recode[26] = {0};
  6. //记录字符出现次数
  7. for(int i=0;i<len;i++){
  8. recode[s[i]-'a']++;
  9. }
  10. //找出第一个出现一次的索引
  11. for(int i=0;i<len;i++){
  12. if(recode[s[i]-'a'] == 1){
  13. return i;
  14. }
  15. }
  16. return -1;
  17. }

运行效率如下所示:


第7题:两个数组的交集 II

试题要求如下:

回答(C语言):


  
  1. /**
  2. * Note: The returned array must be malloced, assume caller calls free().
  3. */
  4. struct cell
  5. {
  6. int value;
  7. int times1;
  8. int times2;
  9. };
  10. int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
  11. int i = 0, cur, mapSize = nums1Size + nums2Size, *ret = (int *)malloc(sizeof(int) * (nums1Size + nums2Size));
  12. *returnSize = 0;
  13. struct cell *hashMap = (struct cell *)memset(malloc(sizeof(struct cell) * mapSize), 0, sizeof(struct cell) * mapSize);
  14. for (i = 0; i < nums1Size; i++)
  15. {
  16. cur = (nums1[i] > 0 ? 1 : -1) * (nums1[i] % mapSize);
  17. while((hashMap[cur].times1 || hashMap[cur].times2) && hashMap[cur].value != nums1[i])
  18. {
  19. cur++;
  20. cur = cur == mapSize ? 0 : cur;
  21. }
  22. if (hashMap[cur].times1 == 0 && hashMap[cur].times2 == 0)
  23. hashMap[cur].value = nums1[i];
  24. hashMap[cur].times1++;
  25. }
  26. for (i = 0; i < nums2Size; i++)
  27. {
  28. cur = (nums2[i] > 0 ? 1 : -1) * (nums2[i] % mapSize);
  29. while((hashMap[cur].times1 || hashMap[cur].times2) && hashMap[cur].value != nums2[i])
  30. {
  31. cur++;
  32. cur = cur == mapSize ? 0 : cur;
  33. }
  34. if (hashMap[cur].times1 == 0 && hashMap[cur].times2 == 0)
  35. hashMap[cur].value = nums2[i];
  36. hashMap[cur].times2++;
  37. }
  38. for (i = 0; i < mapSize; i++)
  39. while ((hashMap[i].times2--) && (hashMap[i].times1--))
  40. ret[(*returnSize)++] = hashMap[i].value;
  41. return ret;
  42. }

运行效率如下所示:


第8题:分发饼干

试题要求如下:

 

回答(C语言):


  
  1. int compare(const void * a, const void * b)
  2. {
  3. return ( *(int*)b - *(int*)a );
  4. }
  5. int findContentChildren(int* g, int gSize, int* s, int sSize){
  6. int count=0;
  7. qsort (g, gSize, sizeof(int), compare);
  8. qsort (s, sSize, sizeof(int), compare);
  9. for(int i = 0, j = 0; i < gSize && j < sSize; i++, j++)
  10. {
  11. if(s[j] >= g[i])
  12. count++;
  13. else
  14. j--;
  15. }
  16. return count;
  17. }

运行效率如下所示:


第9题:旋转图像

试题要求如下:

回答(C语言):


  
  1. void rotate(int** matrix, int matrixSize, int* matrixColSize) {
  2. int matrix_new[matrixSize][matrixSize];
  3. for (int i = 0; i < matrixSize; i++) {
  4. for (int j = 0; j < matrixSize; j++) {
  5. matrix_new[i][j] = matrix[i][j];
  6. }
  7. }
  8. for (int i = 0; i < matrixSize; ++i) {
  9. for (int j = 0; j < matrixSize; ++j) {
  10. matrix[j][matrixSize - i - 1] = matrix_new[i][j];
  11. }
  12. }
  13. }

运行效率如下所示:


第10题:矩阵置零

试题要求如下:

回答(C语言):


  
  1. void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
  2. int i = 0;
  3. int j = 0;
  4. int iRow = matrixSize;
  5. int iCol = matrixColSize[0];
  6. int row[iRow];
  7. int col[iCol];
  8. memset(row, 0x00, sizeof(int) * iRow);
  9. memset(col, 0x00, sizeof(int) * iCol);
  10. //1,遍历一遍,找出所有为0的元素,并在行,列数组中标记
  11. for (i = 0; i < iRow; i++)
  12. {
  13. for (j = 0; j < iCol; j++)
  14. {
  15. if (matrix[i][j] == 0)
  16. {
  17. row[i] = 1;
  18. col[j] = 1;
  19. }
  20. }
  21. }
  22. //2,遍历数组,按照行,列中的结果修改矩阵
  23. for (i = 0; i < iRow; i++)
  24. {
  25. for (j = 0; j < iCol; j++)
  26. {
  27. if (row[i] == 1)
  28. {
  29. matrix[i][j] = 0;
  30. }
  31. if (col[j] == 1)
  32. {
  33. matrix[i][j] = 0;
  34. }
  35. }
  36. }
  37. }

运行效率如下所示:

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

原文链接:handsome-man.blog.csdn.net/article/details/111245331

(完)