力扣(LeetCode)刷题，简单题+中等题(第17期)
【摘要】 目录
第1题：数组中的第K个最大元素
第2题：字符串相乘
第3题：最长重复子数组
第4题：有效的完全平方
第5题：访问所有点的最小时间
第6题：路径总和
第7题：跳水板
第8题：解压缩编码列表
第9题：汉明距离
第10题：判断能否形成等差数列
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互...
目录
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：数组中的第K个最大元素
试题要求如下：
回答（C语言）：
-
int cmp(const void *a,const void*b)
-
{
-
return *(int *)a > *(int *)b;
-
}
-
int findKthLargest(int* nums, int numsSize, int k){
-
qsort(nums,numsSize,sizeof(int),cmp);
-
return nums[numsSize-k];
-
}
运行效率如下所示：
第2题：字符串相乘
试题要求如下：
解答思路：
请参见：力扣官方
回答（C语言）：
-
char * multiply(char * num1, char * num2)
-
{
-
int length1 = strlen(num1);
-
int length2 = strlen(num2);
-
int totalLength = length1 + length2; //获取相乘后字符串的总有效位数
-
-
int charIndex = 0; //定义负责索引字段
-
int valueIndex = 0;
-
-
int *value = (int *)malloc(sizeof(int) * totalLength);
-
memset(value, 0, sizeof(int) * totalLength);
-
-
char *result = (char *)malloc(sizeof(char) * (totalLength + 1));
-
-
for(int i = length1 - 1; i >= 0; i--)
-
{
-
for(int j = length2 - 1; j >= 0; j--)
-
{
-
value[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
-
}
-
}
-
-
for(int i= totalLength - 1; i > 0; i--) //获取每个位置上面的数字并处理进位
-
{
-
value[i - 1] += value[i] / 10;
-
value[i] %= 10;
-
}
-
-
while(value[valueIndex] == 0 && valueIndex < totalLength -1 )
-
{
-
valueIndex++; //忽略掉前面多余的0，但是最高位也就是唯一的一位0不能忽略
-
}
-
while(valueIndex < totalLength)
-
{
-
result[charIndex++] = value[valueIndex++] + '0';
-
}
-
-
result[charIndex] = '\0'; //默认补上字符串的终止符
-
-
return result;
-
}
运行效率如下所示：
第3题：最长重复子数组
试题要求如下：
解答思路：
动态规划。
回答（C语言）：
-
int findLength(int* A, int ASize, int* B, int BSize) {
-
int dp[ASize + 1][BSize + 1];
-
memset(dp, 0, sizeof(dp));
-
int ans = 0;
-
-
for (int i = ASize - 1; i >= 0; i--) {
-
for (int j = BSize - 1; j >= 0; j--) {
-
dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
-
ans = fmax(ans, dp[i][j]);
-
}
-
}
-
-
return ans;
-
}
运行效率如下所示：
第4题：有效的完全平方
试题要求如下：
解答思路：
完全平方指用一个整数乘以自己，例如1*1，2*2，3*3等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。
完全平方数可以通过累加从1往后的奇数找到，
1 = 1;
4 = 1 + 3;
9 = 1 + 3 + 5;
16 = 1 + 3 + 5 + 7;
...
回答（C语言）：
-
bool isPerfectSquare(int num){
-
if (num == 0) return false;
-
-
int i = 1;
-
-
while ( num > 0){
-
num -= i;
-
i += 2;
-
}
-
-
return num == 0 ? true : false;
-
}
运行效率如下所示：
第5题：访问所有点的最小时间
试题要求如下：
解答思路：
把问题看成分析两点之间的距离的关系：
1、两点的x值有一个距离，y值有一个距离
2、因为只能竖着横着或者斜着走，故最佳行走方式即为
(1)、若两点x轴距离大于y轴距离，就先横着走，直到xy距离两者相等
(2)、若两点y轴距离大于x轴距离，就先竖着走，直到xy距离两者相等
3、xy距离相等，直接斜着走，此时距离即为x或y轴距离，直接相加即可
回答（C语言）：
-
int minTimeToVisitAllPoints(int** points, int pointsSize, int* pointsColSize){
-
int sum = 0;//总和
-
int a = 0,b = 0;//两点x、y距离
-
-
for(int i = 0;i < pointsSize-1;i++){
-
a = abs(points[i][0]-points[i+1][0]);
-
b = abs(points[i][1]-points[i+1][1]);
-
sum += abs(a-b);
-
if(a>b) sum += b;
-
else sum += a;
-
}
-
-
*pointsColSize=sum;
-
return sum;
-
}
运行效率如下所示：
第6题：路径总和
试题要求如下：
回答（C语言）：
-
/**
-
* Definition for a binary tree node.
-
* struct TreeNode {
-
* int val;
-
* struct TreeNode *left;
-
* struct TreeNode *right;
-
* };
-
*/
-
-
typedef struct TreeNode TN;
-
bool hasPathSum(struct TreeNode* root, int sum){
-
if(root == NULL)
-
return false;
-
if(root->val == sum && root->left == NULL && root->right == NULL)
-
return true;
-
if(hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val))
-
return true;
-
return false;
-
}
运行效率如下所示：
第7题：跳水板
试题要求如下：
解答思路：
1、如果 k=0k=0，则不能建造任何跳水板，因此返回空数组。
2、如果 shorter和 longer相等，则建造的跳水板的长度是唯一的，都等于 shorter*k。
回答（C语言）：
-
int* divingBoard(int shorter, int longer, int k, int* returnSize) {
-
if (k == 0) {
-
*returnSize = 0;
-
return NULL;
-
}
-
-
if (shorter == longer) {
-
int* p = (int*)malloc(sizeof(int));
-
*p = shorter * k;
-
*returnSize = 1;
-
return p;
-
}
-
-
*returnSize = k + 1;
-
int* lengths = (int*)malloc(sizeof(int) * (k + 1));
-
for (int i = 0; i <= k; ++i) {
-
lengths[i] = shorter * (k - i) + longer * i;
-
}
-
return lengths;
-
}
运行效率如下所示：
第8题：解压缩编码列表
试题要求如下：
回答（C语言）：
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
int* decompressRLElist(int* nums, int numsSize, int* returnSize){
-
int size=0;
-
int *returned=calloc(5000,sizeof(int));
-
-
for(int i = 0,k = 0;i < numsSize;i += 2){
-
size=nums[i]+size;
-
for(int j = 0;j < nums[i];j++){
-
returned[k++]=nums[i+1];
-
}
-
}
-
-
*returnSize=size;
-
return returned;
-
}
运行效率如下所示：
第9题：汉明距离
试题要求如下：
回答（C语言）：
-
int hammingDistance(int x, int y){
-
int cnt = 0, n = 32;
-
-
while(n--){
-
if((x & 1) ^ (y & 1))
-
cnt++;
-
x >>= 1;
-
y >>= 1;
-
}
-
-
return cnt;
-
}
运行效率如下所示：
第10题：判断能否形成等差数列
试题要求如下：
回答（C语言）：
-
int cmp(const void *a, const void *b)
-
{
-
return *((int*)a) - *((int*)b);
-
}
-
-
bool canMakeArithmeticProgression(int* arr, int arrSize){
-
qsort(arr, arrSize, sizeof(int), cmp);
-
-
int minus = arr[1] - arr[0];
-
-
for (int i = 0; i < arrSize; i++) {
-
if (arr[i] != (arr[0] + i * minus)) {
-
return false;
-
}
-
}
-
-
return true;
-
}
运行效率如下所示：
文章来源: handsome-man.blog.csdn.net，作者：不脱发的程序猿，版权归原作者所有，如需转载，请联系作者。
原文链接：handsome-man.blog.csdn.net/article/details/106992117
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）