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

目录

第1题:数组中的第K个最大元素

第2题:字符串相乘

第3题:最长重复子数组

第4题:有效的完全平方

第5题:访问所有点的最小时间

第6题:路径总和

第7题:跳水板

第8题:解压缩编码列表

第9题:汉明距离

第10题:判断能否形成等差数列


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

第1题:数组中的第K个最大元素

试题要求如下:

回答(C语言):


  
  1. int cmp(const void *a,const void*b)
  2. {
  3. return *(int *)a > *(int *)b;
  4. }
  5. int findKthLargest(int* nums, int numsSize, int k){
  6. qsort(nums,numsSize,sizeof(int),cmp);
  7. return nums[numsSize-k];
  8. }

运行效率如下所示:


第2题:字符串相乘

试题要求如下:

解答思路:

 请参见:力扣官方

回答(C语言):


  
  1. char * multiply(char * num1, char * num2)
  2. {
  3. int length1 = strlen(num1);
  4. int length2 = strlen(num2);
  5. int totalLength = length1 + length2; //获取相乘后字符串的总有效位数
  6. int charIndex = 0; //定义负责索引字段
  7. int valueIndex = 0;
  8. int *value = (int *)malloc(sizeof(int) * totalLength);
  9. memset(value, 0, sizeof(int) * totalLength);
  10. char *result = (char *)malloc(sizeof(char) * (totalLength + 1));
  11. for(int i = length1 - 1; i >= 0; i--)
  12. {
  13. for(int j = length2 - 1; j >= 0; j--)
  14. {
  15. value[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
  16. }
  17. }
  18. for(int i= totalLength - 1; i > 0; i--) //获取每个位置上面的数字并处理进位
  19. {
  20. value[i - 1] += value[i] / 10;
  21. value[i] %= 10;
  22. }
  23. while(value[valueIndex] == 0 && valueIndex < totalLength -1 )
  24. {
  25. valueIndex++; //忽略掉前面多余的0,但是最高位也就是唯一的一位0不能忽略
  26. }
  27. while(valueIndex < totalLength)
  28. {
  29. result[charIndex++] = value[valueIndex++] + '0';
  30. }
  31. result[charIndex] = '\0'; //默认补上字符串的终止符
  32. return result;
  33. }

运行效率如下所示:


第3题:最长重复子数组

试题要求如下:

解答思路:

动态规划。

回答(C语言):


  
  1. int findLength(int* A, int ASize, int* B, int BSize) {
  2. int dp[ASize + 1][BSize + 1];
  3. memset(dp, 0, sizeof(dp));
  4. int ans = 0;
  5. for (int i = ASize - 1; i >= 0; i--) {
  6. for (int j = BSize - 1; j >= 0; j--) {
  7. dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
  8. ans = fmax(ans, dp[i][j]);
  9. }
  10. }
  11. return ans;
  12. }

运行效率如下所示:


第4题:有效的完全平方

试题要求如下:

解答思路:

完全平方指用一个整数乘以自己,例如1*1,2*2,3*3等,依此类推。若一个数能表示成某个整数的平方的形式,则称这个数为完全平方数。 

完全平方数可以通过累加从1往后的奇数找到,

1 = 1;

4 = 1 + 3;

9 = 1 + 3 + 5;

16 = 1 + 3 + 5 + 7;

...

回答(C语言):


  
  1. bool isPerfectSquare(int num){
  2. if (num == 0) return false;
  3. int i = 1;
  4. while ( num > 0){
  5. num -= i;
  6. i += 2;
  7. }
  8. return num == 0 ? true : false;
  9. }

运行效率如下所示:


第5题:访问所有点的最小时间

试题要求如下:

解答思路:

把问题看成分析两点之间的距离的关系:

1、两点的x值有一个距离,y值有一个距离

2、因为只能竖着横着或者斜着走,故最佳行走方式即为

(1)、若两点x轴距离大于y轴距离,就先横着走,直到xy距离两者相等

(2)、若两点y轴距离大于x轴距离,就先竖着走,直到xy距离两者相等

3、xy距离相等,直接斜着走,此时距离即为x或y轴距离,直接相加即可

回答(C语言):


  
  1. int minTimeToVisitAllPoints(int** points, int pointsSize, int* pointsColSize){
  2. int sum = 0;//总和
  3. int a = 0,b = 0;//两点x、y距离
  4. for(int i = 0;i < pointsSize-1;i++){
  5. a = abs(points[i][0]-points[i+1][0]);
  6. b = abs(points[i][1]-points[i+1][1]);
  7. sum += abs(a-b);
  8. if(a>b) sum += b;
  9. else sum += a;
  10. }
  11. *pointsColSize=sum;
  12. return sum;
  13. }

运行效率如下所示:


第6题:路径总和

试题要求如下:

回答(C语言):


  
  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * struct TreeNode *left;
  6. * struct TreeNode *right;
  7. * };
  8. */
  9. typedef struct TreeNode TN;
  10. bool hasPathSum(struct TreeNode* root, int sum){
  11. if(root == NULL)
  12. return false;
  13. if(root->val == sum && root->left == NULL && root->right == NULL)
  14. return true;
  15. if(hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val))
  16. return true;
  17. return false;
  18. }

运行效率如下所示:


第7题:跳水板

试题要求如下:

解答思路:

1、如果 k=0k=0,则不能建造任何跳水板,因此返回空数组。

2、如果 shorter和 longer相等,则建造的跳水板的长度是唯一的,都等于 shorter*k。

回答(C语言):


  
  1. int* divingBoard(int shorter, int longer, int k, int* returnSize) {
  2. if (k == 0) {
  3. *returnSize = 0;
  4. return NULL;
  5. }
  6. if (shorter == longer) {
  7. int* p = (int*)malloc(sizeof(int));
  8. *p = shorter * k;
  9. *returnSize = 1;
  10. return p;
  11. }
  12. *returnSize = k + 1;
  13. int* lengths = (int*)malloc(sizeof(int) * (k + 1));
  14. for (int i = 0; i <= k; ++i) {
  15. lengths[i] = shorter * (k - i) + longer * i;
  16. }
  17. return lengths;
  18. }

运行效率如下所示:


第8题:解压缩编码列表

试题要求如下:

回答(C语言):


  
  1. /**
  2. * Note: The returned array must be malloced, assume caller calls free().
  3. */
  4. int* decompressRLElist(int* nums, int numsSize, int* returnSize){
  5. int size=0;
  6. int *returned=calloc(5000,sizeof(int));
  7. for(int i = 0,k = 0;i < numsSize;i += 2){
  8. size=nums[i]+size;
  9. for(int j = 0;j < nums[i];j++){
  10. returned[k++]=nums[i+1];
  11. }
  12. }
  13. *returnSize=size;
  14. return returned;
  15. }

运行效率如下所示:


第9题:汉明距离

试题要求如下:

回答(C语言):


  
  1. int hammingDistance(int x, int y){
  2. int cnt = 0, n = 32;
  3. while(n--){
  4. if((x & 1) ^ (y & 1))
  5. cnt++;
  6. x >>= 1;
  7. y >>= 1;
  8. }
  9. return cnt;
  10. }

运行效率如下所示:


第10题:判断能否形成等差数列

试题要求如下:

回答(C语言):


  
  1. int cmp(const void *a, const void *b)
  2. {
  3. return *((int*)a) - *((int*)b);
  4. }
  5. bool canMakeArithmeticProgression(int* arr, int arrSize){
  6. qsort(arr, arrSize, sizeof(int), cmp);
  7. int minus = arr[1] - arr[0];
  8. for (int i = 0; i < arrSize; i++) {
  9. if (arr[i] != (arr[0] + i * minus)) {
  10. return false;
  11. }
  12. }
  13. return true;
  14. }

运行效率如下所示:

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

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

(完)