diff options
author | Jack Sangdahl <[email protected]> | 2025-01-10 20:20:54 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-10 20:20:54 +0100 |
commit | 906231fba337f2e2a04f5ce33dff6c9cd43b7d97 (patch) | |
tree | 552740d6eef9ef8481b310b59b8dff438951cb73 | |
parent | fbd68b1d63c63150c6ea0e927668fe5f18293be7 (diff) | |
download | leetcode-906231fba337f2e2a04f5ce33dff6c9cd43b7d97.tar.gz leetcode-906231fba337f2e2a04f5ce33dff6c9cd43b7d97.zip |
491. non-decreasing subsequences
-rw-r--r-- | non_decreasing_subseq.c | 60 | ||||
-rw-r--r-- | non_decreasing_subseq.cpp | 25 |
2 files changed, 52 insertions, 33 deletions
diff --git a/non_decreasing_subseq.c b/non_decreasing_subseq.c index 9f46243..69c235c 100644 --- a/non_decreasing_subseq.c +++ b/non_decreasing_subseq.c @@ -1,59 +1,75 @@ // 491. Non-decreasing Subsequences -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * given: integer array 'nums' * return: all possible different non-decreasing subsequences * of given array with at least two elements. return value can be in any order - * - * returns an array of arrays of size '*returnSize' - * sizes of the arrays are returned as '*returnColumnSizes' array - * note: both returned array and '*columnSizes' array must be malloc'd - * (assume caller free()'s) */ int **ans, ansTop, *path, pathTop, *len; -int findUsed(int *uset, int usetSize, int key) { +bool find_used(int *uset, int usetSize, int key) { for (int i = 0; i < usetSize; i++) if (uset[i] == key) - return 1; - return 0; + return true; + return false; } -void backtracking(int *nums, int numsSize, int startIdx) { +void backtrack(int *nums, int numsSize, int startIdx) { if (pathTop >= 2) { - int *tmp = malloc(sizeof(int) * pathTop); + int *tmp = (int *)malloc(pathTop * sizeof(int)); for (int i = 0; i < pathTop; i++) tmp[i] = path[i]; len[ansTop] = pathTop; ans[ansTop++] = tmp; } - int *uset = malloc(sizeof(int) * numsSize), usetTop = 0; + int *uset = (int *)malloc(numsSize * sizeof(int)), usetTop = 0; for (int i = startIdx; i < numsSize; i++) { if (pathTop > 0 && nums[i] < path[pathTop - 1] || - findUsed(uset, usetTop, nums[i])) + find_used(uset, usetTop, nums[i])) continue; uset[usetTop++] = nums[i]; path[pathTop++] = nums[i]; - backtracking(nums, numsSize, i + 1); + backtrack(nums, numsSize, i + 1); pathTop--; } } int **findSubsequences(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) { - ans = malloc(sizeof(int *) * 40000); - path = malloc(sizeof(int) * numsSize); - len = malloc(sizeof(int) * 40000); - pathTop = ansTop = 0; - backtracking(nums, numsSize, 0); + ans = (int **)malloc(10000 * sizeof(int *)); + path = (int *)malloc(numsSize * sizeof(int)); + len = (int *)malloc(10000 * sizeof(int)); + pathTop = 0; + ansTop = 0; + backtrack(nums, numsSize, 0); *returnSize = ansTop; - *returnColumnSizes = malloc(sizeof(int) * ansTop); + *returnColumnSizes = (int *)malloc(ansTop * sizeof(int)); for (int i = 0; i < ansTop; i++) (*returnColumnSizes)[i] = len[i]; return ans; } -int main() { int nums1[] = {4, 6, 7, 7}, nums2[] = {4, 4, 3, 2, 1}; } +int main() { + int n1[] = {4, 6, 7, 7}, n2[] = {4, 4, 3, 2, 1}; + int rs1, rs2, *rcs1, *rcs2; + int **fs1 = findSubsequences(n1, ARRAY_SIZE(n1), &rs1, &rcs1); + int **fs2 = findSubsequences(n2, ARRAY_SIZE(n2), &rs2, &rcs2); + for (int i = 0; i < rs1; i++) { + for (int j = 0; j < *rcs1; j++) + printf("%d ", fs1[i][j]); + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs2; i++) { + for (int j = 0; j < *rcs2; j++) + printf("%d ", fs2[i][j]); + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs1; i++) + free(fs1[i]); + for (int i = 0; i < rs2; i++) + free(fs2[i]); +} diff --git a/non_decreasing_subseq.cpp b/non_decreasing_subseq.cpp index 0b45930..b94510f 100644 --- a/non_decreasing_subseq.cpp +++ b/non_decreasing_subseq.cpp @@ -10,19 +10,18 @@ class Solution { public: - vvd(int) findSubsequences(vector<int> &nums) { + vector<vector<int>> findSubsequences(vector<int> &nums) { set<vector<int>> seqs = {vector<int>(0)}; for (int i = 0; i < nums.size(); i++) { - vvd(int) built(seqs.size()); + vector<vector<int>> built(seqs.size()); copy(seqs.begin(), seqs.end(), built.begin()); - for (auto s : built) { + for (auto s : built) if (s.empty() || nums[i] >= s.back()) { s.push_back(nums[i]); seqs.insert(s); } - } } - vvd(int) ans; + vector<vector<int>> ans; for (auto s : seqs) if (s.size() > 1) ans.push_back(s); @@ -32,12 +31,16 @@ public: int main() { Solution obj; - vector<int> nums1 = {4, 6, 7, 7}, nums2 = {4, 4, 3, 2, 1}; - for (auto i : obj.findSubsequences(nums1)) + vector<int> n1 = {4, 6, 7, 7}, n2 = {4, 4, 3, 2, 1}; + for (auto i : obj.findSubsequences(n1)) { for (auto j : i) - cout << j << ' '; - cout << endl; - for (auto i : obj.findSubsequences(nums2)) + printf("%d ", j); + printf("\n"); + } + printf("\n"); + for (auto i : obj.findSubsequences(n2)) { for (auto j : i) - cout << j << ' '; + printf("%d ", j); + printf("\n"); + } } |