数组

删除有序数组中的重复项

描述：

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

示例：

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

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
	int removeDuplicates(vector<int>& nums) {
		if(nums.empty()) return 0;
		int index = 1;
		for(int i=1;i<nums.size();++i) {
			if(nums[i] != nums[index-1]) {
				nums[index++] = nums[i];
			}
		}
		return index;
	}
};

代码2：

1
2
3
4
5
class Solution {
	int removeDuplicates(vector<int>& nums) {
		return distance(nums.begin(),unique(nums.begin(),nums.end()));
	}
};
1
2
3
4
5
6
7
//distance()函数用于计算两个迭代器表示的范围内包含元素的个数
template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type distance (InputIterator first, InputIterator last);
/*
1. 其中，first 和 last 都为迭代器，其类型可以是输入迭代器、前向迭代器、双向迭代器以及随机访问迭代器
2. 该函数会返回[first, last)范围内包含的元素的个数。
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
<algorithm>中的unique函数,它能删除连续序列的副本(Remove consecutive duplicates in range). 原型如下:
*/
template <class ForwardIterator>
  ForwardIterator unique ( ForwardIterator first, ForwardIterator last );

template <class ForwardIterator, class BinaryPredicate>
  ForwardIterator unique ( ForwardIterator first, ForwardIterator last,
                           BinaryPredicate pred );
/*
“删除连续序列”这样的描述容易造成误解，知道下面几点有助于更好理解这个操作：
1. 其实unique仅仅是按照一个规则来修改[first, last)之间的元素，并不会删除任何东西，它不会改变容器的size。这个规则就是连续一样的元素会被后面的元素覆盖。
2. 它通过一个返回迭代器result，并保证在[first, result)之间的元素是不存在连续重复的元素。可以把[result, last)之间的元素移除掉，这才算删除了连续重复的元素。
3. 默认判断两个元素相等是使用==操作符，第二个版本也可自己指定二元函数（函数，functors，lambda…).
*/

删除有序数组中的重复项 II

描述：

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素最多出现两次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

示例：

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

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
	int removeDuplicates(vector<int>& nums) {
		if (nums.size() <= 2) return nums.size();
		int index = 2;
		for (int i = 2; i < nums.size(); i++) {
			if (nums[i] != nums[index - 2])
			nums[index++] = nums[i];
		}
		return index;
	}
};

单链表

反转链表

问题描述：给你单链表的头节点 $head$ ，请你反转链表，并返回反转后的链表。

示例：

示例图

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = []
输出：[]

方法一：迭代

假设链表为 $1 \to 2 \to 3 \to \phi $ 我们要把它变为 $\phi \gets 1 \gets 2 \gets 3$ 。
在遍历链表时，将当前节点的 $next$ 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* curr = head;
        ListNode* pre = nullptr;
        while(curr != nullptr) {
            ListNode *node = curr->next;
            curr->next = pre;
            pre = curr;
            curr = node;
        }
        return pre;
    }
};

复杂度分析:

  • 时间复杂度： $O(n)$ ，其中 $n$ 是链表的长度。需要遍历链表一次。
  • 空间复杂度： $O(1)$

方法二：递归