国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

【筆記】牛客網(wǎng)算法

buildupchao / 3432人閱讀

摘要：公式復(fù)雜度為復(fù)雜度為復(fù)雜度為只要子問題的規(guī)模是一致的，就可以用公式

時間復(fù)雜度 冒泡排序 
public static void bubbleSort(int[] arr){
        if(arr == null || arr.length < 2)
            return;
        for(int end = arr.length-1; end > 0; end--){
            for(int i = 0; i < end; i++)
                if(arr[i] > arr[i+1])
                    swap(arr,i,i+1);
        }
    }
選擇排序 
public static void selectionSort(int[] arr){
        if(arr == null || arr.length < 2)
            return;
        for(int i = 0; i < arr.length-1; i++){
            int minIndex = i;
            for(int j = i+1; j < arr.length; j++)
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            swap(arr, i, minIndex);
        }
    }
插入排序 
public static void insertionSort(int[] arr){
        if(arr == null || arr.length < 2)
            return;
        for(int i = 1; i < arr.length; i++)
            for(int j = i - 1;j >= 0 && arr[j] > arr[j + 1]; j--)//一次次往前交換
                swap(arr, j, j + 1);
    }
對數(shù)器

隨機產(chǎn)生器：產(chǎn)生隨機數(shù)組

準備一個絕對正確的方法：不需考慮時間復(fù)雜度，保證絕對正確即可

實現(xiàn)比對的方法

把方法a和方法b比對很多次來驗證方法a是否正確

如果有一個樣本是的比對出錯，打印樣本分析是哪個方法出錯

當(dāng)樣本數(shù)量很多時比對測試依然正確，可以確定方法a已經(jīng)正確

以冒泡排序為例

隨機發(fā)生器

public static int[] generateRandomArray(int size, int value){
    int[] arr = new int[(int) ((size + 1) * Math.random())];
    for (int i = 0; i < arr.length; i++)
        arr[i] = (int)((value + 1) * Math.random()) - (int)(value * Math.random());//只要是隨機數(shù)就行
    return arr;
}

準備一個絕對正確的方法

public static void rightMathod(int[] arr){
    Arrays.sort(arr);
}

實現(xiàn)比對的方法

//判斷兩個數(shù)組相等
public static boolean isEqual(int[] arr1, int[] arr2){
    if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null))
        return false;
    if (arr1 == null && arr2 ==null)
        return true;
    if (arr1.length != arr2.length)
        return false;
    for (int i = 0; i < arr1.length; i++) {
        if(arr1[i] != arr2[i])
            return false;
    }
    return true;
}

剩下放在main中的步驟

//Main
public static void main(String[] args) {
    //自己設(shè)置
    int testTime = 500000;
    int size = 10;
    int value = 100;
    boolean succeed = true;
    for (int i = 0; i < testTime; i++){
        int[] arr1 = generateRandomArray(size,value);//生成器
        int[] arr2 = copyArray(arr1);//拷貝arr1
        int[] arr3 = copyArray(arr1);
        bubbleSort(arr1);
        rightMathod(arr2);
        if(!isEqual(arr1,arr2)){
            succeed = false;
            printArrays(arr3);//將錯誤的樣本打印出來
            break;
        }        
    }
    System.out.println(succeed ? "Nice!" : "Error!");
}

//復(fù)制數(shù)組
public static int[] copyArray(int[] arr){
    if (arr == null)
        return null;
    int[] res = new int[arr.length];
    for (int i = 0; i< arr.length; i++)
        res[i] = arr[i];
    return res;
}

//打印樣本
public static int[] printArrays(int[] arr){
    ...
}

剖析遞歸行為和遞歸行為時間復(fù)雜度的估算

遞歸求數(shù)組最大值

public static int getMax(int[] arr, int l,int r){
        if(r == l){
            return arr[l];
        }

        int mid = (l + r)/2;
        int maxLeft = getMax(arr, l, mid);
        int maxRight = getMax(arr, mid+1, r);
        return Math.max(maxLeft, maxRight);
    }

遞歸的本質(zhì)是系統(tǒng)對函數(shù)進行了棧操作。

master公式

T(N) = a*T(N/b) + O(N^d)
1) log(b,a) > d -> 復(fù)雜度為O(N^log(b,a))
2) log(b,a) = d -> 復(fù)雜度為O(N^d * logN)
3) log(b,a) < d -> 復(fù)雜度為O(N^d)

只要子問題的規(guī)模是一致的，就可以用master公式

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/75186.html

相關(guān)文章

  • 基于牛客網(wǎng)Js v8引擎提供的讀/寫方法做的調(diào)試頁面

    摘要：牛客網(wǎng)為了滿足我們用寫編程題的愿望，在那塊，給提供了和兩個方法，用來讀取輸入和輸出但很明顯，這只能在它提供的編碼頁面才能用，我們想線下使用，而且想進行是更不可能的。 項目地址 正直秋招季，對找工作的人來說，牛客網(wǎng)肯定不陌生，現(xiàn)在很多大型互聯(lián)網(wǎng)公司的在線筆試都是在牛客網(wǎng)上面進行的（好像有打廣告的嫌疑）。 Js有那么多的操作數(shù)據(jù)結(jié)構(gòu)的api，ES6新增的那些set、map數(shù)據(jù)結(jié)構(gòu)和其它的比...

    wqj97 評論0 收藏0

  • 【Java】廣州三本秋招經(jīng)歷

    摘要：具體的時間線從月中旬，我開始關(guān)注牛客網(wǎng)的秋招內(nèi)推信息。直至十月中下旬結(jié)束秋招。之前也寫過自己在廣州找實習(xí)的經(jīng)歷，那次把面試的過程都具體貼出來了。我今年就完美錯過了春招實習(xí)經(jīng)歷。 前言 只有光頭才能變強 離上次發(fā)文章已經(jīng)快兩個月時間了，最近一直忙著秋招的事。今天是2018年10月22日，對于互聯(lián)網(wǎng)行業(yè)來說，秋招就基本結(jié)束了。我這邊的流程也走完了(不再筆試/面試了)，所以來寫寫我的秋招經(jīng)歷...

    qqlcbb 評論0 收藏1

  • 用于牛客網(wǎng)Javascript v8引擎評測機的本地測試頁面

    摘要：用于牛客網(wǎng)引擎評測機的本地測試頁面項目地址功能和界面等尚不完善，故歡迎提出各種意見為什么做這個藍橋賽后無所事事隨便做題發(fā)現(xiàn)牛客網(wǎng)允許使用提交，并定義了專有輸入輸出方法和，但是并沒有提供靠譜測試的隨意測試的環(huán)境作為一個自詡為前端汪的大專學(xué)渣 用于牛客網(wǎng) v8引擎評測機的本地測試頁面 項目地址 GitHub https://github.com/iamapig120...Gitee htt...

    zzbo 評論0 收藏0

  • 牛客網(wǎng)JS（nodeJS）單行、多行輸入和輸出

    摘要：實現(xiàn)牛客網(wǎng)的輸入和輸出在牛客網(wǎng)上，用做筆試的童鞋首先要做的事情就是學(xué)會如何輸入和輸出。下面再根據(jù)要求對每一行數(shù)據(jù)進行處理，比如類似于單行輸入將每一行數(shù)據(jù)按照空格轉(zhuǎn)換為數(shù)組等輸出你的結(jié)果 nodeJS實現(xiàn)牛客網(wǎng)的輸入和輸出 在牛客網(wǎng)上，用js做筆試的童鞋首先要做的事情就是學(xué)會如何輸入和輸出。否則就算看得懂題也無法通過筆試。話不多少，我們直接開始： 1、選擇語言showImg(https:...

    ybak 評論0 收藏0

  • 【牛客網(wǎng)】-- 日日刷(第五天)

    還剩11天 ========================================================================= 1、抽象類方法的訪問權(quán)限默認都是public。(√) 在Java1.8以前，抽象類方法默認的訪問權(quán)限為protected在Java1.8以后，抽象類方法默認的訪問權(quán)限為default ============================...

    ARGUS 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<