【代码随想录】【算法训练营】【第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 100
int **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 ;
}
// 递归
// 同一树层used
bool 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 10
int **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 10
int **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 10
int **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 10
int **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数组去重元素或元素值。