一、491 非递减子序列
本题不能按照前面的方法来判断重复数字,因为数组本来就带顺序属性,不能移动。
主要在于怎么选择子序列:首先同层的处理,需要判断,当前层前面出现过的数字,后面不能再使用(很重要!!);另外,如果path头部数字和当前数字不是递增的,那么需要跳过。
int* path;
int** result;
//int used[201];
int path_index;
int resize;
int* recolsize;
void backtracking(int* nums, int numsSize, int startidx)
{
if(path_index > 1)
{
result[resize] = (int*)malloc(sizeof(int) * path_index);
memcpy(result[resize], path, path_index * sizeof(int));
recolsize[resize] = path_index;
resize++;
}
int used[201] = {0};
for(int i = startidx; i < numsSize; i++)
{
/**不满足条件的情况**/
if((path_index > 0 && nums[i] < path[path_index -1]) || (used[nums[i] + 100] == 1))//path[path_index -1]是top元素
{
continue;
}
path[path_index++] = nums[i];
used[nums[i] + 100] = 1;
backtracking(nums, numsSize, i+ 1);
path_index--;
}
}
int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
path = (int*)malloc(sizeof(int) * 20);
result = (int**)malloc(sizeof(int*) * 50000);
recolsize = (int*)malloc(sizeof(int) * 50000);
path_index = 0;
resize = 0;
*returnSize = 0;
*returnColumnSizes = NULL;
if(numsSize <= 0)
{
return NULL;
}
backtracking(nums, numsSize, 0);
*returnSize = resize;
*returnColumnSizes = recolsize;
return result;
}
二、46 全排列
全排列是找所有可能的组合,因此,不需要用startindx来拆分了,数字都会重复使用,但是在纵向迭代时候,需要记录这个值是否使用过,如果使用过,那么跳出;
int** result;
int* path;
int path_idx;
int* used;
int resize;
int* recolsize;
void backtracking(int* nums, int numsSize, int* used)
{
if(path_idx == numsSize)
{
result[resize] = (int*)malloc(sizeof(int) * path_idx);
recolsize[resize] = path_idx;
memcpy(result[resize], path, path_idx * sizeof(int));
resize++;
return;
}
for(int i = 0; i < numsSize; i++)
{
if(used[i] == 1)
{
continue;
}
path[path_idx++] = nums[i];
used[i] = 1;
backtracking(nums, numsSize, used);
used[i] = 0;
path_idx--;
}
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
result = (int*)malloc(sizeof(int*) * 50000);
path = (int*)malloc(sizeof(int) * 10);
int* used = (int*)calloc(10, sizeof(int));//malloc(sizeof(int) * 10);
path_idx = 0;
resize = 0;
recolsize = (int*)malloc(sizeof(int) * 50000);
*returnSize = 0;
*returnColumnSizes = NULL;
if(numsSize <= 0)
{
return NULL;
}
backtracking(nums, numsSize, used);
*returnColumnSizes = recolsize;
*returnSize = resize;
return result;
}
三、全排列II
主要是理解used在树枝和树层的含义!
void sortArr(int* arr, int size)
{
for(int i = 0; i < size; i++)
{
for(int j = i + 1; j < size; j++)
{
if(arr[i] > arr[j])
{
int tmp = 0;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}
int** result;
int* path;
int path_idx;
int* used;
int resize;
int* recolsize;
// used[i - 1] == true,说明同一树枝nums[i - 1]使用过
// used[i - 1] == false,说明同一树层nums[i - 1]使用过
// 如果同一树层nums[i - 1]使用过则直接跳过
void backtracking(int* nums, int numsSize, int* used)
{
if(path_idx == numsSize)
{
result[resize] = (int*)malloc(sizeof(int) * path_idx);
recolsize[resize] = path_idx;
memcpy(result[resize], path, path_idx * sizeof(int));
resize++;
return;
}
for(int i = 0; i < numsSize; i++)
{
if(i > 0 && (used[i -1] == 0) && (nums[i] == nums[i -1]))
{
continue;
}
if(used[i] == 1)
{
continue;
}
path[path_idx++] = nums[i];
used[i] = 1;
backtracking(nums, numsSize, used);
used[i] = 0;
path_idx--;
}
}
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
result = (int*)malloc(sizeof(int*) * 50000);
path = (int*)malloc(sizeof(int) * 10);
int* used = (int*)calloc(10, sizeof(int));//malloc(sizeof(int) * 10);
path_idx = 0;
resize = 0;
recolsize = (int*)malloc(sizeof(int) * 50000);
*returnSize = 0;
*returnColumnSizes = NULL;
if(numsSize <= 0)
{
return NULL;
}
sortArr(nums, numsSize);
backtracking(nums, numsSize, used);
*returnColumnSizes = recolsize;
*returnSize = resize;
return result;
}