Skip to content

Commit 3649f22

Browse files
begeekmyfriendbegeekmyfriend
committed
Refine
Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>
1 parent b5ea034 commit 3649f22

File tree

3 files changed

+47
-51
lines changed

3 files changed

+47
-51
lines changed

‎039_combination_sum/combination_sum.c

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
#include <string.h>
44

55
static void dfs(int *nums, int size, int start, int target, int *stack,
6-
int len, int **results, int *column_sizes, int *count)
6+
int len, int **results, int *count, int *column_sizes)
77
{
88
int i;
99
if (target == 0) {
@@ -24,17 +24,17 @@ static void dfs(int *nums, int size, int start, int target, int *stack,
2424

2525
/**
2626
** Return an array of arrays of size *returnSize.
27-
** The sizes of the arrays are returned as *columnSizes array.
28-
** Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
27+
** The sizes of the arrays are returned as *returnColumnSizes array.
28+
** Note: Both returned array and *returnColumnSizes array must be malloced, assume caller calls free().
2929
**/
30-
static int** combinationSum(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize)
30+
static int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int **returnColumnSizes)
3131
{
32-
int cap = 100;
33-
int *stack = malloc(target * sizeof(int));
32+
int cap = 200;
33+
int *stack = malloc(candidatesSize * sizeof(int));
3434
int **results = malloc(cap * sizeof(int *));
35-
*columnSizes = malloc(cap * sizeof(int));
35+
*returnColumnSizes = malloc(cap * sizeof(int));
3636
*returnSize = 0;
37-
dfs(candidates, candidatesSize, 0, target, stack, 0, results, *columnSizes, returnSize);
37+
dfs(candidates, candidatesSize, 0, target, stack, 0, results, returnSize, *returnColumnSizes);
3838
return results;
3939
}
4040

@@ -53,7 +53,7 @@ int main(int argc, char **argv)
5353
}
5454

5555
int *sizes;
56-
int **lists = combinationSum(nums, argc - 2, target, &sizes, &count);
56+
int **lists = combinationSum(nums, argc - 2, target, &count, &sizes);
5757
for (i = 0; i < count; i++) {
5858
for (j = 0; j < sizes[i]; j++) {
5959
printf("%d ", lists[i][j]);

‎040_combination_sum_ii/combination_sum.c

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ static int compare(const void *a, const void *b)
99
}
1010

1111
static void dfs(int *nums, int size, int start, int target, int *solution, int len,
12-
bool *used, int **results, int *column_sizes, int *count)
12+
bool *used, int **results, int *count, int *column_sizes)
1313
{
1414
int i;
1515
if (target == 0) {
@@ -23,7 +23,7 @@ static void dfs(int *nums, int size, int start, int target, int *solution, int l
2323
if (i > 0 && !used[i - 1] && nums[i - 1] == nums[i]) continue;
2424
used[i] = true;
2525
solution[len] = nums[i];
26-
dfs(nums, size, i + 1, target - nums[i], solution, len + 1, used, results, column_sizes, count);
26+
dfs(nums, size, i + 1, target - nums[i], solution, len + 1, used, results, count, column_sizes);
2727
used[i] = false;
2828
}
2929
}
@@ -32,20 +32,20 @@ static void dfs(int *nums, int size, int start, int target, int *solution, int l
3232

3333
/**
3434
** Return an array of arrays of size *returnSize.
35-
** The sizes of the arrays are returned as *columnSizes array.
36-
** Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
35+
** The sizes of the arrays are returned as *returnColumnSizes array.
36+
** Note: Both returned array and *returnColumnSizes array must be malloced, assume caller calls free().
3737
**/
38-
static int** combinationSum(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize)
38+
static int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes)
3939
{
4040
qsort(candidates, candidatesSize, sizeof(int), compare);
4141

4242
int *solution = malloc(target * sizeof(int));
4343
int **results = malloc(100 * sizeof(int *));
4444
bool *used = malloc(candidatesSize);
4545
memset(used, false, candidatesSize);
46-
*columnSizes = malloc(100 * sizeof(int));
46+
*returnColumnSizes = malloc(100 * sizeof(int));
4747
*returnSize = 0;
48-
dfs(candidates, candidatesSize, 0, target, solution, 0, used, results, *columnSizes, returnSize);
48+
dfs(candidates, candidatesSize, 0, target, solution, 0, used, results, returnSize, *returnColumnSizes);
4949
return results;
5050
}
5151

@@ -64,7 +64,7 @@ int main(int argc, char **argv)
6464
}
6565

6666
int *sizes;
67-
int **lists = combinationSum(nums, argc - 2, target, &sizes, &count);
67+
int **lists = combinationSum(nums, argc - 2, target, &count, &sizes);
6868
for (i = 0; i < count; i++) {
6969
for (j = 0; j < sizes[i]; j++) {
7070
printf("%d ", lists[i][j]);

‎042_trapping_rain_water/trap_water.c

Lines changed: 30 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -1,49 +1,45 @@
11
#include <stdio.h>
22
#include <stdlib.h>
33

4+
5+
static inline int max(int a, int b)
6+
{
7+
return a > b ? a : b;
8+
}
9+
10+
static inline int min(int a, int b)
11+
{
12+
return a < b ? a : b;
13+
}
14+
415
static int trap(int* height, int heightSize)
516
{
6-
if (heightSize < 2) {
17+
if (heightSize < 1) {
718
return 0;
819
}
920

10-
int i, j, top0 = -1, top1 = -1, sum = 0, level = 0;
11-
for (i = 0; i < heightSize; i++) {
12-
if (height[i] > 0) {
13-
top0 = i;
14-
break;
15-
}
21+
int i;
22+
int *lh = malloc(heightSize * sizeof(int));
23+
int *rh = malloc(heightSize * sizeof(int));
24+
25+
/* restore the max height in the left side of [i] (included) */
26+
lh[0] = height[0];
27+
for (i = 1; i < heightSize; i++) {
28+
lh[i] = max(height[i], lh[i - 1]);
1629
}
1730

18-
while (i < heightSize) {
19-
top1 = -1;
20-
for (j = i + 1; j < heightSize; j++) {
21-
if (height[j] >= height[j - 1]) {
22-
if (top1 < 0 || height[j] >= height[top1]) {
23-
top1 = j;
24-
}
25-
if (height[j] >= height[top0]) {
26-
break;
27-
}
28-
}
29-
}
30-
31-
if (top1 >= 0) {
32-
int level = height[top0] < height[top1] ? height[top0] : height[top1];
33-
while (i < top1) {
34-
if (level > height[i]) {
35-
sum += level - height[i];
36-
}
37-
i++;
38-
}
39-
top0 = top1;
40-
i = top1;
41-
} else {
42-
i = j;
43-
}
31+
/* restore the max height in the right side of [i] (included) */
32+
rh[heightSize - 1] = height[heightSize - 1];
33+
for (i = heightSize - 2; i >= 0; i--) {
34+
rh[i] = max(height[i], rh[i + 1]);
35+
}
36+
37+
int capacity = 0;
38+
for (i = 0; i < heightSize; i++) {
39+
capacity += min(lh[i], rh[i]) - height[i];
4440
}
4541

46-
return sum;
42+
return capacity;
4743
}
4844

4945
int main(int argc, char **argv)

0 commit comments

Comments
 (0)