lc513.栈循环
for (int i = 0; i < 2 * n; i++)
{
int current = nums[i % n];
//栈逻辑处理
if (i < n)
{
st.push(i);
}
} 循环栈即 模拟i＜2*n，跑两遍
错误写法
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums)
{
stack<int> st;
int n = nums.size(), mx = INT_MIN;
vector<int> ret(n, -1);
for (int i = 0; i < n; i++) {
mx = max(mx, nums[i]);
while (!st.empty() && nums[i] > nums[st.top()]) {
int t = st.top();
st.pop();
ret[t] = nums[i];
}
st.push(i);
}
while (!st.empty()) {
int t = st.top();
st.pop();
if (nums[t] != mx) {
ret[t] = mx;
}
}
return ret;
}
};
正确写法
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums)
{
stack<int> st;
int n = nums.size();
vector<int> ret(n, -1);
for (int i = 0; i < 2 * n; i++) {
int current = nums[i % n];
while (!st.empty() && current > nums[st.top()]) {
int topIdx = st.top();
st.pop();
ret[topIdx] = current;
}
if (i < n) {
st.push(i);
}
}
return ret;
}
};
lc168.数组转搜索树
l> r null
mid
root = new
-> l
-> r
return root
class Solution {
vector<int> nums;
int n=0;
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
n=nums.size();
this->nums=nums;
return dfs(0,n-1);
}
TreeNode* dfs(int l,int r)
{
if(l>r) return nullptr;
int mid=l+(r-l)/2;
TreeNode* root=new TreeNode(nums[mid]);
root->left=dfs(0,mid-1);
root->right=dfs(mid+1,n-1);
return root;
}
};
并查集
class UnionFind
{
public:
UnionFind(int n)
{
p = vector<int>(n);
size = vector<int>(n, 1);
iota(p.begin(), p.end(), 0);
}
bool unite(int a, int b)
{
int pa = find(a), pb = find(b);
if (pa == pb) {
return false;
}
if (size[pa] > size[pb]) {
p[pb] = pa;
size[pa] += size[pb];
} else {
p[pa] = pb;
size[pb] += size[pa];
}
return true;
}
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
bool connected(int a, int b)
{
return find(a) == find(b);
}
private:
vector<int> p, size;
};
lc1631.最小绝对差路径
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<array<int, 3>> edges;
int dirs[3] = {0, 1, 0};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < 2; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
edges.push_back({abs(heights[i][j] - heights[x][y]), i * n + j, x * n + y});
}
}
}
}
sort(edges.begin(), edges.end());
UnionFind uf(m * n);
for (auto& [h, a, b] : edges)
{
uf.unite(a, b);
if (uf.connected(0, m * n - 1))
{
return h;
}
}
return 0;
}
};
用「并查集」找「最小体力路径」：
1. 把地图变成一堆边
把每个格子看作一个点，计算相邻格子（右、下方向）的高度差，这些高度差就是「移动需要的体力」，记录成“边”（格式：体力值，起点，终点）。
2. 按体力从小到大排序边
先处理体力小的边，这样能优先用省力的方式连接格子。
3. 用并查集“拼”路径
用并查集把边对应的格子连起来，每连一条边就检查：左上角的格子（起点）和右下角的格子（终点）是否连通了。
一旦连通，当前用的这条边的体力值，就是答案——因为我们是从小到大处理的，这时候的体力肯定是最小的。
简单说就是：从小力气的路开始修，哪一刻起点和终点通了，这一刻用的力气就是最小的。
lcr168丑数
class Solution {
public:
int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int res[n];
res[0] = 1;
for(int i = 1; i < n; i++) {
int n2 = res[a] * 2, n3 = res[b] * 3, n5 = res[c] * 5;
res[i] = min(min(n2, n3), n5);
if (res[i] == n2) a++;
if (res[i] == n3) b++;
if (res[i] == n5) c++;
}
return res[n - 1];
}
};