力扣算法刷题记录

---

前言

没刷过算法题，感觉自己算法方面的知识较为薄弱，在力扣上看了几道发现自己都不会，看了解题答案后才感觉逐渐明朗，所以来记录一下算法题。

一、数组篇

一、问题一

给你两个按?非递减顺序?排列的整数数组?nums1?和?nums2，另有两个整数?m?和?n?，分别表示?nums1?和?nums2?中的元素数目。请你?合并?nums2?到?nums1?中，使合并后的数组同样按?非递减顺序?排列。

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

1.第一种解法

 function merge(nums1: number[], m: number, nums2: number[], n: number): void {
            //表示合并的nums1的最后一个索引值
            let k = m + n - 1;
            //nums1的最后一个索引值
            let i = m - 1;
            //nums2的最后一个索引值
            let j = n - 1;
            //当数组1和数组2的索引值都>=0时则可以进行循环
            while (i >= 0 && j >= 0) {
                //如果数组1的最后一个索引值对应的数值>数组2最后一个值对应的数值 则k所对应的最大值则变为i对应的值 反之则为索引j对应的值
                //进行一次操作后 索引值减小 x-- 是先赋值后进行运算
                nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
            }
            //如果存在数组2循环完之后 数组1的排序还没进行完成
            while ((j < 0 && i >= 0) ) {
                nums1[k--] = nums1[i--];
            }
            //如果存在数组1循环完之后 数组2的排序还没进行完成时
            while (i < 0 && j >= 0) {
                nums1[k--] = nums1[j--];
            }
        }

2.第二种解法

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
            //splice方法 从索引开始 删除n个元素，再添加nums2数组内的元素
            nums1.splice(m, n, ...nums2);
            nums1.sort((a, b) => a - b);
        }

?二、问题二

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

注意：不要使用额外的数组空间，你必须仅使用?O(1)?额外空间并?原地?修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明：

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
? ? print(nums[i]);
}

function removeElement(nums: number[], val: number): number {
    let count = 0
    //把每一次循环到不等于val的值依次赋值给索引从0开始
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== val) {
            nums[count] = nums[i]
            count++
        }
    }
    return count
};

?三、问题三

给你一个?非严格递增排列?的数组?nums?，请你?原地?删除重复出现的元素，使每个元素?只出现一次?，返回删除后数组的新长度。元素的?相对顺序?应该保持?一致?。然后返回?nums?中唯一元素的个数。

示例：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

1.第一种解法

function removeDuplicates(nums: number[]): number {
    let count=0
    for (let i = 1; i < nums.length; i++) {
        //若值不一样则可以将nums[i]的值赋值给count+1所对应的值
        if (nums[count] !== nums[i]) {
            nums[++count] = nums[i]
        }
    }
    //输出长度 长度为索引值+1
    return ++count
};

?2.第二种解法

 function removeDuplicates(nums: number[]): number {
            for (let i = 1; i < nums.length; i++) {
                //前一个值等于后一个值
                if (nums[i - 1] === nums[i]) {
                    nums.splice(i, 1);
                    //删除后后面的元素变成当前索引值对应的值，则需要再次进行一次
                    i--;
                }
            }
            return nums.length;
        }

?四、问题四

给你一个有序数组?nums?，请你?原地?删除重复出现的元素，使得出现次数超过两次的元素只出现两次?，返回删除后数组的新长度。

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

?第一种解法（与问题三方法类似）

function removeDuplicates(nums: number[]): number {
    for (let i = 1; i < nums.length; i++) {
        //因为一致的元素只能出现两次，所以如果连续三个值都相等则需要删除一个值
        if (nums[i - 1] === nums[i] && nums[i] === nums[i + 1]) {
            nums.splice(i, 1)
            i--
        }
    }
    return nums.length
};

第二种解法

function removeDuplicates(nums: number[]): number {
    let j = 0
    for (let i = 0; i < nums.length; i++) {
        //索引值为0,1时直接赋值/或者当索引值为x时不与前面x-2索引值相等则说明只会出现2次
        if (j < 2 || nums[i] !== nums[j - 2]) {
            //在这里已经增加了j，返回则不需要了
            nums[j++] = nums[i]
        }
    }
    return j