Leetcode C++

Leetcode初级算法笔记

Posted by QingJun's Blog on November 3, 2020

概述：

Leetcode 官方推出了经典面试题目清单，并将其重新整理规划，将其分为一下三个部分：

  1. 初级算法 - 帮助入门
  2. 中级算法 - 巩固训练
  3. 高级算法 - 提升进阶

然后这篇笔记就是我开的一篇新坑，记录自己在初级算法题目清单中的个人笔记。后续应该也会写中级算法和高级算法。

数组

1.删除排序数组中的重复项

要求在 O(1) 额外空间的条件下，原地删除重复出现的元素。

思路：这题采取双指针的思路。指针 i 用于建立删除重复项之后的数组，标记当前已经剔除重复项的元素存放的位置，指针 j 用来遍历原数组寻找重复项。i 初始化为 0 ，j 初始化为 1，当 nums[j] != nums[i] 时，nums[++i] = nums[j]，也就是把剔除重复想的元素放到新数组的相应位置；因为原数组是有序的，所以重复项是连续的，当 nums[j] == nums[i] 时，直接跳过。

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) 
            return 0;
        int i = 0;
        for (int j = 1; j < nums.size(); j++)
            if (nums[j] != nums[i])
                nums[++i] = nums[j];
        return i + 1;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

双指针

既然提到了双指针，这里我们就详细讲一下双指针的思想。双指针通常用在线性的数据结构中，比如链表和数组，有时候也会用在图算法中。双指针主要分为快慢指针和左右指针。

  1. 快慢指针

两个指针从链表的同一节点出发，其中一个指针前进速度比另一个指针快。利用快慢指针可以用来解决某些算法问题，比如：

  • 计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点。

  • 判断链表是否有环：如果链表中存在环，则在链表上不断前进的指针会一直在环里绕圈子，且不能知道链表是否有环。使用快慢指针，当链表中存在环时，两个指针最终会在环中相遇。

  • 判断链表中环的起点：当我们判断出链表中存在环，并且知道了两个指针相遇的节点，我们可以让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

  • 求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就好了

  • 求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素。

    142_fig1

  1. 左右指针

一般都是排好序的数组或链表，否则无序的话这两个指针的位置也没有什么意义。一般将指向最左侧的索引定义为左指针，最右侧的定义为右指针，然后从两头向中间进行遍历。利用左右指针可以用来解决某些算法问题，比如：

  • 二分查找问题
  • n数之和问题：比如两数之和问题，先对数组排序然后左右指针找到满足条件的两个数。如果是三数问题就转化为一个数和另外两个数的两数问题。以此类推。
  • 滑动窗口：两个指针，一前一后组成滑动窗口，并计算滑动窗口中的元素的问题。这类问题一般包括：
    • 字符串匹配问题
    • 子数组问题

2.买卖股票的最佳时机Ⅱ

因为之前每日一题出现过，我专门写了，所以这里就只放链接，不再赘述。

122.买卖股票的最佳时机Ⅱ

3.旋转数组

  1. 暴力

    旋转 k 次，每次将数组旋转 1 个元素。

    1
2
3
4
5
6
7
8
9
10
11
12
13

    public class Solution {
    public void rotate(int[] nums, int k) {
        int temp, previous;
        for (int i = 0; i < k; i++) {
            previous = nums[nums.length - 1];
            for (int j = 0; j < nums.length; j++) {
                temp = nums[j];
                nums[j] = previous;
                previous = temp;
            }
        }
    }
}
    • 时间复杂度：O(n∗k) 。每个元素都被移动 1 步 O(n)，k次 O(n*k) 。
    • 空间复杂度：O(1)。没有额外空间被使用。

  2. 反转

    当我们旋转数组 k 次， k%n 个尾部元素会被移动到头部，剩下的元素会被向后移动。

    在这个方法中，我们首先将所有元素反转。然后反转前 k 个元素，再反转后面 n−k 个元素，就能得到想要的结果。

    补充：第一次反转是把尾部元素移动到头部，第二次第三次是保证结果仍按原数组顺序。

    1
2
3
4
5
6
7
8

    class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k%nums.size());
        reverse(nums.begin()+k%nums.size(),nums.end());
    }
};
    • 时间复杂度：O(n)。 n 个元素被反转了总共 3 次。
    • 空间复杂度：O(1)。 没有使用额外的空间。

4.存在重复元素

这题不能用朴素线性查找，即两层循环，针对每个元素遍历一次数组找相同的项，因为时间复杂度是 O($n^2$) ，会超时。正确的方法是排序或者哈希表。

CATALOG
    FEATURED TAGS
    Leetcode C++
    FRIENDS