[图片] 纯 C 刷 leetcode(一) 两数之和 题目 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 1 ..

纯 C 刷 LeetCode(一)

纯 C 刷 leetcode(一)

两数之和

题目

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum

题解

第一想法:双重循环遍历,判断两数之和是否等于 target 即可, 时间复杂度 O(n^2)。
当然还有更优解,hash 大法好。

代码

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    static int a[2]={0};
    for (int i = 0; i < numsSize - 1; i++)
    {
        for (int j = i+1; j < numsSize; j++)
        {
	    if (nums[i] + nums[j] == target)
            {
		a[0] = i;
		a[1] = j;
                *returnSize = 2;
		return a;
	    }
	 }
    }
    *returnSize = 0;
    return a;
}

删除排序数组中的重复项

题目

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:

给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

题解

乍一看,有序数组,额外空间条件 O(1), 且不需要考虑数组中超出长度的后面的元素。
遍历数组,只要碰到相邻的数字是相等的,那么从后面往前面将数组覆盖数据,然后减少数组长度即可,如果没有则继续遍历。马上动手写了第一版:

int removeDuplicates(int* nums, int numsSize){
    if (numsSize <= 1)  // 肯定不会重复啦
    {
        return numsSize;
    }
    int i = 0;
    while(i < numsSize)
    {
        if(nums[i] == nums[i+1])  // 遇到相邻的数据相等, 将所有的数据往前移动。
        {
            for (int j=i+1; j<numsSize;j++)
            {
                nums[j-1] = nums[j];
                nums[j] = 0;
            }
            numsSize--;
        }
        else{
            i++;
        }
    }
    return numsSize;
}

最坏情况 O(n^2)的时间复杂度,既然数组遇到相同的可以从后往前移动覆盖,那么可以考虑从前往后,遇到不相等的数字才去覆盖。时间复杂度为 O(n);

最终代码

int removeDuplicates(int* nums, int numsSize){
    if (numsSize <= 1)
    {
        return numsSize;
    }
    int k = 0;
    for (int i = 1; i < numsSize; i++) {
        if (nums[k] != nums[i])
        {
            nums[++k] = nums[i];
        }
    }
    return ++k; // 返回的数组元素个数,需要+1
}

移除元素

题目

给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-element

题解

数组移除与指定值相等元素,那么只需要一重循环判断,与给定值不相等的值重新记录下,否则丢弃即可, 时间复杂度 O(n)。

代码

int removeElement(int* nums, int numsSize, int val){
    int k = 0;
    for (int i = 0; i < numsSize; i++)
    {
        if (nums[i] != val)
        {
            nums[k] = nums[i];
            k++;
        }
    }
    return k;
}

搜索插入位置

题目

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/search-insert-position

题解

找到则返回其索引,找不到返回应该插入的位置,数组是有序的。那么很容易想到遍历数组,只需要判断当前的数组元素是否大于等于目标值。时间复杂度 O(n)。
马上第一版代码就出来了:

int searchInsert(int* nums, int numsSize, int target){
    for (int i = 0; i < numsSize; i++)
    {
        if (nums[i] >= target)
        {
            return i;
        }
    }
    return numsSize;
}

既然数组是有序的,那么自然会想到二分查找。时间复杂度:O(log2n)。

代码

int searchInsert(int* nums, int numsSize, int target){
    int low = 0;
    int high = numsSize;
    int mid = 0;
    while (low < high)
    {
        mid = (low + high) / 2;
        if (nums[mid] > target){
            high = mid;
        } 
        else if (nums[mid] < target){
            low = mid + 1;
        } else{
            return mid;
        }
    }
    return low;
}

最大子序列和

题目

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-subarray

题解

-2 + 1 = -1 < 0 我往后 +2 值为 1, 如果开头的-2 不加,那么值就是 3。明显3 > 1, 推断出序列中如果两数字相加值小于 0,那么影响最大值,该数需要舍弃。
-1 + 1 = 0 = 0 同上。
所以我只需要关心:
设当前序列和为 x=0, 序列为 a[-1, 2, -3, 5], 那么需要满足 x + a[i] > 0, 该序列继续加下去才有意义,否则 x 应该设为 x = a[i];

代码

int maxSubArray(int* nums, int numsSize){
    int sum = 0;
    int maxSum = -2147483646; // 最小int值, 结果可能是负数。
    if (numsSize <= 1)
    {
        return nums[0];
    }
    for (int i = 0; i < numsSize; i++)
    {
        if (sum <= 0)  // 当前sum小于0,所以没必要加了。
        {
            sum = nums[i];
        }
        else{
            sum += nums[i];
        }
        if (sum >= maxSum)
        {
            maxSum = sum;
        }
    }
    return maxSum;
}

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    158 引用 • 61 回帖 • 1 关注
  • 编程基础
    5 引用
  • C

    C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

    42 引用 • 111 回帖 • 501 关注
回帖   
请输入回帖内容...