试题 算法训练 数字游戏 java 题解 228

问题描述

给定一个1~N的排列a[i],每次将相邻两个数相加,得到新序列,再对新序列重复这样的操作,显然每次得到的序列都比上一次的序列长度少1,最终只剩一个数字。
例如:
3 1 2 4
4 3 6
7 9
16
现在如果知道N和最后得到的数字sum,请求出最初序列a[i],为1~N的一个排列。若有多种答案,则输出字典序最小的那一个。数据保证有解。

输入格式

第1行为两个正整数n,sum

输出格式

一个1~N的一个排列

样例输入

4 16

样例输出

3 1 2 4

数据规模和约定

0<n<=10


解题思路:

欲求最初的序列,并且是符合条件的最小序列。可以将所求序列全排列,当每排好一种情况时,则进行累加求和,为了不改变原始数组中的值,需要拷贝一个数组,判断累加和是否等于题给出的和,满足时输出该数组并退出即可。

全排列问题:

全排列问题icon-default.png?t=LA92https://blog.csdn.net/weixin_48898946/article/details/121589155

注意在拷贝数组时,不能用list,因为用list涉及到list的替换元素(set方法),而初始时,list中为空,第一次替换会下标越界(事实上,即使提前处理使得不越界也会超时)。而如果每次都开一个list,对时间和空间都会产生很大代价。由于第五个测试点没有符合条件的解,意味着需要将所有全排列的数都每次开list,所以会超时。所以拷贝数组用一个常规一维数组就行。

java代码:

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int sum = Integer.parseInt(split[1]);
		Temp228 temp = new Temp228(n, sum);
		temp.dfs(1);
	}
}
class Temp228{
	int n;
	int sum;
	boolean visited[];//标志数字是否出现过,避免重复出现
	List<Integer> list = new ArrayList<>();//存放实时数据
	int []arr;//便于筛选时的拷贝数组
	
	public Temp228(int n, int sum) {
		this.n = n;
		this.sum = sum;
		visited = new boolean[n + 1];
		arr = new int[n];
	}
	
	public void dfs(int step) {
		if(step > n) {
			if(compare()) {//当都排列好时,就进行符合条件的筛选
				System.exit(0);//选好直接退出程序
			}
			return;
		}
		for(int i = 1; i <= n; i++) {
			if(!visited[i]) {
				visited[i] = true;
				list.add(i);
				dfs(step + 1);
				visited[i] = false;//回溯
				list.remove(list.size() - 1);
			}
		}
	}
	
	public boolean compare() {
		for(int i = 0; i < list.size(); i++) {
			arr[i] = list.get(i);//拷贝数据
		}
		for(int i = 1; i < n; i++) {//计算相加后的“左下角”值
			for(int j = 1; j <= n - i; j++) {
				arr[j - 1] = arr[j] + arr[j - 1];
			}
		}
		if(arr[0] == sum) {//符合条件时,直接打印并返回true
			for(int i = 0; i < list.size() - 1; i++) {
				System.out.print(list.get(i) + " ");
			}
			System.out.print(list.get(list.size() - 1));
			return true;
		}
		return false;
	}
}

提交截图:

 


版权声明:本文为weixin_48898946原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。