移动

题目分析

小红在一维世界中，给定一个长度为 的字符串 ，仅包含 > 和 <，分别表示向右和向左移动一步。对于每个起始位置 （），从第 个字符开始依次执行移动指令，可以在任意时刻停下。问：对于每个 ，是否存在一种停止时机使得小红恰好回到原点。

思路

前缀和 + 哈希

将 > 看作 ，< 看作 ，定义前缀和 ，。

从位置 出发（0-indexed），执行到位置 后的累计位移为 。回到原点等价于位移为 ，即 ，其中 ，也就是 对某个 成立。

因此问题转化为：对于每个 ，判断前缀和值 是否在 中再次出现。

只需预处理每个前缀和值的最后出现位置 ，然后对位置 判断 即可。

以样例验证： ><><

  • ，
  • ：，，输出
  • ：，，输出
  • ：，，输出
  • ：，，不满足严格大于，输出

结果为 1 1 1 0，与预期一致。

复杂度

  • 时间复杂度：，一次遍历建前缀和，一次遍历查询
  • 空间复杂度：，存储前缀和数组和哈希表

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    char s[n + 1];
    scanf("%s", s);

    vector<int> P(n + 1);
    P[0] = 0;
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + (s[i - 1] == '>' ? 1 : -1);
    }

    unordered_map<int, int> last;
    for (int i = 0; i <= n; i++) {
        last[P[i]] = i;
    }

    for (int i = 0; i < n; i++) {
        if (i > 0) putchar(' ');
        putchar(last[P[i]] > i ? '1' : '0');
    }
    putchar('\n');
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String s = br.readLine().trim();

        int[] P = new int[n + 1];
        P[0] = 0;
        for (int i = 1; i <= n; i++) {
            P[i] = P[i - 1] + (s.charAt(i - 1) == '>' ? 1 : -1);
        }

        HashMap<Integer, Integer> last = new HashMap<>();
        for (int i = 0; i <= n; i++) {
            last.put(P[i], i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(last.get(P[i]) > i ? 1 : 0);
        }
        System.out.println(sb.toString());
    }
}