顺序

leetcode 刷题记录,主要用 C++

1. 数组

1.1 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

题解

1
2
3
4
5
6
7
8
9
10
11
vector<int> twoSum(vector<int>& nums, int target) {
for( int i = 0; i < nums.size(); i++){
for( int j = i+1; j < nums.size(); j++ ){
if (nums[i] + nums[j] == target)
{
return {i, j};
}
}
}
return{ };
}

暴力破解,直接对数组循环两边,每遍对应 twoSum 的一个数字。

1
2
3
4
5
6
7
8
9
vector<int> twoSumHash(vector<int>& nums, int target) {
unordered_map<int,int> hashtable;
for( int i = 0; i < nums.size(); i++){
if( hashtable.end() != hashtable.find(target - nums[i]))
return {hashtable[target - nums[i]], i};
hashtable[nums[i]] = i;
}
return {};
}

利用 hash 表的特性,将寻找 twoSum 中另外一个数的时间复杂度降为 O(1),遍历一遍。
利用 HashMap,键放数组中具体的值,值放索引。
C++ 对应的 HashMap 是 unordered_map 容器。如果 find 方法没有找到对应的 key,返回 hashtablel.end()

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

题目描述

给你一个有序数组 nums ,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。

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

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

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

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

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1:

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

示例 2:

输入: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 。不需要考虑数组中超出新长度后面的元素。

提示:

0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int removeDuplicates(vector<int>& nums) {
if (nums.size()==0)
{
return 0;
}

int index = 0;
for(int i=1; i< nums.size(); ++i)
{
if(nums[index]!=nums[i])
{
++index;
nums[index] = nums[i];
}
}
return index + 1;
}

双指针思想,第一个指针遍历原始数组,第二个指针指向去重后序列
按照题目描述,算法中 nums 应该只存有去重后的序列,而实际上官方的解决方案也没有对 nums 进行去重后对重复数据进行删除处理,目前想到的一种方案是使用 vector 的截取中间一段的函数,这要用到迭代器,可能会影响性能。或者再加一个迭代器,与第一个指针同步,用来实现原地删除。

1.3 移除元素

题目描述

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

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

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

说明

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

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

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

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int removeElement(vector<int>& nums, int val) {
int first = 0;
int last = nums.size() - 1;

while (first <= last)
{
if (nums[first] == val)
{
nums[first] = nums[first] ^ nums[last];
nums[last] = nums[first] ^ nums[last];
nums[first] = nums[first] ^ nums[last];
last--;
}
else
{
first++;
}
}
return first;
}
  1. 双指针思想
  2. 两个数交换,使用按位异或,实现交换。
    原理:一个数同另外一个属连续异或2次,可还原为它自己。
1
2
3
4
5
6
lhs = lhs ^ rhs ; // -1-
rhs = lhs ^ rhs ; // -2-
lhs = lhs ^ rhs ; // -3-

// -1- -2- 合并后即为 rhs = (lhs ^ rhs) ^ rhs
// -2- -3- 合并后即为 lhs = lhs ^ (lhs ^ rhs)

1.4 搜索插入位置

题目描述

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int left = 0;
int right = nums.size()-1;
while(left <= right)
{
int mid = left + ( right - left) / 2;
// return left,= 的判断要放 right。如果 = 放 left 侧判断,当 nums[mid] == target 时,会执行下面 +1 语句,返回结果会多1
if( nums[mid] < target )
{
left = mid + 1;

}else if( nums[mid] >= target )
{
right = mid - 1;
}
}
return left;

二分查找思想

1.5 最大子序和

题目描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

输入:nums = [1]
输出:1

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 最大子序和
int maxSubArray(vector<int> &nums)
{
// if (nums.size() == 1)
// return nums[0];
int maxSum = nums[0];
int currentSum = nums[0];

for (int i = 1; i < nums.size(); i++)
{
if(currentSum < 0)
currentSum = nums[i];
else
currentSum += nums[i];
if( currentSum >= maxSum )
maxSum = currentSum;
}
return maxSum;
}

// 最大子序和
int maxSubArray2(vector<int> &nums)
{
int maxSum = nums[0];
int currentSum = nums[0];

for (int i = 1; i < nums.size(); i++)
{
currentSum = max( nums[i], currentSum+nums[i] );
maxSum = max(currentSum,maxSum);
}
return maxSum;
}

核心点:如果当前序列和 < 0,则丢弃当前序列和,从下一元素重新开始计算;
再用另一个元素记录 maxSum。

2. HOT 100

2.1 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

题解

1
2
3
4
5
6
7
8
9
10
11
vector<int> twoSum(vector<int>& nums, int target) {
for( int i = 0; i < nums.size(); i++){
for( int j = i+1; j < nums.size(); j++ ){
if (nums[i] + nums[j] == target)
{
return {i, j};
}
}
}
return{ };
}

暴力破解,直接对数组循环两边,每遍对应 twoSum 的一个数字。

1
2
3
4
5
6
7
8
9
vector<int> twoSumHash(vector<int>& nums, int target) {
unordered_map<int,int> hashtable;
for( int i = 0; i < nums.size(); i++){
if( hashtable.end() != hashtable.find(target - nums[i]))
return {hashtable[target - nums[i]], i};
hashtable[nums[i]] = i;
}
return {};
}

利用 hash 表的特性,将寻找 twoSum 中另外一个数的时间复杂度降为 O(1),遍历一遍。
利用 HashMap,键放数组中具体的值,值放索引。
C++ 对应的 HashMap 是 unordered_map 容器。如果 find 方法没有找到对应的 key,返回 hashtablel.end()

2.2 两数相加

题目描述

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 2:

输入:l1 = [0], l2 = [0]
输出:[0]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = nullptr; // result 链表的头指针
ListNode *tail = nullptr; // result 链表的尾指针,用于新增 Node
int carry = 0; //进位

// 当两个链表都没有遍历完时
while (l1 != nullptr && l2 != nullptr)
{
int sum = l1->val + l2->val + carry;
if (head == nullptr)
{
head = tail = new ListNode(sum % 10); // 开始构建 result 链表
}
else
{
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10; // 更新进位

l1 = l1->next;
l2 = l2->next;
}

// l2 遍历完,而 l1 没有遍历完的情形
while(l1 != nullptr)
{
// 注意仍然需要判断是否进位
int sum = l1->val + carry;
tail->next = new ListNode(sum%10);
tail = tail->next;
l1 = l1->next;
carry = sum/10;
}

// l1 遍历玩,而 l2 没有遍历完的情形
while(l2 != nullptr)
{
int sum = l2->val + carry;
tail->next = new ListNode(sum%10);
tail = tail->next;
l2 = l2->next;
carry = sum/10;
}

// 判断最后一位是否发生了进位
if(carry!=0){
tail->next = new ListNode(carry);
}

return head;
}

2.3 无重复字符的最长子串

题目描述

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3

示例 2:

输入: s = “bbbbb”
输出: 1

示例 3:

输入: s = “pwwkew”
输出: 3

示例 4:

输入: s = “”
输出: 0

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int lengthOfLongestSubstring(string s)
{
unordered_set<char> hashset;
hashset.insert(s[0]);
unsigned maxLength = 1;
unsigned int left = 0; // 用来标识当前无重复字符串的起始位置

for (unsigned right = 1; right < s.size(); right++)
{
if (!hashset.count(s[right])) // hashset 不存在当前字符
{
hashset.insert(s[right]);
maxLength = max(maxLength, right - left + 1);
}
else
{
if (hashset.size() == 1)
{
left++;
continue;
}
hashset.erase(s[left]);
left++;
// maxLength = max( maxLength, right-left);
while (hashset.count(s[right]) > 0) // 当前字符还与目前字符串有重复字符
{
hashset.erase(s[left]); // 去除无重复字符串最左侧字符
left++;
}
hashset.insert(s[right]);
}
}
return maxLength;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lengthOfLongestSubstring(string s) {
unordered_set<char> hashset;
int right = -1; // 相当于滑动窗口右边边界。初始时滑动窗口还不存在,为-1。
int maxLength = 0;
for (int left = 0; left < s.size(); left++)
{
if( left != 0 )
hashset.erase(s[left-1]); // 滑动窗口左侧向右移动一个位置
while ( right + 1 < s.size() && !hashset.count(s[right+1]) ) // 只有当滑动窗口下一个元素不在滑动窗口内时,才加入滑动窗口,并且滑动窗口右侧扩1
{
hashset.insert(s[right+1]);
right++;
}
maxLength = max(maxLength, right-left+1);
}
return maxLength;
}

2.4 寻找两个正序数组的中位数

题目描述

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000

示例 2:

输入:nums1 = [], nums2 = [1]
输出:1.00000

提示:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

进阶:

你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
double findMedianSortedArrays1(vector<int> &nums1, vector<int> &nums2)
{
int indexSum = nums1.size() + nums2.size();
int midIndex = indexSum / 2;
vector<int> nums; // 合并 num1,num2
unsigned i = 0;
unsigned j = 0;
unsigned k = 0;

// 其中一个数组为空
if (nums1.size() == 0)
nums = nums2;
if (nums2.size() == 0)
nums = nums1;

nums.resize(indexSum); // 两个数组都不为空,调整合并数组大小

// 遍历两个待合并数组,直至其中一个数组遍历完
while (i < nums1.size() && j < nums2.size())
{
if (nums1[i] > nums2[j])
{
nums[k] = nums2[j];
j++;
}
else
{
nums[k] = nums1[i];
i++;
}
k++;
}

while (i < nums1.size())
{
nums[k] = nums1[i];
i++;
k++;
}

while (j < nums2.size())
{
nums[k] = nums2[j];
j++;
k++;
}

// 返回合并数组的中位数
if (indexSum % 2 != 0) // 奇
return nums[midIndex];
else // 偶
return (nums[midIndex] + nums[midIndex - 1]) / 2.0;
}

第一种方法,对两个数组直接进行合并,然后返回中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 我们不需要合并的数组,实际上只要知道中位数在就行了。
// 开始的思路是进行一次完整的遍历,当到达中位数这个位置时就返回,但这里对奇偶以及边界判断会很麻烦,代码很乱,并且时间复杂度与第一种方法不变。
// 可以在循环处判断到中位数那个位置,同时记录下上一次遍历和这一次遍历的结果。对于奇,中位数就是当前位置,对于偶,就是与上一次结果的平均。
double findMedianSortedArrays2(vector<int> &nums1, vector<int> &nums2)
{
int indexSum = nums1.size() + nums2.size();
int midIndex = indexSum / 2 + 1; // 中位数的位置,非索引
int left = 0; // 上一轮的值
int right = 0; // 当前遍历的值
int start1 = 0; // 第一个数组遍历索引
int start2 = 0; // 第二个数组遍历索引
for (unsigned i = 0; i < midIndex; i++)
{
left = right;
// 需要先判断 nums1 是否为空,否则当 nums1 为空时,nums1[start1] 将会越界
// 后部分需要先判断 start2 是否已经遍历完或者为空,否则 nums2[start2]会越界
if (start1 < nums1.size() && (start2 >= nums2.size() || nums1[start1] < nums2[start2]))
{
right = nums1[start1];
start1++;
}
else
{
right = nums2[start2];
start2++;
}
}

if (indexSum % 2 != 0)
{
return right;
}
else
{
return (left + right) / 2.0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 用的是二分法查找两个数组中第 k 小的数
double findMedianSortedArrays3(vector<int> &nums1, vector<int> &nums2)
{
int n = nums1.size();
int m = nums2.size();
// 将奇偶统一。如果总数是奇数,那个 left == right
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
// 返回第 left 小 和第 right 小的数的平均值
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) / 2.0;
}

// start、end 是索引,k指第几小 Kth
int getKth(vector<int> nums1, int start1, int end1, vector<int> nums2, int start2, int end2, int k)
{
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;

// 递归出口:其中一个数组为空,或者 k = 1,即求最小的数
// 确保当存在数组为空时,一定是 nums1
if ( len2 < len1 ) // 两个数组交换位置
return getKth(nums2, start2, end2, nums1, start1, end1, k);

if(len1 == 0)
return nums2[start2 + k - 1];

if(k == 1) // 即返回最小的一个数
return min(nums1[start1], nums2[start2]);

// 取两个数组第 k/2 的索引。还需要判断 k/2 是否超过数组长度 len 的情况
int i = start1 + min(k/2, len1) - 1;
int j = start2 + min(k/2, len2) - 1;

// 从找第 k 小变成了 第 (k - 弃掉数个数)小了
// 弃掉数可能是 k/2,也有可能是 len 长度
if ( nums1[i] > nums2[j] )
{
return getKth( nums1, start1, start2, nums2, j + 1, end2, k-( j - start2 + 1) );
}else{
return getKth( nums1, i + 1, end1, nums2, start2, end2, k - ( i - start1 + 1 ) );
}
}

思路源于 leetcode 作者:windliang,链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

解法二中,我们一次遍历就相当于去掉不可能是中位数的一个值,也就是一个一个排除。由于数列是有序的,其实我们完全可以一半儿一半儿的排除。假设我们要找第 k 小数,我们可以每次循环排除掉 k/2 个数。看下边一个例子。

假设我们要找第 7 小的数字。

我们比较两个数组的第 k/2 个数字,如果 k 是奇数,向下取整。也就是比较第 33 个数字,上边数组中的 44 和下边数组中的 33,如果哪个小,就表明该数组的前 k/2 个数字都不是第 k 小数字,所以可以排除。也就是 11,22,33 这三个数字不可能是第 77 小的数字,我们可以把它排除掉。将 13491349 和 4567891045678910 两个数组作为新的数组进行比较。

更一般的情况 A[1] ,A[2] ,A[3],A[k/2] … ,B[1],B[2],B[3],B[k/2] … ,如果 A[k/2]<B[k/2] ,那么A[1],A[2],A[3],A[k/2]都不可能是第 k 小的数字。

A 数组中比 A[k/2] 小的数有 k/2-1 个,B 数组中,B[k/2] 比 A[k/2] 小,假设 B[k/2] 前边的数字都比 A[k/2] 小,也只有 k/2-1 个,所以比 A[k/2] 小的数字最多有 k/1-1+k/2-1=k-2个,所以 A[k/2] 最多是第 k-1 小的数。而比 A[k/2] 小的数更不可能是第 k 小的数了,所以可以把它们排除。

橙色的部分表示已经去掉的数字。

由于我们已经排除掉了 3 个数字,就是这 3 个数字一定在最前边,所以在两个新数组中,我们只需要找第 7 - 3 = 4 小的数字就可以了,也就是 k = 4。此时两个数组,比较第 2 个数字,3 < 5,所以我们可以把小的那个数组中的 1 ,3 排除掉了。

我们又排除掉 2 个数字,所以现在找第 4 - 2 = 2 小的数字就可以了。此时比较两个数组中的第 k / 2 = 1 个数,4 == 4,怎么办呢?由于两个数相等,所以我们无论去掉哪个数组中的都行,因为去掉 1 个总会保留 1 个的,所以没有影响。为了统一,我们就假设 4 > 4 吧,所以此时将下边的 4 去掉。

由于又去掉 1 个数字,此时我们要找第 1 小的数字,所以只需判断两个数组中第一个数字哪个小就可以了,也就是 4。

所以第 7 小的数字是 4。

我们每次都是取 k/2 的数进行比较,有时候可能会遇到数组长度小于 k/2的时候。

此时 k / 2 等于 3,而上边的数组长度是 2,我们此时将箭头指向它的末尾就可以了。这样的话,由于 2 < 3,所以就会导致上边的数组 1,2 都被排除。造成下边的情况。

由于 2 个元素被排除,所以此时 k = 5,又由于上边的数组已经空了,我们只需要返回下边的数组的第 5 个数字就可以了。

从上边可以看到,无论是找第奇数个还是第偶数个数字,对我们的算法并没有影响,而且在算法进行中,k 的值都有可能从奇数变为偶数,最终都会变为 1 或者由于一个数组空了,直接返回结果。

所以我们采用递归的思路,为了防止数组长度小于 k/2,所以每次比较 min(k/2,len(数组) 对应的数字,把小的那个对应的数组的数字排除,将两个新数组进入递归,并且 k 要减去排除的数字的个数。递归出口就是当 k=1 或者其中一个数字长度是 0 了。