LeetCode 补充题 146. 带省略号的分页导航
题目描述
输入总页数
N与当前页K，返回要显示的页码及省略号。当
N<7时，显示全部页码；否则显示首页、尾页和K前后各两页。超出1…N的页码忽略，重复页码合并，相邻显示页码不连续时插入一个省略号。
示例 1：
输入：
N = 94, K = 5
输出：["1","…","3","4","5","6","7","…","94"]
解释： 保留 1、94 以及3…7，缺失的两段分别用省略号表示。
示例 2：
输入：
N = 94, K = 93
输出：["1","…","91","92","93","94"]
解释： 超过尾页的 95 忽略，不向左补满。
提示：
-
1≤K≤N≤2³¹−1。 - 最多显示七个数字页码，省略号不计入这七个。
- 靠近两端时不额外补满窗口。
题意分析
题目已经明确哪些数字页码需要出现，不要求靠近边缘时补满窗口。可以先生成至多七个候选页码，再处理它们之间的缺口，无需扫描
1～N的所有页面。
解法：常数个候选页码排序去重
核心思路
[!blue]
N < 7时直接加入所有页码；否则加入首页、尾页，以及裁剪到合法范围内的[K-2,K+2]。首页和尾页可能与窗口重叠，用集合去重后按数值升序处理。记录上一个输出的数字页码
previous，若当前页与它相差大于 1，说明中间至少缺失一页，先插入一个省略号。即使只缺一页也按题目规则显示省略号，不额外补数字。页码加减偏移前先提升到 64 位，避免
K接近 32 位上限时K+2溢出。候选始终为常数规模，页数增大不会使循环线性增长。
解题步骤
- 按小页数特例或首尾加当前页前后两页生成候选。
- 用有序集合或排序去重保证页码递增。
- 相邻候选页码相差超过 1 时，在中间输出省略号。
代码实现
class Solution {
public List<String> pageLabels(int n, int k) {
TreeSet<Long> pages = new TreeSet<>();
if (n < 7) {
for (long p = 1; p <= n; p++) {
pages.add(p);
}
} else {
pages.add(1L);
pages.add((long) n);
for (long p = Math.max(1L, (long) k - 2); p <= Math.min((long) n, (long) k + 2); p++) {
pages.add(p);
}
}
List<String> out = new ArrayList<>();
long previous = 0;
for (long p : pages) {
if (previous != 0 && p - previous > 1) {
out.add("…");
}
out.add(Long.toString(p));
previous = p;
}
return out;
}
}
import (
"sort"
"strconv"
)
func pageLabels(n, k int) []string {
set := map[int64]bool{}
if n < 7 {
for p := int64(1); p <= int64(n); p++ {
set[p] = true
}
} else {
set[1] = true
set[int64(n)] = true
for p := max(1, int64(k)-2); p <= min(int64(n), int64(k)+2); p++ {
set[p] = true
}
}
pages := make([]int64, 0, len(set))
for p := range set {
pages = append(pages, p)
}
sort.Slice(pages, func(i, j int) bool {
return pages[i] < pages[j]
})
out := []string{}
previous := int64(0)
for _, p := range pages {
if previous != 0 && p-previous > 1 {
out = append(out, "…")
}
out = append(out, strconv.FormatInt(p, 10))
previous = p
}
return out
}
复杂度分析
- 时间复杂度：$O(1)$。
- 空间复杂度：辅助空间 $O(1)$。
候选页码数量不超过七个。
关键点总结
[!green]
候选页码最多七项，页数再大也只处理常量规模；先转 64 位再计算当前页加减偏移。
易错点总结
[!yellow]
省略号不是一个数字页码；K 接近最大整数时，K+2 应先提升到 64 位再计算。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 228. 汇总区间 | 简单 | 同样比较相邻数字识别间隔，原题把连续段压成区间，本题在省略的页码间插入省略号。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！