草庐IT

华为OD机试 - 第 N 个排列（C++） | 附带编码思路 【2023】

梦想橡皮擦 2023-09-06 原文

刷算法题之前必看

参加华为od机试，一定要注意不要完全背诵代码，需要理解之后模仿写出，通过率才会高。

华为 OD 清单查看地址：https://blog.csdn.net/hihell/category_12199283.html

华为OD详细说明：https://dream.blog.csdn.net/article/details/128980730

华为OD机试题

第 N 个排列

题目

给定参数n
从1到n会有n个整数 1，2，3，...n
这n个数字共有n!种排列 按大小顺序升序列出所有排列情况
并一一标记
当n = 3 时，所有排列如下
"123","132","213","231","312","321"
给定n和k返回第n个排列

输入

第一行为n
第二行为k
n 的范围是 1 ~ 9
k 的范围是 1 ~ n!

输出

输出排列第k位置的数字

示例一

输入

3
3

输出

213

示例二

输入

2
2

输出

21

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

set<string> s;

void solveMethod(int n, int k);
void perm(vector<int>& array, int start, int end);
void swap(vector<int>& array, int i, int j);

int main() {
    int n, k;
    cin >> n >> k;
    solveMethod(n, k);
    return 0;
}

void solveMethod(int n, int k) {
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        arr[i] = i + 1;
    }
    perm(arr, 0, n - 1);
    string res = *next(s.begin(), k - 1);
    cout << res << endl;
}

void perm(vector<int>& array, int start, int end) {
    if (start == end) {
        string num;
        for (int i : array) {
            num += to_string(i);
        }
        s.insert(num);
    } else {
        for (int i = start; i <= end; ++i) {
            swap(array, start, i);
            perm(array, start + 1, end);
            swap(array, start, i);
        }
    }
}

void swap(vector<int>& array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

编码思路

上述代码的算法思路是求1~n的全排列，存储在一个set中，按照字典序从小到大排序，然后输出第k个。具体的算法实现如下：

  1. 输入n和k，初始化一个数组arr，包含1到n的所有数。
  2. 调用perm函数，生成所有的排列。
  3. 将所有的排列存储在一个set中，set会自动去重和排序。
  4. 从set中找到第k个排列，输出。

perm函数实现的是递归求解全排列。对于数组arr中的每个位置i，从i开始将arr中的元素和arr[i]交换，得到一个新的排列，然后对新的排列继续递归求解全排列。当start == end时，表示arr数组已经排好序了，将arr中的所有数字拼接成一个字符串，并加入到set中。最终set中存储的是所有的全排列，按照字典序排序。

👇 全网 6000+人正在学习的 爬虫专栏 👇👇👇👇

⭐️ Python 爬虫 120，点击订购 ⭐️
⭐️ 爬虫 100 例教程，点击订购 ⭐️

C++2023spanclasstoken华为算法华为机试华为od

有关华为OD机试 - 第 N 个排列（C++） | 附带编码思路 【2023】的更多相关文章

  1. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  2. ruby - 用逗号、双引号和编码解析 csv - 2

    我正在使用ruby​​1.9解析以下带有MacRoman字符的csv文件#encoding:ISO-8859-1#csv_parse.csvName,main-dialogue"Marceu","Giveittohimóhe,hiswife."我做了以下解析。require'csv'input_string=File.read("../csv_parse.rb").force_encoding("ISO-8859-1").encode("UTF-8")#=>"Name,main-dialogue\r\n\"Marceu\",\"Giveittohim\x97he,hiswife.\"\

  3. ruby - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

  4. ruby - 按值降序排列散列，然后按升序键入 ruby - 2

    我有这样的哈希trial_hash={"key1"=>1000,"key2"=>34,"key3"=>500,"key4"=>500,"key5"=>500,"key6"=>500}我按值降序排列:my_hash=trial_hash.sort_by{|k,v|v}.reverse我现在是这样理解的:[["key1",1000],["key4",500],["key5",500],["key6",500],["key3",500],["key2",34]]但我希望当值相同时按键的升序排序。我该怎么做？例如:上面的散列将以这种方式排序:[["key1",1000],["key3",500

  5. C# 到 Ruby sha1 base64 编码 - 2

    我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha

  6. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  7. 华为常用命令 - 2

    system-view进入系统视图quit退到系统视图sysname交换机命名vlan20创建vlan(进入vlan20)displayvlan显示vlanundovlan20删除vlan20displayvlan20显示vlan里的端口20Interfacee1/0/24进入端口24portlink-typeaccessvlan20把当前端口放入vlan20undoporte1/0/10删除当前VLAN端口10displaycurrent-configuration显示当前配置02配置交换机支持TELNETinterfacevlan1进入VLAN1ipaddress192.168.3.100

  8. ruby-on-rails - 有没有一种工具可以在编码时自动保存对文件的增量更改？ - 2

    我最喜欢的Google文档功能之一是它会在我工作时不断自动保存我的文档版本。这意味着即使我在进行关键更改之前忘记在某个点进行保存，也很有可能会自动创建一个保存点。至少，我可以将文档恢复到错误更改之前的状态，并从该点继续工作。对于在MacOS(或UNIX)上运行的Ruby编码器，是否有具有等效功能的工具？例如，一个工具会每隔几分钟自动将Gitcheckin我的本地存储库以获取我正在处理的文件。也许我有点偏执，但这点小保险可以让我在日常工作中安心。 最佳答案 虚拟机有些人可能讨厌我对此的回应，但我在编码时经常使用VIM，它具有自动保存功

  9. c - Ruby - 源代码 - 编码风格 - 2

    查看Ruby代码，它具有以下proc_arity:staticVALUEproc_arity(VALUEself){intarity=rb_proc_arity(self);returnINT2FIX(arity);}更多的是C编码风格问题，但为什么staticVALUE在单独的一行而不是像这样的:staticVALUEproc_arity(VALUEself) 最佳答案 它来自UNIX世界，因为它有助于轻松grep函数的定义:$grep-n'^proc_arity'*.c或使用vim:/^proc_arity

  10. ruby - 如何以编程方式删除实例上的 "singleton information"以使其编码(marshal)？ - 2

    我创建了一个由于“在运行时执行的单例元类定义”而无法编码的对象(这段代码的描述是否正确？)。这是通过以下代码执行的:#defineclassXthatmyusesingletonclassmetaprogrammingfeatures#throughcallofmethod:break_marshalling!classXdefbreak_marshalling!meta_class=class我该怎么做才能使对象编码正确？是否可以从对象instance_of_x的classX中“移除”单例组件？我真的需要一个建议，因为我们的一些对象需要通过Marshal.dump序列化机制进行缓存。

随机推荐