题解 | #向后找#

题目链接

题目描述

给定一个长度为 $n$ 的字符串 $s$ 。要求从字符串的末尾开始向前查找，找到第一个与字符串首字符 $s[0]$ 相同的字符（但不能是 $s[0]$ 自身）。如果找到了，输出该字符的1-based下标；如果不存在这样的字符，则输出 -1。

解题思路

本题的目标非常明确：找到首字符在字符串其余部分中最后一次出现的位置。这是一个简单的线性搜索问题。

最直观且高效的方法是 从后向前遍历 字符串。

首先，读取输入的字符串长度 $n$ 和字符串 $s$ 。
确定我们的目标字符，即 target = s[0]。
从字符串的最后一个字符（下标为 $n-1$ ）开始，一直遍历到第二个字符（下标为 $1$ ）。我们不需要检查下标为 0 的位置，因为题目要求找到除第一个字符外的匹配项。
在遍历过程中，一旦发现当前字符 s[i] 与 target 相同，就意味着我们找到了最靠后的匹配项。此时，我们直接输出其1-based的下标（即 $i+1$ ），然后结束程序即可。
如果整个循环结束都没有找到匹配的字符（例如，字符串中只有一个字符，或者首字符是唯一的），那么就说明不存在符合条件的字符。在这种情况下，我们输出 -1。

这个方法确保了我们找到的是“首个与 $s[0]$ 相同的字符”（从末尾开始算），并且时间复杂度是线性的，足以应对本题的数据范围。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    string s;
    cin >> s;

    if (n <= 1) {
        cout << -1 << endl;
        return 0;
    }

    char target = s[0];
    int found_pos = -1;

    for (int i = n - 1; i >= 1; --i) {
        if (s[i] == target) {
            found_pos = i + 1;
            break; // 找到第一个就停止
        }
    }

    cout << found_pos << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        if (n <= 1) {
            System.out.println(-1);
            return;
        }

        char target = s.charAt(0);
        int foundPos = -1;

        for (int i = n - 1; i >= 1; i--) {
            if (s.charAt(i) == target) {
                foundPos = i + 1;
                break; // 找到第一个就停止
            }
        }

        System.out.println(foundPos);
    }
}

n = int(input())
s = input()

if n <= 1:
    print(-1)
else:
    target = s[0]
    found_pos = -1
    # 从 n-1 遍历到 1
    for i in range(n - 1, 0, -1):
        if s[i] == target:
            found_pos = i + 1
            break  # 找到第一个就停止
    
    print(found_pos)

算法及复杂度

算法：线性搜索（从后向前）
时间复杂度： $\mathcal{O}(N)$ ，其中 $N$ 是字符串的长度。在最坏的情况下，我们需要遍历整个字符串一次。
空间复杂度： $\mathcal{O}(N)$ ，主要用于存储输入的字符串 $s$ 。