当前位置：首页 > news >正文

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

news 来源：原创 2024/9/21 19:07:33

题目

在这里插入图片描述
题目链接：
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;}}}
};