【Leetcode刷题记录_C++】【数据结构】_给定一个字符串,里面包含n个数,其中前n-1个数是数组序列,第n个数是需要赢的次数。

数据结构

数组

448. 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
思路：
桶计数
代码：

class Solution {
public:
	vector<int> findDisappearedNumbers(vector<int>& nums) {
		vector<int> a(nums.size(), 0), re;
		for (int i = 0; i < nums.size(); i++) 
			a[nums[i] - 1] = 1;
		for (int i = 0; i < nums.size(); i++) {
			if (a[i] == 0)
				re.push_back(i + 1);
		}
		return re;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
思路：
不能另存，那么就一次换完，由外向内出发，比如4*4的矩阵，只需操作(0,0)-(0-3)即可完成整个外层的替换
代码：

class Solution {
public:
	void rotate(vector<vector<int>>& matrix) {
		for (int i = matrix.size() - 1, cnt = 0; i > 0; i -= 2, cnt++) {
			for (int j = cnt, temp1, k = i + cnt, l; j - cnt < i; j++) {
				l = k - j + cnt;
				temp1 = matrix[l][cnt];
				matrix[l][cnt] = matrix[k][l];
				matrix[k][l] = matrix[j][k];
				matrix[j][k] = matrix[cnt][j];
				matrix[cnt][j] = temp1;
			}
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
1
2

思路：
注意是m*n矩阵
可以从右上角开始查找，若当前值大于待搜索值，我们向左移动一位；若当前值小于待搜索值，我们向下移动一位（这里的思路很巧妙，由题可得，每个点的值是以他为右下角的所有矩形的最大值，从右上角开始搜索，实际上就是从行开始排除，若比目标小，说明在外层，否则在内层）
代码：

class Solution {
public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		int j = matrix[0].size() - 1, i = 0;
		while (j >= 0 && i < matrix.size()) {
			if (matrix[i][j] > target)
				j--;
			else if (matrix[i][j] < target)
				i++;
			else
				return true;
		}
		return false;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

769. 最多能完成排序的块

数组arr是[0, 1, …, arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

思路：
意思是下一个块内数字必须大于上一个块内数字，那么，遍历数组，建立一个新数组p，p[i]指第i块的最大值，每次遇到一个大于p尾的最大值，push_back，如果遇到一个值小于队尾，从p头遍历，遇到大于该值的，remove掉，直到只剩最后一个个元素
代码：

class Solution {
public:
	int maxChunksToSorted(vector<int>& arr) {
		int cnt = 0, max = -1, sum = 0;
		for (int i = 0; i < arr.size(); i++) {
			sum += pow(2, arr[i]);
			if (arr[i] > max) 
				max = arr[i];
			if (sum == pow(2, i + 1) - 1)//发现截止至i位置的数包含了0-i的数即可以分为一块
				cnt++;
		}
		return cnt;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

栈和队列

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(MyQueue* obj, int x) 将元素 x 推到队列的末尾
int pop(MyQueue* obj) 从队列的开头移除并返回元素
int peek(MyQueue* obj) 返回队列开头的元素
boolean empty(MyQueue* obj) 如果队列为空，返回 true ；否则，返回 false
1
2
3
4

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
1
2

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
1

思路：
栈：顶入顶出
队列：尾入头出
设置两个栈in&out
push：栈out空：push入栈in 非空：pop复制栈out到in
pop：如果栈out空，pop栈in，push到栈out，返回最后的值，如果非空，pop到栈out
peek：peek栈out
empty：is empty in&out
代码：

class MyQueue {
public:
    stack<int> s1, s2;
    MyQueue() {

    }

    void push(int x) {
        s1.push(x);
    }

    int pop() {
        int a = peek();
        s2.pop();
        return a;
    }

    int peek() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();   
            }
        }
        return s2.top();
    }

    bool empty() {
        if (s1.empty() && s2.empty())
            return true;
        return false;
    }
};
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

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

void push(MinStack* obj, int val) —— 将元素 x 推入栈中。
int pop(MinStack* obj) —— 删除栈顶的元素。
int top(MinStack* obj) —— 获取栈顶元素。
int getMin(MinStack* obj) —— 检索栈中的最小元素。
1
2
3
4

思路：
push：插入，每次记录更新链长度
pop：删除链尾
top：返回链尾
getMin：每次记录最小值在栈属性（同样用栈记录，这样最小值pop掉后栈顶就是第二小的了，因为栈是后入先出，所以不用担心pop掉当前最小值之后出来的不是第二小的，因为当前栈中第二小的值一定会在第一小的值之前pop掉的，所以哪怕它不在最小栈中也没事）
代码：

class MinStack {
public:
    int min = INT_MAX;
    stack<int> s, ms;
    MinStack() {

    }

    void push(int val) {
        if (val <= min) {
            min = val;
            ms.push(val);
        }
        s.push(val);
    }

    void pop() {
        if (s.top() == min) {
            ms.pop();
            min = ms.empty() ? INT_MAX : ms.top();//注意空栈
        }
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return ms.top();
    }
};
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

20. 有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
1
2

思路：
括号匹配是典型的使用栈来解决的问题。我们从左往右遍历，每当遇到左括号便放入栈内，遇到右括号则判断其和栈顶的括号是否是统一类型，是则从栈内取出左括号，否则说明字符串不合法。
代码：

class Solution {
public:
	bool isValid(string s) {
		stack<char> a;
		for (int i = 0; i < s.size(); i++) {
			switch(s[i]){
			case ')':
				if (!a.empty() && a.top() == '(')
					a.pop();
				else
					return false;
				break;
			case ']':
				if (!a.empty() && a.top() == '[')
					a.pop();
				else
					return false;
				break;
			case '}':
				if (!a.empty() && a.top() == '{')
					a.pop();
				else
					return false;
				break;
			default:
				a.push(s[i]);	
            }	
		}
		return a.empty();//输出关键
	}
};
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

单调栈

739. 每日温度

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
思路：
从左到右将天数入栈，当天温度入栈大于栈底（栈内最大）天数的温度就开始返回天数差，反之，只入栈
代码：

class Solution {
public:
	vector<int> dailyTemperatures(vector<int>& temperatures) {
		stack<int> temp;
		for (int i = 0; i < temperatures.size(); i++) {		
			while (!temp.empty()) {
				if (temperatures[i] > temperatures[temp.top()]) {
					temperatures[temp.top()] = i - temp.top();
					temp.pop();
				}
				else
					break;
			}
			temp.push(i);
		}
        while (!temp.empty()) {
			temperatures[temp.top()]=0;
            temp.pop();
		}
		return temperatures;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

优先队列

优先队列（priority queue）可以在 O(1) 时间内获得最大值，并且可以在 O(log n) 时间内取出最大值或插入任意值。
优先队列常常用堆（heap）来实现。堆是一个完全二叉树，其每个节点的值总是大于等于子节点的值。实际实现堆时，我们通常用一个数组而不是用指针建立一个树。这是因为堆是完全二叉树，所以用数组表示时，位置 i 的节点的父节点位置一定为 i/2，而它的两个子节点的位置又一定分别为 2i 和 2i+1。

最核心的两个操作是上浮和下沉：如果一个节点比父节点大，那么需要交换这个两个节点；交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，我们称之为上浮；类似地，如果一个节点比父节小，也需要不断地向下进行比较和交换操作，我们称之为下沉。如果一个节点有两个子节点，我们总是交换最大的子节点。

插入任意值：把新的数字放在最后一位，然后上浮
删除最大值：把最后一个数字挪到开头，然后下沉

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。
思路：
优先队列：我们需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。

代码：

class Solution {
public:
	struct Comp {
		bool operator() (ListNode* l1, ListNode* l2) {
			return l1->val > l2->val;//大于号顶部才是最小
		}
	};
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		ListNode* re, * head;
		priority_queue<ListNode*, vector<ListNode*>, Comp> q;
		re = new ListNode;
		head = re;
		for (int i = 0; i < lists.size(); i++) {
			if (lists[i] != NULL)
				q.push(lists[i]);
		}
		while(!q.empty()) {
			head->next = q.top();
			q.pop();
			head = head->next;
			if (head->next != NULL)
				q.push(head->next);
		}
		return re->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
25
26

218. 天际线问题

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的 天际线 。

每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。
1
2
3

天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],…] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意：输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]
思路：
（优先队列）
通过分析问题：
如果是「从下到上」转向「水平方向」，纵坐标最大的点是关键点；
如果是「从上到下」转向「水平方向」，纵坐标第二大的点是关键点。

代码：

class Solution {
public:
	vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {//默认输入是从左到右的建筑
		vector<vector<int>> ans;
		priority_queue<pair<int, int>> max_heap; // <高度, 右端>
		int i = 0, len = buildings.size();
		int cur_x, cur_h;
		while (i < len || !max_heap.empty()) {//保证建筑没遍历完，或者遍历完了但是max_heap没遍历完
			if (max_heap.empty() || i < len && buildings[i][0] <= max_heap.top().second) {//如果当前建筑左坐标比优先队列最高建筑的右坐标小，判断上升转折点
				cur_x = buildings[i][0];
				while (i < len && cur_x == buildings[i][0]) {//所有左端相同的建筑放入优先队列
					max_heap.emplace(buildings[i][2], buildings[i][1]);
					++i;
				}
			}
			else {//如果当前建筑左坐标比优先队列的最大高度建筑的右坐标大，说明一群建筑结束，可以开始判断该群建筑的所有下降转折点了
				cur_x = max_heap.top().second;
				while (!max_heap.empty() && cur_x >= max_heap.top().second) {//把所有优先队列内比头右坐标小的剔除(下降点只会在最高点的右边)
					max_heap.pop();//如果是「从上到下」转向「水平方向」，纵坐标第二大的点是关键点。
				}
			}
			cur_h = (max_heap.empty()) ? 0 : max_heap.top().first;
			if (ans.empty() || cur_h != ans.back()[1]) {//因为只有判断下降时才会pop优先队列，所以在同一群建筑中和优先队列最高高度不一样才加入输出
				ans.push_back({ cur_x, cur_h });//如果是「从下到上」转向「水平方向」，纵坐标最大的点是关键点；所以上升不pop。
			}
		}
		return ans;
	}
};
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

双端队列

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

思路：
如果当前遍历的数比队尾的值大，则需要弹出队尾值，直到队列重新满足从大到小的要求。刚开始遍历时，L 和 R 都为 0，有一个形成窗口的过程，此过程没有最大值，L 不动，R 向右移。当窗口大小形成时，L 和 R 一起向右移，每次移动时，判断队首的值的数组下标是否在 [L,R] 中，如果不在则需要弹出队首的值，当前窗口的最大值即为队首的数。

代码：

class Solution {
public:
	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
		vector<int> re;
		deque<int> a;
		for (int i = 0; i < nums.size(); i++) {
			if (i - a.front() == k)
				a.pop_front();
			while (!a.empty()&& nums[i] >= nums[a.back()]) 
				a.pop_back();
			a.push_back(i);
			if (i >= k - 1)
				re.push_back(nums[a.front()]);
		}
		return re;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

哈希表

哈希表，又称散列表，使用 O(n) 空间复杂度存储数据，通过哈希函数映射位置，从而实现近似 O(1) 时间复杂度的插入、查找、删除等操作。

例如我们需要统计一个字符串中所有字母的出现次数，则可以用一个长度为 26 的数组来进行统计，其哈希函数即为字母在字母表的位置，这样空间复杂度就可以降低为常数。

1. 两数之和

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

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

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

思路：
哈希表：target-nums[i]
代码：

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		unordered_map<int, int> m;
		for (int i = 0; i < nums.size(); i++) {
			auto pos = m.find(target - nums[i]);//移动迭代器
			if (pos == m.end())
				m[nums[i]] = i;//不用insert
			else
				return { i,pos->second };
		}
		return {};
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路：
把所有数字放到一个哈希表，然后不断地从哈希表中任意取一个值，并删除掉其之前之后的所有连续数字，然后更新目前的最长连续序列长度。重复这一过程，我们就可以找到所有的连续数字序列。
代码：

class Solution {
public:
	int longestConsecutive(vector<int>& nums) {
		unordered_set<int> m;
		int cur, next, prev, max1 = INT_MIN;
        if(nums.size() == 0)
            return 0;
		for (int i = 0; i < nums.size(); i++)
			m.insert(nums[i]);
		while (!m.empty()) {
			cur = *m.begin();
			next = cur + 1;
			prev = cur - 1;
			m.erase(cur);
			while (m.count(next)) 
				m.erase(next++);
			while (m.count(prev))
				m.erase(prev--);
			max1 = max(max1, next - prev - 1);
		}
		return max1;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

149. 直线上最多的点数

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

思路：
直线：
y=kx+b
对于每个点，和其他点必成一条直线，建立哈希表统计次数
代码：

class Solution {
public:
	int maxPoints(vector<vector<int>>& points) {
		unordered_map<double, int> m;
		int max1 = 1, ay = 1;
		double s;
		for (int i = 0; i < points.size(); i++) {
			for (int j = i + 1; j < points.size(); j++) {
				if (points[i][0] == points[j][0])
					ay++;
				else {
					s = (double)(points[i][1] - points[j][1]) / (double)(points[i][0] - points[j][0]);
					if (m.count(s))
						m[s]++;
					else
						m[s] = 2;
				}
				max1 = max(max1, ay);
			}
			for (const auto& v : m)
				max1 = max(max1, v.second);
			m.clear();
			ay = 1;
		}
		return max1;
	}
};
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

多重集合和映射

332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
1

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

思路：
通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。
通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的无向图称为欧拉图。
具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。

Hierholzer 算法用于在连通图中寻找欧拉路径，其流程如下：

1.从起点出发，进行深度优先搜索。
2.每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边，对下一个顶点继续深度优先。
3.如果没有可移动的路径，则将所在节点加入到答案中。
1
2
3

本题起点唯一

代码：

class Solution {
public:
	vector<string> findItinerary(vector<vector<string>>& tickets) {
		vector<string> ans;
		unordered_map<string, multiset<string>> hash;
		for (const auto& ticket : tickets) 
			hash[ticket[0]].insert(ticket[1]);
		stack<string> s;
		s.push("JFK");
		while (!s.empty()) {
			string next = s.top();
			if (hash[next].empty()) {
				ans.push_back(next);
				s.pop();
			}
			else {
				s.push(*hash[next].begin());
				hash[next].erase(hash[next].begin());
			}
		}
		reverse(ans.begin(), ans.end());
		return ans;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

前缀和与积分图

一维的前缀和，二维的积分图，都是把每个位置之前的一维线段或二维矩形预先存储，方便加速计算。如果需要对前缀和或积分图的值做寻址，则要存在哈希表里；如果要对每个位置记录前缀和或积分图的值，则可以储存到一维或二维数组里，也常常伴随着动态规划

303. 区域和检索 - 数组不可变

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
1
2

思路：
设置数组p[i]，长度与输入相同p[i]指到i为止的总和
代码：

class NumArray {
public:
	vector<int> acc;
	NumArray(vector<int>& nums) :acc(nums.size()+1,0){
        partial_sum(nums.begin(),nums.end(),acc.begin()+1);
	}
	int sumRange(int left, int right) {
		return acc[right+1] - acc[left];
	}
};

1
2
3
4
5
6
7
8
9
10
11

304. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
1

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
1
2

思路：
类似303，不一样的是创建二维数组，记录每一行的p[i]
代码：

class NumMatrix {
public:
	vector<vector<int>> acc;
	NumMatrix(vector<vector<int>>& matrix) :acc(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0)) {
		for (int i = 1; i < acc.size(); i++) {
			for (int j = 1; j < acc[0].size(); j++) 
				acc[i][j] = acc[i - 1][j] + acc[i][j - 1] - acc[i - 1][j - 1] + matrix[i - 1][j - 1];
		}
	}

	int sumRegion(int row1, int col1, int row2, int col2) {
		return acc[row2 + 1][col2 + 1] - acc[row2 + 1][col1] - acc[row1][col2 + 1] + acc[row1][col1];
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
思路：
设置一个数组，索引是前缀和，键是前缀和出现的次数，比如前缀和为4出现2次，那么前缀和为4+k时肯定和前缀和为4之间的区间满足条件，一共两个区间，加在总数上
具体：
代码：

class Solution {
public:
	int subarraySum(vector<int>& nums, int k) {
		unordered_map<int, int> m;
		int cnt = 0, sum = 0;
		for (int i = 0; i < nums.size(); i++) {
			sum += nums[i];
       if(m.count(sum - k))
				cnt += m[sum - k];
      	if (sum == k)//特殊情况
				cnt++;
			if (m.count(sum))//先计算cnt再变哈希表，防止k=0的时候多加一个自身
				m[sum]++;
			else
				m[sum] = 1;			
		}
		return cnt;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

练习

566. 重塑矩阵

在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。

给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。

如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

思路：
判断是否可行很简单，至于重塑，直接顺序输出
代码：

class Solution {
public:
	vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
		int m = mat.size(), n = mat[0].size(), i = 0, j = 0, o = 0, p = 0;
		if (r == m || r * c != m * n)
			return mat;
		vector<vector<int>> re(r, vector<int>(c, 0));
		while (i < m) {
			re[o][p] = mat[i][j];
			j++, p++;
			if (j >= n)
				j = 0, i++;
			if (p >= c)
				p = 0, o++;
		}
        return re;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
1
2
3
4

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
1
2

思路：
栈：顶入顶出
队列：尾入头出
设置两个队列in&out

代码：

class MyStack {
public:
	queue<int> q1, q2;
    MyStack() {

    }

    void push(int x) {
		q1.push(x);
    }

    int pop() {
		int re = top();
		q1.pop();
		while (!q2.empty()) {//q2到q1
			q1.push(q2.front());
			q2.pop();
		}
		return re;
    }

    int top() {
		while (q1.size() != 1) {//q1只留一个
			q2.push(q1.front());
			q1.pop();
		}
		return q1.front();
    }

    bool empty() {
		return q1.empty();//q1没了就是真没了
    }
};
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

503. 下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

思路：
栈，每次入栈（入的是下标）如果小于栈顶，入栈，否则一直出栈到小于栈顶或者栈空再入栈，出栈使当前入栈元素即是出栈元素的下一个最大值（关于循环：遍历两遍，第二遍不入栈，出栈时比较索引，若超出，返回-1）
代码：

class Solution {
public:
	vector<int> nextGreaterElements(vector<int>& nums) {
		int i = 1, n = nums.size();
		bool flag = true;
        stack<int> a;
		vector<int> re(n, -1);
        if(n == 1)
            return re;
		a.push(0);
		while (i != a.top()) {
			while (!a.empty() && nums[i] > nums[a.top()]) {
				re[a.top()] = nums[i];
				a.pop();
			}
			if(flag)
				a.push(i);
			if (++i == n)
				i = 0, flag = false;
		}
		return re;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

217. 存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

思路：
哈希
代码：

//先排后比
class Solution {
public:
	bool containsDuplicate(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		for (int i = 1; i < nums.size(); i++) {
			if (nums[i] == nums[i - 1])
				return true;
		}
		return false;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12

//哈希
class Solution {
public:
	bool containsDuplicate(vector<int>& nums) {
		unordered_set<int> a;
		for (int i = 0; i < nums.size(); i++) {
			if (a.count(nums[i]))
				return true;
			a.insert(nums[i]);
		}
		return false;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13

697. 数组的度

给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

思路：
每一个数映射到一个长度为 3 的数组，数组中的三个元素分别代表这个数出现的次数、这个数在原数组中第一次出现的位置和这个数在原数组中最后一次出现的位置。当我们记录完所有信息后，我们需要遍历该哈希表，找到元素出现次数最多，且前后位置差最小的数。
代码：

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, vector<int>> mp;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (mp.count(nums[i])) {
                mp[nums[i]][0]++;
                mp[nums[i]][2] = i;
            } else {
                mp[nums[i]] = {1, i, i};
            }
        }
        int maxNum = 0, minLen = 0;
        for (auto& [_, vec] : mp) {
            if (maxNum < vec[0]) {
                maxNum = vec[0];
                minLen = vec[2] - vec[1] + 1;
            } else if (maxNum == vec[0]) {
                if (minLen > vec[2] - vec[1] + 1) {
                    minLen = vec[2] - vec[1] + 1;
                }
            }
        }
        return minLen;
    }
};
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

594. 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
思路：
哈希

代码：

class Solution {
public:
	int findLHS(vector<int>& nums) {
		set<int> a;
		unordered_map<int, int> b;
		int max1 = 0, temp, last = INT_MIN;
		for (int i = 0; i < nums.size(); i++) {
			a.insert(nums[i]);
			if (b.count(nums[i]))
				b[nums[i]]++;
			else
				b[nums[i]] = 1;
		}
		for (auto it : a) {
			if (it - 1 == last)
				max1 = max(max1, b[it] + b[it - 1]);
			last = it;
		}
		return max1;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

思路：
Floyd 判圈算法
数组nums想象成一个链表，i指向nums[i]，因为数字都在 1 到 n 之间，索引在0到n之间，所以合法，而且因为nums[i]可能重复，就会导致多个点指向nums[i]，而因为每个点的出度必须为1（一维数组），而且除重复点外每个点入度最多为1（只有一个数重复），nums[i]指向的点则必然会最终回到指向nums[i] 的点，说明必然会出现环，而这个环的入口就是重复的这个nums[i]
代码：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

313. 超级丑数

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

思路：
保证从小到大：使用优先队列：

起始先将最小丑数 1 放入队列
每次从队列取出最小值 x，然后将 x 所对应的丑数 x∗primes[i]进行入队。
对步骤 2 循环多次，第 n 次出队的值即是答案。
1
2
3

为了防止同一丑数多次进队，我们需要使用数据结构 Set来记录入过队列的丑数。

代码：

870. 优势洗牌

给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列，使其相对于 B 的优势最大化。

示例 1：

输入：A = [2,7,11,15], B = [1,10,4,11]
输出：[2,11,7,15]

思路：
升序排序A做栈，遍历B的每一个数Bi，对于Bi，遇到的第一个A中比它大的，从A中排除，加入输出（哈希表记录删除）
代码：

307. 区域和检索 - 数组可修改

给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。

实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回子数组 nums[left, right] 的总和（即，nums[left] + nums[left + 1], ..., nums[right]）
1
2
3

思路：
update：改值后，其后的前缀和也修改相应差
sumRange：前缀和
代码：