首页 > 试题广场 >

迷雾

[编程题]迷雾

热度指数：3422 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

亮亮深吸一口气，打开了地图，地图上写着(X:12,Y:?)，这可让亮亮犯了愁，这个问号代表了什么意思呢？亮亮绞尽脑汁也想不出什么思路，忽然他在地图背面发现了一串数字，数字下面写着一段话“这只是一个1~n的混乱排列，不用在意第i个值”，亮亮眼前一亮，“这个混乱排列中第i个一定是Y的值！”于是，亮亮开始恢复这个混乱排列。

输入描述:

每组数据第一行一个整数n(0<n≤25)，第二行即现在纸上的数字串

输出描述:

一行n个空格隔开的整数，为小明写下的排列。

示例1

输入

4
2413

输出

2 4 1 3

算法知识视频讲解

Java

Sen🍓🍀

import java.util.*;

// 回溯：分割字符串 → 数字1~n
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        while (in.hasNext()) {
            int n = in.nextInt();
            char[] s = in.next().toCharArray();
            path =  new ArrayList<>();
            used = new boolean[n + 1];
            dfs(s, 0, n);
            for (int x : path) sb.append(x).append(' ');
            sb.append('\n');
        }

        System.out.println(sb.toString());
    }

    private static List<Integer> path;
    private static boolean[] used;

    private static boolean dfs(char[] s, int i, int n) { // 1~n
        if (i == s.length) return true;
        if (s[i] == '0') return false;
        int j = i, num = 0;
        while (j < s.length && num * 10 + s[j] - '0' <= n) {
            num = num * 10 + s[j] - '0';
            if (!used[num]) {
                used[num] = true;
                path.add(num);
                if (dfs(s, j + 1, n)) return true;
                used[num] = false;
                path.remove(path.size() - 1);
            }
            j++;
        }
        return false;
    }
}

发表于 2025-07-02 00:15:52 回复(0)

Java

娓娓道来

import java.util.*;
public class Main
    {
    public static void main(String[] args)
        {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext())
            {
            int n=sc.nextInt();
            String str=sc.next();
            int[] arr=new int[str.length()];
            for(int i=0;i<str.length();i++)
            	arr[i]=Integer.parseInt(String.valueOf(str.charAt(i)));
            List<Integer> li=new ArrayList<Integer>();
            splitNumStr(li,arr,n);
            for(int i:li)
            	System.out.print(i+" ");
            System.out.println();
        }
    }
    public static void splitNumStr(List<Integer> li,int[] arr,int n)
    {
    	for(int i=0;i<arr.length;)
    	{
    		int temp;
    		if(i!=arr.length-1)
    		{
    			temp=arr[i]*10+arr[i+1];
    			if(!li.contains(temp) && temp<=n)
    				i+=2;
    			else
    			{
    				temp=arr[i];
    				i++;
    			}
    		}
    		else
    		{
    			temp=arr[i];
    			i++;
    		}
    		li.add(temp);
    	}
    	while(li.size()<n)
    	{
    		for(int i=0;i<li.size();i++)
    		{
    			if(li.get(i)>10&&li.get(i)!=20)
    			{
    				int r=li.get(i)%10;
    				li.add(i+1, r);
    				break;
    			}
    		}
    	}
    }
}

发表于 2016-09-29 11:36:54 回复(0)