LOADING STUFF...
百度&必应权4, 日IP8000. 查看详情
自助收录

2023年华为OD机考真题:组装新的数组

算法刷题1年前 (2023)更新 江南白衣
489 0 0
2023年华为OD机考真题:组装新的数组

全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。

真题库:https://www.yuque.com/codernav.com/od

题目:组装新的数组
知识点:回溯数组
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:
给你一个整数M和数组N,N中的元素为连续整数,要求根据N中的元素组装成新的数组R,组装规则:
1.R中元素总和加起来等于M
2.R中的元素可以从N中重复选取
3.R中的元素最多只能有1个不在N中,且比N中的数字都要小(不能为负数)
请输出:数组R一共有多少组装办法
输入描述:
第一行输入是连续数组N,采用空格分隔
第二行输入数字M
输出描述:
输出的是组装办法数量,int类型
补充说明:
1 <= N.length <= 30
1 <= N.length <= 1000
示例1
输入:
2
5
输出:
1
说明:
只有1种组装办法,就是[2,2,1]
示例2
输入:
2 3
5
输出:
2
说明:
一共2种组装办法,分别是[2,2,1],[2,3]
解题思路:
因为数组是连续的,所以先求出最小值(第一个数)和最大值(最后一个数)
通过回溯法遍历出所有可能性。

代码实现:Java代码满分实现

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 组装新的数组
 * @Description 给你一个整数M和数组N, N中的元素为连续整数,要求根据N中的元素组装成新的数组R,组装规则:
 * 1.R中元素总和加起来等于M
 * 2.R中的元素可以从N中重复选取
 * 3.R中的元素最多只能有1个不在N中,且比N中的数字都要小(不能为负数)
 * 请输出:数组R一共有多少组装办法
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static int max;
    public static int min;
    public static int res;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strings = sc.nextLine().split(" ");
        int M = sc.nextInt();
        min = Integer.parseInt(strings[0]);      //数组中的最小数
        max = Integer.parseInt(strings[strings.length - 1]);   //数组中的最大数
        handle(min, M);
        System.out.println(res);
    }

    /**
     * 3 4 5
     * 10
     * 5 5
     * 4 5 1
     * 4 4 2
     * 3 5 2
     * 3 3 4
     * 3 3 3 1
     *
     * @param n   数组中的数字
     * @param sum M减去数组中的数字的差值
     */
    public static void handle(int n, int sum) {
        if (sum < min) {  //剩下的小于最小数就可以组装(符合第三个规则)
            res++;
            return;
        }
        if (n > max) {    //大于最大数则返回
            return;
        }
        int i = 0;
        while (true) {
            handle(n + 1, sum - i * n);   //因为数组中的数字是连续的,所以只需要+1
            i++;
            if (sum - i * n <= 0) {
                if (sum - i * n == 0) {     //完美符合
                    res++;
                }
                break;
            }
        }
    }
}

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...