您现在的位置是:首页 >其他 >(C语言版)力扣(LeetCode)题库1-5题解析网站首页其他
(C语言版)力扣(LeetCode)题库1-5题解析
1.两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
题目链接:两数之和
解析
代码如下:
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
for(int i=0;i<numsSize;i++)
{
for(int j=i+1;j<numsSize;j++)
{
if(nums[i]+nums[j]==target)
{
int* ret=malloc(sizeof(int)*2);
ret[0]=i;
ret[1]=j;
*returnSize=2;
return ret;
}
}
}
*returnSize=0;
return NULL;
}
这道题最简单的一种写法,就是两层循环嵌套遍历数组每一位和后面的每一位进行相加,最终找到后将两数存入需返回的数组,遍历结束若没找到符合的值,则返回空。
2.两数相加
题目
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
题目链接:两数相加
解法
代码如下:
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* head=NULL,* tail=NULL;
int carry=0;
while(l1||l2)
{
int n1=l1?l1->val:0;
int n2=l2?l2->val:0;
int sum=n1+n2+carry;
if(!head)
{
head=tail=malloc(sizeof(struct ListNode));
tail->val=sum%10;
tail->next=NULL;
}
else
{
tail->next=malloc(sizeof(struct ListNode));
tail->next->val=sum%10;
tail=tail->next;
tail->next=NULL;
}
carry=sum/10;
if(l1)
l1=l1->next;
if(l2)
l2=l2->next;
}
if(carry>0)
{
tail->next=malloc(sizeof(struct ListNode));
tail->next->val=carry;
tail->next->next=NULL;
}
return head;
}
首先这里我们先建立两个节点,head为头节点,也就是最后我们要返回的头结点,tail则为插入元素的一个指针结点,定义carry初始值为0,它是用来记录满10进一的,比如两数相加等于10时,则此位为0,而carry=1,那么下一位相加时,就多进1,第一个while循环就是为了不断遍历l1和l2的,首先是n1和n2分别记录l1和l2当前节点的值,sum记录n1+n2以及carry进一值,第一次进入循环进入第一个条件语句,因为此时head节点为空,head和tail同时开辟一段空间,当前节点记录的值为sum%10的值,因为一个节点只能记录一位数,下面再将sum/10的值赋给carry,若为两位数,那么carry就为1,下一次sum值相加时就多进一,第二次往后进入循环,就进入else语句,fail不断向后赋值,直至两链表遍历结束为止,最后一次相加结束后,跳出循环,再对carry值进行判定,如果大于零,说明最高位还有一位,再加入一个新结点记录最高位的值,也就是carry的值,最后返回新链表头结点head即可。
3.无重复字符的最长字串
题目
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
题目链接:无重复字符的最长字串
解法
int lengthOfLongestSubstring(char * s){
int len=strlen(s);
int left=0,right=0,max=0;;
for(int i=0;i<len;i++)
{
if(left<right)
{
for(int j=left;j<right;j++)
{
if(s[j]==s[right])
{
left=j+1;
break;
}
}
}
max=max<(right-left+1)?(right-left+1):max;
right++;
}
return max;
}
这种解法使用了子串前后差值的解法,避免了使用count重复遍历进行++的麻烦,且更高效,首先我们记录字符串的长度,初始化左右差值即最大长度max为0,right每向前一步,进行判定,若left和此时的right相等,则left向前一步,max不断记录left和right之间的差值产生的最大值,遍历字符串完成,此时max记录的即为最大子串的长度。
4. 寻找两个正序数组的中位数
题目
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
题目链接:寻找两个正序数组的中位数
解法
这里题目的要求是时间复杂度应该为 O(log (m+n)),因为作者这里是用c的写法,暂时没想到能达到这个标准的写法,两种解法均为暴力求解,如果有更好的解法,可以在评论区写写或和作者私聊探讨。
解法一
代码如下:
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
int sz=nums1Size+nums2Size;
int* nums3=malloc(sizeof(int)*sz);
for(int i=0;i<nums1Size;i++)
nums3[i]=nums1[i];
int m=nums1Size-1,n=nums2Size-1,k=sz-1;
while(n>=0)
{
if(m<0||nums2[n]>nums3[m])
nums3[k--]=nums2[n--];
else
nums3[k--]=nums3[m--];
}
if(sz%2==0)
return (nums3[sz/2-1]+nums3[sz/2])/2.0;
else
return nums3[sz/2];
}
这种写法首先创建额外的数组nums3,长度为两数组长度相加的长度,首先插入数组1的全部值,然后再调整顺序依次插入数组2的值,最终得到的nums3即为有序的合并数组,长度如果为奇数,直接返回中间值即可,若为偶数,则返回中间两值相加再除2即可。
解法二:
代码如下:
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
void AdjustDown(int* a, int n, int parent)//向下调整
{
int child = parent * 2 + 1;
while (child < n)
{
// 选出左右孩子中小的那一个
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
// 如果小的孩子小于父亲,则交换,并继续向下调整
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 堆排序 -- O(N*logN)
void HeapSort(int* a, int n)
{
// O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
// O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
void ShellSort(int* a, int n)
{
// 多次预排序(gap > 1) +直接插入 (gap == 1)
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
int sz=nums1Size+nums2Size;
int* nums3=malloc(sizeof(int)*sz);
for(int i=0;i<nums1Size;i++)
nums3[i]=nums1[i];
for(int i=nums1Size,j=0;i<sz;i++,j++)
nums3[i]=nums2[j];
ShellSort(nums3,sz);
if(sz%2==0)
return (nums3[sz/2-1]+nums3[sz/2])/2.0;
else
return nums3[sz/2];
}
这种写法就是直接合并再使用一个堆排序,什么排序都行,然后和上面返回值一样,两种写法都属于暴力解法,严格来说不符合题目要求,学过C++应该是可以写出很好的题解的,作者对这道题也是能力有限了,还得继续学习啊。
5. 最长回文子串
题目
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
题目链接:最长回文子串
解法
代码如下:
void extend(char* s,int left,int right,int* ans)
{
if(left<0&&right>=strlen(s))
return;
while(left>=0&&right<strlen(s)&&s[left]==s[right])
{
left--;
right++;
}
if(right-left>ans[1]-ans[0])
{
ans[0]=left;
ans[1]=right;
}
}
char * longestPalindrome(char * s){
int ans[2]={0};
for(int i=0;i<strlen(s);i++)
{
extend(s,i,i,ans);
extend(s,i,i+1,ans);
}
char* ret=malloc(ans[1]-ans[0]);
strncpy(ret,s+ans[0]+1,ans[1]-ans[0]-1);
ret[ans[1]-ans[0]-1]='