刷爆leetcode第二期 0002~0006

leetcode题目

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-element

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

我们可以这样思考

intremoveElement(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

intremoveDuplicates(int* nums,int numsSize){if(nums==NULL){return0;}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

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

voidmerge(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应该模上七得到最后的值

代码表示如下

voidmerge(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().
 */voidreverse(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;}