數(shù)據(jù)結構和算法視頻學習-創(chuàng)新互聯(lián)

數(shù)據(jù)結構和算法學習排序快速排序—分治

步驟：

專業(yè)成都網(wǎng)站建設公司，做排名好的好網(wǎng)站，排在同行前面，為您帶來客戶和效益!創(chuàng)新互聯(lián)公司為您提供成都網(wǎng)站建設，五站合一網(wǎng)站設計制作，服務好的網(wǎng)站設計公司，成都做網(wǎng)站、網(wǎng)站設計負責任的成都網(wǎng)站制作公司!

確定分界點x,可以是左邊界可以是右邊界可以是中點
調(diào)整區(qū)間（左邊段小于等于x，右邊段大于等于x）重點和難點 ?
遞歸處理左右兩端（最終使左右兩斷有序，因為左邊始終小于等于右邊，所以整個有序）

#includeusing namespace std;
const int N = 1e6 + 10;
int n;
int q[N];

void quick_sort(int q[], int l, int r) {if (l >= r) return;
    int x = q[l], i = l - 1, j = r + 1;//選擇左右都是可以的
    while (i< j) {do {i++;
        } while (q[i]< x);
        do {j++;
        } while (q[j] >x);
        if (i< j) {swap(q[i], q[j]);
        }
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

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

歸并排序—分治

步驟：

確定分界點—中點
遞歸排序左右兩邊
將左右兩個數(shù)組合并成一個有序的數(shù)組—歸并 ?

#includeusing namespace std;
const int N = 1e6;
int n;
int arr1[N], temp[N];

void merge_sort(int arr[], int l, int r) {if (l >= r) return;
    int midNum = arr[l + (r - l) >>1];
    int k = 0, i = 0, j = 0;
    merge_sort(arr, l, midNum);
    merge_sort(arr, midNum + 1, r);
    while (i<= midNum && j<= r) {if (arr[i]<= arr[j]) temp[k ++] = arr[i ++];
        else temp[k ++] = arr[j ++];
    }
    while (i<= midNum) temp[k ++] = arr[i ++];
    while (j<= r) temp[k ++] = arr[j ++];
    for (int m = 0; m< n; ++m) {arr[m] = temp[m];
    }
}

int main() {//歸并排序
    //1.選擇中點作為分界
    //2.對左右兩邊不斷進行遞歸
    //3.聲明i，j兩個指針進行比較，放入到中間數(shù)數(shù)組中；
    //當其中一個指針到達結尾時，另一個數(shù)據(jù)全部接入中間數(shù)據(jù)
    //4.將中間數(shù)組復制到原數(shù)組中結束
    scanf("%d", &n);
    for (int i = 0; i< n; ++i) {scanf("%d", &arr1[i]);
    }
    merge_sort(arr1, 0, n - 1);
    for (int i = 0; i< n; ++i) {printf("%d", arr1[i]);
    }
    return 0;
};

二分

二分的本質(zhì)并不是單調(diào)性，通過二分保證答案在區(qū)間內(nèi)

整數(shù)二分

步驟：

針對有序數(shù)組

找出中間值
判斷中間值是否為真，根據(jù)情況更新區(qū)間注意是否需要+1 處理邊界問題

#include//using namespace std;
//const int N = 100000;
//int n,m;
//int q[N];
using namespace std;

int main() {//scanf("%d%d",&n,&m);
    //讀入從n個數(shù)的數(shù)組中讀取m的開始位置和結束位置
    int n = 6, m = 3;
    bool flag = true;
    int q[6] = {1, 2, 3, 3, 3, 6};
    while (flag) {int l = 0, r = n - 1;
        while (l< r) {int midNum = l + r >>1;
            if (q[midNum] >= m) {r = midNum;
            } else {l = midNum + 1;
            }
        }
        if (q[l] != m) {cout<< "-1 -1"<< endl;
            flag = false;
        } else {cout<< l<< " ";
            l = 0, r = n - 1;
            while (l< r) {int midNum = l + r + 1 >>1;
                if (q[midNum]<= m) {l = midNum;
                } else {r = midNum - 1;
                }
            }
            cout<< l<< endl;
            flag = false;
        }
    }
    return 0;
}

浮點數(shù)二分

不用考慮邊界問題

#includeusing namespace std;

int main(){int n;
    scanf("%d",&n);
    double l = 0, r = n;
    double minigap = 1e-8;
    while ((r - l) >minigap) {double midnum = (l + r) / 2;
        if ((midnum * midnum)<= n) l = midnum;
        else r = midnum;
    }
    if (1) cout<< 0<< endl;
    printf("%f", l);

    return 0;
};

高精度

C++中存在的問題

大整數(shù)的存儲問題，是將數(shù)據(jù)存儲到數(shù)組中，從索引0開始到最后，分別存儲個位、十位、百位…最高位，因為運算過程中可能存在進位問題，數(shù)組在尾部加數(shù)據(jù)更加方便。

A + B 類型

#include#includeusing namespace std;
int N = 100000 + 10;

vectoraddbignum (vector&A, vector&B){int t = 0;
    vectorC;
    for (int i = 0; i< A.size()|| i< B.size(); ++i) {if (i< A.size()) t += A[i];
        if (i< B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(1);
    return C;
}

int main(){//高精度大整數(shù)相加
    //1.先將兩個大整數(shù)倒敘寫入到各自的vector集合(頭文件需要定義)中
    //2.調(diào)用自定義的add函數(shù)實現(xiàn)相加和進位，最終以集合返回
    //3.倒敘遍歷輸出最終結果

    //大整數(shù)用string
    string a = "12",b = "30";//例如a = 123456
    vectorA,B;//最為A,B的集合存放數(shù)據(jù)
    for (int i = a.size() - 1; i >= 0; --i) {A.push_back(a[i] - '0');
    }
    for (int i = b.size() - 1; i >= 0; --i) {B.push_back(b[i] - '0');
    }
    vectorC = addbignum(A, B);
    for (int i = C.size() - 1 ; i >= 0; --i) {cout<< C[i];
    }
    return 0;
}

A - B 類型

#include#includeusing namespace std;

bool cmp(vector&A, vector&B) {
    //減法計算前需要判斷AB的大小關系
    //分幾種情況，AB長度相同，不相同
    if (A.size() != B.size()) return A.size() - B.size();
    else {
        for (int i = A.size() - 1; i >= 0; --i) {
            if (A[i] != B[i]) {
                return A[i] - B[i];
            }
        }
        return true;
    }
}

vectordec(vector&A, vector&B) {
    vectorC;//存放結果的數(shù)組
    int t = 0;
    for (int i = 0; i< A.size(); ++i) {
        t = A[i] - t;
        if (i< B.size()) t = t - B[i];
        C.push_back((t + 10) % 10);
        if (t< 0) t = 1;
        else t = 0;
    }
    while (C.size() >1 && C.back() == 0) C.pop_back();//解決輸出結果為0009這些情況
    return C;
}

int main() {
    string a = "10", b = "1";//a,b兩個大正整數(shù)
    vectorA, B;//集合AB存放數(shù)據(jù)
    for (int i = a.size() - 1; i >= 0; --i) {
        A.push_back(a[i] - '0');
    }
    for (int i = b.size() - 1; i >= 0; --i) {
        B.push_back(b[i] - '0');
    }
    vectorC;
    //首先需要判斷AB誰大，是誰減誰
    if (cmp(A, B)) {
        //true 則A >= B
        C = dec(A, B);
        for (int i = C.size() - 1; i >= 0; --i) {
            printf("%d", C[i]);
        }
    } else {
        //B >A
        C = dec(B, A);
        cout<< '-';
        for (int i = C.size() - 1; i >= 0; --i) {
            printf("%d", C[i]);
        }
    }
    return 0;
}

A * a 類型

#include#includeusing namespace std;
vectormul(vector&A, int b) {
    vectorC;
    int t =0;
    for (int i = 0; i< A.size() || t; ++i) {
        if (i< A.size()) t = b * A[i] + t;
        C.push_back((t) % 10);
        t /= 10;
    }
    return C;
}
int main(){
    string a = "999";
    int b = 9;
    vectorA, C;
    for (int i = a.size() - 1; i >= 0; --i) {
        A.push_back(a[i] - '0');
    }
    C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; --i) {
        printf("%d",C[i]);
    }
    return 0;
}

A / a 類型

#include#include#include 

using namespace std;

vectordiv(vector&A, int b, int &r) {//余數(shù)通過引用&返回回去
    vectorC;
    for (int i = A.size() - 1; i >= 0; --i) {r = r * 10 + A[i];
        C.push_back(r / b);
        r = r % b;
    }
    reverse(C.begin(), C.end());//得反轉(zhuǎn)以下，否則輸出不一致
    while (C.size() >1 && C.back() == 0) C.pop_back();
    return C;
}

int main() {string a = "1247";
    int b = 4, r = 0;
    vectorA, C;
    for (int i = a.size() - 1; i >= 0; --i) {A.push_back(a[i] - '0');
    }
    C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; --i) {printf("%d", C[i]);
    }
    cout<< endl<< r<< endl;
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞標題：數(shù)據(jù)結構和算法視頻學習-創(chuàng)新互聯(lián)
分享鏈接：http://weahome.cn/article/icdge.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

數(shù)據(jù)結構和算法視頻學習-創(chuàng)新互聯(lián)

其他資訊

網(wǎng)站制作

企業(yè)服務

網(wǎng)站建設

服務器托管