LeetCode刷题笔记(十): 数据结构
一、数组
题目一：找到所有数组中消失的数字
给定一个长度为n的数组，其中包含范围为1到n的整数，有些整数重复了多次，有些整数没有出现，求1到n中没有出现过的整数。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
vector<int> bucket(n);
for (int num : nums) ++bucket[num - 1];
vector<int> res;
for (int i = 0; i < n; ++i) {
if (!bucket[i])
res.push_back(i + 1);
}
return res;
}
};提示：很简单不说了。
题目二：旋转图像
给定一个n×n的矩阵，求它顺时针旋转90度的结果，且必须在原矩阵上修改(in-place)。怎样能够尽量不创建额外储存空间呢？
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size() - 1;
for (int i = 0; i < (n + 1) / 2; ++i) {
for (int j = i; j < n - i; ++j) {
int temp = matrix[i][j];
int temp_i = i, temp_j = j;
for (int k = 0; k < 3; ++k) {
matrix[temp_i][temp_j] = matrix[n - temp_j][temp_i];
int temp2 = temp_i;
temp_i = n - temp_j;
temp_j = temp2;
}
matrix[temp_i][temp_j] = temp;
}
}
}
};提示：注意找到旋转的数字之间的位置关系。
题目三：搜索二维矩阵 II
给定一个二维矩阵，已知每行和每列都是增序的，尝试设计一个快速搜索一个数字是否在矩阵中存在的算法。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix[0].size(), m = matrix.size();
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target) return true;
if (matrix[i][j] > target) --j;
else ++i;
}
return false;
}
};提示：思考其性质，从右上角或左下角来进行搜索都是可以的。
题目四：最多能完成排序的块
给定一个含有0到n整数的数组，每个整数只出现一次，求这个数组最多可以分割成多少个子数组，使得对每个子数组进行增序排序后，原数组也是增序的。解答：
1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int maxArr = 0, chunks = 0;
for (int i = 0; i < arr.size(); ++i) {
maxArr = max(maxArr, arr[i]);
chunks += (maxArr == i);
}
return chunks;
}
};提示：如果当前最大值大于数组位置，则说明右边一定有小于数组位置的数字，需要把它也加入待排序的子数组；又因为数组只包含不重复的0到n，所以当前最大值一定不会小于数组位置。所以每当当前最大值等于数组位置时，假设为p，我们可以成功完成一次分割，并且其与上一次分割位置q之间的值一定是q+1到p的所有数字。
二、栈和队列
题目一：用栈实现队列
尝试使用栈(stack)来实现队列(queue)。解答：
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
36class MyQueue {
private:
vector<int> stack1;
vector<int> stack2;
public:
MyQueue() {}
void push(int x) {
while (!stack1.empty()) {
int temp = stack1.back();
stack1.pop_back();
stack2.push_back(temp);
}
stack1.push_back(x);
while (!stack2.empty()) {
int temp = stack2.back();
stack2.pop_back();
stack1.push_back(temp);
}
}
int pop() {
int ret = stack1.back();
stack1.pop_back();
return ret;
}
int peek() {
return stack1.back();
}
bool empty() {
return stack1.empty();
}
};提示：简单题，两次先入后出等价于先入先出。
题目二：最小栈
设计一个最小栈，除了需要支持常规栈的操作外，还需要支持在O(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
29class MinStack {
private:
vector<int> stack;
vector<int> minNumStack;
public:
MinStack() {}
void push(int val) {
stack.push_back(val);
if (minNumStack.empty() || minNumStack.back() >= val)
minNumStack.push_back(val);
}
void pop() {
int ret = stack.back();
stack.pop_back();
if (!minNumStack.empty() && ret == minNumStack.back())
minNumStack.pop_back();
}
int top() {
return stack.back();
}
int getMin() {
return minNumStack.back();
}
};提示：push()时判断一次，pop()时再判断一次即可，不需要每次都去排序或者进行插入删除操作。
题目三：有效的括号
给定一个只由左右圆括号、花括号和方括号组成的字符串，求这个字符串是否合法。合法的定义是每一个类型的左括号都有一个右括号一一对应，且括号内的字符串也满足此要求。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
bool isValid(string s) {
vector<char> stack;
for (char c : s) {
if (c == '(' || c == '[' || c == '{')
stack.push_back(c);
else if (!stack.empty() &&
(c == ')' && stack.back() == '(' ||
c == ']' && stack.back() == '[' ||
c == '}' && stack.back() == '{'))
stack.pop_back();
else return false;
}
return stack.empty();
}
};提示：运用一下栈的性质即可，因为这道题当左括号连续出现时也遵循先入后出的原则。
三、单调栈
算法解释：单调栈通过维持栈内值的单调递增(递减)性，在整体O(n)的时间内处理需要大小比较的问题。
题目：每日温度
给定每天的温度，求对于每一天需要等几天才可以等到更暖和的一天。如果该天之后不存在更暖和的天气，则记为0。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> stack;
vector<int> res(n);
for (int i = n - 1; i >= 0; --i) {
while (!stack.empty() && temperatures[stack.back()] <= temperatures[i])
stack.pop_back();
int temp = stack.empty() ? i : stack.back();
res[i] = temp - i;
stack.push_back(i);
}
return res;
}
};提示：虽然比较的是温度大小，但是栈应该存储下标方便用于进行天数差计算。
四、优先队列
算法解释：优先队列(priority queue)可以在O(1)时间内获得最大值，并且可以在O(log n)时间内取出最大值或插入任意值。
优先队列常常用堆(heap)来实现。堆是一个完全二叉树，其每个节点的值总是大于等于子节点的值。实际实现堆时，我们通常用一个数组而不是用指针建立一个树。这是因为堆是完全二叉树，所以用数组表示时，位置i的节点的父节点位置一定为(i-1)/2，而它的两个子节点的位置又一定分别为2i+1和2i+2。
以下是堆的实现方法，其中最核心的两个操作是上浮和下沉：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
47class Heap {
private:
vector<int> heap_;
public:
Heap() {}
// 上浮。
void swim(int pos) {
int next_pos = (pos - 1) / 2;
while (pos > 0 && heap_[next_pos] < heap_[pos]) {
swap(heap_[next_pos], heap_[pos]);
pos = next_pos;
next_pos = (pos - 1) / 2;
}
}
// 下沉。
void sink(int pos) {
int n = heap_.size();
int next_pos = 2 * pos + 1;
while (next_pos < n) {
if (next_pos < n - 1 && heap_[next_pos] < heap_[next_pos + 1])
++next_pos;
if (heap_[pos] >= heap_[next_pos]) break;
swap(heap_[next_pos], heap_[pos]);
pos = next_pos;
next_pos = 2 * pos + 1;
}
}
// 插入任意值：把新的数字放在最后一位，然后上浮。
void push(int k) {
heap_.push_back(k);
swim(heap_.size() - 1);
}
// 删除最大值：把最后一个数字挪到开头，然后下沉。
void pop() {
heap_[0] = heap_.back();
heap_.pop_back();
sink(0);
}
// 获得最大值。
int top() { return heap_[0]; }
};题目一：合并 K 个升序链表
给定k个增序的链表，试将它们合并成一条增序链表。解答：
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
54
55
56
57
58// struct ListNode {
// int val;
// ListNode *next;
// ListNode() : val(0), next(nullptr) {}
// ListNode(int x) : val(x), next(nullptr) {}
// ListNode(int x, ListNode *next) : val(x), next(next) {}
// };
class Solution {
private:
void swim(vector<pair<int, int>>& res, int val, int i) {
res.push_back({val, i});
int pos = res.size() - 1;
int next = (pos - 1) / 2;
while (pos > 0 && res[pos].first < res[next].first) {
swap(res[pos], res[next]);
pos = next;
next = (pos - 1) / 2;
}
}
void sink(vector<pair<int, int>>& res) {
res[0] = res.back();
res.pop_back();
int pos = 0;
int next = pos * 2 + 1;
int size = res.size();
while (next < size) {
if (next < size - 1 && res[next].first > res[next + 1].first) ++next;
if (res[pos].first < res[next].first) break;
swap(res[pos], res[next]);
pos = next;
next = pos * 2 + 1;
}
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* res = new ListNode(0);
ListNode* head = res;
vector<pair<int, int>> priority_queue;
for (int i = 0; i < lists.size(); ++i) {
if (lists[i] != nullptr)
swim(priority_queue, lists[i]->val, i);
}
while (!priority_queue.empty()) {
auto [i, j] = priority_queue[0];
ListNode *temp = new ListNode(i);
head->next = temp;
head = head->next;
sink(priority_queue);
lists[j] = lists[j]->next;
if (lists[j] != nullptr)
swim(priority_queue, lists[j]->val, j);
}
return res->next;
}
};题目二：天际线问题
给定建筑物的起止位置和高度，返回建筑物轮廓(天际线)的拐点。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<vector<int>> skylines;
priority_queue<pair<int, int>> pq;
int i = 0, cur_x, cur_h;
int n = buildings.size();
while (i < n || !pq.empty()) {
if (pq.empty() || (i < n && buildings[i][0] <= pq.top().second)) {
cur_x = buildings[i][0];
while (i < n && buildings[i][0] <= cur_x) {
pq.emplace(buildings[i][2], buildings[i][1]);
++i;
}
} else {
cur_x = pq.top().second;
while (!pq.empty() && pq.top().second <= cur_x) pq.pop();
}
cur_h = pq.empty() ? 0 : pq.top().first;
if (skylines.empty() || cur_h != skylines.back()[1])
skylines.push_back({cur_x, cur_h});
}
return skylines;
}
};提示：非常难的一道题，我们可以使用优先队列储存每个建筑物的高度和右端(这里使用pair，其默认比较函数是先比较第一个值，如果相等则再比较第二个值)，从而获取目前会拔高天际线、且妨碍到前一个建筑物的右端端点的下一个建筑物。
五、双端队列
题目：滑动窗口最大值
给定一个整数数组和一个滑动窗口大小，求在这个窗口的滑动过程中，每个时刻其包含的最大值。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> maxArr;
for (int i = 0; i < k; ++i) {
while (!maxArr.empty() && nums[i] > nums[maxArr.back()])
maxArr.pop_back();
maxArr.push_back(i);
}
res.push_back(nums[maxArr.front()]);
for (int i = k; i < nums.size(); ++i) {
if (maxArr.front() == i - k)
maxArr.pop_front();
while (!maxArr.empty() && nums[i] > nums[maxArr.back()])
maxArr.pop_back();
maxArr.push_back(i);
res.push_back(nums[maxArr.front()]);
}
return res;
}
};提示：我们可以利用双端队列进行操作：每当向右移动时，把窗口左端的值从双端队列左端剔除，把双端队列右边小于窗口右端的值全部剔除。这样双端队列的最左端永远是当前窗口内的最大值。另外，这道题也是单调栈的一种延申：该双端队列利用从左到右递减来维持大小关系。
六、哈希表
算法解释：哈希表(hash table, hash map)，又称散列表，使用O(n)空间复杂度存储数据，通过哈希函数(hash function)映射位置，从而实现近似O(1)时间复杂度的插入、查找、删除等操作。哈希表可以用来统计频率，记录内容等等。
题目一：两数之和
给定一个(未排序的)整数数组，已知有且只有两个数的和等于给定值，求这两个数的位置。解答：
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); ++i) {
if (map.count(target - nums[i]) != 0)
return {i, map[target - nums[i]]};
map.emplace(nums[i], i);
}
return {};
}
};提示：典中典之空间换时间。
题目二：最长连续序列
给定一个整数数组，求这个数组中的数字可以组成的最长连续序列有多长。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> set(nums.begin(), nums.end());
int res = 0;
while (!set.empty()) {
int len = 1;
int temp = *set.begin();
int temp2 = temp;
set.erase(temp);
while (set.count(temp - 1)) {
++len;
--temp;
set.erase(temp);
}
while (set.count(temp2 + 1)) {
++len;
++temp2;
set.erase(temp2);
}
res = max(res, len);
}
return res;
}
};提示：我讨厌这道题，实际上并不难，想一下怎样才不会漏算或者多算，答案就是直接向两边遍历即可。
题目三：直线上最多的点数
给定一些二维坐标中的点，求同一条线上最多有多少点。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int res = 1;
int n = points.size();
for (int i = 0; i < n; ++i) {
auto vec1 = points[i];
unordered_map<double, int> map;
for (int j = i + 1; j < n; ++j) {
auto vec2 = points[j];
double k = vec2[0] - vec1[0] == 0 ? 1e8 : (double)(vec2[1] - vec1[1]) / (double)(vec2[0] - vec1[0]);
++map[k];
res = max(res, map[k] + 1);
}
}
return res;
}
};提示：hash表用以记录斜率和数量，小技巧是第i个节点只需要算i+1以及之后的点，因为之前的点已经在之前算过了。
七、多重集合和映射
题目：重新安排行程
给定一个人坐过的一些飞机的起止机场，已知这个人从 JFK 起飞，那么这个人是按什么顺序飞的；如果存在多种可能性，返回字母序最小的那种。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
unordered_map<string, multiset<string>> adj;
vector<string> res;
void dfs(const string &s) {
while (!adj[s].empty()) {
string next = *adj[s].begin();
adj[s].erase(adj[s].begin());
dfs(next);
}
res.push_back(s);
}
public:
vector<string> findItinerary(vector<vector<string>> &tickets) {
for (const auto &ticket : tickets) {
adj[ticket[0]].insert(ticket[1]);
}
dfs("JFK");
reverse(res.begin(), res.end());
return res;
}
};提示：很难很难的题，直接用深搜暴力遍历的话也是无法做出来的，关键是在于如何剪枝，当一条路经走完后应该直接跳到之前的某个点。而这里的代码很巧妙的解决了这个问题，当adj[s]为empty的时候会返回之前的节点，而且当该路经可通时才把整个路经push进res。因为是倒着push的，所以最后需要reverse。
八、前缀和与积分图
算法解释：一维的前缀和(cumulative sum)，二维的积分图(summed-area table, image integral)都是把每个位置之前的一维线段或二维矩形预先存储，方便加速计算。如果需要对前缀和或积分图的值做寻址，则要存入哈希表；如果要对每个位置记录前缀和或积分图的值，则可以储存到一维或二维数组里，也常常伴随着动态规划。
题目一：区域和检索 - 数组不可变
设计一个数据结构，使得其能够快速查询给定数组中，任意两个位置间所有数字的和。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class NumArray {
private:
vector<int> myNums;
public:
NumArray(vector<int>& nums) {
for (int i = 1; i < nums.size(); ++i) {
nums[i] += nums[i - 1];
}
myNums.push_back(0);
myNums.insert(myNums.begin() + 1, nums.begin(), nums.end());
}
int sumRange(int left, int right) {
return myNums[right + 1] - myNums[left];
}
};提示：使用前缀和来完成，注意需要一个前置零来标志前缀和为零的情况。
题目二：二维区域和检索 - 矩阵不可变
设计一个数据结构，使得其能够快速查询给定矩阵中，任意两个位置包围的长方形中所有数字的和。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class NumMatrix {
public:
NumMatrix(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
myMatrix.assign(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
myMatrix[i][j] = matrix[i - 1][j - 1] + myMatrix[i - 1][j] + myMatrix[i][j - 1] - myMatrix[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return myMatrix[row2 + 1][col2 + 1] - myMatrix[row1][col2 + 1] - myMatrix[row2 + 1][col1] + myMatrix[row1][col1];
}
private:
vector<vector<int>> myMatrix;
};提示：注意一下前缀和的计算方式即可，注意会有有重复的部分。
题目三：和为 K 的子数组
给定一个数组，寻找和为k的连续区间个数。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int prefix = 0, count = 0;
unordered_map<int, int> map;
map[prefix] = 1;
for (int num : nums) {
prefix += num;
count += map[prefix - k];
++map[prefix];
}
return count;
}
};提示：需要利用map来快速查找是否有对应的前缀和，连续区间经常使用前缀和来表示。
九、练习
题目一：重塑矩阵
将一个m*n的矩阵转化为r*l的矩阵。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
int n = mat.size(), m = mat[0].size();
if (n * m != r * c) return mat;
vector<vector<int>> reshapeMat(r, vector<int>(c));
int row = 0, column = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
reshapeMat[row][column++] = mat[i][j];
if (column == c) {
column = 0;
++row;
}
}
}
return reshapeMat;
}
};提示：很简单，没什么好说的。
题目二：下一个更大元素 II
给定一个循环数组nums(nums[nums.length - 1]的下一个元素是nums[0])，返回nums中每个元素的下一个更大元素。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int size = nums.size();
nums.insert(nums.end(), nums.begin(), nums.end() - 1);
vector<int> res(size, -1);
vector<int> stack;
for (int i = 0; i < size * 2 - 1; ++i) {
while (!stack.empty() && nums[i] > nums[stack.back()]) {
int index = stack.back() % size;
res[index] = nums[i];
stack.pop_back();
}
stack.push_back(i);
}
return res;
}
};提示：有点儿意思但不多，核心考点是单调栈，然后循环的处理很简单，直接在后面接上前面的元素就行了。
题目三：数组的度
给定一个非空且只包含非负数的整数数组nums，数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是在nums中找到与nums拥有相同大小的度的最短连续子数组，返回其长度。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
unordered_map<int, int> map1;
unordered_map<int, pair<int, int>> map2;
int maxCount = 0, minLength = 50001;
for (int i = 0; i < nums.size(); ++i) {
if (map2.count(nums[i]))
map2[nums[i]].second = i;
else
map2[nums[i]] = {i, i};
++map1[nums[i]];
maxCount = max(map1[nums[i]], maxCount);
}
for (auto [i, j] : map1) {
if (j == maxCount) {
int len = map2[i].second - map2[i].first + 1;
minLength = min(minLength, len);
}
}
return minLength;
}
};提示：不是很难，主要是两个映射关系，数字对度和数字对长度。
题目四：最长和谐子序列
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。给你一个整数数组nums，请你在所有可能的子序列中找到最长的和谐子序列的长度。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
int findLHS(vector<int> &nums) {
unordered_map<int, int> map;
int maxCount = 0;
for (int num : nums) ++map[num];
for (auto [i, j] : map) {
if (map.count(i - 1))
maxCount = max(maxCount, j + map[i - 1]);
if (map.count(i + 1))
maxCount = max(maxCount, j + map[i + 1]);
}
return maxCount;
}
};提示：记住需要先count,这才是效率更高的做法。如果直接加
map[i - 1]的话，map会自己创建一个{i - 1, 0}。题目五：三数之和
给你一个整数数组nums，请你返回所有和为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
28class Solution {
public:
vector<vector<int>> threeSum(vector<int> &nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) ++left;
else if (sum > 0) --right;
else {
res.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1])
++left;
while (left < right && nums[right] == nums[right - 1])
--right;
++left;
--right;
}
}
}
return res;
}
};提示：这道题更像是双指针的题，通过双指针把三数之和降维成两数之和，那为什么会放在妙用数据结构里呢？答案是cpp20+可以直接使用
unordered_set(vector<int>)。题目六：寻找重复数
给定一个包含n+1个整数的数组nums，其数字都在[1, n]范围内(包括1和n)，假设nums只有一个重复的整数，返回这个重复的数。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int findDuplicate(vector<int>& nums) {
int fast = 0, slow = fast;
do {
fast = nums[nums[fast]];
slow = nums[slow];
} while (fast != slow);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return fast;
}
};提示：和数据结构到底有什么关系呢我请问了，使用unordered_map会变得很慢且消耗更多空间，这道题的关键在于将重复数的特殊性(因为值一定小于等于下标)映射为环路问题，从而使用floyd判圈法即可。
题目七：超级丑数
超级丑数是一个正整数，并满足其所有质因数都出现在质数数组primes中。给你一个整数n和一个整数数组primes，返回第n个超级丑数。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
priority_queue<int, vector<int>, greater<int>> min_heap;
min_heap.emplace(1);
while (n --) {
int min_num = min_heap.top();
min_heap.pop();
if (n == 0) return min_num;
for (int prime : primes) {
if (prime <= __INT_MAX__ / min_num)
min_heap.emplace(prime * min_num);
if (min_num % prime == 0) break;
}
}
return -1;
}
};提示：有点难想，使用最小堆来完成，主要是要知道何时pop以及怎么插入，注意边界判断以及去重处理(减少重复操作)。
题目八：优势洗牌
给定两个长度相等的数组nums1和nums2，nums1相对于nums2的优势可以用满足nums1[i]>nums2[i]的索引i的数目来描述。返回nums1的任意排列，使其相对于nums2的优势最大化。解答一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> numTocount;
set<int> replaceNums;
for (int num : nums1) {
++numTocount[num];
replaceNums.emplace(num);
}
for (int i = 0; i < nums2.size(); ++i) {
auto temp = replaceNums.lower_bound(nums2[i] + 1);
int replaceNum = -1;
if (temp != replaceNums.end())
replaceNum = *temp;
else replaceNum = *replaceNums.begin();
nums2[i] = replaceNum;
numTocount[replaceNum]--;
if (numTocount[replaceNum] == 0)
replaceNums.erase(replaceNum);
}
return nums2;
}
};提示：有点蠢，不建议使用这个方法，仅供利用数据结构的解法参考。
解答二：
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
26class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<pair<int, int>> nums2ValToIndex(n);
for (int i = 0; i < n; ++i) {
nums2ValToIndex[i].first = nums2[i];
nums2ValToIndex[i].second = i;
}
sort(nums1.begin(), nums1.end());
sort(nums2ValToIndex.begin(), nums2ValToIndex.end(), [](auto &a, auto &b)
{ return a.first < b.first; });
int start = 0, end = n - 1;
for (int i = 0; i < n; ++i) {
if (nums1[i] > nums2ValToIndex[start].first) {
nums2ValToIndex[start++].first = nums1[i];
} else {
nums2ValToIndex[end--].first = nums1[i];
}
}
for (int i = 0; i < n; ++i) {
nums2[nums2ValToIndex[i].second] = nums2ValToIndex[i].first;
}
return nums2;
}
};提示：排完序之后变得非常简单，双指针就能轻松写完，且复杂度主要是在排序上，主要是快排是无序的所以需要记录一下值和下标的映射关系。
题目九：区域和检索 - 数组可修改
设计一个数据结构，使得其能够快速查询给定数组中任意两个位置间所有数字的和以及更新数组中的元素。解答：
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
54
55
56
57
58
59
60class NumArray {
struct TreeNode {
int val;
int l, r;
TreeNode(int _l, int _r) : val(0), l(_l), r(_r) {}
};
private:
vector<TreeNode> tr;
vector<int> myNums;
void build(int u, int l, int r) {
tr[u] = TreeNode(l, r);
if (l == r) return;
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void update(int u, int x, int v) {
if (tr[u].l == x && tr[u].r == x) {
tr[u].val += v;
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) update(u << 1, x, v);
else update(u << 1 | 1, x, v);
tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}
int query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r)
return tr[u].val;
int mid = (tr[u].l + tr[u].r) >> 1;
int sum = 0;
if (l <= mid) sum += query(u << 1, l, r);
if (r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
public:
NumArray(vector<int>& nums) {
myNums = nums;
int n = nums.size();
tr.assign(4 * n, TreeNode(0, 0));
build(1, 0, n - 1);
for (int i = 0; i < n; ++i) {
update(1, i, nums[i]);
}
}
void update(int index, int val) {
update(1, index, val - myNums[index]);
myNums[index] = val;
}
int sumRange(int left, int right) {
return query(1, left, right);
}
};提示：使用线段树结构，线段树是区间查询和区间更新的二叉树结构。它能把区间操作从O(n)降到O(log n)，常用于处理区间最值、区间和、区间修改等问题。
相关推荐
2025-08-25
LeetCode刷题笔记(一): 贪心
贪心算法的核心思想：局部最优以实现全局最优。 一、分配问题 题目：分发糖果n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。 相邻两个孩子中，评分更高的那个会获得更多的糖果。请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。 解答： 123456789101112131415161718class Solution {public: int candy(vector<int> &ratings) { int n = ratings.size(); vector<int> candies(n, 1); for (int i = 1; i < n; ++i) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] +...
2025-09-15
LeetCode刷题笔记(七): 数学问题
一、最大公约数和最小公倍数这个没什么好说的，辗转相除法： 1234567int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }int lcm(int a, int b) { return a * b / gcd(a, b); } 也可以通过扩展欧几里得算法(extended gcd)在求得a和b最大公因数的同时，也得到它们的系数x和y，从而使ax+by=gcd(a, b)，也就是贝祖等式。 12345678910int xGCD(int a, int b, int &x, int &y) { if (b == 0) { x = 1, y = 0; return a; } int x_inner, y_inner; int gcd = xGCD(b, a % b, x_inner, y_inner); x = y_inner, y =...
2025-08-26
LeetCode刷题笔记(二): 双指针
双指针算法的核心思想：双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。 一、Two Sum 题目：两数之和 II - 输入有序数组给你一个下标从1开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。 解答： 12345678910vector<int> twoSum(vector<int>& numbers, int target) { int l = 0, r = numbers.size() - 1, two_sum; while (l < r) { ...
2025-09-02
LeetCode刷题笔记(五): 搜索
搜索算法主要包括深度优先搜索和广度优先搜索。 一、深度优先搜索 算法介绍：深度优先搜索(depth-first search，DFS)在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈(stack)来实现，也可以通过与栈等价的递归来实现。对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。 12345 1 / \ 2 3...
2025-08-27
LeetCode刷题笔记(三): 二分查找
二分查找算法的核心思想：二分查找也常被称为二分法或者折半查找 (binary search, bisect)，每次查找时通过将待查找的单调区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为O(n)的数组，二分查找的时间复杂度为O(logn)。 一、求开方 题目：x 的平方根给定一个非负整数 x，求它的开方，向下取整。 解答： 12345678910111213141516int mySqrt(int x) { int l = 1, r = x, mid, x_div_mid; while (l <= r) { mid = l + (r - l) / 2; x_div_mid = x / mid; if (mid == x_div_mid) { return mid; } if (mid < x_div_mid) { l = mid + 1; }...
2025-09-18
LeetCode刷题笔记(八): 分治
算法解释：顾名思义，分治问题由“分”(divide)和“治”(conquer)两部分组成，通过把原问题分为子问题，再将子问题进行处理合并，从而实现对原问题的求解。我们在排序章节展示的归并排序就是典型的分治问题，其中“分”即为把大数组平均分成两个小数组，通过递归实现，最终我们会得到多个长度为1的子数组;“治”即为把已经排好序的两个小数组合成为一个排好序的大数组从长度为 1 的子数组开始，最终合成一个大数组。 自上而下的分治可以和 memoization 结合，避免重复遍历相同的子问题。如果方便推导，也可以换用自下而上的动态规划方法求解。 一、表达式问题 题目：为运算表达式设计优先级给定一个只包含加、减和乘法的数学表达式，求通过加括号可以得到多少种不同的结果。 解答： 1234567891011121314151617181920212223242526272829303132class Solution {public: vector<int> diffWaysToCompute(string expression) { ...
评论
公告
去听サイエンス谢谢喵ヾ(=`ω´=)ノ”
