（C语言版）力扣（LeetCode）题库1-5题解析

力扣（LeetCode）题库1-5题解析

• 1.两数之和
• • 题目
  • 解析
• 2.两数相加
• • 题目
  • 解法
• 3.无重复字符的最长字串
• • 题目
  • 解法
• 4. 寻找两个正序数组的中位数
• • 题目
  • 解法
• 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]='\0';
    return ret;
}

首先我们建立一个数组用于记录最长字符串的前后下标位置，这里使用的算法是中心扩散的思维，分为中心值为1位和2位两种情况，左右相等向两边扩散，直至不等为止，需要注意的是，left和right的值肯定是小于和大于下标一位的，举个例子，比如最长回文字符串就是开头的3位，那么，left和right的值应分别为-1和3，不理解的小伙伴可以画图看看。遍历完成后，数组ans记录了最长回文字符串的偏值下标，这时我们建立一个两数差值长度的字符数组用于记录最长回文字符串，再用strncpy函数拷贝，再将最后一位赋值为’\0’,最后返回字符串数组即可。

结语

这里的解法代码部分来自力扣官方和作者自己的解法，作者只是进行了详细的剖析和部分改动方便大家理解和提升自己，学会多角度观察问题，解决问题。

有兴趣的小伙伴可以关注作者，如果觉得内容不错，请给个一键三连吧，蟹蟹你哟！！！
制作不易，如有不正之处敬请指出
感谢大家的来访，UU们的观看是我坚持下去的动力
在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！