牛客NC367 第K个n的排列【困难 dfs,全排列问题 Java/Go/PHP/C++】

题目

在这里插入图片描述
题目链接:
https://www.nowcoder.com/practice/1595969179464e4c940a90b36abb3c54

思路

	全排列问题本文提供的答案在力扣同一道题60. 排列序列,超时了但是截止文章发表日,牛客上是能通过全部测试用例的

Java代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param n int整型* @param k int整型* @return string字符串*/public String KthPermutation (int n, int k) {int[] arr = new int[n];for (int i = 0; i < n ; i++) {arr[i] = i + 1;}List<String> ll = new ArrayList<>();dfs(arr, 0, ll);Collections.sort(ll);return ll.get(k - 1);}public void dfs(int[] arr, int idx, List<String> ll) {if (idx == arr.length) {StringBuilder sb = new StringBuilder();for (int i : arr) {sb.append(i);}ll.add(sb.toString());return;}for (int i = idx; i < arr.length ; i++) {swap(arr, idx, i);dfs(arr, idx + 1, ll);swap(arr, idx, i);}}public void swap(int[] arr, int i, int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}
}

Go代码

package mainimport ("sort""bytes""strconv"
)/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param n int整型* @param k int整型* @return string字符串*/
func KthPermutation(n int, k int) string {//全排列问题ll := []string{}arr := make([]int, n)for i := 0; i < n; i++ {arr[i] = i + 1}dfs(arr, 0, &ll)sort.Strings(ll)return ll[k-1]
}func dfs(arr []int, idx int, ll *[]string) {if idx == len(arr) {var bt bytes.Bufferfor i := 0; i < len(arr); i++ {bt.WriteString(strconv.Itoa(arr[i]))}*ll = append(*ll, bt.String())} else {for i := idx; i < len(arr); i++ {swap(arr, i, idx)dfs(arr, idx+1, ll)swap(arr, i, idx)}}
}func swap(arr []int, i, j int) {t := arr[i]arr[i] = arr[j]arr[j] = t
}

PHP代码

<?php/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param n int整型 * @param k int整型 * @return string字符串*/
function KthPermutation( $n ,  $k )
{//全排列问题$ll =[];$arr = [];for($i=0;$i<$n;$i++){$arr[$i] = $i+1;}dfs($arr,0,$ll,$n);sort($ll);return $ll[$k-1];
}function dfs($arr,$idx,&$ll,$size){if($idx == count($arr)){$str='';for($i=0;$i<$size;$i++){$str.=$arr[$i];}$ll[count($ll)] = $str;}else{for($i=$idx;$i<$size;$i++){swap($arr,$i,$idx);dfs($arr,$idx+1,$ll,$size);swap($arr,$i,$idx);}}
}function swap(&$arr,$i,$j){$t = $arr[$i];$arr[$i] =$arr[$j];$arr[$j] = $t;
}

C++代码

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param n int整型* @param k int整型* @return string字符串*/string KthPermutation(int n, int k) {//全排列问题vector<string> ll;vector<int> arr(n);for (int i = 0; i < n; i++) {arr[i] = i + 1;}dfs(arr, 0, &ll, n);std::sort(ll.begin(), ll.end());return ll[k - 1];}void dfs(vector<int> arr, int idx, vector<string>* ll, int size) {if (idx == size) {std::stringstream ss;for (int i = 0; i < size; i++) {ss << std::to_string(arr[i]);}std::string combined_string = ss.str();ll->push_back(combined_string);} else {for (int i = idx; i < size; i++) {int t = arr[i];arr[i] = arr[idx];arr[idx] = t;dfs(arr, idx + 1, ll, size);//恢复现场int t1 = arr[i];arr[i] = arr[idx];arr[idx] = t1;}}}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/335495.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【漏洞复现】大华智能物联综合管理平台 fastjson远程代码执行漏洞

0x01 产品简介 大华ICC智能物联综合管理平台对技术组件进行模块化和松耦合&#xff0c;将解决方案分层分级&#xff0c;提高面向智慧物联的数据接入与生态合作能力。 0x02 漏洞概述 由于大华智能物联综合管理平台使用了存在漏洞的Fastson组件,未经身份验让的攻击者可利用 /e…

Qt 基于FFmpeg的视频转换器 - 转GIF动图

Qt 基于FFmpeg的视频转换器 - 转GIF动图 引言一、设计思路二、核心源码三、参考链接 引言 gif格式的动图可以通过连续播放一系列图像或视频片段来展示动态效果&#xff0c;使信息更加生动形象&#xff0c;可以很方便的嵌入到网页或者ppt中。上图展示了视频的前几帧转为gif动图的…

深入解析 JSONPath:从入门到精通

码到三十五 &#xff1a; 个人主页 在数据处理和交换领域&#xff0c;JSON已经成为了一种广泛使用的数据格式&#xff0c; 如何有效地查询和操作这些数据也变得越来越重要。在这种情况下&#xff0c;JSONPath 应运而生&#xff0c;成为了一种在JSON数据中定位和提取信息的强大工…

【PingPong_注册安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞 …

(超详细)字符函数和字符串函数【上】

前言 C 语言中对字符和字符串的处理很是频繁&#xff0c;但是 C 语言本身是没有字符串类型的&#xff0c;字符串通常放在 常量字符串 中或者 字符数组 中。 字符串常量 适用于那些对它不做修改的字符串函数 . 1.求字符串长度函数 strlen函数 我们要求一个字符串函数的长度…

树--搜索二叉树

现有一棵结点数目为n的二叉树&#xff0c;采用二叉链表的形式存储。对于每个结点均有指向左右孩子的两个指针域&#xff0c;而结点为n的二叉树一共有n-1条有效分支路径。那么&#xff0c;则二叉链表中存在2n-(n-1)n1个空指针域。那么&#xff0c;这些空指针造成了空间浪费。 例…

通过vlan实现同一网段下的网络隔离

现有两个电脑通过交换机直接连接在一起 pc1&#xff1a; pc2&#xff1a; 正常状态下是可以ping成功的 现在先进入交换机命令行界面&#xff0c;创建两个vlan <Huawei>system-view Enter system view, return user view with CtrlZ. [Huawei]vlan 10 [Huawei-vlan10…

python基础知识总结(第一节)

一、python简介&#xff1a; Python是一种解释型&#xff0c;面向对象的高级语言。 Pyhton的语法和动态类型&#xff0c;以及解释性语言的本质&#xff0c;使它一跃成为多数平台上写脚本和快速开发应用的编程语言。 python语言百度百科介绍 二、Python基础语法&#xff1a;…

交换机的三层交换技术

现有pc1与pc2不在同一个网段之下&#xff0c;通过交换机相连接。 进人交换机1&#xff0c;创建两个vlan 10和vlan 20 &#xff0c;进入串口2设置串口模式为access&#xff0c;并且设置默认vlan为10.进入串口3设置串口模式为access&#xff0c;并且设置默认vlan为20. 进入串口1…

操作系统真象还原:完善MBR

第3章-完善MBR 这是一个网站有所有小节的代码实现&#xff0c;同时也包含了Bochs等文件 编译器给程序中各符号&#xff08;变量名或函数名等&#xff09;分配的地址&#xff0c;就是各符号相对于文件开头的偏移量 。 section 称为节&#xff0c;在有的编译器中&#xff0c;同…

做视频号小店和达人对接的好,爆单少不了!

大家好&#xff0c;我是喷火龙。 目前&#xff0c;视频号是没有什么自然流量的&#xff0c;所以&#xff0c;想要出单、爆单的话&#xff0c;靠达人带货的方式才是最可靠的&#xff0c;靠达人带货是肯定要对接达人&#xff0c;并和达人沟通带货的。 下面给大家讲一讲应该怎么…

【Python】解决Python报错:TypeError: unsupported operand type(s) for ...

&#x1f9d1; 博主简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟&#xff0c;欢迎关注。提供嵌入式方向…

Kafka原生API使用Java代码-生产者-分区策略-默认分区策略轮询分区策略

文章目录 1、代码演示1.1、pom.xml1.2、KafkaProducerPartitioningStrategy.java1.2.1、ProducerConfig.LINGER_MS_CONFIG取 0 值得情况&#xff0c;不轮询1.2.2、ProducerConfig.LINGER_MS_CONFIG取 0 值得情况&#xff0c;轮询1.2.3、ProducerConfig.LINGER_MS_CONFIG取 1000…

前端应用开发实验:表单控件绑定

目录 实验目的相关知识点实验内容代码实现效果 实验目的 &#xff08;1&#xff09;熟练掌握应用v-model指令实现双向数据绑定的方法&#xff0c;学会使用 v-model指令绑定文本框、复选框、单选按钮、下拉菜单&#xff1b; &#xff08;2&#xff09;学会值绑定&#xff08;将…

Java枚举

引入&#xff1a; 当有一些类&#xff0c;希望它的成员的值是具体的有限的值&#xff0c;且只读不需要修改&#xff0c;不希望用户去自定义其他的值。 比如季节类&#xff0c;它的成员只能是春夏秋冬&#xff0c;不希望用户构造其他的值。 枚举enum&#xff1a; 枚举是一组的特…

SQL数据库多层嵌套 json转sql建表语句,SQL数据库里数组里对象数据怎么创建

1. uniapp sqlite 一个数组包含对象嵌套对象通过主外键方式插入数据库&#xff1a; // 假设有一个对象数组&#xff0c;对象中包含嵌套对象 const objectsArray [{parentObject: {id: 1,name: Parent 1,// 其他父对象属性},childObject: {id: 11,parentId: 1,name: Child 1 o…

字符串操作:写一个方法,实现字符串的反转,如:输入abc,输出cba

import java.util.Scanner; public class Test_A15 {public static void main(String[] args){String strA"";System.out.println("请输入一串字符串:");Scanner scannernew Scanner(System.in);strAscanner.next();Test_A15 T15new Test_A15();String re…

使用 LangFuse 意外被挂马!我是怎么恢复系统稳定的?

在使用 LangFuse 过程中,被意外挂马!通过一番折腾服务恢复正常~ 本文将详细介绍应对恶意脚本和进程的完整方案,包括识别、清理、恢复和预防步骤。 阿里云扫到的信息 被执行的 Base64 SUlaQnRTCmV4ZWMgJj4vZGV2L251bGwKSUhDa0hQbmQ9Li8uJChkYXRlfG1kNXN1bXxoZWFkIC1jMjApCl…

AI Agent智能体概述及原理

AI Agent概述 AI Agent旨在理解、分析和响应人类输入&#xff0c;像人类一样执行任务、做出决策并与环境互动。它们可以是遵循预定义规则的简单系统&#xff0c;也可以是根据经验学习和适应的复杂、自主的实体&#xff1b;可以是基于软件的实体&#xff0c;也可以是物理实体。…

行为型设计模式之模板模式

文章目录 概述原理结构图实现 小结 概述 模板方法模式(template method pattern)原始定义是&#xff1a;在操作中定义算法的框架&#xff0c;将一些步骤推迟到子类中。模板方法让子类在不改变算法结构的情况下重新定义算法的某些步骤。 模板方法中的算法可以理解为广义上的业…