Google Drive
Gist
Clipboard
contributed by < TimidCactus >
目前 95 分，欠常數。
用 bitwise operator 用有寫程式的感覺。
> gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
> lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 43 bits physical, 48 bits virtual
CPU(s): 128
On-line CPU(s) list: 0-127
Thread(s) per core: 2
Core(s) per socket: 64
Socket(s): 1
NUMA node(s): 1
Vendor ID: AuthenticAMD
CPU family: 23
Model: 49
Model name: AMD Ryzen Threadripper 3990X 64-Core Processor
Stepping: 0
Frequency boost: enabled
CPU MHz: 1980.432
CPU max MHz: 2900.0000
CPU min MHz: 2200.0000
BogoMIPS: 5789.17
Virtualization: AMD-V
L1d cache: 2 MiB
L1i cache: 2 MiB
L2 cache: 32 MiB
L3 cache: 256 MiB
NUMA node0 CPU(s): 0-127
依據指示著手修改 queue.[ch] 和連帶的檔案。
使用完整漢語描述
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, l) {
list_del(node);
q_release_element(list_entry(node, element_t, list));
}
free(l);
}
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = (element_t *) malloc(sizeof(element_t));
if (!node)
return false;
node->value = strdup(s);
if (!node->value) {
free(node);
return false;
}
list_add(&node->list, head);
return true;
}
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = (element_t *) malloc(sizeof(element_t));
if (!node)
return false;
node->value = strdup(s);
if (!node->value) {
free(node);
return false;
}
list_add_tail(&node->list, head);
return true;
}
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_entry(head->next, element_t, list);
list_del(&node->list);
int32_t len =
min(min(bufsize - 1, strlen(node->value) + 1), abs((intptr_t) sp) - 1);
size_t i = len;
while (len >= 0) {
intptr_t mask = (-!!(len ^ i));
sp[len] = node->value[len] & mask;
len--;
}
return node;
}
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_entry(head->prev, element_t, list);
list_del(&node->list);
int32_t len =
min(min(bufsize - 1, strlen(node->value) + 1), abs((intptr_t) sp) - 1);
size_t i = len;
while (len >= 0) {
intptr_t mask = (-!!(len ^ i));
sp[len] = node->value[len] & mask;
len--;
}
return node;
}
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
size_t len = 0;
struct list_head *node;
list_for_each (node, head)
len++;
return len;
}
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *node = NULL, *next = head->next, *prev = head->prev;
while (!node) {
if (next == prev)
node = next;
if (next->next == prev)
node = prev;
next = next->next;
prev = prev->prev;
}
list_del(node);
q_release_element(list_entry(node, element_t, list));
return true;
}
有更好的寫法嗎? 這一點都不“good taste”
有辦法只用一個條件式嗎?
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
char *del_patten = NULL;
element_t *node, *safe;
for (node = list_entry(head->next, element_t, list),
safe = list_entry(node->list.next, element_t, list);
&safe->list != head;
node = safe, safe = list_entry(node->list.next, element_t, list)) {
intptr_t mask =
-(!strcmp(node->value, safe->value)) | (node->value == del_patten);
del_patten = (char *) ((intptr_t) safe->value & mask);
if (del_patten && !strcmp(del_patten, node->value)) {
list_del(&node->list);
q_release_element(node);
}
}
if (del_patten && !strcmp(del_patten, node->value)) {
list_del(&node->list);
q_release_element(node);
}
return true;
}
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
if (safe == head)
return;
list_del(node);
list_add(node, safe);
safe = node->next;
}
}
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
node->next = node->prev;
node->prev = safe;
}
node->next = node->prev;
node->prev = safe;
}
struct list_head *merge(struct list_head *a, struct list_head *b)
{
struct list_head *sorted, **temp, **tail = &sorted;
while (a && b) {
temp = (strcmp(list_entry(a, element_t, list)->value,
list_entry(b, element_t, list)->value) <= 0)
? &a
: &b;
*tail = *temp;
*temp = (*temp)->next;
tail = &((*tail)->next);
}
*tail = (struct list_head *) ((intptr_t) a | (intptr_t) b);
return sorted;
}
struct list_head *merge_sort(struct list_head *head)
{
if (!head->next)
return head;
struct list_head *mid, *last;
for (mid = head, last = head->next; last && last->next;
mid = mid->next, last = last->next->next)
;
last = mid;
mid = mid->next;
last->next = NULL;
head = merge_sort(head);
mid = merge_sort(mid);
return merge(head, mid);
}
void q_sort(struct list_head *head)
{
if (!head || (head->next == head->prev))
return;
struct list_head *tail;
head->prev->next = NULL;
tail = merge_sort(head->next);
head->next = tail;
tail->prev = head;
while (tail->next) {
tail->next->prev = tail;
tail = tail->next;
}
head->prev = tail;
tail->next = head;
}
同上
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe