【代码随想录】【算法训练营】【第29天】 [491]非递减子序列 [46]全排列 [47]全排列II

前言

思路及算法思维，指路 代码随想录。
题目来自 LeetCode。

day 29，周三，坚持坚持~

题目详情

[491] 非递减子序列

题目描述

491 非递减子序列

解题思路

前提：组合子集问题，可能有重复元素，收集条件为递增，至少两个元素
思路：回溯，使用used数组标识同一树层不选取重复元素，输出符合要求结点路径。
重点：不能对数组进行排序，因为要选取的是递增序列，无法改变元素的相对位置；used数组在同一树层有效，并且需要回溯。

代码实现

C语言

used数组记录同层元素是否已使用过

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/#define MAX_NUMS_SIZE 210
#define OFFSET_NUM 100int **ans;
int ansSize;
int *length;
int *path;
int pathSize;void collect()
{ans[ansSize] = (int *)malloc(sizeof(int) * pathSize);for (int i = 0; i < pathSize; i++) {ans[ansSize][i] = path[i];}length[ansSize] = pathSize;ansSize++;return ;
}void backtracking(int *nums, int numsSize, int startIdx)
{// 收集条件if (pathSize > 1) {collect();}// 退出条件if (startIdx >= numsSize) {return ;}// 递归// 同一树层usedbool used[MAX_NUMS_SIZE];for (int j = 0; j < MAX_NUMS_SIZE; j++) {used[j] = false;}for (int idx = startIdx; idx < numsSize; idx++) {// 去重: 重复元素，递减元素if ((used[nums[idx] + OFFSET_NUM] == true) || ((pathSize > 0) && (nums[idx] < path[pathSize - 1]))){continue;}// 记录path[pathSize] = nums[idx];pathSize++;used[nums[idx] + OFFSET_NUM] = true;backtracking(nums, numsSize, idx + 1);// 回溯pathSize--;// used数组不需要回溯}return ;
}int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {// 初始化ans = (int **)malloc(sizeof(int *) * 50000);ansSize = 0;length = (int *)malloc(sizeof(int) * 50000);path = (int *)malloc(sizeof(int) * numsSize);pathSize = 0;*returnSize = 0;backtracking(nums, numsSize, 0);*returnSize = ansSize;*returnColumnSizes = length;return ans;
}

[46] 全排列

题目描述

46 全排列

解题思路

前提：排列问题，元素位置不同视为不同排列结果
思路：回溯，输出叶子结点的路径
重点：不含重复数字时，used数组标记元素值是否使用。

代码实现

C语言

used数组标记元素值是否使用

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/#define MAX_NUMS  21
#define NUM_OFFSET 10int **ans;
int ansSize;
int *length;
int *path;
int pathSize;
bool *used;void collect()
{ans[ansSize] = (int *)malloc(sizeof(int) * pathSize);for (int i = 0; i < pathSize; i++) {ans[ansSize][i] = path[i];}length[ansSize] = pathSize;ansSize++;return ;
}void backtracking(int *nums, int numsSize)
{// 收集条件if (pathSize == numsSize) {collect();return ;}// 递归for (int idx = 0; idx < numsSize; idx++) {if (used[nums[idx] + NUM_OFFSET] == true) {continue;}// 保存该元素path[pathSize++] = nums[idx];used[nums[idx] + NUM_OFFSET] = true;backtracking(nums, numsSize);// 回溯pathSize--;used[nums[idx] + NUM_OFFSET] = false;}return ;
}int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {ans = (int **)malloc(sizeof(int *) * 10000);ansSize = 0;length = (int *)malloc(sizeof(int) * 10000);path = (int *)malloc(sizeof(int) * numsSize);pathSize = 0;used = (int *)malloc(sizeof(bool) * MAX_NUMS);for (int j = 0; j < MAX_NUMS; j++) {used[j] = false;}backtracking(nums, numsSize);*returnSize = ansSize;*returnColumnSizes = length;return ans;
}

[47] 全排列II

题目描述

47 全排列II

解题思路

前提：排列问题，元素位置不同视为不同排列结果
思路：回溯，输出叶子结点的路径
重点：重复数字时，used数组标记元素值是否使用完，usedLoc数组标识同一树层元素是否重复选取。

代码实现

C语言

以下3中实现方式，均为去重条件的不同，也可以视为used数组含义不同。

两个used数组分别标识元素是否使用及同一树层元素是否重复使用

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/#define MAX_NUMS 21
#define NUM_OFFSET 10int **ans;
int ansSize;
int *length;
int *path;
int pathSize;
int *used;int cmp(int *p1, int *p2)
{return *p1 > *p2;
}void initUsed(int *nums, int numsSize)
{used = (int *)malloc(sizeof(int) * MAX_NUMS);// 初始化for (int k = 0; k < MAX_NUMS; k++) {used[k] = 0;}// 统计元素数量for (int n = 0; n < numsSize; n++) {(used[nums[n] + NUM_OFFSET])++;}return ;
}void collect()
{ans[ansSize] = (int *)malloc(sizeof(int) * pathSize);for (int i = 0; i < pathSize; i++) {ans[ansSize][i] = path[i];}length[ansSize] = pathSize;ansSize++;return ;
}void backtracking(int *nums, int numsSize)
{// 退出条件if (pathSize == numsSize) {collect();return ;}// 递归// 标识同一树层元素是否使用bool usedLoc[numsSize];for (int u = 0; u < numsSize; u++) {usedLoc[u] = false;}for (int idx = 0; idx < numsSize; idx++) {// 去重if (((idx > 0) && (nums[idx] == nums[idx - 1]) && (usedLoc[idx - 1] == false)) || (used[nums[idx] + NUM_OFFSET] == 0)) {continue;}path[pathSize++] = nums[idx];(used[nums[idx] + NUM_OFFSET])--;usedLoc[idx] = true;backtracking(nums, numsSize);// 回溯pathSize--;usedLoc[idx] = false;(used[nums[idx] + NUM_OFFSET])++;}return ;
}int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {// 初始化ans = (int *)malloc(sizeof(int *) * 10000);ansSize = 0;length = (int *)malloc(sizeof(int) * 10000);path = (int *)malloc(sizeof(int) * numsSize);pathSize = 0;initUsed(nums, numsSize);// 排序qsort(nums, numsSize, sizeof(int), cmp);backtracking(nums, numsSize);*returnSize = ansSize;*returnColumnSizes = length;return ans;
}

used数组标识元素值是否使用，同一树层元素去重

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/#define MAX_NUMS 21
#define NUM_OFFSET 10int **ans;
int ansSize;
int *length;
int *path;
int pathSize;
int *used;int cmp(int *p1, int *p2)
{return *p1 > *p2;
}void initUsed(int *nums, int numsSize)
{used = (int *)malloc(sizeof(int) * MAX_NUMS);// 初始化for (int k = 0; k < MAX_NUMS; k++) {used[k] = 0;}// 统计元素数量for (int n = 0; n < numsSize; n++) {(used[nums[n] + NUM_OFFSET])++;}return ;
}void collect()
{ans[ansSize] = (int *)malloc(sizeof(int) * pathSize);for (int i = 0; i < pathSize; i++) {ans[ansSize][i] = path[i];}length[ansSize] = pathSize;ansSize++;return ;
}void backtracking(int *nums, int numsSize)
{// 退出条件if (pathSize == numsSize) {collect();return ;}// 递归// 标识同一树层元素是否使用for (int idx = 0; idx < numsSize; idx++) {// 去重if (((idx > 0) && (nums[idx] == nums[idx - 1])) || (used[nums[idx] + NUM_OFFSET] == 0)) {continue;}path[pathSize++] = nums[idx];(used[nums[idx] + NUM_OFFSET])--;backtracking(nums, numsSize);// 回溯pathSize--;(used[nums[idx] + NUM_OFFSET])++;}return ;
}int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {// 初始化ans = (int *)malloc(sizeof(int *) * 10000);ansSize = 0;length = (int *)malloc(sizeof(int) * 10000);path = (int *)malloc(sizeof(int) * numsSize);pathSize = 0;initUsed(nums, numsSize);// 排序qsort(nums, numsSize, sizeof(int), cmp);backtracking(nums, numsSize);*returnSize = ansSize;*returnColumnSizes = length;return ans;
}

used数组标识是否使用，同一树层是否已有重复元素，或该元素是否已经选取过

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/#define MAX_NUMS 21
#define NUM_OFFSET 10int **ans;
int ansSize;
int *length;
int *path;
int pathSize;
bool *used;int cmp(int *p1, int *p2)
{return *p1 > *p2;
}void collect()
{ans[ansSize] = (int *)malloc(sizeof(int) * pathSize);for (int i = 0; i < pathSize; i++) {ans[ansSize][i] = path[i];}length[ansSize] = pathSize;ansSize++;return ;
}void backtracking(int *nums, int numsSize)
{// 退出条件if (pathSize == numsSize) {collect();return ;}// 递归for (int idx = 0; idx < numsSize; idx++) {// 去重: 该元素已使用，或 同一树层已有重复元素if (((idx > 0) && (nums[idx] == nums[idx - 1]) && (used[idx - 1] == false)) || (used[idx] == true)) {continue;}path[pathSize++] = nums[idx];used[idx] = true;backtracking(nums, numsSize);// 回溯pathSize--;used[idx] = false;}return ;
}int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {// 初始化ans = (int *)malloc(sizeof(int *) * 10000);ansSize = 0;length = (int *)malloc(sizeof(int) * 10000);path = (int *)malloc(sizeof(int) * numsSize);pathSize = 0;used = (bool *)malloc(sizeof(bool) * numsSize);// 初始化for (int k = 0; k < numsSize; k++) {used[k] = false;}// 排序qsort(nums, numsSize, sizeof(int), cmp);backtracking(nums, numsSize);*returnSize = ansSize;*returnColumnSizes = length;return ans;
}

今日收获

1. 组合子集问题：书上所有结点，输出路径，可能会用到used数组去重元素；
2. 组合排列问题：叶子结点，输出路径，used数组去重元素或元素值。