TOP101题解 | BM55#没有重复项数字的全排列#
没有重复项数字的全排列
https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @author Senky * @date 2023.08.26 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1 * * @param num int整型一维数组 * @param numLen int num数组长度 * @return int整型二维数组 * @return int* returnSize 返回数组行数 * @return int** returnColumnSizes 返回数组列数 */ #include <string.h> void backtrack(int* num, int numLen,int* flag, int* path, int depth, int** result ,int* returnSize) { /*层数为长度时,即结束*/ if(depth == numLen) { // result[*returnSize] = (int*)malloc(sizeof(int) * numsLen); // memcpy(result[*returnSize], path, sizeof(int) * numsLen); // (*returnSize)++; result[(*returnSize)++] = path; return ; } else { for(int i = 0; i < numLen; i++) { if(!flag[i])/*未标记*/ { path[depth] = num[i];/*记录元素*/ flag[i] = 1;/*该元素打上标记*/ backtrack(num, numLen, flag, path, depth + 1, result, returnSize);/*递归*/ flag[i] = 0;/*该depth位使用元素num[i],使用完后清除标记*/ } } } } int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) { // write code here /*算出n!即排列组合的个数*/ int total = 1; for(int i = 1; i <= numLen; i++) { total *= i; } *returnSize = 0;/*初始为0*/ *returnColumnSizes = (int*)malloc(total * sizeof(int)); int* flag = (int*)calloc(numLen,sizeof(int));/*标记数组,初始默认为0*/ int** result = (int**)malloc(total * sizeof(int*));/*结果数组*/ int* path = (int*)malloc(numLen * sizeof(int));/*结果路径,每条路径都会保存在结果数组中*/ backtrack(num, numLen, flag, path, 0, result, returnSize); for (int i = 0; i < *returnSize; i++) { (*returnColumnSizes)[i] = numLen; } return result; }
TOP101-BM系列 文章被收录于专栏
系列的题解