当前位置：首页 > news >正文

5.25 note

news 2025/5/28 0:27:46

from vs join

from 的隐式关联两表
join的话可以避免代码膨胀

类比理解：

having vs where

- WHERE：先过滤原始数据（比如先排除无关比赛）。

- HAVING：再过滤分组后的结果（比如只看拿过冠军的球员）。

select

player_id,

player_name,

sum(wimbledon = player_id) + sum(Fr_open = player_id) + sum(US_open = player_id) + sum(Au_open = player_id) as grand_slams_count

from

Players p, Championships c

group by

player_id

having

grand_slams_count > 0

语句功能

统计至少拿过 1 次大满贯（温网、法网、美网、澳网）的球员信息，包括球员 ID、姓名及其大满贯总数。

语句拆解

1. 表与别名

- Players p ：球员表，别名 p （存储球员 ID 和姓名）。

- Championships c ：赛事表，别名 c （存储 4 项大满贯的冠军 ID）。

2. SELECT 字段

- player_id, player_name ：直接从球员表获取球员 ID 和姓名。

- 大满贯总数计算：

sum(wimbledon = player_id) +

sum(Fr_open = player_id) +

sum(US_open = player_id) +

sum(Au_open = player_id)

- 每个 sum(赛事冠军 = 球员 ID) ：

- 若球员 ID 等于某赛事冠军 ID，赛事冠军 = 球员 ID 为 1 ，否则为 0 。

- sum 统计该球员在该赛事中的夺冠次数（可能为 0 或 1 ，假设同一赛事同一球员最多夺冠 1 次）。

- 最终结果：4 项赛事夺冠次数之和，即该球员的大满贯总数。

3. GROUP BY player_id

- 按 player_id 分组，确保每个球员的信息和数据被聚合统计。

4. HAVING grand_slams_count > 0

- 筛选条件：仅保留大满贯总数大于 0 的球员（即至少拿过 1 次大满贯的球员）。

执行逻辑

1. 关联表： Players 和 Championships 表隐式关联（未用 JOIN 语法，需注意数据准确性）。

2. 分组统计：按球员分组，计算每人的大满贯总数。

3. 结果过滤：排除未拿过任何大满贯的球员，仅显示有夺冠记录的球员。

注意：实际开发中建议用显式 JOIN (可以避免膨胀) 替代隐式关联（如 FROM Players p JOIN Championships c ON ... ），避免笛卡尔积问题。

review 窗口函数

select sale_date, sold_num-ld as diff
from (
select sale_date,
fruit,
sold_num,
lead(sold_num)over(partition by sale_date order by fruit) as ld
from Sales
) a
where fruit = 'apples'

窗口函数计算苹果销量的环比差值

子查询逻辑（ from 内）：

- 表： Sales （销售表，含日期、水果、销量）

- 窗口函数：

lead(sold_num) over(partition by sale_date order by fruit)

- 按日期分组（ partition by sale_date ），同一日期内

- 按水果排序（ order by fruit ），取当前行下一行的 sold_num 作为 ld （下一行销量）

主查询逻辑：

- 筛选 fruit='apples' 的行

- 计算 sold_num - ld ：

当前苹果销量与下一行苹果销量的差值（需注意：若同一日期内苹果是最后一个水果， ld 为 null ，差值也为 null ）

示例场景：

若某天销售记录为：

sale_date fruit sold_num

2025-05-25 apples 100

2025-05-25 oranges 80

则苹果的 ld 是 oranges 的销量 80 ，差值为 100-80=20 。

sql 计算学生总分的分差

select max(assignment1+assignment2+assignment3)-
min(assignment1+assignment2+assignment3)
difference_in_score

from
Scores

功能：

计算 Scores 表中所有学生的 assignment1+assignment2+assignment3 总分的最大值与最小值之差，即分差。

关键部分：

1. max(总分) ：求总分最大值

2. min(总分) ：求总分最小值

3. difference_in_score ：给计算结果取别名（列名）

示例结果：

若总分最大值为 280，最小值为 180，则结果为 100 ，列名为 difference_in_score 。

可见山的数量- 单调栈

区间

按左边界排序，仅通过一次遍历找“首个更大右边界”，假设后续区间不会遮挡前面已处理的区间

class Solution {

public:

int visibleMountains(vector<vector<int>>& peaks) {

vector<pair<int,int>> vec;

for(auto const& v : peaks) {

int x = v[0], y = v[1];

int st = x-y, ed = x+y;

vec.emplace_back(st,ed);

}

sort(vec.begin(), vec.end(), [](pair<int,int> p1, pair<int,int> p2) {

if(p1.first == p2.first)

return p1.second > p2.second;

return p1.first < p2.first;

});

// for(auto [x,y] : vec)

// cout << x << "," << y << " ";

// cout << endl;

int ret = 0;

for(int i=0; i<vec.size();) {

auto [x,y] = vec[i];

bool dick = 0;

int j;

for(j=i+1; j<vec.size(); ++j) {

auto [x1,y1] = vec[j];

if(y1 > y) break;

else if(y1 == y && x1 == x)

dick = 1;

}

if(!dick)

++ ret;

i = j;

}

return ret;

}

};

借助栈

class Solution {
public:
int visibleMountains(vector<vector<int>>& peaks) {
int n = peaks.size();
sort(peaks.begin(), peaks.end(), [&](const vector<int>& p1, const vector<int>& p2){
return p1[0] == p2[0] ? p1[1] > p2[1] : p1[0] < p2[0];
});

stack<pair<int,int>> stk;
stk.emplace(0, 0);
for(int i=1; i<n; ++i){
// 重复情况标记区间
if(!stk.empty() && peaks[i][0] == peaks[stk.top().first][0] && peaks[i][1] == peaks[stk.top().first][1]){
stk.top().second |= 1;
}

// 被栈顶区间包含
if(!stk.empty() && peaks[i][1] <= peaks[stk.top().first][1] - (peaks[i][0] - peaks[stk.top().first][0])){
continue;
}

// 包含栈顶区间
while(!stk.empty() && peaks[i][1] >= peaks[stk.top().first][1] + (peaks[i][0] - peaks[stk.top().first][0])){
stk.pop();
}

// 入栈
stk.emplace(i, 0);
}
int ans = 0;
while(!stk.empty()){
// 仅统计非重复的山
if(stk.top().second == 0){
ans++;
}
stk.pop();
}
return ans;
}
};

排序➕栈

1. 输入与排序

- 输入：每个山峰用坐标 [x, h] 表示（x 是位置，h 是高度）。

- 排序规则：

- 先按 x 从小到大排（左边的山在前）。

- x 相同时，按 h 从大到小排（同一位置，高的山优先）。

2. 用栈处理可见性

- 栈：保存可能可见的山峰，每个元素记录 (山峰索引, 是否重复标记) 。

- 遍历逻辑：

- 重复山峰：若当前山与栈顶山坐标完全相同，标记为重复（避免重复计数）。

- 被遮挡判断：

若当前山的高度 h_i 小于等于栈顶山的“右侧遮挡高度”（ h_top - (x_i - x_top) ），说明被栈顶山完全遮挡，跳过。

- 反向遮挡处理：

若当前山比栈顶山更高且更“宽”（ h_i >= h_top + (x_i - x_top) ），则栈顶山会被当前山完全遮挡，弹出栈顶，直到栈顶山不被当前山遮挡。

- 入栈：处理完遮挡关系后，将当前山入栈。

3. 统计结果

- 遍历结束后，栈中剩下的元素都是未被完全遮挡的山峰。

- 忽略被标记为重复的山峰，统计剩余数量即为可见山峰数。

举个🌰：

假设有山峰 [(1,3), (2,4), (3,2), (3,4)] ：

- 排序后： [(1,3), (2,4), (3,4), (3,2)] （同一 x=3 时，4>2）。

- 处理过程：

- 栈初始为 [(0,0)] （索引0是(1,3)）。

- 处理(2,4)：比栈顶(1,3)高且宽，弹出栈顶，入栈(1,0)，可见数+1。

- 处理(3,4)：与栈顶(2,4)同x，标记为重复（栈顶变为(1,1)）。

- 处理(3,2)：被栈顶(3,4)遮挡，跳过。

- 最终栈中有效元素为(1,0)和(3,1)，但重复标记的不算，所以可见数为 1（即(2,4)）。

总结：

代码通过排序和栈结构，依次处理每个山峰是否被之前的高山遮挡，最终统计未被遮挡且不重复的山峰数量，核心是利用几何关系判断遮挡逻辑。

我们先把每个山峰想象成一个等腰三角形（左右两侧坡度相同），山峰的可见性取决于是否被其他三角形完全遮挡。

核心几何逻辑围绕三角形的斜边展开，栈用来维护当前未被遮挡的山峰序列，下面逐步拆解：

一、为什么用栈？

栈的特性是后进先出，适合处理“嵌套遮挡”关系：

- 后处理的山峰（x更大）可能遮挡前面的山峰，需要从栈顶（最近的山峰）开始判断遮挡关系。
- 栈中始终保存从左到右，未被完全遮挡的山峰，且它们的右侧斜边不会被后续山峰覆盖。

二、关键几何判断：如何确定遮挡？

每个山峰 (x, h) 的左右两侧斜边方程为：

- 左侧斜边：从山脚左侧延伸，斜率为 +1 （左移1单位，高度降1）。
- 右侧斜边：从山脚右侧延伸，斜率为 -1 （右移1单位，高度降1）。

判断A是否遮挡B的条件：
假设山峰A在山峰B右侧（x_A > x_B），若A的左侧斜边在B的右侧斜边下方，则B会被A完全遮挡。
用公式表示为：
h_A ≥ h_B + (x_A - x_B)
（A的高度足够高，且与B的水平距离足够近，使得A的左斜边覆盖B的右斜边）。

三、栈的处理逻辑详解

1. 重复山峰处理

若当前山峰与栈顶山峰坐标完全相同（ x相同且h相同），标记为重复（ stk.top().second |= 1 ），避免重复计数。

2. 当前山峰是否被栈顶山峰遮挡？

计算栈顶山峰（记为top）的右侧斜边在当前山峰x位置的高度：
top_h_right = top.h - (current.x - top.x)
若当前山峰高度 current.h ≤ top_h_right ，说明当前山峰完全在top的右侧斜边下方，被遮挡，直接跳过（ continue ）。

3. 当前山峰是否遮挡栈顶山峰？

反向判断：当前山峰的左侧斜边是否在栈顶山峰的右侧斜边上方？
即 current.h ≥ top.h + (current.x - top.x)
若成立，说明当前山峰会完全遮挡栈顶山峰，弹出栈顶（ stk.pop() ），重复此步骤直到栈顶不被遮挡。

4. 入栈

处理完所有可能被当前山峰遮挡的栈顶元素后，将当前山峰入栈，作为后续山峰的遮挡判断基准。

四、举个🌰：几何关系演示

假设有两座山：

- 山A：(x=1, h=3)，右侧斜边方程： y = 3 - (x-1) = 4 - x
- 山B：(x=3, h=4)，左侧斜边方程： y = 4 - (3 - x) = x + 1

判断B是否遮挡A：

- 计算A的右侧斜边在x=3处的高度： 4 - 3 = 1
- B的高度4 > 1，且 4 ≥ 3 + (3-1) （4≥5？不成立），不遮挡A。

若山B高度为5：

- 5 ≥ 3 + 2 （5≥5成立），则B的左斜边完全覆盖A的右斜边，A被B遮挡，会被弹出栈。

五、栈的本质：维护“可见山峰的轮廓”

栈中保存的山峰形成一个从左到右逐渐升高的轮廓，每个山峰的右侧斜边都是当前轮廓的上边界。后续山峰若能“突破”这个轮廓（高度足够高），则会加入轮廓并可能遮挡前面的低矮山峰。

总结：几何关系的核心

- 遮挡=斜边覆盖：通过比较山峰斜边的高度关系，判断是否完全遮挡。
- 栈的作用：动态维护当前未被遮挡的山峰序列，保证后续山峰只需与栈顶（最近的高个子）比较，避免重复计算。
- 重复标记：同一坐标的山峰只算一个，通过栈元素的第二位标记是否重复。

查找root

利用root 没有parents
set.count

class Solution {

public:

Node* findRoot(vector<Node*> tree) {

unordered_set<Node*> children;

for (Node* t : tree)

{

for (Node* child : t->children)

{

children.insert(child);

}

for (Node* t : tree)

{

if (children.find(t) == children.end())

{

return t;

}

return nullptr;

}

};

看似lca，实则相交链表

/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* parent;
};
*/

class Solution {
public:
Node* lowestCommonAncestor(Node* p, Node * q) {
unordered_set<int> s;
while (p != nullptr) {
s.insert(p -> val);
p = p -> parent;
}
while (q != nullptr) {
if (s.count(q -> val)) {
return q;
}
q = q -> parent;
}
return nullptr;
}
};

lowest common ancestor

class Solution {
unordered_set<TreeNode*> st;
public:
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*> &nodes) {
for (auto node: nodes) {
st.insert(node);
}
return traverse(root);
}

TreeNode* traverse(TreeNode* node) {
if (node == 0) return 0;
if (st.count(node)) return node;

TreeNode* left = traverse(node->left);
TreeNode* right = traverse(node->right);

if (left && right) return node;
return left ? left : right;
}
};

1. 标记目标节点

先把要找的所有节点存到集合 st 里（比如节点A、B、C），后续用它快速判断当前节点是否是目标节点。

2. 递归逻辑：后序遍历找目标

从根节点开始递归遍历左右子树，后序遍历顺序（先左→再右→最后处理当前节点）：

- 终止条件：若当前节点是空（ root==null ）或当前节点是目标节点（在 st 里），直接返回当前节点。

- 递归左右子树：先递归左子树得到 left ，再递归右子树得到 right 。

- 合并结果：
- 如果 left 和 right 都不为空→说明当前节点的左右子树各有至少一个目标节点→当前节点就是公共祖先，返回它。

- 否则→返回非空的那个子树结果（哪边有目标节点就返回哪边）。

3. 最终返回的含义

递归会从最底层目标节点往上找，当某个节点的左右子树都包含目标节点时，它就是最低公共祖先。
比如：若左子树返回A（目标节点），右子树返回B（目标节点）→它们的父节点C会同时收到左右非空结果→C就是LCA。

查看全文

http://www.xdnf.cn/news/642331.html