刷爆leetcode第二期 0002~0006

发布于:2022-11-28 ⋅ 阅读:(372) ⋅ 点赞:(0)

题目一 删除数组中所有val值

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

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

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

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

这里题目中给了我们一个数组和一个要删除的值

我们可以这样思考

在这里插入图片描述

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

题目二 删除有序数组中的重复项

给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-duplicates-from-sorted-array在这里插入图片描述

整体思路还是一个双指针问题

左边指针先不动

右指针遍历整个数组

如果遍历到跟左指针不同的值就先++左指针再赋值给它

最后元素的个数就是left+1

int removeDuplicates(int* nums, int numsSize)
{
    if(nums==NULL)
    {
        return 0;
    }
    int left =0;
    int right =0;
    for (right =0; right<numsSize;right++)
    {
        if(nums[left]!=nums[right])
        {
            nums[++left]=nums[right];
        } 

    }
    return left+1;
}

题目三 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/merge-sorted-array

这个题目其实再我的上一篇博客中已经讲解过了

在这里插入图片描述

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    //设置好三个指针
    int m1 = m -1;
    int n1 = n -1;
    int des = m+n -1;


    //循环条件
    while ((m1>=0)&&(n1>=0))
    {
        if(nums1[m1]>nums2[n1])
        {
            nums1[des]=nums1[m1];
            m1--;
            des--;
        }
        else
        {
            nums1[des]=nums2[n1];
            n1--;
            des--;
        }
    }

    while(n1>=0)
    {
        nums1[des]=nums2[n1];
        n1--;
        des--;
    }
}

题目四 旋转数组

给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/rotate-array

这个题目其实掌握了方法就很简单

我们先看图

在这里插入图片描述

这里我们只要将这个数组逆序三次 就能得到我们想要的旋转后的数组

但是这里其实是有个小bug

如果旋转的次数等于6呢?

其实是不是就是相当于这个数组没有动

如果等于七呢 是不是就跟旋转一次一样

所以说我们的k应该模上七得到最后的值

代码表示如下

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    //设置好三个指针
    int m1 = m -1;
    int n1 = n -1;
    int des = m+n -1;


    //循环条件
    while ((m1>=0)&&(n1>=0))
    {
        if(nums1[m1]>nums2[n1])
        {
            nums1[des]=nums1[m1];
            m1--;
            des--;
        }
        else
        {
            nums1[des]=nums2[n1];
            n1--;
            des--;
        }
    }

    while(n1>=0)
    {
        nums1[des]=nums2[n1];
        n1--;
        des--;
    }
}

题目五 数组形式的整数加法

整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。

例如,对于 num = 1321 ,数组形式是 [1,3,2,1] 。
给定 num ,整数的 数组形式 ,和整数 k ,返回 整数 num + k 的 数组形式 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/add-to-array-form-of-integer

还是一样 我们先画图

在这里插入图片描述

但是 如果是这种情况呢?

在这里插入图片描述
但是 这里还有一种更特殊的情况

在这里插入图片描述
这个时候我们可以发现 数组竟然需要往前进一位

这就意味着我们不确定再相加的时候最高位是否要往前进一

那么有没有什么是我们确定的呢?

当然有 那就是数组的首位以及加法的最低位

那么我们就可以有这种思路

在这里插入图片描述
我们可以将先算出来的数字放在首位

最后的时候将这个数组输入的位数逆序一遍就可以

这个时候我们再来梳理下思路

在这里插入图片描述
代码表示如下

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

void reverse(int *arr,int begin ,int end)
{
    int tmp;
    while(begin<end)
    {
        tmp =arr[end];
        arr[end]=arr[begin];
        arr[begin]=tmp;
        begin++;
        end--;
    }
}


int* addToArrayForm(int* num, int numSize, int k, int* returnSize)
{
    int* arr = (int *)malloc(10001*sizeof(int));
    int ki = 0;
    int ai =0;
    int ret =0;
    int next =0;
    int numi =numSize-1;
    int count =0;
    while((k>0)||(numi>=0))
    {
        if(k>0)
        {
            ki=k%10;
            k/=10;
        }
        if(numi>=0)
        {
            ai=num[numi];
            numi--;
        }
        ret = ai+ki+next;
        if(ret>9)
        {
            ret%=10;
            next=1;
        }
        else
        {
            next=0;
        }

        arr[count]=ret;
        count++;
        ret =0;
        ai =0;
        ki=0;
    }
    if(next==1)
    {
        arr[count]=1;
        count++;
    }
    reverse(arr,0,count-1);
    *returnSize = count;
    return arr;

}

网站公告

今日签到

点亮在社区的每一天
去签到