算法学习过程入门篇(2)

入门

排序

sort函数

#include <algorithm>
using namespace std;//两行必须添加
sort(stu + num -k,stu + num, cmp);

sort(a,b,cmp);a起始位置，b结束的下一个位置，cmp排序条件（可没有，没有就是按增序排列）

sort(a,a + 4);

若a为数组，表示排序从第一个排到第四个，因为数组下标从0开始

cmp

bool cmp(student a, student b) {if(a.score != b.score) return a.score > b.score;else return strcmp(a.id,b.id) < 0;
}

1.如果两个学生分数不相同，那么分数高的排在前面
2.否则，将按姓名字典序小地排在前面

解释strcmp函数

strcmp(s1,s2)当s1的字典序小于s2时返回负数，相等返回0，大于返回正数
cmp中就是表示a的字典序小于b的字典序

排名

分数不同的排名不同，分数相同的排名相同但占用一个位置

stu[0].r = 1;for(int j = 1; j < n; j++) {if(stu[j].score == stu[j -1].score) {stu[j].r = stu[j - 1].r;}else {stu[j].r = i + 1;}}

散列

字符串hash初步

int hashFunc(char S[], int len) {int id = 0;for(int i = 0; i < len; i++) {if(S[i] >= 'A' && S[i] <= 'Z') {id = id * 52 + (S[i] - 'A');}else if(S[i] >= 'a' && S[i] <= 'z'){id = id * 52 + (S[i] - 'a') + 26;}}return id;
}

递归

全排列

#include <cstdio>
const int maxn = 11;
int n, P[maxn], hashTable[maxn] = {false};
void generateP(int index) {if(index == n+1) {for(int i = 1; i <= n; i++) {printf("%d",P[i]);}printf("\n");return;}for(int x = 1; x <= n; x++) {if(hashTable[x] == false) {P[index] = x;hashTable[x] = true;generateP(index + 1);hashTable[x] = false;}}
}
int main() {n = 3;generateP(1);return 0;
}

n皇后

#include <cstdio>
int count = 0;
void generateP(int index) {if(index == n+1) {bool flag = true;for(int i = 1; i <= n; i++) {for(int j = i + 1; j <= n; j++) {if(abs(i - j) == abs(P[i] - P[j]))flag = false;}}if(flag) count++;return;}for(int x = 1; x <= n; x++) {if(hashTable[x] == false) {P[index] = x;hashTable[x] = true;generateP(index + 1);hashTable[x] = false;}}
}

贪心

区间贪心

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10;
struct Interval {int x, y;
}I[maxn];
bool cmp(Interval a, Interval b) {if(a.x != b.x) return a.x > b.x;else return a.y < b.y;
}
int main() {int n;while(scanf("%d",&n), n != 0) {for(int i = 0; i < n; i++) {scanf("%d %d", &I[i].x, &I[i].y);}sort(I, I + n, cmp);int ans = 1,lastX = I[0].x;for(int i = 0; i < n; i++) {if(I[i].y <= lastX) {lastX = I[i].x;ans++;}}printf("%d\n",ans);}return 0;
}

二分

二分法

#include <cstdio>
int binarySearch(int A[], int left, int right, int x) {int mid;while(left <= right) {mid = left + (right - left) / 2;if(A[mid] == x) return mid;else if(A[mid] < x) {left = mid + 1;}else {right = mid -1;}}return -1;
}
int main() {
const int n = 10;int A[n] = {1,3,4,6,7,8,10,11,12,15};printf("%d %d",binarySearch(A,0,n-1,6),binarySearch(A,0,n-1,9));return 0;
}

快速幂

typedef long long LL;
LL binaryPow(LL a, LL b, LL m) {if(b == 0) return 1;if(b % 2 == 1) return a * binaryPow(a, b-1, m) % m;else {LL mul = binaryPow(a, b / 2, m);return mul * mul % m;}
}

迭代写法

typedef long long LL;
LL binaryPoq(LL a, LL b, LL m) {LL ans = 1;while(b > 0) {if(b & 1) {ans = ans * a % m;}a = a * a % m;b >> = 1;}return ans;
}

two points

two points

while(i < j) {if(a[i] + a[j] == m) {printf("%d %d\n", i, j);i++;j--;}else if(a[i] + a[j] < m) {i++;}else{j--;}
}

归并

递归实现

const int maxn = 100;
void merge(int A[], int L1, int R1, int L2, int R2) {int i =L1, j = L2;int temp[maxn], index = 0;while(i <= R1 && j <= R2) {if(A[i] <= A[j]) {temp[index++] = A[i++];}else {temp[index++] = A[j++];}}while(i <= R1) temp[index++] = A[i++];while(j <= R2) temp[index++] = A[j++];for(int i = 0; i < index; i++) {A[L1 + i] = temp[i];}
}
void mergeSort(int A[], int left, int right) {if(left < right) {int mid = (left + right) / 2;mergeSort(A,left,mid);mergeSort(A,mid+1,right);merge(A,left,mid,mid+1,right);}
}

快速排序

int Partition(int A[], int left, int right) {int temp = A[0];while(left < right) {while(left < right && A[right] > temp) right--;A[left] = A[right];while(left < right && A[left] < temp) left++;A[right] = A[left];}A[left] = temp;return left;
}
void quickSort(int A[], int left, int right) {if(left < right) {int pos = Partition(A, left, right);quickSort(A, left, pos - 1);quickSort(A, pos + 1, right);}
}

随机选择算法

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int randPartition(int A[], int left, int rigt) {int p = (round(1.0*rand()/RAND_MAX*(right - left) + left);swap(A[p], A[left]);int temp = A[left];while(left < right) {while(left < right && A[right] > temp) right--;A[left] = A[right];while(left < right && A[left] < temp) left++;A[right] = A[left];}A[left] = temp;return left;
}
void randSelect(int A[], int left, int right, int K) {if(left == right) return;int p =randPartition(A, left, right);int M = p - left + 1;if(K == M) return;if(K < M) {randSelect(A, left, p - 1, K);} else {randSelect(A, p + 1, right, K - M);}
}
int main() {srand((unsigned)time(NULL));int sum = 0, sum1 = 0;scanf("%d", &n);for(int i = 0; i < n; i++) {scanf("%d",&A[i]);sum += A[i];}randSelect(A, 0, n - 1, n / 2);for(int i = 0; i < n / 2; i++) {sum1 += A[i];}printf("%d\n", (sum - sum1) - sum1);return 0;
}

算法学习过程入门篇(2)

入门

排序

sort函数

#include <algorithm>
using namespace std;//两行必须添加
sort(stu + num -k,stu + num, cmp);

sort(a,b,cmp);a起始位置，b结束的下一个位置，cmp排序条件（可没有，没有就是按增序排列）

sort(a,a + 4);

若a为数组，表示排序从第一个排到第四个，因为数组下标从0开始

cmp

bool cmp(student a, student b) {if(a.score != b.score) return a.score > b.score;else return strcmp(a.id,b.id) < 0;
}

1.如果两个学生分数不相同，那么分数高的排在前面
2.否则，将按姓名字典序小地排在前面

解释strcmp函数

strcmp(s1,s2)当s1的字典序小于s2时返回负数，相等返回0，大于返回正数
cmp中就是表示a的字典序小于b的字典序

排名

分数不同的排名不同，分数相同的排名相同但占用一个位置

stu[0].r = 1;for(int j = 1; j < n; j++) {if(stu[j].score == stu[j -1].score) {stu[j].r = stu[j - 1].r;}else {stu[j].r = i + 1;}}

散列

字符串hash初步

int hashFunc(char S[], int len) {int id = 0;for(int i = 0; i < len; i++) {if(S[i] >= 'A' && S[i] <= 'Z') {id = id * 52 + (S[i] - 'A');}else if(S[i] >= 'a' && S[i] <= 'z'){id = id * 52 + (S[i] - 'a') + 26;}}return id;
}

递归

全排列

#include <cstdio>
const int maxn = 11;
int n, P[maxn], hashTable[maxn] = {false};
void generateP(int index) {if(index == n+1) {for(int i = 1; i <= n; i++) {printf("%d",P[i]);}printf("\n");return;}for(int x = 1; x <= n; x++) {if(hashTable[x] == false) {P[index] = x;hashTable[x] = true;generateP(index + 1);hashTable[x] = false;}}
}
int main() {n = 3;generateP(1);return 0;
}

n皇后

#include <cstdio>
int count = 0;
void generateP(int index) {if(index == n+1) {bool flag = true;for(int i = 1; i <= n; i++) {for(int j = i + 1; j <= n; j++) {if(abs(i - j) == abs(P[i] - P[j]))flag = false;}}if(flag) count++;return;}for(int x = 1; x <= n; x++) {if(hashTable[x] == false) {P[index] = x;hashTable[x] = true;generateP(index + 1);hashTable[x] = false;}}
}

贪心

区间贪心

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10;
struct Interval {int x, y;
}I[maxn];
bool cmp(Interval a, Interval b) {if(a.x != b.x) return a.x > b.x;else return a.y < b.y;
}
int main() {int n;while(scanf("%d",&n), n != 0) {for(int i = 0; i < n; i++) {scanf("%d %d", &I[i].x, &I[i].y);}sort(I, I + n, cmp);int ans = 1,lastX = I[0].x;for(int i = 0; i < n; i++) {if(I[i].y <= lastX) {lastX = I[i].x;ans++;}}printf("%d\n",ans);}return 0;
}

二分

二分法

#include <cstdio>
int binarySearch(int A[], int left, int right, int x) {int mid;while(left <= right) {mid = left + (right - left) / 2;if(A[mid] == x) return mid;else if(A[mid] < x) {left = mid + 1;}else {right = mid -1;}}return -1;
}
int main() {
const int n = 10;int A[n] = {1,3,4,6,7,8,10,11,12,15};printf("%d %d",binarySearch(A,0,n-1,6),binarySearch(A,0,n-1,9));return 0;
}

快速幂

typedef long long LL;
LL binaryPow(LL a, LL b, LL m) {if(b == 0) return 1;if(b % 2 == 1) return a * binaryPow(a, b-1, m) % m;else {LL mul = binaryPow(a, b / 2, m);return mul * mul % m;}
}

迭代写法

typedef long long LL;
LL binaryPoq(LL a, LL b, LL m) {LL ans = 1;while(b > 0) {if(b & 1) {ans = ans * a % m;}a = a * a % m;b >> = 1;}return ans;
}

two points

two points

while(i < j) {if(a[i] + a[j] == m) {printf("%d %d\n", i, j);i++;j--;}else if(a[i] + a[j] < m) {i++;}else{j--;}
}

归并

递归实现

const int maxn = 100;
void merge(int A[], int L1, int R1, int L2, int R2) {int i =L1, j = L2;int temp[maxn], index = 0;while(i <= R1 && j <= R2) {if(A[i] <= A[j]) {temp[index++] = A[i++];}else {temp[index++] = A[j++];}}while(i <= R1) temp[index++] = A[i++];while(j <= R2) temp[index++] = A[j++];for(int i = 0; i < index; i++) {A[L1 + i] = temp[i];}
}
void mergeSort(int A[], int left, int right) {if(left < right) {int mid = (left + right) / 2;mergeSort(A,left,mid);mergeSort(A,mid+1,right);merge(A,left,mid,mid+1,right);}
}

快速排序

int Partition(int A[], int left, int right) {int temp = A[0];while(left < right) {while(left < right && A[right] > temp) right--;A[left] = A[right];while(left < right && A[left] < temp) left++;A[right] = A[left];}A[left] = temp;return left;
}
void quickSort(int A[], int left, int right) {if(left < right) {int pos = Partition(A, left, right);quickSort(A, left, pos - 1);quickSort(A, pos + 1, right);}
}

随机选择算法

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int randPartition(int A[], int left, int rigt) {int p = (round(1.0*rand()/RAND_MAX*(right - left) + left);swap(A[p], A[left]);int temp = A[left];while(left < right) {while(left < right && A[right] > temp) right--;A[left] = A[right];while(left < right && A[left] < temp) left++;A[right] = A[left];}A[left] = temp;return left;
}
void randSelect(int A[], int left, int right, int K) {if(left == right) return;int p =randPartition(A, left, right);int M = p - left + 1;if(K == M) return;if(K < M) {randSelect(A, left, p - 1, K);} else {randSelect(A, p + 1, right, K - M);}
}
int main() {srand((unsigned)time(NULL));int sum = 0, sum1 = 0;scanf("%d", &n);for(int i = 0; i < n; i++) {scanf("%d",&A[i]);sum += A[i];}randSelect(A, 0, n - 1, n / 2);for(int i = 0; i < n / 2; i++) {sum1 += A[i];}printf("%d\n", (sum - sum1) - sum1);return 0;
}