Leetcode笔记

借这篇博客记录并复习Leetcode做题时的笔记。

二分查找

模板及细节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;

while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
  • while循环中<与<=的选择

    初始化right赋值是nums.length-1时,说明搜索区间为[left,right]左闭右闭区间,初始化right赋值是nums.length时,说明搜索区间为[left,right)左闭右开区间,因为nums.length是越界的。当while(left<right)退出时,left==right对应的索引漏搜索了一次,所以需要在退出循环后额外进行一次判断。

  • 搜索区间的收缩

    当搜索区间为[left,right]时,如果索引mid不是要找的target时,需要将它从搜索区间中去除,下一个要搜索的区间自然变成了[left,mid-1]和[mid+1,right]。当搜索区间为[left,right)时,去掉mid后的下一个搜索区间变成了[left,mid-1]和[mid+1,right),所以此时left=mid+1而right=mid。

在排序数组中查找元素的第一个和最后一个位置

题目:给定一个按照升序排列的整数数组nums,和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1, -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
//这道题目是要寻找给定元素在数组中的左侧边界和右侧边界
//因为元素在数组中可能重复,在nums[mid]==target时不能马上break,如果是寻找左侧边界就令right=mid在[left,mid)中继续寻找,如果是寻找右侧边界就令left=mid+1在[mid+1,right)中继续寻找
class Solution {
private:
int left_bound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
//根据left和right的取值搜索区间为[left,right)
while(left < right) {
int mid = left + (right-left) / 2;
if(nums[mid] == target) {
right = mid;
}else if(nums[mid] < target) {
left = mid+1;
}else if(nums[mid] > target) {
right = mid;
}
}
//搜索完left==right,取值范围为[0,nums.size()],需要判断没找到target的情况
//返回值left可以理解为在target左侧有left个元素
//特别如果target大于数组中所有元素,left==nums.size(),需要先判断越界
if(left == nums.size() || nums[left] != target) return -1;
return left;
}

int right_bound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
//根据left和right的取值搜索区间为[left,right)
while(left < right) {
int mid = left + (right-left) / 2;
if(nums[mid] == target) {
//while循环结束时,nums[left]一定不等于target,而nums[left-1]可能是target
left = mid+1;
}else if(nums[mid] < target) {
left = mid+1;
}else if(nums[mid] > target) {
right = mid;
}
}
//搜索完left==right,取值范围为[0,nums.size()],需要判断没找到target的情况
//返回值left可以理解为在target左侧有left个元素
//特别如果target小于数组中所有元素,left==0,需要先判断越界
if(left == 0 || nums[left-1] != target) return -1;
return left-1;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = left_bound(nums, target);
int right = right_bound(nums, target);
return vector<int>{left, right};
}
};

搜索插入位置

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while(left < right) {
int mid = left + (right-left)/2;
if(nums[mid] == target) {
return mid;
}else if(nums[mid] > target) {
right = mid;
}else if(nums[mid] < target) {
left = mid+1;
}
}
return right;
}
};

x的平方根

题目:给你一个非负整数 x ,计算并返回 x 的平方根。由于返回类型是整数,结果只保留整数部分,小数部分将被舍去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//初始搜索区间为[1,x]左闭右闭,因此while循环条件为left<=right
//循环跳出时left=right+1,right*right为小于x的最大平方数
class Solution {
public:
int mySqrt(int x) {
int left = 1, right = x;
while(left <= right) {
int mid = left + (right-left)/2;
long long guess = (long long)mid*mid;
if(guess == x) {
return mid;
}else if(guess > x) {
right = mid-1;
}else if(guess < x) {
left = mid+1;
}
}
return right;
}
};

山脉数组的峰顶索引

题目:给你由整数组成的山脉数组 arr,返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标i。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//初始搜索区间为[1,arr.size()-1]左闭右闭,因此while循环条件为left<=right
//山峰左侧满足单调递增,右侧满足单调递减
//如果左侧不满足单调递增,将搜索区间收缩为[left,mid],右侧同理,收缩为[mid,right]
//不排除mid是因为mid虽然自身做不了山峰但可以判断下一处山峰,例如[3,5,3,2,0],以左侧为例,第一次mid=2,arr[1]>arr[2],如果right=mid-1区间只剩下[3,5],这时候5无法作为山峰,右侧同理
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0, right = arr.size()-1;
int answer;
while(left <= right){
int mid = left + (right-left)/2;
if(arr[mid] < arr[mid-1]) right = mid;
else if(arr[mid] < arr[mid+1]) left = mid;
else{
answer = mid;
break;
}
}
return answer;
}
};

旋转数组的最小数字

题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转,该数组的最小值为1。

42vUu6.png
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//寻找旋转数组的最小元素即为寻找右排序数组的首个元素
//当nums[mid]>nums[right]时,一定在左排序数组里,旋转点一定在[mid+1,right]区间内
//当nums[mid]<nums[right]时,一定在右排序数组里,旋转点一定在[left,mid]区间内
//当nums[mid]==nums[right]时,无法判断,缩小搜索区间为[left,right-1]
//与right比较是因为right初始值肯定在右排序数组中,而left如果原数组未旋转在右排序,旋转则在左排序
//初始搜索区间为[1,numbers.size()-1]左闭右闭,因此while循环条件为left<=right
//退出循环时left=right+1,此时numbers[right]一定不是旋转点,right指向的是旋转点左侧的位置
class Solution {
public:
int minArray(vector<int>& numbers) {
int left = 0, right = numbers.size()-1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(numbers[mid] > numbers[right]) left = mid+1;
else if(numbers[mid] < numbers[right]) right = mid;
else right--;
}
return numbers[left];//return numbers[right+1]
}
};

0~n-1中缺失的数字

题目:一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的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
//缺失数字的右侧满足nums[mid]>mid,左侧满足nums[mid]=mid
//初始搜索区间为[1,numbers.size())左闭右开,因此while循环条件为left<right
//当mid位于右侧时,缩小搜索区间为[left,mid),当mid位于左侧时,缩小搜索区间为[mid+1,right)
class Solution {
public:
int missingNumber(vector<int>& nums) {
int left = 0, right = nums.size();
while(left < right) {
int mid = left + (right-left)/2;
if(nums[mid] > mid) {
right = mid;
}else if(nums[mid] <= mid) {
left = mid+1;
}
}
return left;
}
};

//初始搜索区间为[1,numbers.size()-1]左闭右闭,因此while循环条件为left<=right
//当mid位于右侧时,缩小搜索区间为[left,mid-1],当mid位于左侧时,缩小搜索区间为[mid+1,right]
//退出循环时left==right+1,根据它们的更新式,此时nums[right]<=mid,而nums[left]>mid,right指向缺失数字左边的位置,而left正好指向缺失数字的位置
class Solution {
public:
int missingNumber(vector<int>& nums) {
int left = 0, right = nums.size()-1;
while(left <= right) {
int mid = left + (right-left)/2;
if(nums[mid] > mid) {
right = mid-1;
}else if(nums[mid] <= mid) {
left = mid+1;
}
}
return left;
}
};

搜索旋转排序数组

题目:整数数组nums按升序排列,数组中的值互不相同。 在传递给函数之前,nums在预先未知的某个下标 k(0 <= k < nums.length)上进行了旋转。给你旋转后的数组nums和一个整数target ,如果 nums中存在这个目标值 target ,则返回它的下标,否则返回 -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
//旋转数组的特点是,数组中至少有一半的元素是有序的,每次二分时只需要判断target是否在有序的一侧
//初始搜索区间为[1,arr.size()-1]左闭右闭,因此while循环条件为left<=right
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
while(left <= right) {
int mid = left + (right-left)/2;
if(nums[mid] == target) return mid;
//当left==right且target不存在数组时,会进入死循环,需要额外进行判断
if(left == right && nums[mid] != target) return -1;
//左子数组有序
if(nums[mid] > nums[right]) {
//在左子数组中,可能target刚好位于左边界target[left],这里要用>=
//而判断是否为目标值交给nums[mid]==target判断
if(target >= nums[left] && target < nums[mid]) {
right = mid-1;
//在右子数组中
}else{
left = mid+1;
}
}
//右子数组有序
else if(nums[mid] < nums[right]) {
//在右子数组中
if(target > nums[mid] && target <= nums[right]) {
left = mid+1;
//在左子数组中
}else{
right = mid-1;
}
}
}
return -1;
}
};

搜索旋转数组

题目:给定一个排序后的数组,包含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
//旋转数组的特点是,数组中至少有一半的元素是有序的,每次二分时只需要判断target是否在有序的一侧
//初始搜索区间为[1,arr.size()-1]左闭右闭,因此while循环条件为left<=right
class Solution {
public:
int search(vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while(left <= right){
//当target不存在
if(left == right && arr[left] != target){
return -1;
}
int mid = (left + right) / 2;
if(arr[mid] == target){
//找到target的同时还需要找到其中索引值最小的一个
while(mid > 0 && arr[mid] == arr[mid - 1]){
mid--;
}
if(arr[0] == target) return 0;
return mid;
}
//arr[mid] == arr[left] 则缩短数组左边界
while(left < mid && arr[mid] == arr[left]){
left++;
}
//arr[mid] == arr[right] 则缩短数组右边界
while(right > mid && arr[mid] == arr[right]){
right--;
}
//左边有序
if(arr[mid] >= arr[left]){
//目标在左边部分,缩减搜索区间为[left,mid-1]
if(target >= arr[left] && target <= arr[mid]){
right = mid - 1;
}else{
//目标在右边部分,缩减搜索区间为[mid+1,right]
left = mid + 1;
}
}else{
//右边有序,arr[mid] <= arr[right]
//目标在右边部分,缩减搜索区间为[mid+1,right]
if(target >= arr[mid] && target <= arr[right]){
left = mid + 1;
}else{
//目标在左边部分,缩减搜索区间为[left,mid-1]
right = mid - 1;
}
}
}
return -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
//1. 数字直接输出
//2. 运算符号
//若当前运算符优先度较高,进栈,否则栈顶出栈输出,直到当前运算符优先度高于栈顶运算符,再进栈
vector<string> RPN;//后缀表达式(波兰表达式)

bool isNumber(string& c) {
return !((c == "+") || (c == "-") || (c == "*") || (c == "/"));
}
void InToRPN(string& s) {
stack<string> cs;
unordered_map<string, int> record({{"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}});
istringstream iss(s);
int num;
char op;
while(iss >> num) {
RPN.push_back(to_string(num));
iss >> op;
if(!iss) break;//读取完表达式最后一个整数,这时的op不需要再使用
string token(1, op);
if(cs.empty()) cs.push(token);
else{
int priority = record[token];
if(priority > record[cs.top()]) cs.push(token);
else{
while(!cs.empty() && priority <= record[cs.top()]) {
RPN.push_back(cs.top());
cs.pop();
}
cs.push(token);
}
}
}
while(!cs.empty()) {
RPN.push_back(cs.top());
cs.pop();
}
}

排序算法

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int size = nums.size();
int i, j;
for(i = 0; i < size; i++) {
int temp = nums[i];
for(j = i; j > 0 && nums[j-1] > temp; j--) {
nums[j] = nums[j-1];//升序排列,将比temp大的数往数组后面移动
}
nums[j] = temp;
}
return nums;
}
};

基尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int size = nums.size();
for(int gap = size / 2; gap > 0; gap /= 2) {
for(int i = gap; i < size; i++) {
int temp = nums[i];
int j;
for(j = i; j >= gap && nums[j-gap] > temp; j-= gap) {
nums[j] = nums[j-gap];
}
nums[j] = temp;
}
}
return nums;
}
};

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int size = nums.size();
bool bubble = true;
while(bubble) {
bubble = false;
for(int i = 0; i < size-1; i++) {
if(nums[i] > nums[i+1]) {
swap(nums[i], nums[i+1]);
bubble = true;
}
}
}
return nums;
}
};

归并排序

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
//1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
//2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
//3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
//4. 重复步骤3直到某一指针到达序列尾
//5. 将另一序列剩下的所有元素直接复制到合并序列尾
class Solution {
private:
void merge(vector<int>& nums, int l, int m, int r) {
int i, j, k;
int n1 = m-l+1;
int n2 = r-m;
int L[n1], R[n2];

for(i = 0; i < n1; i++)
L[i] = nums[l+i];
for(j = 0; j < n2; j++)
R[j] = nums[m+1+j];

i = j = 0;
k = l;
while(i < n1 && j < n2) {
if(L[i] <= R[j])
nums[k++] = L[i++];
else
nums[k++] = R[j++];
}
while(i < n1) nums[k++] = L[i++];
while(j < n2) nums[k++] = R[j++];
}

void mergeSort(vector<int>& nums, int l, int r) {
if(l < r) {
int m = l + (r-l) / 2;
mergeSort(nums, l, m);
mergeSort(nums, m+1, r);
merge(nums, l, m, r);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
int size = nums.size();
mergeSort(nums, 0, size-1);
return nums;
}
};

堆排序

img

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
//最大堆中的最大元素值出现在根结点(堆顶),且堆中每个父节点的元素值都大于等于其孩子结点
class Solution {
private:
void heapify(vector<int>& nums, int n, int i) {
int largest = i;//将最大元素设为堆顶元素
int l = 2*i + 1;//左孩子结点
int r = 2*i + 2;//右孩子结点

//如果left比root大的话
if(l < n && nums[l] > nums[largest])
largest = l;
//如果right比right大的话
if(r < n && nums[r] > nums[largest])
largest = r;

if(largest != i) {
swap(nums[i], nums[largest]);
heapify(nums, n, largest);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
//建立堆
for(int i = n/2-1; i >= 0; i--)
heapify(nums, n, i);
//把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆
for(int i = n-1; i >= 0; i--) {
swap(nums[0], nums[i]);
heapify(nums, i, 0);
}
return nums;
}
};

快速排序

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
//1. 从数列中挑出一个元素,称为 "基准"(pivot);
//2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
//3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序;
class Solution {
private:
int Partition(vector<int>& nums, int low, int high) {
int n = nums.size();
int i = low + (rand() % (high-low+1));//直接以第一个元素为pivot会超时
swap(nums[low], nums[i]);
int pivot = nums[low];
while(low < high) {
while(low < high && nums[high] >= pivot) high--;
nums[low] = nums[high];
while(low < high && nums[low] <= pivot) low++;
nums[high] = nums[low];
}
nums[low] = pivot;
return low;
}

void quickSort(vector<int>& nums, int low, int high) {
if(low < high) {
int pivot = Partition(nums, low, high);
quickSort(nums, low, pivot-1);
quickSort(nums, pivot+1, high);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
quickSort(nums, 0, n-1);
return nums;
}
};