Algorithm

Algorithm

Index

位运算

test code 
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
#include<stdio.h>
/* 二进制转化函数 */
void printBinary(int n){
    for(int i=9;i>=0;i--){//int 类型最多31 long long 应该用1LL<<i
        printf("%d",(n&(1<<i))==0?0:1);
    }
    puts("");
}

int main()
{
    int n=255;
    printBinary(n);
    int b=0b11111111;
    printf("%d\n",b);
    printf("%x\n",b);
    int c=0xff;
    printf("%d\n",c);
    puts("--------------");
    /* 与或非 */
    int g = 0b0001010;
	int h = 0b0001100;
    printBinary(g|h);
    printBinary(g&h);
    printBinary(g^h);
    puts("--------------");
    /* 左移 右移 表示 乘 和 除 2^i */
    int k=10;
    printf("%d\n",k<<1);
    printf("%d\n",k<<2);
    printf("%d\n",k<<3);
    printf("%d\n",k>>1);
    printf("%d\n",k>>2);
    printf("%d\n",k>>3);
    return 0;
}
output 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0011111111
255
ff
255
--------------
0000001110
0000001000
0000000110
--------------
20
40
80
5
2
1

三傻排序

Selection Sort 
1
2
3
4
5
6
7
for(int i=0;i<arr.size();i++){
    int minIndex=i;
    for(int j=i+1;j<size()-1;j++){
        if(arr[j]<arr[minIndex]) minIndex=j;
    }
    swap(arr[i],arr[minIndex]);
}
Bubble Sort 
1
2
3
4
5
for(int i=0;i<arr.size()-1,i++){
    for(int j=0;j<arr.size()-i-1,j++){
        if(arr[j]>arr[j+1]) swap(arr[i],arr[i+1]);
    }
}
Insertion Sort 
1
2
3
4
5
for(int i=1;i<arr.size(),i++){
    for(j=i-1;j>=0&&arr[j]>arr[j+1];j--){
        swap(arr[j],arr[j+1]);
    }
}

二分

Code 
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
#include<stdio.h>

typedef long long ll;

int check(ll n, ll k, ll mid) {
}

ll solve(ll n, ll k) {
    ll left = 1, right = n;
    ll ans = 1;
    while (left <= right) {
        ll mid = left + (right - left) / 2;
        if (check(n, k, mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

int main() {
    ll T;
    scanf("%lld", &T);
    while (T--) {
        ll n, k;
        scanf("%lld%lld", &n, &k);      
        for (ll i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }
        printf("%lld\n", solve(n, k));
    }
    return 0;
}

链表

单链表

Code 
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include<stdio.h>
#include<stdlib.h>

typedef struct ListNode{
    int val;
    struct ListNode *next;
}ListNode;

/* 打印链表 */
void printList(ListNode*L){
    ListNode* cur=L;
    while(cur!=NULL){
        printf("%d ",cur->val);
        cur=cur->next;
    }
    puts("");
}

/* 尾插法创建链表 */
void InsertTail(ListNode** L,int val){
    /* 如果这个是个空链表，L=NULL */
    if(*L==NULL){
        *L=(ListNode*)malloc(sizeof(ListNode));
        (*L)->val=val;
        (*L)->next=NULL;
        return ;
    }
    /* 找到尾节点
    尾节点next指向NULL
    定义一个指针cur->next==NULL 说明cur已经指向最后一个节点 */
    ListNode* cur=*L;
    while(cur->next!=NULL){
        cur=cur->next;
    }
    /* 创建新节点 */
    ListNode* newNode=(ListNode*)malloc(sizeof(ListNode));
    newNode->val=val;
    newNode->next=NULL;
    cur->next=newNode;
}

/* 头插法创建链表 */
void InsertHead(ListNode** L,int val){
    ListNode* newNode=(ListNode*)malloc(sizeof(ListNode));
    newNode->val=val;
    newNode->next=*L;
    *L=newNode;
}

/* 中间插入 */
void InsertMid(ListNode* preNode,int val){
    if(preNode==NULL) return ;
    ListNode* newNode=(ListNode*)malloc(sizeof(ListNode));
    newNode->val=val;
    newNode->next=preNode->next;
    preNode->next=newNode;
}

/* 直接删除节点 */
void  RemoveNode1(ListNode** L,int val){
    /* 判断首节点是否为空 */
    if(*L==NULL) return ;
    /* 判断首节点值是否为val */
    if((*L)->val==val){
        ListNode* cur=*L;
        *L=(*L)->next;
        free(cur);
    }
    /* 不为首节点，删除中间节点 */
    ListNode* cur=*L;
    while(cur->next!=NULL){
        if(cur->next->val==val){
            ListNode* temp=cur->next;
            cur->next=cur->next->next;
            free(temp);
        }else{
            cur=cur->next;
        }
    }
}

/* 虚拟头节点删除 */
void RemoveNode2(ListNode** L,int val){
    ListNode* dummyHead=(ListNode*)malloc(sizeof(ListNode));
    dummyHead->next=*L;
    ListNode* cur=dummyHead;
    while(cur->next!=NULL){
        if(cur->next->val==val){
            ListNode* temp=cur->next;
            cur->next=cur->next->next;
            free(temp);
        }else{
            cur=cur->next;
        }
    }
}

/* 查找指定值的节点 */
ListNode* FindNode(ListNode* L, int val) {
    ListNode* cur = L;
    while (cur != NULL) {
        if (cur->val == val) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

void FreeList(ListNode** L){
    ListNode* cur=*L;
    while(cur!=NULL){
        ListNode* temp=cur;
        cur=cur->next;
        free(temp);
    }
    *L=NULL;
}

int main()
{
    ListNode* L=NULL;

    /* 使用尾插法 */
    for(int i=0;i<10;i++){
        InsertTail(&L,i*10);
    }
    printList(L);

    /* 使用头插法 */
    for(int i=0;i<10;i++){
        InsertHead(&L,i*10);
    }
    printList(L);

    /* 使用中间插入 */
    ListNode* NewNode=L->next->next;
    InsertMid(NewNode,78);
    printList(L);

    /* 查找节点 */
    ListNode* node = FindNode(L, 78);
    if (node != NULL) {
        printf("Find node: %d\n", node->val);
    } else {
        printf("Not found\n");
    }
    free(node);

    /* 直接删除特定节点 */
    RemoveNode1(&L,90);
    printList(L);

    /* 虚拟头节点删除 */
    RemoveNode2(&L,0);
    printList(L);

    /* 释放链表 */
    FreeList(&L);
    return 0;
}
output 
1
2
3
4
5
6
0 10 20 30 40 50 60 70 80 90
90 80 70 60 50 40 30 20 10 0 0 10 20 30 40 50 60 70 80 90      
90 80 70 78 60 50 40 30 20 10 0 0 10 20 30 40 50 60 70 80 90   
Find node: 78
80 70 78 60 50 40 30 20 10 0 0 10 20 30 40 50 60 70 80
80 70 78 60 50 40 30 20 10 10 20 30 40 50 60 70 80

双向链表

暂无

练习

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
		public static ListNode reverseList(ListNode head) {
			ListNode pre = null;
			ListNode next = null;
			while (head != null) {
				next = head.next;
				head.next = pre;
				pre = head;
				head = next;
			}
			return pre;
		}
	}
Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
		public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
			if (head1 == null || head2 == null) {
				return head1 == null ? head2 : head1;
			}
			ListNode head = head1.val <= head2.val ? head1 : head2;//令head指向两个链表中较小的头节点
			ListNode cur1 = head.next;//双指针
			ListNode cur2 = head == head1 ? head2 : head1;
			ListNode pre = head;
			while (cur1 != null && cur2 != null) {
				if (cur1.val <= cur2.val) {
					pre.next = cur1;
					cur1 = cur1.next;
				} else {
					pre.next = cur2;
					cur2 = cur2.next;
				}
				pre = pre.next;
			}
			pre.next = cur1 != null ? cur1 : cur2;//补充剩下的
			return head;
		}
	}
Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *head=nullptr,*tail =nullptr;
    int carry=0;
    while(l1||l2){
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int sum = n1 + n2 + carry;
        if(!head){
            head = tail = new ListNode(sum%10);//创建头节点
        }else{
            tail->next = new ListNode(sum%10);//否则添加节点
            tail = tail->next;
        }
        carry = sum/10;
        if(l1) l1 = l1->next;
        if(l2) l2 = l2->next;
        if(carry) tail->next = new ListNode(carry);
    }
    return head;
}
Code 
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
class Solution {
		public static ListNode partition(ListNode head, int x) {
			ListNode leftHead = null, leftTail = null; // < x的区域
			ListNode rightHead = null, rightTail = null; // >=x的区域
			ListNode next = null;
			while (head != null) {
				next = head.next;
				head.next = null;
				if (head.val < x) {
					if (leftHead == null) {
						leftHead = head;
					} else {
						leftTail.next = head;
					}
					leftTail = head;
				} else {
					if (rightHead == null) {
						rightHead = head;
					} else {
						rightTail.next = head;
					}
					rightTail = head;
				}
				head = next;
			}
			if (leftHead == null) {
				return rightHead;
			}
			// < x的区域有内容！
			leftTail.next = rightHead;
			return leftHead;
		}
	}

队列和栈

Code 
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
#include<stdio.h>
#include<string.h>

typedef long long ll;
#define N 100010
ll stack[N];
ll minstack[N];

void push(int *top,ll x,int *mintop){
    stack[(*top)++]=x;
    if(*mintop==0||x<minstack[*mintop-1]){
        minstack[(*mintop)++]=x;
    }
}

void pop(int *top,int *mintop){
    stack[(*top)--]=0;
    if(stack[*top]==minstack[*mintop-1]){
        minstack[(*mintop)--]=0;
    }
}

ll getMin(int *mintop){
    return minstack[*mintop-1];
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,top=0,mintop=0;
        scanf("%d",&n);
        char str[10];
        ll num;
        for(int i=0;i<n;i++){
            scanf("%s",str);
            if(strcmp(str,"MIN")==0){
                if(top==0) printf("NULL\n");
                else printf("%lld\n",getMin(&mintop));
            }
            if(strcmp(str,"PUSH")==0){
                scanf("%lld",&num);
                push(&top,num,&mintop);
            }
            if(strcmp(str,"POP")==0){
                pop(&top,&mintop);
            }
        }
    }
    return 0;
}

algorithm
#algorithm
Algorithm
http://example.com/2024/10/24/Algorithm/
Author
Anfsity
Posted on
October 24, 2024
Licensed under