首页 > 试题广场 >

小红的排列构造②

[编程题]小红的排列构造②
  • 热度指数：4103 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红定义一个仅由 \texttt{0} 和 \texttt{1} 两个字符构成的字符串 s 与一个长度为 n 的数组 p 为匹配，当且仅当满足下列两点：
{\hspace{20pt}}_\texttt{1.}\,若 s_i=\texttt{1}，则数组 \{p_1,p_2,\dots,p_i\} 恰好构成一个排列；
{\hspace{20pt}}_\texttt{2.}\,若 s_i=\texttt{0}，则数组 \{p_1,p_2,\dots,p_i\} 无法构成一个排列。

\hspace{15pt}现在小红给出了一个长度为 n 的字符串 s，请你构造一个长度为 n 的排列 p 使得 s 与 p 匹配；如果不存在这样的排列，请输出 -1。

\hspace{15pt}【名词解释】
\hspace{23pt}\bullet\,排列：排列是由 1\sim n 这 n 个整数按任意顺序组成的数组，其中每个整数恰好出现一次。

输入描述:
\hspace{15pt}第一行输入一个整数 n\left(1\leqq n\leqq 10^5\right) 表示字符串及排列的长度。 
\hspace{15pt}第二行输入一个长度为 n，仅由 \texttt{0} 和 \texttt{1} 构成的字符串 s。


输出描述:
\hspace{15pt}如果不存在满足条件的排列，直接输出 -1；否则，在一行上输出 n 个整数 p_1,p_2,\dots,p_n 表示你构造出的排列。 
\hspace{15pt}如果存在多个满足条件的排列，输出任意一个均可，系统将自动判定其正确性。请注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
示例1

输入

3
001

输出

3 1 2

说明

\hspace{15pt}对于这个样例，
\hspace{23pt}\bullet\,由于 s_0 = {\tt 0}，排列的前一项元素无法构成一个排列；
\hspace{23pt}\bullet\,由于 s_1 = {\tt 0}，排列的前两项元素无法构成一个排列；
\hspace{23pt}\bullet\,由于 s_2 = {\tt 1}，排列的前三项元素构成一个排列；
\hspace{15pt}同时，输出 \{2,3,1\}、\{3,2,1\} 等答案也都是合法的。
示例2

输入

4
1110

输出

-1

说明

在此样例中，若存在合法排列，则前三位必须依次形成排列，但第四位又要求整体不形成排列，显然不可能，因此答案为 -1。
算法知识视频讲解
添加回答
Java
BraveCoder头像 BraveCoder 
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();  // 读取01字符串
        sc.close(); // 关闭扫描器

        // 若字符串最后一位不是1，直接输出-1（无法满足置换要求）
        if (s.charAt(n - 1) != '1') {
            System.out.println(-1);
            return;
        }

        int flag = 0; // 标记下一个置换区间的起始位置
        int[] arr = new int[n]; // 存储置换结果的数组

        // 遍历字符串，处理每个'1'对应的置换
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                // '0'对应的位置：值=自身索引+1（不置换）
                for (int j = flag + 1; j < i; j++) {
                    arr[j] = j + 1;
                }
                // '1'对应的位置：flag和i互换（值=对方索引+1）
                arr[flag] = i + 1;
                arr[i] = flag + 1;
                flag = i + 1; // 更新下一个置换区间起点
            }
        }

        // 输出最终置换结果
        for (int a : arr) {
            System.out.print(a + " ");
        }
    }
}

发表于 2025-10-16 19:56:10 回复(0)
Java
清浅QAQ头像 清浅QAQ
import java.util.*;

//找到1就倒叙添加到list
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        in.nextLine();
        String s = in.nextLine();
        int len = s.length();
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0; i < len; i++){
            if(s.charAt(i) == '0')
                continue;
            int temp = res.size();
            for(int j = i + 1; j > temp; j--){
                res.add(j);
            }
        }
        if(n != res.size())
            System.out.println("-1");
        else{
            for(int i = 0; i < n; i++){
                if(i == n - 1)
                    System.out.println(res.get(i));
                else
                    System.out.print(res.get(i) + " ");
            }
        }
    }
}
发表于 2025-09-10 19:01:04 回复(0)
Java
牛客281381469号头像 牛客281381469号 
控制台传过来的字符串为str，①无结果：当str的结尾为0时，说明不可能有满足题意的字符顺序，直接输出-1。
②有结果：遇到1时再填充字符，两层for循环，外层right从前到后寻找字符“1”，
内层j从上一个字符“1”后开始遍历到外层找到的1，填充为j + 2（下标比当前位置靠后。比如第二个位置，我们输入3），
遍历到达“1”（right）时，输出left + 1的值，再把left赋值为right + 1。
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int lens = in.nextInt();
            in.nextLine();
            String str = in.nextLine();
            char[] chars = str.toCharArray();

            if (chars[chars.length - 1] == '0'){
                System.out.println(-1);
            }else{
                int impossible = 2;
                int possible = 1;
                int left = 0;
                for (int right = 0; right < chars.length; right++){
                    if (chars[right] == '1'){
                        for (int j = left; j < right; j++){
                            System.out.print(j + 2 + " ");
                        }
                        System.out.print(left + 1 + " ");
                        left = right + 1;
                    }
                }
            }
        }
    }
}

发表于 2025-07-21 01:42:30 回复(0)
Java
s0va头像 s0va

以堆栈的思路来写，遍历字符串的每项，遍历到第i项则将i存入堆栈，若第i项为1则将堆栈内全部内容输出，否则不作操作
以001为例，{p1}，{p1，p2}不能构成排序，而{p1,p2,p3}要构成排序，这时就可以想到将1压入栈底，将2,3先输出
以0101为例，对于前两项先输出了2 1，对于第3项，同理将3压入栈底，前两项已经构成排序，即已经包含1与2，只要p3输出的不是3，那么{p1，p2，p3}就不能构成排序，而第4项为1，这时输出堆栈中的内容，p3为4，p4为3，恰能构成排序
代码示例： 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        String s=in.next();
        Stack<Integer> st=new Stack<Integer>();
        if(s.charAt(n-1)=='0'){
            System.out.print(-1);
            return;
        }
        for(int i=1;i<=n;i++){
            st.push(i);
            if(s.charAt(i-1)!='0'){
                while(!st.empty()) System.out.print(st.pop()+" ");
            }
        }
    }
}


发表于 2025-06-27 15:02:27 回复(0)
Java
牛客907437933号头像 牛客907437933号 
2,3,1  不是说这种也是合法的吗，为什么输出这个不行
发表于 2025-03-23 23:55:41 回复(1)
Java
牛客279643016号头像 牛客279643016号
解题思路：
1. 找规律，结尾是0的肯定不符合条件
2. 每个长串可以理解为多个0开始1结尾或者全1的子串
3. 如果是全部为1，这该位置直接放入对应的数字
4. 如果是0开始1结尾这种子串，0的位置填该位置后一位，1位置填首位0的位置。举例：0001 ==> 2341
代码示例： 
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String length = in.nextLine();
        String input = in.nextLine();
        resultList = new LinkedList<>();
        boolean res = getResult(input);
        if (res) {
            resultList.forEach(s->System.out.print(s + " "));
        } else {
            System.out.println(-1);
        }
    }

    static List<Integer> resultList = new LinkedList<>();
    public static boolean getResult(String str) {
        if (str.endsWith("0")) {
            return false;
        }
        Integer temp = 1;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                resultList.add(i + 2);
            } else {
                resultList.add(temp);
                temp = i + 2;
            }
        }
        return true;
    }


发表于 2025-03-23 21:46:23 回复(0)
Java
牛客430757235号头像 牛客430757235号
//D老师代码看不懂 头铁自己写 写了一下午 5小时！！！！ 大家记得把输出最后末尾的空格去掉哦！！！

import java.util.ArrayList;
import java.util.Scanner;
import java.util.List;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String s = in.nextLine();
        if (s.charAt(s.length() - 1) == '0') {
            System.out.println(-1);
            return;
        }
        boolean onekai = false;
        int b = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                b++;
                onekai = true;
            } else {
                break;
            }
        }
        List<Integer> q = new ArrayList<>();
        int count = 0;
        if (onekai) {
            b = b + 1;
            for (int i =  b; i < n; i++) {
                if (s.charAt(i) == '1') {
                    q.add(count);
                    count = 0;
                }
                if (s.charAt(i) == '0') {
                    count++;
                }
            }
            /*
                        System.out.println("NO");
                        for (int i = 0; i < q.size(); i++) {
                            System.out.print(q.get(i));
                        }
                        System.out.println("NO");

             */

            if (b != 0) {
                System.out.print(b + " ");
                for (int i = 1; i < b ; i++) {
                    if (i == n-1) {
                        System.out.print(i);
                    } else {
                        System.out.print(i + " ");
                    }
                }
            }
            for (int i = b; i < n;) {
                for (int j : q) {
                    j++;
                    int a = i;
                    while (j-- > 0) {
                        i++;
                        if (i == n) {
                            System.out.print(1 + a + j);
                        } else {
                            System.out.print(1 + a + j + " ");
                        }
                    }
                }
            }
        } else {
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == '1') {
                    q.add(count);
                    count = 0;
                }
                if (s.charAt(i) == '0') {
                    count++;
                }
            }
            /*
                        System.out.println("NO");
                        for (int i = 0; i < q.size(); i++) {
                            System.out.print(q.get(i));
                        }
                        System.out.println("NO");

             */
            for (int i = 0; i < n;) {
                for (int j : q) {
                    j++;
                    int a = i;
                    while (j-- > 0) {
                        i++;
                        if (i == n) {
                            System.out.print(1 + a + j);
                        } else {
                            System.out.print(1 + a + j + " ");
                        }
                    }
                }
            }
        }
    }
}

发表于 2025-03-19 19:06:07 回复(0)
提交观点

问题信息

模拟
难度：
7条回答 547浏览

热门推荐

相关试题

小红的排列构造②

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号