(C语言版)力扣(LeetCode)题库1-5题解析

简介: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

fcaf61ada81e4a95b221eef76e5500af.png


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们的观看是我坚持下去的动力

在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!

4ab94fd1ec5e495aa033dadfbb489f64.png

相关文章
|
3月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
129 1
|
3月前
|
分布式计算 算法 Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本文讲解了两道经典的图论问题:**岛屿数量(LeetCode 200)** 和 **腐烂的橘子(LeetCode 994)**,分别通过 DFS/BFS 实现。在“岛屿数量”中,利用深度或广度优先搜索遍历二维网格,标记连通陆地并计数;“腐烂的橘子”则采用多源 BFS,模拟腐烂传播过程,计算最短时间。两者均需掌握访问标记技巧,是学习网格搜索算法的绝佳实践。
137 1
|
4月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
253 14
|
4月前
|
存储 算法 Go
【LeetCode 热题100】17:电话号码的字母组合(详细解析)(Go语言版)
LeetCode 17题解题思路采用回溯算法,通过递归构建所有可能的组合。关键点包括:每位数字对应多个字母,依次尝试;递归构建下一个字符;递归出口为组合长度等于输入数字长度。Go语言实现中,使用map存储数字到字母的映射,通过回溯函数递归生成组合。时间复杂度为O(3^n * 4^m),空间复杂度为O(n)。类似题目包括括号生成、组合、全排列等。掌握回溯法的核心思想,能够解决多种排列组合问题。
123 11
|
4月前
|
Go
【LeetCode 热题100】155:最小栈(详细解析)(Go语言版)
本文详细解析了力扣热题155:最小栈的解题思路与实现方法。题目要求设计一个支持 push、核心思路是使用辅助栈法,通过两个栈(主栈和辅助栈)来维护当前栈中的最小值。具体操作包括:push 时同步更新辅助栈,pop 时检查是否需要弹出辅助栈的栈顶,getMin 时直接返回辅助栈的栈顶。文章还提供了 Go 语言的实现代码,并对复杂度进行了分析。此外,还介绍了单栈 + 差值记录法的进阶思路,并总结了常见易错点,如 pop 操作时忘记同步弹出辅助栈等。
138 6
|
4月前
|
Go 索引
【LeetCode 热题100】739:每日温度(详细解析)(Go语言版)
这篇文章详细解析了 LeetCode 第 739 题“每日温度”,探讨了如何通过单调栈高效解决问题。题目要求根据每日温度数组,计算出等待更高温度的天数。文中推荐使用单调递减栈,时间复杂度为 O(n),优于暴力解法的 O(n²)。通过实例模拟和代码实现(如 Go 语言版本),清晰展示了栈的操作逻辑。此外,还提供了思维拓展及相关题目推荐,帮助深入理解单调栈的应用场景。
144 6
|
3月前
|
Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本篇博客详细解析了三道经典的动态规划问题:198. 打家劫舍(线性状态转移)、279. 完全平方数与322. 零钱兑换(完全背包问题)。通过 Go 语言实现,帮助读者掌握动态规划的核心思想及其实战技巧。从状态定义到转移方程,逐步剖析每道题的解法,并总结其异同点,助力解决更复杂的 DP 问题。适合初学者深入理解动态规划的应用场景和优化方法。
81 0
|
3月前
|
算法 Go 索引
【LeetCode 热题100】回溯:括号生成 & 组合总和(力扣22 / 39 )(Go语言版)
本文深入解析了LeetCode上的两道经典回溯算法题:**22. 括号生成**与**39. 组合总和**。括号生成通过维护左右括号数量,确保路径合法并构造有效组合;组合总和则允许元素重复选择,利用剪枝优化搜索空间以找到所有满足目标和的组合。两者均需明确路径、选择列表及结束条件,同时合理运用剪枝策略提升效率。文章附有Go语言实现代码,助你掌握回溯算法的核心思想。
102 0
|
5月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
114 4
|
5月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
131 10

推荐镜像

更多
  • DNS