LeetCode215.数组中第K个最大元素：
题目描述：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
思路：
题意：找出排序之后的数组中第k个最大的元素
要求时间复杂度为O(n), 二分的时间复杂度为log(n),肯定不行，考虑使用快选算法，因为这里要你选第k大的，而快速排序中，如果第一次排完之后知道要选的数在哪边，则只需要递归排一侧即可，那么时间复杂度计算为：n + n / 2 + n / 4 … 大概为O(2n),也是O(n)的复杂度。
注意：这里是求第k最大元素，也就是从后往前选k个，而快排是将小的排前面，所以这里需要将排的顺序调转一下。
时间复杂度：O(n)
注释代码：
class Solution {
public:
int quick_sort(vector<int>& nums, int l, int r, int k)
{
if(l >= r) return nums[k];
int x = nums[l], i = l - 1, j = r + 1;
while(i < j)
{
do i++; while(nums[i] > x);
do j--; while(nums[j] < x);
if(i < j) swap(nums[i], nums[j]);
}
//如果k是小于左半边的个数，那么只需要递归左边即可，反之如果大于就递归右边
if(k <= j) return quick_sort(nums, l, j, k);
else return quick_sort(nums, j + 1, r, k);
}
int findKthLargest(vector<int>& nums, int k) {
return quick_sort(nums, 0, nums.size() - 1, k -1); //这里第k大的元素，但是数组是从下标0开始的
}
};
纯享版：
class Solution {
public:
int quick_sort(vector<int>& nums, int l, int r, int k)
{
if(l >= r) return nums[k];
int x = nums[l], i = l - 1, j = r + 1;
while(i < j)
{
do i++; while(nums[i] > x);
do j--; while(nums[j] < x);
if(i < j) swap(nums[i], nums[j]);
}
if(k <= j) return quick_sort(nums, l, j, k);
else return quick_sort(nums, j + 1, r, k);
}
int findKthLargest(vector<int>& nums, int k) {
return quick_sort(nums, 0, nums.size() - 1, k - 1);
}
};
LeetCode216.组合总和Ⅲ：
题目描述：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 9
1 <= n <= 60
思路：
题意：从1~9中选k个数使它们之和为n，并且每个数只能选一次。
属于一种组合问题，也就是从19中选出k个数，使他们总和为n，可以有较多种选择，为了方便我们只从小往大选，例如当前选到start，如果start是小于n的话，那么从start9挨个选i作为当前第k个选的数往下搜， 下一层就是从当前选的数i的下一个数开始搜(i + 1)， n的话每次选当前数进入下一层则是以n -i作为总和去搜，k-1表示选择了一个数就减1，直到n刚好减为0， 并且k也刚好为0，说明刚好选了k个数使得它们和为n。
时间复杂度:
注释代码：
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum3(int k, int n) {
//从哪个数开始选，当前总和是多少， 选了几个数
dfs(1, n, k);
return res;
}
void dfs(int start, int n, int k)
{
if(!n) //如果n减为0，说明找到了这样一条路径
{
if(!k) res.push_back(path); ////如果k也减为0，说明选的路径刚好包含k个数
}else if(k) //如果k还未选满，则继续搜索
{
for(int i = start; i <= 9; i++) //从1~9升序选，当前选到start，往后选
{
if(n >= i)
{
path.push_back(i);
//以当前i作为路径的一个数继续搜
dfs(i + 1, n - i, k - 1);
path.pop_back(); //恢复现场
}
}
}
}
};
纯享版：
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum3(int k, int n) {
dfs(1, n, k);
return res;
}
void dfs(int start, int n, int k)
{
if(!n)
{
if(!k) res.push_back(path);
}else if(k)
{
for(int i = start; i <= 9; i++)
{
if(n >= i)
{
path.push_back(i);
dfs(i + 1, n - i, k - 1);
path.pop_back();
}
}
}
}
};
LeetCode217.存在重复元素：
题目描述：
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1]
输出：true
解释：
元素 1 在下标 0 和 3 出现。
示例 2：
输入：nums = [1,2,3,4]
输出：false
解释：
所有元素都不同。
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
提示：
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
hash表判重：
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> S;
for(auto x : nums)
{
if(S.count(x)) return true;
else S.insert(x);
}
return false;
}
};
hash表计数：
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++)
{
hash[nums[i]]++;
if(hash[nums[i]]!= 1) return true;
}
return false;
}
};
LeetCode218.天际线问题：
题目描述：
城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。
每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：
lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。
你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。
天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],…] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
注意：输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]
示例 1：
输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：
图 A 显示输入的所有建筑物的位置和高度，
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。
示例 2：
输入：buildings = [[0,2,3],[2,5,3]]
输出：[[0,3],[5,0]]
提示：
1 <= buildings.length <= 104
0 <= lefti < righti <= 231 - 1
1 <= heighti <= 231 - 1
buildings 按 lefti 非递减排序
思路：
时间复杂度：O(nlogn)
注释代码：
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<vector<int>> res;
vector<pair<int, int>> points; //存每一个端点
multiset<int> heights; //用于存当前段内的高度
for(auto& b : buildings)
{
//对于左端点来说，如果横坐标相同则需要将较大的排在前面先插入，高度变成负的，在sort时会将高度最大的(负的最小)排序在前面
points.push_back({b[0], -b[2]});
//对于右端点来说，如果横坐标相同则需要将较小的排在前面先插入高度进行比较
points.push_back({b[1], b[2]});
}
sort(points.begin(), points.end()); //将所有点排序一遍
heights.insert(0); //x轴也需要看成轮廓的一部分
for(auto& p : points)
{
int x = p.first, h = abs(p.second);
if(p.second < 0) //左端点
{
//如果当前左端点的高度是大于目前高度中的最大值，则说明当前端点会成为轮廓中的一部分
if(h > *heights.rbegin())
{
res.push_back({x, h});
}
heights.insert(h); //当前是左端点，要将高度加入
}else{ //右端点
heights.erase(heights.find(p.second)); //碰到右端点将属于右端点的那个高度删除
//这样后面开始比较时就不会将前面的高度比进去
//将当前右端点属于的高度删除之后，如果当前端点的高度还是剩余高度中最大值，说明当前端点下的最高高度也是轮廓的一部分
if(h > *heights.rbegin())
{
res.push_back({x, *heights.rbegin()}); //插入当前右端点和删除最大高度之后的最大高度
}
}
}
return res;
}
};
纯享版：
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<vector<int>> res;
vector<pair<int, int>> points;
multiset<int> heights;
for(auto& b : buildings)
{
points.push_back({b[0], -b[2]});
points.push_back({b[1], b[2]});
}
sort(points.begin(), points.end()); //给点排序
heights.insert(0); //x轴也算
for(auto p : points)
{
int x = p.first, h = abs(p.second);
if(p.second < 0) //左端点
{
if(h > *heights.rbegin())
{
res.push_back({x, h});
}
heights.insert(h);
}else{ //右端点
heights.erase(heights.find(p.second)); //
if(h > *heights.rbegin())
{
res.push_back({x, *heights.rbegin()});
}
}
}
return res;
}
};
LeetCode219.存在重复元素Ⅱ：
题目描述：
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true
示例 3：
输入：nums = [1,2,3,1,2,3], k = 2
输出：false
提示：
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5
思路：
题意：找到数组中两个相同的元素，判断它们的下标差是否小于等于k
要找相同元素的下标差，那么从开始往后找，如果存在相同元素，肯定找离当前元素最近的相同元素，那么对于多个相同的元素，我们使用hash表存相同元素的离当前最近的下标
时间复杂度：O(n)
注释代码：
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int, int> hash;
for(int i = 0; i < n; i++)
{
int x = nums[i];
//如果当前已经存在x了，那么看下标是否和最近的x的下标差满足k
if(hash.count(x) && i - hash[x] <= k) return true;
hash[x] = i; //将hash表中相同元素的下标存成最近的元素下标
}
return false;
}
};
纯享版：
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++)
{
int x = nums[i];
if(hash.count(x) && i - hash[x] <= k) return true;
hash[x] = i;
}
return false;
}
};
LeetCode220.存在重复元素Ⅲ：
题目描述：
给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。
找出满足下述条件的下标对 (i, j)：
i != j,
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff
如果存在，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
输出：true
解释：可以找出 (i, j) = (0, 3) 。
满足下述 3 个条件：
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0
示例 2：
输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
输出：false
解释：尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。
提示：
2 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
1 <= indexDiff <= nums.length
0 <= valueDiff <= 10^9
思路：
题意：需要在数组中找到两个元素(下标不一样)，满足下标之差小于等于k， 数值之差小于等于t
使用一个类似滑动窗口，记录满足与当前下标之差满足小于等于k的，每次使用lower_bound找到比当前元素稍微大一点的(大于当前元素的最小元素)，看他是否满足和当前x的差值是小于等于t的，如果不是，再找比当前元素稍微小一点的(小于当前元素的最大元素),看二者差值是否小于等于t，同时将当前元素插入滑动窗口
时间复杂度：O(nlogn)
注释代码：
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
typedef long long LL;
multiset<LL> S; //维护下标距离为k的元素
S.insert(1e18), S.insert(-1e18); //插入哨兵
for(int i = 0, j = 0; i < nums.size(); i++)
{
//如果当前元素下标差超过k则将最前面的元素移除
if(i - j > k) S.erase(S.find(nums[j++]));
int x = nums[i];
auto it = S.lower_bound(x); //找到比x大的最小的数
//如果这个数 - 当前元素满足条件则为true
if(*it - x <= t) return true;
--it; //找到小于x的最大数
if(x - *it <= t) return true;
//最后将x插入S中
S.insert(x);
}
return false;
}
};
纯享版：
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
typedef long long LL;
multiset<LL> S;
S.insert(1e8), S.insert(-1e8);
for(int i = 0, j = 0; i < nums.size(); i++)
{
auto x = nums[i];
if(i - j > k) S.erase(S.find(nums[j++]));
auto it = S.lower_bound(x);
if(*it - x <= t) return true;
--it;
if(x - *it <= t) return true;
S.insert(x);
}
return false;
}
};
LeetCode221.最大正方形：
题目描述：
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：4
示例 2：
输入：matrix = [[“0”,“1”],[“1”,“0”]]
输出：1
示例 3：
输入：matrix = [[“0”]]
输出：0
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’
思路：
动态规划： 使用状态集合f[i][j]表示以当前(i,j)点为右下顶点的全为1的正方形的最大边长
下面开始搬运别人的解释：
时间复杂度：
注释代码：
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.empty() || matrix[0].empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> f(n + 1, vector<int>(m + 1));
int res = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(matrix[i - 1][j - 1] == '1')
{
f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
res = max(res, f[i][j]);
}
}
}
return res * res; //返回面积
}
};
纯享版：
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.empty() || matrix[0].empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> f(n + 1, vector<int> (m + 1));
int res = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(matrix[i - 1][j - 1] == '1')
{
f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
res = max(res, f[i][j]);
}
}
}
return res * res;
}
};
LeetCode222.完全二叉树的节点个数：
题目描述：
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
提示：
树中节点的数目范围是[0, 5 * 10^4]
0 <= Node.val <= 5 * 10^4
题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
##O(n)做法：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
int res = 0, right = 0, left = 0;
if(!root) return res;
if(root -> right) right = countNodes(root -> right);
if(root -> left) left = countNodes(root -> left);
res = right + left + 1;
return res;
}
};
思路：
这里需要提高算法效率，普通O(n)做法不能满足
如何提高算法效率？
对于一个二叉树来说，完全二叉树是指左右子树的层数可以不一致，但是必须多的层数在左边
时间复杂度：O(logn*logn)
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
if(!root) return 0;
auto l = root -> left, r = root -> right;
int x = 1, y = 1;
while(l) l = l -> left, x++;
while(r) r = r ->right, y++;
//如果左右子树的层数是一样的， 说明该root节点下的是满二叉树
//直接返回满二叉树的节点数即可
if(x == y) return (1 << x) - 1;
//否则的话就正常计算节点数
return countNodes(root -> left) + countNodes(root -> right) + 1;
}
};
LeetCode223.矩形面积：
题目描述：
给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形，请你计算并返回两个矩形覆盖的总面积。
每个矩形由其 左下 顶点和 右上 顶点坐标表示：
第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。
示例 1：
Rectangle Area
输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45
示例 2：
输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
输出：16
提示：
-10^4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4
思路：
题意:一个矩形由左下角的坐标和右上角的坐标两个点确定，现在给出两个矩形，可能重叠可能不重叠，要你求两个矩形围成的面积(重叠的只能算一次)
现在的问题就是如何确定两个矩形重叠的面积，我们可以将两个矩形水平方向的边长映射到X坐标轴上，将二维问题转化成一维。如图：
这样就可以确定他们重叠的一条边长，同理将竖直方向上的边长映射到Y坐标轴上就可以确定另外一条边长，二者相乘就是两个矩形重叠的面积。
什么？如果有一条边长不重叠怎么办，我们只计算两条线段重叠的长度，如果不重叠则为0，那么该面积为0。
那么问题转移成为如何求两条线段重叠长度：
时间复杂度：O(1)
注释代码：
class Solution {
public:
typedef long long LL;
int computeArea(LL A, LL B, LL C, LL D, LL E, LL F, LL G, LL H) {
LL X = max(0ll, min(C, G) - max(A, E));
LL Y = max(0ll, min(D, H) - max(B, F));
return (C - A) * (D - B) + (G - E) * (H- F) - X * Y;
}
};
纯享版：
class Solution {
public:
typedef long long LL;
int computeArea(LL ax1, LL ay1, LL ax2, LL ay2, LL bx1, LL by1, LL bx2, LL by2) {
LL X = max(0ll, min(ax2, bx2) - max(ax1, bx1));
LL Y = max(0ll, min(ay2, by2) - max(ay1, by1));
return (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1) - X * Y;
}
};
LeetCode225.用队列实现栈：
题目描述：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空
进阶：你能否仅用一个队列来实现栈。
思路：
题意：需要用队列来实现栈的各种操作，考察栈和队列的理解
时间复杂度：O(n)
注释代码：
class MyStack {
public:
queue<int> q, w; //第一个队列存所有数，第二个队列用于缓存第一个队列队尾（栈顶）下面的元素
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
while(q.size() > 1) w.push(q.front()), q.pop(); //将第一个队列的前i-1个缓存到第二个队列中
int x = q.front(); //获取q的队头(之前的队尾)
q.pop(); //将q的队头弹掉
while(w.size()) q.push(w.front()), w.pop(); //将第二个队列的i-1个数重新下载回来
return x; //返回栈顶(队头)
}
int top() {
while(q.size() > 1) w.push(q.front()), q.pop();
int x = q.front();
q.pop();
while(w.size()) q.push(w.front()), w.pop();
q.push(x);
return x;
}
bool empty() {
return q.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
纯享版：
class MyStack {
public:
queue<int> q, w;
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
while(q.size() > 1) w.push(q.front()), q.pop();
int x = q.front();
q.pop();
while(w.size()) q.push(w.front()), w.pop();
return x;
}
int top() {
while(q.size() > 1) w.push(q.front()), q.pop();
int x = q.front();
q.pop();
while(w.size()) q.push(w.front()), w.pop();
q.push(x);
return x;
}
bool empty() {
return q.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
一个队列：
class MyStack {
public:
queue<int> q;
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
int sz = q.size();
while(sz-- > 1) q.push(q.front()), q.pop();
int x = q.front();
q.pop();
return x;
}
int top() {
int sz = q.size();
while(sz-- > 1) q.push(q.front()), q.pop();
int x = q.front();
q.pop();
q.push(x);
return x;
}
bool empty() {
return q.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
LeetCode226.翻转二叉树：
题目描述：
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
思路:
时间复杂度：O(n)
注释代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return NULL;
swap(root -> right, root -> left); //交换当前节点下的两个儿子
invertTree(root -> right); //递归交换左子树和右子树
invertTree(root -> left);
return root;
}
};
纯享版：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return NULL;
swap(root -> right, root -> left);
invertTree(root -> right);
invertTree(root -> left);
return root;
}
};
LeetCode227.基本计算器Ⅱ：
题目描述：
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = “3+2*2”
输出：7
示例 2：
输入：s = " 3/2 "
输出：1
示例 3：
输入：s = " 3+5 / 2 "
输出：5
提示：
1 <= s.length <= 3 * 10^5
s 由整数和算符 (‘+’, ‘-’, ‘*’, ‘/’) 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
题目数据保证答案是一个 32-bit 整数
思路：
跟 LeetCode224.基本计算器 是一致的思路，这类题的模板都是一样的，如图：
这里不同的是这里需要判断运算符的优先级，如果当前符号栈顶的运算符优先级大于当前碰到的运算符优先级，那么应该先算栈顶运算符。
如何判断运算符的优先级，这里* 和/ 是优先于+ 和-的， 那么使用hashmap，直接对应当前符号的优先级，pr['*'] = pr['*'] = 2 pr['+'] = pr['-'] = 1
这样碰到运算符时只需要判断跟当前符号栈顶的运算符的优先级，即可判断当前是应该先将栈顶的运算符计算掉还是先将当前运算符存下来。
时间复杂度：O(n)
注释代码：
class Solution {
public:
stack<int> num;
stack<char> op;
void eval()
{
auto b = num.top(); num.pop();
auto a = num.top(); num.pop();
auto c = op.top(); op.pop();
int r;
if(c == '+') r = a + b;
else if(c == '-') r = a - b;
else if(c == '*') r = a * b;
else if(c == '/') r = a/ b;
num.push(r);
}
int calculate(string s) {
unordered_map<char, int> pr; //使用hash表来映射运算符的优先级
pr['*'] = pr['/'] = 2, pr['-'] = pr['+'] = 1; //记录运算符的优先级
for(int i = 0; i < s.size(); i++)
{
auto c = s[i];
if(c == ' ') continue;
if(isdigit(c))
{
int x = 0, j = i;
while(j < s.size() && isdigit(s[j])) x = x * 10 + (s[j++] - '0');
num.push(x);
i = j - 1;
}else{
//否则就是运算符
//看栈顶的运算符和当前运算符的优先级，如果栈顶优先级高，则先计算栈顶
while(op.size() && pr[op.top()] >= pr[c]) eval();
op.push(c); //将当前运算符加入栈中
}
}
while(op.size()) eval();
return num.top();
}
};
纯享版：
class Solution {
public:
stack<int> nums;
stack<char> op;
void eval()
{
auto b = nums.top(); nums.pop();
auto a = nums.top(); nums.pop();
auto c = op.top(); op.pop();
int res;
if(c == '+') res = a + b;
else if(c == '-') res = a - b;
else if(c == '*') res = a * b;
else if(c == '/') res = a / b;
nums.push(res);
}
int calculate(string s) {
unordered_map<char, int> pr;
pr['*'] = pr['/'] = 2, pr['+'] = pr['-'] = 1;
for(int i = 0; i < s.size(); i++)
{
auto c = s[i];
if(c == ' ') continue;
if(isdigit(c))
{
int x = 0, j = i;
while(j < s.size() && isdigit(s[j])) x = x * 10 + (s[j++] - '0');
nums.push(x);
i = j - 1;
}else{
while(op.size() && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
while(op.size()) eval();
return nums.top();
}
};
LeetCode228.汇总区间：
题目描述：
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
“a->b” ，如果 a != b
“a” ，如果 a == b
示例 1：
输入：nums = [0,1,2,4,5,7]
输出：[“0->2”,“4->5”,“7”]
解释：区间范围是：
[0,2] --> “0->2”
[4,5] --> “4->5”
[7,7] --> “7”
示例 2：
输入：nums = [0,2,3,4,6,8,9]
输出：[“0”,“2->4”,“6”,“8->9”]
解释：区间范围是：
[0,0] --> “0”
[2,4] --> “2->4”
[6,6] --> “6”
[8,9] --> “8->9”
提示：
0 <= nums.length <= 20
-2^31 <= nums[i] <= 2^31 - 1
nums 中的所有值都 互不相同
nums 按升序排列
思路：
题意：将给出升序数组中的连续元素并成单独的小区间，比如： 0 1 2 3 4： 0 -> 4,单独一个数则单独记。
自己的做题情况：题目简单，思路没问题，但是细节双指针的细节还是没把握好，而且还忘记了整数转字符to_string，搞得转个字符转半天。
时间复杂度：O(n)
注释代码：
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> res;
for(int i = 0; i < nums.size(); i++)
{
int j = i + 1;
while(j < nums.size() && nums[j] == nums[j - 1] + 1) j++;
if(j == i + 1) res.push_back(to_string(nums[i])); //只有一个数就直接push_back
else res.push_back(to_string(nums[i]) + "->" + to_string(nums[j - 1]));
i = j - 1;
}
return res;
}
};
纯享版：
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> res;
for(int i = 0; i < nums.size(); i++)
{
int j = i + 1;
while(j < nums.size() && nums[j] == nums[j - 1] + 1) j++;
if(j == i + 1) res.push_back(to_string(nums[i]));
else res.push_back(to_string(nums[i]) + "->" + to_string(nums[j - 1]));
i = j - 1;
}
return res;
}
};
LeetCode229.求众数Ⅱ：
题目描述：
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：nums = [3,2,3]
输出：[3]
示例 2：
输入：nums = [1]
输出：[1]
示例 3：
输入：nums = [1,2]
输出：[1,2]
提示：
1 <= nums.length <= 5 * 10^4
-10^9 <= nums[i] <= 10^9
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
思路：
题意：找出数组中出现次数超过n / 3下取整次数的数
跟之前一题找到出现次数超过n/2下取整次数的数类似。这类题目可以统一使用摩尔投票法来解决。
该做法也可以扩展成求出现次数超过n / k下取整的数：开k - 1个仓库
时间复杂度：O(n)
空间复杂度：O(1)
注释代码：
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
//r1和r2表示仓库，c1和c2表示仓库存的数
int r1, r2, c1 = 0, c2 = 0;
for(auto x : nums)
{
if(c1 && x == r1) c1++; //如果跟仓库1的数一致，则存入仓库1
else if(c2 && x == r2) c2++;
else if(!c1) r1 = x, c1++; //如果仓库1是空的则存入仓库1
else if(!c2) r2 = x, c2++;
else c1--, c2--; //如果既不跟仓库1的数一致，也不跟仓库2的数一致，则从两个仓库各拿一个出来抵消
}
c1 = 0, c2 = 0; //清空仓库
for(auto x : nums)
{
//重新统计两个仓库中的数量
if(x == r1) c1++;
else if(x == r2) c2++;
}
vector<int> res;
int n = nums.size();
//如果仓库1的数量大于n/3则是正确的
if(c1 > n / 3) res.push_back(r1);
if(c2 > n / 3) res.push_back(r2);
return res;
}
};
纯享版：
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int r1, r2, c1 = 0, c2 = 0;
for(auto x : nums)
{
if(c1 && x == r1) c1++;
else if(c2 && x == r2) c2++;
else if(!c1) r1 = x, c1++;
else if(!c2) r2 = x, c2++;
else c1--, c2--;
}
c1 = 0, c2 = 0;
for(auto x : nums)
{
if(x == r1) c1++;
else if(x == r2) c2++;
}
vector<int> res;
int n = nums.size();
if(c1 > n / 3) res.push_back(r1);
if(c2 > n / 3) res.push_back(r2);
return res;
}
};
LeetCode230.二叉搜索树中第K小的元素：
题目描述：
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
提示：
树中的节点数为 n 。
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
思路：
题意找到二叉搜索数排序之后第k个值
二叉搜索树的中序遍历是有序的，所以也就是让我们返回二叉搜索树的中序遍历的第k个数。
时间复杂度：O(k)
注释代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int k, res;
int kthSmallest(TreeNode* root, int _k) {
k = _k;
dfs(root);
return res;
}
bool dfs(TreeNode* root)
{
if(!root) return false;
if(dfs(root -> left)) return true; //如果左子树能找到第k个数则直接返回true
if(--k == 0) //每找一个点k减1
{
res = root -> val; //当k减为0时即是中序遍历的第k个数
return true;
}
return dfs(root -> right); //再遍历右子树
}
};
纯享版：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int res = 0, k;
int kthSmallest(TreeNode* root, int _k) {
k = _k;
dfs(root);
return res;
}
bool dfs(TreeNode* root)
{
if(!root) return false;
if(dfs(root -> left)) return true;
if(--k == 0)
{
res = root -> val;
return true;
}
dfs(root -> right);
return false;
}
};
LeetCode231.2的幂：
题目描述：
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1
输出：true
解释：20 = 1
示例 2：
输入：n = 16
输出：true
解释：24 = 16
示例 3：
输入：n = 3
输出：false
提示：
-2^31 <= n <= 2^31 - 1
进阶：你能够不使用循环/递归解决此问题吗？
思路：lowbit函数！！
时间复杂度：O(1)
代码：
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & -n) == n;
}
};
LeetCode232.用栈实现队列：
题目描述：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
思路：
跟用队列实现栈一样的思路，就是多开一个栈实现缓存功能。
代码：
class MyQueue {
public:
stack<int> stk1, stk2;
MyQueue() {
}
void push(int x) {
stk1.push(x);
}
int pop() {
while(stk1.size() > 1)
{
stk2.push(stk1.top());
stk1.pop();
}
int x = stk1.top();
stk1.pop();
while(stk2.size())
{
stk1.push(stk2.top());
stk2.pop();
}
return x;
}
int peek() {
while(stk1.size() > 1)
{
stk2.push(stk1.top());
stk1.pop();
}
int x = stk1.top();
while(stk2.size())
{
stk1.push(stk2.top());
stk2.pop();
}
return x;
}
bool empty() {
return stk1.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
纯享版：
class MyQueue {
public:
stack<int> stk1, stk2;
MyQueue() {
}
void push(int x) {
stk1.push(x);
}
int pop() {
while(stk1.size() > 1)
{
stk2.push(stk1.top()), stk1.pop();
}
int t = stk1.top();
stk1.pop();
while(stk2.size()) stk1.push(stk2.top()), stk2.pop();
return t;
}
int peek() {
while(stk1.size() > 1)
{
stk2.push(stk1.top()), stk1.pop();
}
int t = stk1.top();
while(stk2.size()) stk1.push(stk2.top()), stk2.pop();
return t;
}
bool empty() {
return stk1.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
LeetCode233.数字1的个数：
题目描述：
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13
输出：6
示例 2：
输入：n = 0
输出：0
提示：
0 <= n <= 10^9
思路：
依次枚举n的每一位，对每一位上可能出现1的次数进行讨论：
时间复杂度：
注释代码：
class Solution {
public:
int countDigitOne(int n) {
vector<int> nums;
while(n) nums.push_back(n % 10), n /= 10;
reverse(nums.begin(), nums.end());
int res = 0;
for(int i = 0; i < nums.size(); i++)
{
int d = nums[i];
int left = 0, right = 0, p = 1;
for(int j = 0; j < i; j++) left = left * 10 + nums[j];
for(int j = i + 1; j < nums.size(); j++)
{
right = right * 10 + nums[j];
p *= 10;
}
if(d == 0) res += left * p; //n当前位置上如果是0，那么我们要求当前位置上可能出现1的次数，也就是前面
else if(d == 1) res += left * p + right + 1;
else res += (left + 1) * p;
}
return res;
}
};
纯享版：
class Solution {
public:
int countDigitOne(int n) {
vector<int> nums;
while(n)
{
nums.push_back(n % 10), n /= 10;
}
reverse(nums.begin(), nums.end());
int res = 0;
for(int i = 0; i < nums.size(); i++)
{
int d = nums[i];
int left = 0, right = 0, p = 1;
for(int j = 0; j < i; j++) left = left * 10 + nums[j];
for(int j = i + 1; j < nums.size(); j++)
{
right = right * 10 + nums[j];
p *= 10;
}
if(d == 0) res += left * p;
else if(d == 1) res += left * p + right + 1;
else res += (left + 1) * p;
}
return res;
}
};
LeetCode234.回文链表：
题目描述：
给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表
。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 10^5] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路：
判断回文链表最重要的是如何从两边往中间开始判断
这里将后半段先翻转一下，也就是从第n - n / 2下取整开始将链表进行翻转，然后从两头开始对比节点值
这里主要的注意点就是需要注意边界条件以及翻转的次数，防止丢失造成空指针
时间复杂度：O(n)
注释代码：
/**
* Definition for singly-linked list.
* 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 {
public:
bool isPalindrome(ListNode* head) {
int n = 0;
for(auto p = head; p; p = p -> next) n++; //统计链表长度
if(n <= 1) return true;
int half = n / 2;
auto a = head;
for(int i = 0; i < n - half; i++) a = a -> next; //先走到后半段开始位置
auto b = a -> next;
for(int i = 0; i < half - 1; i++) //翻转
{
auto c = b -> next;
b -> next = a;
a = b, b = c;
}
bool flag = true;
auto p = head, q = a;
for(int i = 0; i < half; i++) //对比
{
if(p -> val != q -> val)
{
flag = false;
break;
}
p = p -> next;
q = q -> next;
}
auto tail = a;
b = a -> next;
for(int i = 0; i < half - 1; i++) //恢复
{
auto c = b -> next;
b -> next = a;
a = b, b = c;
}
tail -> next = NULL;
return flag;
}
};
纯享版：
/**
* Definition for singly-linked list.
* 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 {
public:
bool isPalindrome(ListNode* head) {
int n = 0;
for(auto p = head; p; p = p -> next) n++;
if(n <= 1) return true;
int half = n / 2;
auto a = head;
for(int i = 0; i < n - half; i++) a = a -> next;
auto b = a -> next;
for(int i = 0; i < half - 1; i++)
{
auto c = b -> next;
b -> next = a;
a = b, b = c;
}
auto p = head, q = a;
bool flag = true;
for(int i = 0; i < half; i++)
{
if(p -> val != q -> val)
{
flag = false;
break;
}
p = p -> next;
q = q -> next;
}
auto tail = a;
b = a -> next;
for(int i = 0; i < half - 1; i++)
{
auto c = b -> next;
b -> next = a;
a = b, b = c;
}
tail -> next = NULL;
return flag;
}
};