1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
// 3170. Lexicographically Minimum String After Removing Stars
#include "leetcode.h"
/*
* you are given a string 's'. it may contain any number of '*' characters. your
* task to remove all '*' characters. while there is a '*' character, do the
* following: delete the leftmost '*' and the smallest non-'*' character to its
* left. if there are several smallest characters, you can delete any of them.
* return the lexicographically smallest resulting string after removing all '*'
* characters.
*/
struct node {
char c;
int idx;
};
struct pq {
int (*cmp)(const void *, const void *);
int size;
int capacity;
void **data;
};
struct node *node_init(char c, int idx) {
struct node *obj = (struct node *)malloc(sizeof(struct node));
obj->c = c;
obj->idx = idx;
return obj;
}
int cmp(const void *a, const void *b) {
char c1 = ((struct node *)a)->c;
char c2 = ((struct node *)b)->c;
int n1 = ((struct node *)a)->idx;
int n2 = ((struct node *)b)->idx;
if (c1 < c2)
return 1;
if (c1 > c2)
return -1;
if (n1 > n2)
return 1;
if (n1 < n2)
return -1;
return 0;
}
struct pq *pq_init(int capacity, int (*cmp)(const void *, const void *)) {
struct pq *obj = (struct pq *)malloc(sizeof(struct pq));
obj->cmp = cmp;
obj->size = 0;
obj->capacity = capacity;
obj->data = (void **)malloc(capacity * sizeof(void *));
for (int i = 0; i < capacity; i++)
obj->data[i] = NULL;
return obj;
}
void pq_swap(struct pq *obj, const int key1, const int key2) {
void *tmp = obj->data[key1];
obj->data[key1] = obj->data[key2];
obj->data[key2] = tmp;
return;
}
void pq_repair_bottom(struct pq *obj) {
int child = obj->size - 1, parent = (child - 1) / 2;
while (child > 0 && obj->cmp(obj->data[child], obj->data[parent]) == 1) {
pq_swap(obj, child, parent);
child = parent;
parent = (child - 1) / 2;
}
return;
}
void pq_push(struct pq *obj, void *item) {
assert(obj->size < obj->capacity);
obj->data[obj->size++] = item;
pq_repair_bottom(obj);
return;
}
void pq_repair_top(struct pq *obj) {
int parent = 0, child = parent * 2 + 1;
while (child < obj->size) {
if (child + 1 < obj->size &&
obj->cmp(obj->data[child + 1], obj->data[child]) == 1)
child++;
if (obj->cmp(obj->data[parent], obj->data[child]) == 1)
break;
pq_swap(obj, parent, child);
parent = child;
child = parent * 2 + 1;
}
return;
}
void *pq_pop(struct pq *obj) {
assert(obj->size > 0);
pq_swap(obj, 0, obj->size - 1);
obj->size--;
pq_repair_top(obj);
return obj->data[obj->size];
}
void pq_free(struct pq *obj) {
for (int i = 0; i < obj->size; i++)
free(obj->data[i]);
free(obj->data);
free(obj);
return;
}
char *clearStars(char *s) {
const int n = strlen(s);
char *ans = (char *)malloc((n + 1) * sizeof(char));
struct pq *pq = pq_init(n, cmp);
for (int i = 0; i < n; i++) {
if (s[i] != '*') {
struct node *n = node_init(*(s + i), i);
pq_push(pq, n);
} else if (pq->size > 0) {
struct node *curr = pq_pop(pq);
s[curr->idx] = '#';
}
}
pq_free(pq);
int idx = 0;
for (; *s; s++)
if (*s != '#' && *s != '*')
ans[idx++] = *s;
ans[idx] = '\0';
return ans;
}
int main() {
char *s1 = "aaba*", *cs1 = clearStars(s1);
char *s2 = "abc", *cs2 = clearStars(s2);
printf("%s\n", cs1); // expect: aab
printf("%s\n", cs2); // expect: abc
}
|