Skip to content

Commit abcf598

Browse files
begeekmyfriendbegeekmyfriend
committed
Improvement
Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>
1 parent adf424d commit abcf598

File tree

3 files changed

+68
-48
lines changed

3 files changed

+68
-48
lines changed

‎053_maximum_subarray/max_subarray.c

Lines changed: 37 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,9 +2,42 @@
22
#include <stdlib.h>
33
#include <limits.h>
44

5+
static int recursive(int *nums, int lo, int hi)
6+
{
7+
if (lo == hi) {
8+
return nums[lo];
9+
}
10+
11+
int ce = (hi - lo) / 2;
12+
int left_max = recursive(nums, lo, lo + ce);
13+
int right_max = recursive(nums, hi - ce, hi);
14+
15+
int i;
16+
int left_border = 0, left_border_max = INT_MIN;
17+
for (i = ce; i >= lo; i--) {
18+
left_border += nums[i];
19+
if (left_border > left_border_max) {
20+
left_border_max = left_border;
21+
}
22+
}
23+
24+
int right_border = 0, right_border_max = INT_MIN;
25+
for (i = ce + 1; i <= hi; i++) {
26+
right_border += nums[i];
27+
if (right_border > right_border_max) {
28+
right_border_max = right_border;
29+
}
30+
}
31+
32+
int sum = left_border_max + right_border_max;
33+
int max = left_max > right_max ? left_max : right_max;
34+
return sum > max ? sum : max;
35+
}
36+
537
static int maxSubArray(int* nums, int numsSize)
638
{
7-
int i, max = INT_MIN, len = 0;
39+
#if 1
40+
int i, len = 0, max = INT_MIN;
841
for (i = 0; i < numsSize; i++) {
942
len += nums[i];
1043
/* Calculate maximum each time in loop */
@@ -14,6 +47,9 @@ static int maxSubArray(int* nums, int numsSize)
1447
}
1548
}
1649
return max;
50+
#else
51+
return recursive(nums, 0, numsSize - 1);
52+
#endif
1753
}
1854

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

‎098_validate_binary_search_tree/valid_bst.c

Lines changed: 12 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,39 +1,41 @@
11
#include <stdio.h>
22
#include <stdlib.h>
33
#include <stdbool.h>
4+
#include <limits.h>
45

56
struct TreeNode {
67
int val;
78
struct TreeNode *left;
89
struct TreeNode *right;
910
};
1011

11-
static int last_val = -1;
12-
13-
static bool traverse(struct TreeNode* node)
12+
static bool traverse(struct TreeNode* node, int *last_val)
1413
{
1514
bool ret = true;
1615

1716
if (ret && node->left != NULL) {
18-
ret = traverse(node->left);
17+
ret = traverse(node->left, last_val);
1918
}
2019

21-
if (last_val != -1 && node->val <= last_val) {
20+
if (node->val <= *last_val) {
2221
return false;
2322
}
24-
last_val = node->val;
23+
*last_val = node->val;
2524

2625
if (ret && node->right != NULL) {
27-
ret = traverse(node->right);
26+
ret = traverse(node->right, last_val);
2827
}
2928
return ret;
3029
}
3130

3231
static bool isValidBST(struct TreeNode* root)
3332
{
34-
if (root == NULL) return true;
35-
last_val = -1;
36-
return traverse(root);
33+
if (root == NULL) {
34+
return true;
35+
} else {
36+
int last_val = -1;
37+
return traverse(root, &last_val);
38+
}
3739
}
3840

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

‎102_binary_tree_level_order_traversal/bst_bfs.c

Lines changed: 19 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -29,48 +29,41 @@ struct list_head {
2929
struct list_head *next, *prev;
3030
};
3131

32-
static inline void
33-
INIT_LIST_HEAD(struct list_head *list)
32+
static inline void INIT_LIST_HEAD(struct list_head *list)
3433
{
3534
list->next = list->prev = list;
3635
}
3736

38-
static inline int
39-
list_empty(const struct list_head *head)
37+
static inline int list_empty(const struct list_head *head)
4038
{
4139
return (head->next == head);
4240
}
4341

44-
static inline void
45-
__list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
42+
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
4643
{
4744
next->prev = new;
4845
new->next = next;
4946
new->prev = prev;
5047
prev->next = new;
5148
}
5249

53-
static inline void
54-
list_add(struct list_head *_new, struct list_head *head)
50+
static inline void list_add(struct list_head *_new, struct list_head *head)
5551
{
5652
__list_add(_new, head, head->next);
5753
}
5854

59-
static inline void
60-
list_add_tail(struct list_head *_new, struct list_head *head)
55+
static inline void list_add_tail(struct list_head *_new, struct list_head *head)
6156
{
6257
__list_add(_new, head->prev, head);
6358
}
6459

65-
static inline void
66-
__list_del(struct list_head *entry)
60+
static inline void __list_del(struct list_head *entry)
6761
{
6862
entry->next->prev = entry->prev;
6963
entry->prev->next = entry->next;
7064
}
7165

72-
static inline void
73-
list_del(struct list_head *entry)
66+
static inline void list_del(struct list_head *entry)
7467
{
7568
__list_del(entry);
7669
entry->next = entry->prev = NULL;
@@ -135,41 +128,30 @@ static int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSiz
135128
}
136129

137130
struct list_head free_list;
138-
struct list_head bfs_queue0;
139-
struct list_head bfs_queue1;
131+
struct list_head q0;
132+
struct list_head q1;
140133
INIT_LIST_HEAD(&free_list);
141-
INIT_LIST_HEAD(&bfs_queue0);
142-
INIT_LIST_HEAD(&bfs_queue1);
134+
INIT_LIST_HEAD(&q0);
135+
INIT_LIST_HEAD(&q1);
143136

144137
int **results = malloc(BST_MAX_LEVEL * sizeof(int *));
145138
*columnSizes = malloc(BST_MAX_LEVEL * sizeof(int));
146139
memset(*columnSizes, 0, BST_MAX_LEVEL * sizeof(int));
147140

148141
int level = 0;
149-
struct bfs_node *new;
150-
if (root->left != NULL) {
151-
new = node_new(&free_list, root->left);
152-
list_add_tail(&new->link, &bfs_queue0);
153-
}
154-
155-
if (root->right != NULL) {
156-
new = node_new(&free_list, root->right);
157-
list_add_tail(&new->link, &bfs_queue0);
158-
}
159-
160-
results[level] = malloc(sizeof(int));
161-
results[level][0] = root->val;
162-
(*columnSizes)[level] = 1;
142+
struct bfs_node *new = node_new(&free_list, root);
143+
list_add_tail(&new->link, &q0);
163144

164-
while (!list_empty(&bfs_queue0) || !list_empty(&bfs_queue1)) {
165-
if (++level & 1) {
166-
queue(&bfs_queue0, &bfs_queue1, &free_list, results, *columnSizes, level);
145+
while (!list_empty(&q0) || !list_empty(&q1)) {
146+
if (level & 0x1) {
147+
queue(&q1, &q0, &free_list, results, *columnSizes, level);
167148
} else {
168-
queue(&bfs_queue1, &bfs_queue0, &free_list, results, *columnSizes, level);
149+
queue(&q0, &q1, &free_list, results, *columnSizes, level);
169150
}
151+
level++;
170152
}
171153

172-
*returnSize = level + 1;
154+
*returnSize = level;
173155
return results;
174156
}
175157

0 commit comments

Comments
 (0)