首页 > 其他分享 >华为OD机试真题---第k个排列

华为OD机试真题---第k个排列

时间:2024-10-04 10:49:14浏览次数:9  
标签:current used 数字 nums int OD --- 数组 真题

针对华为OD机试真题中的“第k个排列”问题,以下是对题目的详细解析及解答方法:

题目描述

给定参数n,从1到n会有n个整数:1, 2, 3, …, n。这n个数字共有n!种排列。按大小顺序升序列出所有排列的情况,并一一标记。给定n和k,返回第k个排列。

输入与输出

  • 输入

    1. 第一行为n,给定n的范围是[1, 9]。
    2. 第二行为k,给定k的范围是[1, n!]。
  • 输出

    • 输出排在第k位置的数字序列。

示例

  • 示例1

    • 输入:3 3
    • 输出:213
    • 说明:3的排列有123, 132, 213, …, 那么第三位置就是213。
  • 示例2

    • 输入:2 2
    • 输出:21
    • 说明:2的排列有12, 21,那么第二位置就是21。

解题思路

  1. 阶乘数组:首先,我们可以预计算一个阶乘数组,其中factorial[i]表示i的阶乘。这个数组将帮助我们确定每个数字在排列中的“组”位置。
  2. 确定每一位的数字:从最高位(最左边的数字)开始,我们可以通过将k除以(n-1)!来确定当前位的数字。具体来说,k / (n-1)!的商表示当前位的数字在1到n中的位置(注意要减1,因为数组是从0开始的),而余数则用于确定下一位的数字。
  3. 更新k值:在确定当前位的数字后,我们需要更新k值为余数,并继续处理下一位,直到所有位都被确定。

代码实现(Java)

package cn.gov.test.gt4.swjggl.leetcode;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;
import java.util.Scanner;

public class KthPermutation {
    private static final Logger log = LoggerFactory.getLogger(KthPermutation.class);

    public static void main(String[] args) {
        // 创建Scanner对象以读取命令行输入
        Scanner scanner = new Scanner(System.in);
        // 读取整数n,表示数字的范围
        int n = scanner.nextInt();
        // 读取整数k,表示排列的索引(从1开始)
        int k = scanner.nextInt();
        // 关闭Scanner对象
        scanner.close();

        // 生成从1到n的数字数组
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }

        // 从最高位开始确定每一位的数字,并同时移除已使用的数字
        int[] result = new int[n];
        k--; // 转换为从0开始的索引
        for (int i = 0; i < n; i++) {
            // 计算剩余元素的阶乘,用于确定当前位的数字
            int factorial = 1;
            for (int j = 1; j <= n - i - 1; j++) {
                factorial *= j;
            }

            // 确定当前位的数字(从0开始索引)
            int index = k / factorial;
            // 存储数字
            result[i] = nums[index];

            // 将已使用的数字从nums数组中移除(通过覆盖的方式)
            for (int j = index; j < n - 1; j++) {
                nums[j] = nums[j + 1];
            }
   
            // 更新k值为在当前“缩小”后的数组中的偏移量(仍然是从0开始索引)
            k %= factorial;
        }

        // 输出结果数组
        for (int num : result) {
            System.out.print(num);
        }
    }
}

**若想要打印出排列组合:**

// 打印出从1到n的所有数字的排列组合
    public static void printAllPermutations(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        boolean[] used = new boolean[nums.length]; // 标记数字是否已被使用
        printPermutations(nums, used, new StringBuilder());
    }
    // 递归打印排列组合的辅助方法
    private static void printPermutations(int[] nums, boolean[] used, StringBuilder current) {
        if (current.length() == nums.length) {
            // 当current字符串的长度等于nums数组的长度时,说明已经生成了一个完整的排列
            log.info(current.toString());
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                // 如果当前数字还没有被使用过
                used[i] = true; // 标记为已使用
                current.append(nums[i]); // 将数字添加到当前排列中

                // 递归调用,继续生成下一个位置的数字
                printPermutations(nums, used, current);

                // 回溯:移除刚刚添加的数字,并标记为未使用
                current.deleteCharAt(current.length() - 1);
                used[i] = false;
            }
        }
    }

注意事项

  1. 数组索引:在Java中,数组索引是从0开始的,而题目中的排列是从1开始的。因此,在代码中需要注意这种差异,并进行适当的调整。
  2. 输入验证:虽然题目已经给出了n和k的取值范围,但在实际编程中,最好还是添加一些输入验证的代码来确保输入的有效性。
  3. 性能优化:由于n的取值范围较小(最多为9),上述实现已经足够高效。但如果n的取值范围更大,可能需要考虑更高效的算法或数据结构来优化性能。

标签:current,used,数字,nums,int,OD,---,数组,真题
From: https://blog.csdn.net/lbp0123456/article/details/142651232

相关文章

  • 测试H7-TOOL的CANFD助手J1939批量数据传输连续运行30个小时稳定不丢包
    根据客户需求做的一个不断电连续运行测试。测试条件1、H7-TOOL的CAN/CANFD助手控制一个节点设备2、使用J1939协议3、经典CAN方式,波特率250KbpsJ1939测试命令,250ms一次发送接收测试昨天下午三点到今晚9点半,共计30个小时不断电连续测试,实时记录的文件:现在还在持续运行的......
  • C# - 异步编程 - BackgroundWorker 类
    后台线程,BackgroundWorker类用于创建一个线程,在后台持续运行以完成某项工作,并不时地与主线程通信。BackgroundWorker类的属性,方法与事件。属性:WorkerReportsProgress:设置后台任务是否可以把它的进度汇报给主线程。WorkerSupportsCancellation:是否支持从主线程取消。IsB......
  • Codeforces Round 972 (Div. 2)
    一万一参赛,VP赛时136A.SimplePalindrome简单构造题。字母集是5,相同字母间一定构成若干回文子串。将相同字母排列在一起,则只有相同字母可以构成回文子串。显然,优先添加较少的字母即可。#include<bits/stdc++.h>usingnamespacestd;intT,n;chars[5]={'a','e','i......
  • CSP-J/S2024总结
    CSP-J/S2024游记初赛前记今年最后一年J了...希望圆我个2年都没有实现的J一等梦还有希望S考好点期待1=day-1考完不放假,然后月考,高兴坏了day1没什么好说的,行就行,不行就AFO(假CSP-J本来就打算摆烂,所以不慌因为是最后一个考场,只有26人,赢!嗯?开局放int?完辣!组合题放那......
  • Debuggers 1012:Introductory GDB
    OpenSecurityTraining2LearningPaths:VulnerabilityHunting&Exploitationpython:https://www.learnpython.org/路径图:https://ost2.fyi/OST2_LP_Vulns_Exploits.pdfDebuggers1012:IntroductoryGDB(与python)-->Architecture1001:x86-64Assembly-->R......
  • Cisco Secure Network Analytics 7.5.1 - 领先的网络检测和响应 (NDR) 解决方案
    CiscoSecureNetworkAnalytics7.5.1-领先的网络检测和响应(NDR)解决方案SecureNetworkAnalytics(formerlyStealthwatch)-NetworkVisibilityandSegmentation请访问原文链接:https://sysin.org/blog/cisco-secure-network-analytics/,查看最新版。原创作品,转载请保......
  • 24.10.4-2
    虽然想着不就是没有朋友吗,我怎么能为这点事情去送死呢,但是内心还是非常不舒服我的人生意义到底是什么财富,美食,兴趣?这些其实完全不感兴趣食物只是维持生理活动的必需品罢了,如果不是必须吃,我宁愿不吃。财富所能满足的人不是欲望十足,就是野心十足,反正对我来说也只是维持生命的必......
  • <动态规划>Leetcode96.不同的二叉搜索树
    给你一个整数n,求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种?返回满足题意的二叉搜索树的种数。解题步骤如下:二叉搜素树的相关概念寻找规律思路建立代码实现1.二叉搜索树的相关概念①:若左子树不空,则左子树所有节点的值均小于它的根节点的值。......
  • 10.3 - AM - 模拟赛 总结
    复盘T1很水,一道异或求和,但是某两位仁兄因没打括号而死。T2很水,一道字符串处理,但是我和某位仁兄因没特判而死(虽然没有hack掉我,所以我理论上还是满分)。T3不水,看了很久,没想出来,自闭了就去看了T4。发现也做不出来。此时我出去晃了一圈,大概是不知道从哪里看到了一个“二”字......
  • 系统设计面试参考-设计Spotify系统
         Spotify是世界上最受欢迎的音乐流媒体平台,每月活跃用户(MAU)超过6亿,付费用户超过2亿。在本文中,我们将学习如何设计像Spotify这样的音乐流媒体服务,该服务每天可以处理数以百计的数百万用户和数十亿个音乐流,确保低延迟和高可用性。1.需求收集功能需求在深入研究......