Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit8229f94

Browse files
Add C++ implementation
Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>
1 parentec1138e commit8229f94

File tree

13 files changed

+395
-419
lines changed

13 files changed

+395
-419
lines changed

‎0030_substring_with_concatenation_of_all_words/concatenation.c‎

Lines changed: 52 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -3,48 +3,67 @@
33
#include<stdbool.h>
44
#include<string.h>
55

6+
67
#definecontainer_of(ptr,type,member) \
78
((type *)((char *)(ptr) - (size_t)&(((type *)0)->member)))
89

910
#definelist_entry(ptr,type,member) \
1011
container_of(ptr, type, member)
1112

12-
#definehlist_for_each(pos,head) \
13-
for (pos =(head)->first;pos; pos = pos->next)
14-
15-
structhlist_node;
13+
#definelist_for_each_entry(pos,head,member) \
14+
for (pos =list_entry((head)->next, typeof(*pos), member); \
15+
&(pos)->member != (head); \
16+
pos = list_entry((pos)->member.next, typeof(*pos), member))
1617

17-
structhlist_head {
18-
structhlist_node*first;
18+
structlist_head {
19+
structlist_head*next,*prev;
1920
};
2021

21-
structhlist_node {
22-
structhlist_node*next,**pprev;
22+
structword_node {
23+
char*word;
24+
intindex;
25+
structlist_headlink;
2326
};
2427

25-
staticinlinevoidINIT_HLIST_HEAD(structhlist_head*h) {
26-
h->first=NULL;
28+
staticinlinevoidINIT_LIST_HEAD(structlist_head*list)
29+
{
30+
list->next=list->prev=list;
2731
}
2832

29-
staticinlineinthlist_empty(structhlist_head*h) {
30-
return !h->first;
33+
staticinlineintlist_empty(conststructlist_head*head)
34+
{
35+
return (head->next==head);
3136
}
3237

33-
staticinlinevoidhlist_add_head(structhlist_node*n,structhlist_head*h)
38+
staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_head*next)
3439
{
35-
if (h->first!=NULL) {
36-
h->first->pprev=&n->next;
37-
}
38-
n->next=h->first;
39-
n->pprev=&h->first;
40-
h->first=n;
40+
next->prev=new;
41+
new->next=next;
42+
new->prev=prev;
43+
prev->next=new;
4144
}
4245

43-
structword_node {
44-
structhlist_nodenode;
45-
char*word;
46-
intindex;
47-
};
46+
staticinlinevoidlist_add(structlist_head*_new,structlist_head*head)
47+
{
48+
__list_add(_new,head,head->next);
49+
}
50+
51+
staticinlinevoidlist_add_tail(structlist_head*_new,structlist_head*head)
52+
{
53+
__list_add(_new,head->prev,head);
54+
}
55+
56+
staticinlinevoid__list_del(structlist_head*entry)
57+
{
58+
entry->next->prev=entry->prev;
59+
entry->prev->next=entry->next;
60+
}
61+
62+
staticinlinevoidlist_del(structlist_head*entry)
63+
{
64+
__list_del(entry);
65+
entry->next=entry->prev=NULL;
66+
}
4867

4968
staticinlineintBKDRHash(char*s,size_tsize)
5069
{
@@ -56,26 +75,23 @@ static inline int BKDRHash(char *s, size_t size)
5675
returnhash %size;
5776
}
5877

59-
staticintfind(char*word,structhlist_head*heads,intsize)
78+
staticintfind(char*word,structlist_head*heads,intsize)
6079
{
80+
structword_node*wn;
6181
inthash=BKDRHash(word,size);
62-
structhlist_node*pos;
63-
hlist_for_each(pos,&heads[hash]) {
64-
structword_node*wn=list_entry(pos,structword_node,node);
82+
list_for_each_entry(wn,&heads[hash],link) {
6583
if (!strcmp(wn->word,word)) {
6684
returnwn->index;
6785
}
6886
}
6987
return-1;
7088
}
7189

72-
staticvoidadd(char**words,intindex,structhlist_head*heads,intsize,int*freqs)
90+
staticvoidadd(char**words,intindex,structlist_head*heads,intsize,int*freqs)
7391
{
74-
inthash=BKDRHash(words[index],size);
75-
structhlist_node*pos;
7692
structword_node*wn;
77-
hlist_for_each(pos,&heads[hash]) {
78-
wn=list_entry(pos,structword_node,node);
93+
inthash=BKDRHash(words[index],size);
94+
list_for_each_entry(wn,&heads[hash],link) {
7995
if (!strcmp(wn->word,words[index])) {
8096
freqs[wn->index]++;
8197
return;
@@ -84,7 +100,7 @@ static void add(char **words, int index, struct hlist_head *heads, int size, int
84100
wn=malloc(sizeof(*wn));
85101
wn->word=words[index];
86102
wn->index=index;
87-
hlist_add_head(&wn->node,&heads[hash]);
103+
list_add(&wn->link,&heads[hash]);
88104
freqs[wn->index]++;
89105
}
90106

@@ -101,9 +117,9 @@ static int *findSubstring(char *s, char **words, int wordsSize, int *returnSize)
101117

102118
inti,j,cap=10000,count=0;
103119
inthash_size=wordsSize;
104-
structhlist_head*heads=malloc(hash_size*sizeof(*heads));
120+
structlist_head*heads=malloc(hash_size*sizeof(*heads));
105121
for (i=0;i<hash_size;i++) {
106-
INIT_HLIST_HEAD(&heads[i]);
122+
INIT_LIST_HEAD(&heads[i]);
107123
}
108124

109125
int*freqs=malloc(wordsSize*sizeof(int));

‎0105_construct_binary_tree_from_preorder_and_inorder_traversal/binary_tree_build.c‎

Lines changed: 42 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -1,71 +1,67 @@
11
#include<stdio.h>
22
#include<stdlib.h>
33

4+
45
#definecontainer_of(ptr,type,member) \
56
((type *)((char *)(ptr) - (size_t)&(((type *)0)->member)))
67

78
#definelist_entry(ptr,type,member) \
89
container_of(ptr, type, member)
910

10-
#definehlist_for_each(pos,head) \
11-
for (pos = (head)->first; pos; pos = pos->next)
11+
#definelist_for_each_entry(pos,head,member) \
12+
for (pos = list_entry((head)->next, typeof(*pos), member); \
13+
&(pos)->member != (head); \
14+
pos = list_entry((pos)->member.next, typeof(*pos), member))
1215

13-
structhlist_node;
16+
structlist_head {
17+
structlist_head*next,*prev;
18+
};
1419

15-
structhlist_head {
16-
structhlist_node*first;
20+
structTreeNode {
21+
intval;
22+
structTreeNode*left;
23+
structTreeNode*right;
1724
};
1825

19-
structhlist_node {
20-
structhlist_node*next,**pprev;
26+
structorder_node {
27+
structlist_headlink;
28+
intval;
29+
intindex;
2130
};
2231

23-
staticinlinevoidINIT_HLIST_HEAD(structhlist_head*h) {
24-
h->first=NULL;
32+
staticinlinevoidINIT_LIST_HEAD(structlist_head*list)
33+
{
34+
list->next=list->prev=list;
2535
}
2636

27-
staticinlineinthlist_empty(structhlist_head*h) {
28-
return !h->first;
37+
staticinlineintlist_empty(conststructlist_head*head)
38+
{
39+
return (head->next==head);
2940
}
3041

31-
staticinlinevoidhlist_add_head(structhlist_node*n,structhlist_head*h)
42+
staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_head*next)
3243
{
33-
if (h->first!=NULL) {
34-
h->first->pprev=&n->next;
35-
}
36-
n->next=h->first;
37-
n->pprev=&h->first;
38-
h->first=n;
44+
next->prev=new;
45+
new->next=next;
46+
new->prev=prev;
47+
prev->next=new;
3948
}
4049

41-
staticinlinevoidhlist_del(structhlist_node*n)
50+
staticinlinevoidlist_add(structlist_head*_new,structlist_head*head)
4251
{
43-
structhlist_node*next=n->next;
44-
structhlist_node**pprev=n->pprev;
45-
*pprev=next;
46-
if (next!=NULL) {
47-
next->pprev=pprev;
48-
}
52+
__list_add(_new,head,head->next);
4953
}
5054

51-
structTreeNode {
52-
intval;
53-
structTreeNode*left;
54-
structTreeNode*right;
55-
};
56-
57-
structorder_node {
58-
structhlist_nodenode;
59-
intval;
60-
intindex;
61-
};
55+
staticinlinevoidlist_add_tail(structlist_head*_new,structlist_head*head)
56+
{
57+
__list_add(_new,head->prev,head);
58+
}
6259

63-
staticintfind(intnum,intsize,structhlist_head*heads)
60+
staticintfind(intnum,intsize,structlist_head*heads)
6461
{
65-
structhlist_node*p;
62+
structorder_node*on;
6663
inthash= (num<0 ?-num :num) %size;
67-
hlist_for_each(p,&heads[hash]) {
68-
structorder_node*on=list_entry(p,structorder_node,node);
64+
list_for_each_entry(on,&heads[hash],link) {
6965
if (num==on->val) {
7066
returnon->index;
7167
}
@@ -74,7 +70,7 @@ static int find(int num, int size, struct hlist_head *heads)
7470
}
7571

7672
staticstructTreeNode*dfs(int*preorder,intpre_low,intpre_high,int*inorder,
77-
intin_low,intin_high,structhlist_head*in_heads,intsize)
73+
intin_low,intin_high,structlist_head*in_heads,intsize)
7874
{
7975
if (in_low>in_high||pre_low>pre_high) {
8076
returnNULL;
@@ -87,21 +83,21 @@ static struct TreeNode *dfs(int *preorder, int pre_low, int pre_high, int *inord
8783
returntn;
8884
}
8985

90-
staticvoidnode_add(intval,intindex,intsize,structhlist_head*heads)
86+
staticvoidnode_add(intval,intindex,intsize,structlist_head*heads)
9187
{
9288
structorder_node*on=malloc(sizeof(*on));
9389
on->val=val;
9490
on->index=index;
9591
inthash= (val<0 ?-val :val) %size;
96-
hlist_add_head(&on->node,&heads[hash]);
92+
list_add(&on->link,&heads[hash]);
9793
}
9894

99-
staticstructTreeNode*buildTree(int*preorder,intpreorderSize,int*inorder,intinorderSize)
95+
structTreeNode*buildTree(int*preorder,intpreorderSize,int*inorder,intinorderSize)
10096
{
10197
inti;
102-
structhlist_head*in_heads=malloc(inorderSize*sizeof(*in_heads));
98+
structlist_head*in_heads=malloc(inorderSize*sizeof(*in_heads));
10399
for (i=0;i<inorderSize;i++) {
104-
INIT_HLIST_HEAD(&in_heads[i]);
100+
INIT_LIST_HEAD(&in_heads[i]);
105101
}
106102
for (i=0;i<inorderSize;i++) {
107103
node_add(inorder[i],i,inorderSize,in_heads);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp