{ }codelper
指针P0074

用指针走出最长的一段

第一行给出 n,第二行给出 n 个整数。
相邻且相等的数连成的部分称为一段(单独一个数也是长度为 1 的一段)。
输出最长一段的起始位置(从 1 开始数)和长度,用一个空格分隔。
如果有多段同样最长,输出最靠前的一段。
试着写一个函数来解:它接收两个指针,一个指向第一个元素,一个指向最后一个元素的下一个位置,每次把指针移动一个元素地走下去,返回指向最长一段开头的指针。
起始位置用这个指针减去数组首元素的指针求得。

输入
1 ≤ n ≤ 100,000,所有数都是 -1,000,000,000 到 1,000,000,000 之间的整数
输出
一行:起始位置 长度
样例 1 · stdin
7
3 1 2 2 2 1 1
stdout
3 3
样例 2 · stdin
5
1 2 2 3 3
stdout
2 2
main.py
输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写?查看各语言题解 · 2 种语言题解

这道题只接受 C 和 C++。
持有地址、用 p++ 前进的指针以及指针相减只有这两种语言有,Python、JavaScript、TypeScript、Java 和 Craykon 用下标 i 来走(C# 只能在 unsafe 里用指针)。
函数像 const int *longest_run(const int *first, const int *last, int *len) 这样接收 [first, last)。
last = a + n 是末尾的下一个位置,只能指向、不能读取,循环条件是 p != last。
同一数组中的两个指针相减得到的是元素个数而不是字节数,所以 start - a 是从 0 数的位置,q - p 是一段的长度。
C++ 传 a.data() 和 a.data() + a.size(),实际代码里更常用同样形状的迭代器(a.begin()、a.end())。
三个陷阱:① 在函数里用 sizeof(a) / sizeof(a[0]) 求长度会出错,因为参数 int a[] 其实是指针,在 64 位上得到 8 / 4 = 2,只看前两个元素;所以要另外传长度或末尾指针。
② 不要像 (start - a) / sizeof(int) 这样再除一次,指针相减已经是元素个数。
③ 用 >= 比较长度,长度相同时会换成后面的一段;只有更长(>)时才替换。

C++main.cpp · 31 行
#include <iostream>#include <vector> // [first, last) 를 포인터로 걷는다. 길이는 참조로 돌려준다const int* longest_run(const int* first, const int* last, int& len) {    const int* best = first;    len = 0;    for (const int* p = first; p != last;) {        const int* q = p;        while (q != last && *q == *p) ++q;        if (q - p > len) {            best = p;            len = static_cast<int>(q - p);        }        p = q;    }    return best;} int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n;    std::cin >> n;    std::vector<int> a(n);    for (int& v : a) std::cin >> v;     int len;    const int* start = longest_run(a.data(), a.data() + a.size(), len);    std::cout << (start - a.data()) + 1 << " " << len << "\n";}
Cmain.c · 34 行
#include <stdio.h>#include <stdlib.h> /* [first, last) 구간을 포인터로 걸으며 가장 긴 같은 수 덩이를 찾는다.   덩이의 시작을 가리키는 포인터를 돌려주고, 길이는 *len에 써 넣는다. */const int *longest_run(const int *first, const int *last, int *len) {    const int *best = first;    *len = 0;    const int *p = first;    while (p != last) {        const int *q = p;        while (q != last && *q == *p) q++;  /* q는 덩이 바로 다음 칸 */        if (q - p > *len) {                 /* 포인터 빼기 = 칸 수. 더 길 때만 바꿔서 비기면 앞의 것 */            best = p;            *len = (int)(q - p);        }        p = q;    }    return best;} int main(void) {    int n;    scanf("%d", &n);    int *a = malloc(n * sizeof *a);    for (int i = 0; i < n; i++) scanf("%d", &a[i]);     int len;    const int *start = longest_run(a, a + n, &len);  /* a + n은 끝 바로 다음: 가리키기만 하고 읽지 않는다 */    printf("%d %d\n", (int)(start - a) + 1, len);    /* start - a 가 0부터 센 자리 */     free(a);    return 0;}