← 返回编程题库
coding-cluster-correlated-tickers中等免费版2000ms未尝试

强相关标的聚类

Cluster Correlated Tickers

开始编码

risk 中台每天会从因子模型或者历史日收益里算出一份 N×N 的 ticker 相关系数矩阵,用来识别真正独立的风险敞口。如果两只 ticker 在过去窗口里的相关系数绝对值 ≥ 某个阈值(强负相关同样意味着「同一波动源在驱动」——只是符号相反),它们就被视为同一个风险簇,对外只算作一个独立头寸。给定 ticker 列表、相关矩阵和阈值,请把所有 ticker 划分成连通分量——每个连通分量就是一个风险簇。

请实现 solution(tickers: list[str], corr: list[list[float]], threshold: float) -> list[list[str]]。建图规则:节点是 ticker,对 i < jabs(corr[i][j]) >= threshold 时连边(无向)。对角线 corr[i][i] = 1.0 算自环——它的存在只是为了让矩阵看起来正常,孤立的 ticker 还是要单独成一族。返回所有连通分量;每个分量内部 ticker 按它们在 tickers 输入里的下标升序排列;外层按每族「最小下标 ticker 的下标」升序排列。

举例:tickers = ["AAPL", "MSFT", "GOOG", "XOM", "CVX", "TLT"],相关矩阵阈值 0.7 下满足 |corr| ≥ 0.7 的 pair 是 {AAPL, MSFT}{AAPL, GOOG}{XOM, CVX},那么连通分量是 [AAPL, MSFT, GOOG][XOM, CVX][TLT]——前两族是科技股 / 能源股各自相关;TLT(长债 ETF)和谁都不强相关,自己一族。返回 [["AAPL", "MSFT", "GOOG"], ["XOM", "CVX"], ["TLT"]]:外层按各族最小下标(AAPL=0 < XOM=3 < TLT=5)排序,内层按下标升序。

实现上 BFS 或 DFS 都行:从 i = 0 起遍历 tickers,如果 i 没被访问过,从它出发用队列 / 栈把这个连通分量整族挖出来,标记访问过的下标,然后继续往后扫。挖一个分量时邻居判定按 abs(corr[i][j]) >= threshold 即可。复杂度 O(n²) 来自必须看一遍相关矩阵的所有 off-diagonal 元素。

约束条件

  • 0 ≤ len(tickers) ≤ 500,tickers 内字符串两两不同
  • corr 是 n×n 的 list[list[float]],n = len(tickers);corr[i][i] == 1.0;|corr[i][j]| ≤ 1.0
  • 0.0 ≤ threshold ≤ 1.0
  • 对角线不视为「自环」——单只 ticker 单独成一族时返回 `[ticker]`,不会因 corr[i][i] = 1 ≥ threshold 而被算进别的簇
  • 连边判据是 `abs(corr[i][j]) >= threshold`(含等号)
  • 返回 `list[list[str]]`:内层按 ticker 在输入 `tickers` 里的下标升序排序;外层按每族「最小下标 ticker 的下标」升序排序

样例

Case 1 · example from statement

输入: [["AAPL","MSFT","GOOG","XOM","CVX","TLT"],[[1,0.82,0.75,0.1,0.12,-0.2],[0.82,1,0.68,0.08,0.05,-0.18],[0.75,0.68,1,0.15,0.11,-0.22],[0.1,0.08,0.15,1,0.91,-0.3],[0.12,0.05,0.11,0.91,1,-0.28],[-0.2,-0.18,-0.22,-0.3,-0.28,1]],0.7]

期望: [["AAPL","MSFT","GOOG"],["XOM","CVX"],["TLT"]]

阈值 0.7 下满足 |corr| ≥ 0.7 的 pair 是 (AAPL,MSFT)=0.82、(AAPL,GOOG)=0.75、(XOM,CVX)=0.91(其他要么 0.68 < 0.7、要么相关性弱)。注意 (MSFT,GOOG)=0.68 < 0.7 没有直接边,但通过 AAPL 间接连通,所以三只科技股仍归一族。TLT 和谁都不强相关,自己一族。外层按各族最小下标排序:AAPL=0、XOM=3、TLT=5。

Case 2 · two clearly correlated, one isolated

输入: [["A","B","C"],[[1,0.95,0.1],[0.95,1,0.05],[0.1,0.05,1]],0.8]

期望: [["A","B"],["C"]]

(A,B)=0.95 ≥ 0.8 连边;C 和 A、B 的相关都低于 0.8,自己一族。外层按各族最小下标:A=0 在前,C=2 在后。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · example from statement

输入: [["AAPL","MSFT","GOOG","XOM","CVX","TLT"],[[1,0.82,0.75,0.1,0.12,-0.2],[0.82,1,0.68,0.08,0.05,-0.18],[0.75,0.68,1,0.15,0.11,-0.22],[0.1,0.08,0.15,1,0.91,-0.3],[0.12,0.05,0.11,0.91,1,-0.28],[-0.2,-0.18,-0.22,-0.3,-0.28,1]],0.7]

期望: [["AAPL","MSFT","GOOG"],["XOM","CVX"],["TLT"]]

阈值 0.7 下满足 |corr| ≥ 0.7 的 pair 是 (AAPL,MSFT)=0.82、(AAPL,GOOG)=0.75、(XOM,CVX)=0.91(其他要么 0.68 < 0.7、要么相关性弱)。注意 (MSFT,GOOG)=0.68 < 0.7 没有直接边,但通过 AAPL 间接连通,所以三只科技股仍归一族。TLT 和谁都不强相关,自己一族。外层按各族最小下标排序:AAPL=0、XOM=3、TLT=5。

Case 2 · two clearly correlated, one isolated

输入: [["A","B","C"],[[1,0.95,0.1],[0.95,1,0.05],[0.1,0.05,1]],0.8]

期望: [["A","B"],["C"]]

(A,B)=0.95 ≥ 0.8 连边;C 和 A、B 的相关都低于 0.8,自己一族。外层按各族最小下标:A=0 在前,C=2 在后。