[算法刷题打卡]Day1

1、Leetcode-面试经典150题目1-88. 合并两个有序数组

思路

1.  首先考虑输入和输出，输出要求输出nums1数组，即需要将nums2合并到nums1。因此考虑额外开了一个temp数组存储结果，最后再放到nums1中。
2. 其次，核心代码思路是比较nums1和nums2数组的大小，将较小的先放入temp数组。
3. 退出循环后，nums1和nums2不可能都已经比较完，可能还有剩的，直接放到temp中即可。
4. 最后，将temp数组复制到nums1

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = 0, j = 0, a = 0;
        int temp[m + n];//临时数组，用于放入nums1和nums2的比较结果
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                temp[a++] = nums1[i++];
            } else {
                temp[a++] = nums2[j++];
            }
        }
        //还可能有剩余的
        while (i < m)
            temp[a++] = nums1[i++];
        while (j < n)
            temp[a++] = nums2[j++];
        //复制到nums1中
        for (int i = 0; i < m + n; i++) {
            nums1[i] = temp[i];
        }
    }
};

在看完官方题解后，发现了一种不需要使用temp数组的方法，就是逆向双指针，就是利用nums1后面的元素是空的，将指针从后向前遍历，将两者之中最大值放入。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;//数组尾部
        int cur;//定义指针
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {//1.nums1数组中的数遍历完
                cur = nums2[p2--];
            } else if (p2 == -1) {//2.nums2数组中的数遍历完
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {//3.非递减顺序，所以要取大者放入数组
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }
};

知识点总结：数组、双指针、排序

2、Leetcode-面试经典150题目2-27. 移除元素

思路

1.         输入：一个数组nums 和一个值 val  
2.  要求原地删除所有数值等于val的，且使用O(1)的额外空间，并返回数组的新长度
3. 这一题一开始没有做出来，只通过了部分案例，在结尾就是要删除的数字不通过，试了很多次，对边界的把握不行
4. 看完题解，思路还是双指针（双指针对于好多题真的奇招），定义了左指针left和右指针right,遍历right指针，如果指向元素！= val，则先将右指针指向的元素复制到左指针（表示输出），左右指针++，如果右指针指向的元素=val，则不能输出，右指针++
5. 左指针left一方面最终的值便是要输出的新数组长度，其实也能算新数组的索引下标
6. 而右指针right则是起到一个去掉val值的元素。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0 , right = 0;
        
        while(right < nums.size()) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
                right++;

            } else {
                right++;
            }
        }
        return left;
    }
};

知识点总结：双指针、数组

3、Leetcode-面试经典150题目-3-26. 删除有序数组中的重复项

思考

1. 数组是有序的，重复的元素一定相邻
2. 所以使用双指针left 和 right
3. 比较left 和right是否相等，如果相等rigth++；否则right位置的元素复制到left+1；同时left++，rigth++
4. 最后left+1即为新数组长度。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // 依然可以考虑用双指针
        int left = 0, right = 0, i = 0;

        if (nums.size() == 1)
            return 1;
        while (right < nums.size()) {

            if (nums[right] == nums[left]) {
                right++;

            } else {
                nums[left + 1] = nums[right];
                left++;
                right++;
            }
        }

        return left + 1;
    }
};

 知识点总结：数组、双指针

每日一言：坚持不懈地努力，才能取得成功的果实！

2024年3月19日

softdream