數(shù)據(jù)結(jié)構(gòu)和算法視頻學(xué)習(xí)-創(chuàng)新互聯(lián)

數(shù)據(jù)結(jié)構(gòu)和算法學(xué)習(xí) 排序快速排序—分治

步驟：

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

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

#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;
}

歸并排序—分治

步驟：

確定分界點(diǎn)—中點(diǎn)
遞歸排序左右兩邊
將左右兩個(gè)數(shù)組合并成一個(gè)有序的數(shù)組—?dú)w并 ?

#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.選擇中點(diǎn)作為分界
    //2.對(duì)左右兩邊不斷進(jìn)行遞歸
    //3.聲明i，j兩個(gè)指針進(jìn)行比較，放入到中間數(shù)數(shù)組中；
    //當(dāng)其中一個(gè)指針到達(dá)結(jié)尾時(shí)，另一個(gè)數(shù)據(jù)全部接入中間數(shù)據(jù)
    //4.將中間數(shù)組復(fù)制到原數(shù)組中結(jié)束
    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)性，通過(guò)二分保證答案在區(qū)間內(nèi)

整數(shù)二分

步驟：

針對(duì)有序數(shù)組

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

#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個(gè)數(shù)的數(shù)組中讀取m的開(kāi)始位置和結(jié)束位置
    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;
}

浮點(diǎn)數(shù)二分

不用考慮邊界問(wèn)題

#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++中存在的問(wèn)題

大整數(shù)的存儲(chǔ)問(wèn)題，是將數(shù)據(jù)存儲(chǔ)到數(shù)組中，從索引0開(kāi)始到最后，分別存儲(chǔ)個(gè)位、十位、百位…最高位，因?yàn)檫\(yùn)算過(guò)程中可能存在進(jìn)位問(wèn)題，數(shù)組在尾部加數(shù)據(jù)更加方便。

A + B 類(lèi)型

#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.先將兩個(gè)大整數(shù)倒敘寫(xiě)入到各自的vector集合(頭文件需要定義)中
    //2.調(diào)用自定義的add函數(shù)實(shí)現(xiàn)相加和進(jìn)位，最終以集合返回
    //3.倒敘遍歷輸出最終結(jié)果

    //大整數(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 類(lèi)型

#include#includeusing namespace std;

bool cmp(vector&A, vector&B) {
    //減法計(jì)算前需要判斷AB的大小關(guān)系
    //分幾種情況，AB長(zhǎng)度相同，不相同
    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;//存放結(jié)果的數(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();//解決輸出結(jié)果為0009這些情況
    return C;
}

int main() {
    string a = "10", b = "1";//a,b兩個(gè)大正整數(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誰(shuí)大，是誰(shuí)減誰(shuí)
    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 類(lèi)型

#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 類(lèi)型

#include#include#include 

using namespace std;

vectordiv(vector&A, int b, int &r) {//余數(shù)通過(guò)引用&返回回去
    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)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標(biāo)題：數(shù)據(jù)結(jié)構(gòu)和算法視頻學(xué)習(xí)-創(chuàng)新互聯(lián)
分享URL：http://muchs.cn/article14/icdge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護(hù)、ChatGPT、搜索引擎優(yōu)化、網(wǎng)頁(yè)設(shè)計(jì)公司、云服務(wù)器、動(dòng)態(tài)網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容