本文介绍: 有一座保密大楼,你从0楼到达指定楼层m,必须这样的规则乘坐电梯给定个数序列,每次根据序列中的数字n上升n层或者下降n层,前后两次操作方向必须相反,规定首次的方向向上,自行组织序列的顺序按规定操作到达指定楼层。求解到达楼层的序列组合,如果不能到达楼层,给出小于该楼层的最近序列组合。说明:操作电梯时不限定楼层范围必须对序列中的每个项进行操作,不能只使用—部分。第一行:期望的楼层,取值范围[1,50];序列总个数取值范围[1,23]第二行:序列,每个取值范围[1,50]

题目

有一座保密大楼,你从0楼到达指定楼层m,必须这样的规则乘坐电梯给定一个数字序列,每次根据序列中的数字n上升n层或者下降n层,前后两次操作的方向必须相反,规定首次的方向向上,自行组织序列的顺序按规定操作到达指定楼层。求解到达楼层的序列组合,如果不能到达楼层,给出小于该楼层的最近序列组合。
说明:
操作电梯时不限定楼层范围
必须对序列中的每个项进行操作,不能只使用—部分。
输入描述:
第一行:期望的楼层,取值范围[1,50];序列总个数,取值范围[1,23]
第二行:序列,每个值取值范围[1,50]
输出描述
能够达到楼层或者小于该楼层最近的序列
补充说明:
操作电梯时不限定楼层范围
必须对序列中的每个项进行操作,不能只使用—部分
示例1
输入:
5 3
1 2 6
输出:
6 2 1
说明:
1 2 6
6 2 1
均为可行解,按先处理大值的原则结果为6 2 1

思路

排列组合题,此类问题思路可参考:【JAVA-排列组合】一个套路速解排列组合题
此题来说,有两种思路解题:

  1. 排列思路
  2. 组合思路

排列思路

因为题目说明中有”优先处理大值原则”,比如9 8 5 1和9 5 5 4两组数的和相等,按照大值原则应该选择9 8 5 1。所以可以先将原数组从大到小排序,这样在计算排列的时,会优先选择大的数
然后求其全排列,第一个为正,第二个为负…,记录一组排列的和
找到最符合条件的和的组合:
当存在组合的总和与目标值相等时,如果只有一个,直接输出该组合;如果存在多个时,输出第一个即可。(优先输出较大值。因为已经按倒序排列,所以第一个相等的组合一定是优先输出的。)
当不存在组合的总和等于目标值时,找到最接近的总和(只能比目标值小),
输出结果

组合思路

排列的方法有很多冗余计算,效率较低。可以考虑将问题转为组合问题
设序列和为sum,正数和为positive,负数和为neg,目标为target,那么:
因为:positive+neg=sum;positive-neg<=target
所以:positive<=(sum+target)/2
考虑数组总数为奇数的情况,由于第一个是正数,那么其正数的数量应该为,(nums.length+1)/2;负数的数量为:nums.length/2
所以原来的题目就转化为,在nums中找(nums.length+1)/2个数,使其和<=(sum+target)/2,求sum最大时的组合是多少,存在多个时,按照大值原则输出。
关键在于此种情况存在多个值时,应该怎么判断取哪一个?

比如,nums:4 5 2 5 9 8 5 1,target:7
可能能找到的整数组合为:9 8 5 1或者9 5 5 4两者和都为23,如果取前者,那么8是正数,否则8为负数。组装答案时必须先正后负的形式,前者最符合的情况是9 X 8…,后者最符合的情况是 9 8 5…,很明显后者更符合情况。
所以当两组数同时符合时,判断逻辑应该是根据奇偶位判断,如果是奇数位,越大越好,如果是偶数位,越小越好(越小,说明能够留给负数的值更大,可以排在前面)

根据组合思路,可以找到原nums中应该标记正数的索引集合。从而区分出nums哪些为正,哪些为负
最后,根据正负数集合,先从交替从正、负数集合选择值到最后的结果即可。

题解

排列

package hwod;

import java.util.*;
import java.util.stream.Collectors;

public class SecurityElevator {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int target = sc.nextInt();
        int n = sc.nextInt();
        sc.nextLine();
        int nums[] = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int[] res = securityElevator(nums, target);
        for (int i = 0; i < res.length; i++) {
            if (i != 0) System.out.print(" ");
            System.out.print(res[i]);
        }

    }

    private static int[] res;
    private static int nearest = Integer.MAX_VALUE;

    private static int[] securityElevator(int[] nums, int target) {
        Arrays.sort(nums);
        LinkedList<Integer> path = new LinkedList<>();
        int[] used = new int[nums.length];
        res = new int[nums.length];
        dfs(nums, used, path, target);
        return res;
    }

	//排列思路解题
    private static void dfs(int[] nums, int[] used, LinkedList<Integer> path, int target) {
        if (path.size() == nums.length &amp;&amp; target >= 0) {
            if (target < nearest) {
                res = path.stream().mapToInt(i -> i).toArray();
                nearest = target;
            }

        }

        for (int i = nums.length - 1; i >= 0; i--) {
            if (used[i] == 1) continue; //不能选择自身
            path.addLast(nums[i]);
            used[i] = 1;
            int flag = (path.size() &amp; 1) == 1 ? 1 : -1;
            dfs(nums, used, path, target - (nums[i] * flag));
            path.removeLast();
            used[i] = 0;
        }
    }
}

组合

package hwod;

import java.util.*;
import java.util.stream.Collectors;

public class SecurityElevator {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int target = sc.nextInt();
        int n = sc.nextInt();
        sc.nextLine();
        int nums[] = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int[] res = securityElevator(nums, target);
        for (int i = 0; i < res.length; i++) {
            if (i != 0) System.out.print(" ");
            System.out.print(res[i]);
        }

    }

    private static int[] res;
    private static int nearest = Integer.MAX_VALUE;

    private static int[] securityElevator(int[] nums, int target) {
        Arrays.sort(nums);
        LinkedList<Integer> path = new LinkedList<>();
        int[] used = new int[nums.length];
        res = new int[nums.length];
        dfs(nums, used, path, target);
        return res;
    }
private static int[] securityElevator2(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        //neg >=(sum - target) / 2
        //选一半的数,使和<=pos
        //neg+positive=sum,positive-neg<=target;2*pos-sum<=target,pos<=(sum+target)/2
        int positive = (sum + target) / 2;
        Arrays.sort(nums);
        LinkedList<Integer> path = new LinkedList<>();
        int[] used = new int[nums.length];
        //得到正数的索引集合res
        dfs2(nums, nums.length - 1, path, used, positive);
        List<Integer> positiveIdxList = Arrays.stream(res).boxed().collect(Collectors.toList());
        //标记数组的正负号
        int[] positives = new int[(nums.length + 1) / 2];
        int[] negatives = new int[nums.length / 2];
        int m = 0, n = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (positiveIdxList.contains(i)) {
                positives[m++] = nums[i];
            } else {
                negatives[n++] = nums[i];
            }
        }
        //组装正负数,得到答案,先正后负
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if((i&amp;1)==0)ans[i] = positives[i / 2];
            else ans[i] = negatives[i / 2];
        }


        return ans;
    }

    //组合思路解题,在nums中找(nums.length+1)/2个数,使其和<=(sum+target)/2;
    private static void dfs2(int[] nums, int start, LinkedList<Integer> path, int[] used, int target) {

        if (target < 0) return;
        if (path.size() == (nums.length + 1) / 2) {
            if (target < nearest) {
                res = path.stream().mapToInt(i -> i).toArray();
                nearest = target;
            } else if (target == nearest) {
                res = getMoreBigger(res, path.stream().mapToInt(i -> i).toArray(), nums);
            }
            return;

        }
        for (int i = start; i >= 0; i--) {
            if (i < start - 1 &amp;&amp; nums[i] == nums[i + 1] &amp;& used[i + 1] == 0) continue;
            path.addLast(i);
            used[i] = 1;
            dfs2(nums, i - 1, path, used, target - nums[i]);
            path.removeLast();
            used[i] = 0;
        }
    }

    private static int[] getMoreBigger(int[] arr1, int[] arr2, int[] nums) {
        int i = 0;
        int size = arr1.length;
        while (i < size && arr1[i] == arr2[i]) {
            i++;
        }
        if (i >= size) return arr1;
        if ((i & 1) == 0) return nums[arr1[i]] > nums[arr2[i]] ? arr1 : arr2;
        else return nums[arr1[i]] > nums[arr2[i]] ? arr2 : arr1;
    }
}

推荐

如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA)查看当前专栏更新的所有题目。

原文地址:https://blog.csdn.net/qq_31076523/article/details/134649112

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_3234.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注