【算法笔记自学】入门篇（2）—

4.1排序

自己写的题解

#include <stdio.h>
#include <stdlib.h>

void selectSort(int A[], int n) {
    for(int i = 0; i < n - 1; i++) { // 修正索引范围
        int k = i;
        for(int j = i + 1; j < n; j++) { // 修正索引范围
            if(A[j] < A[k]) {
                k = j;
            }
        }
        if (k != i) { // 仅在需要时进行交换
            int temp = A[i];
            A[i] = A[k];
            A[k] = temp;
        }
    }
}

int main() {
    int n = 0;
    scanf("%d", &n);
    int A[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    selectSort(A, n); // 直接传递数组名
    for(int i = 0; i < n; i++) {
        if(i!=n-1)
        {
            printf("%d ", A[i]);
        }
        else
        {
            printf("%d", A[i]);
        }
    }
    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

自己写的题解

#include <stdio.h>
#include <stdlib.h>
void insertSort(int A[], int n) {
    for(int i=1;i<=n-1;i++){
        int temp=A[i],j=i;
        while(j>0&&temp<A[j-1]){
            A[j]=A[j-1];
            j--;
        }
        A[j]=temp;
    }
}

int main() {
    int n = 0;
    scanf("%d", &n);
    int A[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    insertSort(A, n); // 直接传递数组名
    for(int i = 0; i < n; i++) {
        if(i!=n-1)
        {
            printf("%d ", A[i]);
        }
        else
        {
            printf("%d", A[i]);
        }
    }
    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

4.2散列

#include <stdio.h>
#include <stdlib.h>

const int maxn = 100010;
int hashTable[maxn] = {0};

int main() {
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        if (x >= 0 && x < maxn) { // 确保x在合法范围内
            hashTable[x]++;
        }
    }
    for (int i = 0; i < maxn; i++) { // 修正遍历范围
        if (hashTable[i] != 0) {
            printf("%d %d\n", i, hashTable[i]); // 修正输出格式
        }
    }
    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

标答

#include <cstdio>
#include <cstring>

const int MAXN = 26;
const int MAXL = 1001;
char str1[MAXL], str2[MAXL];
bool hashTable[MAXN] = {false};

int getHashKey(char c) {
    return c - 'a';
}

int main () {
    scanf("%s%s", str1, str2);
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    for (int i = 0; i < len1; i++) {
        hashTable[getHashKey(str1[i])] = true;
    }
    for (int i = 0; i < len2; i++) {
        printf("%d", hashTable[getHashKey(str2[i])]);
        printf(i < len2 - 1 ? " " : "\n");
    }
    return 0;
}

#include <cstdio>

const int MAXN = 26 * 26 * 26;
const int MAXL = 1001;
char str[MAXL];
int hashTable[MAXN] = {0};

int getHashKey(char s[]) {
    return (s[0] - 'A') * 26 * 26 + (s[1] - 'A') * 26 + (s[2] - 'A');
}

int main () {
    int n, m;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        hashTable[getHashKey(str)]++;
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%s", str);
        printf("%d", hashTable[getHashKey(str)]);
        printf(i < m - 1 ? " " : "\n");
    }
    return 0;
}

4.3递归

#include <stdio.h>
#include <stdlib.h>


void print(int n) {
    if (n == 0) {
        printf("讲你妹的故事啊！快点去睡觉！！！\n");
    } else {
        printf("从前有座山，山上有座庙\n庙里有一个老和尚和一个小和尚\n睡前老和尚给小和尚讲故事：\n");
        print(n - 1);
        printf("然后老和尚和小和尚就睡觉啦\n");
    }
}

int main() {
    int n;
    scanf("%d", &n);
    print(n);
    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

#include <stdio.h>
#include <stdlib.h>


int F(int n) {
    if(n==1)return 1;
    if(n==2)return 1;
    if(n>2)return F(n-1)+F(n-2);
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d",F(n));
    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
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(i<n ? " " : "\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;
    scanf("%d",&n);
    generateP(1);
    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

4.4贪心

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100000;    // 箱子数量上限
int a[MAXN];                // 箱子数组
int main() {
    int n, maxW;            // 箱子数量、载重
    scanf("%d%d", &n, &maxW);
    for (int i = 0; i < n; i++) {    // 输入各箱子重量
        scanf("%d", &a[i]);
    }
    sort(a, a + n);                  // 将箱子按重量从小到大排序
    int num = 0, sum = 0;            // 最大箱子数量、最大累计重量
    for (int i = 0; i < n; i++) {    // 从小到大遍历箱子
        if (sum + a[i] <= maxW) {    // 如果加上当前箱子的重量之后没有超过载重
            num++;                   // 最大箱子数量加1
            sum += a[i];             // 最大累计重量加上当前箱子的重量
        } else {                     // 如果超过载重，那么退出循环
            break;
        }
    }
    printf("%d %d", num, sum);       // 输出最大箱子数量和最大累计重量
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
struct Interval {    // 区间结构体定义
    int l, r;
} interval[MAXN];    // 区间数组

bool cmp(Interval a, Interval b) {    // 区间的比较函数
    if (a.l != b.l) {                 // 如果左端点不同，那么按左端点从大到小
        return a.l > b.l;
    } else {                          // 否则，按右端点从小到大
        return a.r < b.r;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {         // 输入n个区间的左右端点
        scanf("%d%d", &interval[i].l, &interval[i].r);
    }
    sort(interval, interval + n, cmp);    // 将区间数组进行排序
    int num = 1, lastL = interval[0].l;   // 排序后的第一个区间总是被选中
    for (int i = 1; i < n; i++) {         // 遍历剩余的区间
        if (interval[i].r <= lastL) {     // 如果和上一个选中的区间不相交
            lastL = interval[i].l;        // 那么选中当前区间
            num++;                        // 并令选中的区间数量加1
        }
    }
    printf("%d", num);                    // 输出选中的区间数量
    return 0;
}

4.5二分法

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
int binarySearch(int A[],int left,int right,int x)
{
    int mid;
    while(left<=right){
        mid=(left+right)/2;
        if(A[mid]==x)return mid;
        else if(A[mid]>x){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return -1;
}
int main() {
    int n=0,x=0;
    scanf("%d %d", &n,&x);
    int a[n];
    for (int i = 0; i < n; i++) {         // 输入n个区间的左右端点
        scanf("%d", &a[i]);
    }
    printf("%d", binarySearch(a,0,n-1,x));                    // 输出选中的区间数量
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
int lower_bound(int A[],int left,int right,int x)
{
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(A[mid]>=x){
            right=mid;
        }else{
            left=mid+1;
        }
    }
    return left;
}
int main() {
    int n=0,x=0;
    scanf("%d %d", &n,&x);
    int a[n];
    for (int i = 0; i < n; i++) {         // 输入n个区间的左右端点
        scanf("%d", &a[i]);
    }
    printf("%d", lower_bound(a,0,n,x));                    // 输出选中的区间数量
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
int upper_bound(int A[],int left,int right,int x)
{
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(A[mid]>x){
            right=mid;
        }else{
            left=mid+1;
        }
    }
    return left;
}
int main() {
    int n=0,x=0;
    scanf("%d %d", &n,&x);
    int a[n];
    for (int i = 0; i < n; i++) {         // 输入n个区间的左右端点
        scanf("%d", &a[i]);
    }
    printf("%d", upper_bound(a,0,n,x));                    // 输出选中的区间数量
    return 0;
}

#include <cstdio>

const int MAXN = 100000;
int n, a[MAXN], target;

int binarySearch() {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (l < n && a[l] == target) {
        return l;
    } else {
        return -1;
    }
}

int main() {
    scanf("%d%d", &n, &target);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    printf("%d", binarySearch());
    return 0;
}

#include <cstdio>

const int MAXN = 100000;
int n, a[MAXN], target;

int binarySearch() {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] > target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (l >0 && a[l-1] == target) {
        return l-1;
    } else {
        return -1;
    }
}

int main() {
    scanf("%d%d", &n, &target);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    printf("%d", binarySearch());
    return 0;
}

#include <cstdio>
const int MAXN = 100000;
const double eps=1e-6;
double a;
double f(double x){
    return x*x*x+x*x+x-a;
}
double calSqrt(){
    double left=-100,right=100,mid;
    while(right-left>eps){
        mid=(left+right)/2;
        if(f(mid)>0){
            right=mid;
        }else{
            left=mid;
        }
    }
    return mid;
}



int main() {
    scanf("%lf",&a);
    printf("%.2f",calSqrt());
    return 0;
}

4.6 two pointers

#include <cstdio>

const int MAXN = 100000;
int n, k, a[MAXN];

int twoSum() {
    int counter = 0;
    int i = 0, j = n - 1;
    while (i < j) {
        if (a[i] + a[j] == k) {
            counter++;
            i++;
            j--;
        } else if (a[i] + a[j] < k) {
            i++;
        } else {
            j--;
        }
    }
    return counter;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    printf("%d", twoSum());
    return 0;
}

#include <cstdio>

const int MAXN = 100000;
int n, a[MAXN];
int m, b[MAXN];
int merged[MAXN * 2];

void merge() {
    int i = 0, j = 0, cnt = 0;
    while (i < n && j < m) {
        if (a[i] < b[j]) {
            merged[cnt++] = a[i++];
        } else {
            merged[cnt++] = b[j++];
        }
    }
    while (i < n) {
        merged[cnt++] = a[i++];
    }
    while (j < m) {
        merged[cnt++] = b[j++];
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &b[i]);
    }
    merge();
    for (int i = 0; i < n + m; i++) {
        printf("%d", merged[i]);
        if (i < n + m - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>

const int MAXN = 1000;
int n, a[MAXN];
int merged[MAXN];

void merge(int l1, int r1, int l2, int r2) {
    int i = l1, j = l2, cnt = 0;
    while (i <= r1 && j <= r2) {
        if (a[i] < a[j]) {
            merged[cnt++] = a[i++];
        } else {
            merged[cnt++] = a[j++];
        }
    }
    while (i <= r1) {
        merged[cnt++] = a[i++];
    }
    while (j <= r2) {
        merged[cnt++] = a[j++];
    }
    for (i = 0; i < cnt; i++) {
        a[l1 + i] = merged[i];
    }
}

void mergeSort(int l, int r) {
    if (l < r) {
        int mid = (l + r) / 2;
        mergeSort(l, mid);
        mergeSort(mid + 1, r);
        merge(l, mid, mid + 1, r);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    mergeSort(0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d", a[i]);
        if (i < n - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>

const int MAXN = 1000;
int n, a[MAXN];
int mergedNums[MAXN];

int partition(int l, int r) {
    int temp = a[l];
    while (l < r) {
        while (l < r && a[r] > temp) {
            r--;
        }
        a[l] = a[r];
        while (l < r && a[l] <= temp) {
            l++;
        }
        a[r] = a[l];
    }
    a[l] = temp;
    return l;
}

void quickSort(int l, int r) {
    if (l < r) {
        int pos = partition(l, r);
        quickSort(l, pos - 1);
        quickSort(pos + 1, r);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    quickSort(0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d", a[i]);
        if (i < n - 1) {
            printf(" ");
        }
    }
    return 0;
}

4.7其他高效技巧与算法

#include <cstdio>

int main() {
    int n, x, numZero = 0;
    scanf("%d", &n);
    long long result = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        if (x == 1) {
            result += numZero;
        } else {
            numZero++;
        }
    }
    printf("%lld", result);
    return 0;
}

#include <cstdio>
const int MAXN = 100000;
int n,k,a[MAXN];
int mergedNums[MAXN];

int partition(int l, int r) {
    int temp = a[l];
    while (l < r) {
        while (l < r && a[r] > temp) {
            r--;
        }
        a[l] = a[r];
        while (l < r && a[l] <= temp) {
            l++;
        }
        a[r] = a[l];
    }
    a[l] = temp;
    return l;
}

void quickSort(int l, int r) {
    if (l < r) {
        int pos = partition(l, r);
        quickSort(l, pos - 1);
        quickSort(pos + 1, r);
    }
}
int main() {
    scanf("%d %d", &n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    quickSort(0, n - 1);
    for(int i=0;i<n;i++)
    {
        if(i==k-1)
        printf("%d",a[i]);
    }
    return 0;
}