【笔记】牛客网算法

buildupchao 发布于2019-08-16 18:29 / 3338人阅读

摘要：公式复杂度为复杂度为复杂度为只要子问题的规模是一致的，就可以用公式

时间复杂度 冒泡排序

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

对数器

随机产生器：产生随机数组

准备一个绝对正确的方法：不需考虑时间复杂度，保证绝对正确即可

实现比对的方法

把方法a和方法b比对很多次来验证方法a是否正确

如果有一个样本是的比对出错，打印样本分析是哪个方法出错

当样本数量很多时比对测试依然正确，可以确定方法a已经正确

以冒泡排序为例

随机发生器

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());//只要是随机数就行
    return arr;
}

准备一个绝对正确的方法

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

实现比对的方法

//判断两个数组相等
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) {
    //自己设置
    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!");
}

//复制数组
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){
    ...
}

剖析递归行为和递归行为时间复杂度的估算

递归求数组最大值

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

递归的本质是系统对函数进行了栈操作。

master公式

T(N) = a*T(N/b) + O(N^d)
1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)

只要子问题的规模是一致的，就可以用master公式

服务器托管云服务器牛客网牛客上 python 牛客帐客网

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75186.html

基于牛客网Js v8引擎提供的读/写方法做的调试页面

摘要：牛客网为了满足我们用写编程题的愿望，在那块，给提供了和两个方法，用来读取输入和输出但很明显，这只能在它提供的编码页面才能用，我们想线下使用，而且想进行是更不可能的。项目地址正直秋招季，对找工作的人来说，牛客网肯定不陌生，现在很多大型互联网公司的在线笔试都是在牛客网上面进行的（好像有打广告的嫌疑）。 Js有那么多的操作数据结构的api，ES6新增的那些set、map数据结构和其它的比...

wqj97 2019-08-21 16:24 评论0 收藏0
【Java】广州三本秋招经历

摘要：具体的时间线从月中旬，我开始关注牛客网的秋招内推信息。直至十月中下旬结束秋招。之前也写过自己在广州找实习的经历，那次把面试的过程都具体贴出来了。我今年就完美错过了春招实习经历。前言只有光头才能变强离上次发文章已经快两个月时间了，最近一直忙着秋招的事。今天是2018年10月22日，对于互联网行业来说，秋招就基本结束了。我这边的流程也走完了(不再笔试/面试了)，所以来写写我的秋招经历...

qqlcbb 2019-08-16 13:29 评论0 收藏1
用于牛客网Javascript v8引擎评测机的本地测试页面

摘要：用于牛客网引擎评测机的本地测试页面项目地址功能和界面等尚不完善，故欢迎提出各种意见为什么做这个蓝桥赛后无所事事随便做题发现牛客网允许使用提交，并定义了专有输入输出方法和，但是并没有提供靠谱测试的随意测试的环境作为一个自诩为前端汪的大专学渣用于牛客网 v8引擎评测机的本地测试页面项目地址 GitHub https://github.com/iamapig120...Gitee htt...

zzbo 2019-08-22 17:33 评论0 收藏0
牛客网JS（nodeJS）单行、多行输入和输出

摘要：实现牛客网的输入和输出在牛客网上，用做笔试的童鞋首先要做的事情就是学会如何输入和输出。下面再根据要求对每一行数据进行处理，比如类似于单行输入将每一行数据按照空格转换为数组等输出你的结果 nodeJS实现牛客网的输入和输出在牛客网上，用js做笔试的童鞋首先要做的事情就是学会如何输入和输出。否则就算看得懂题也无法通过笔试。话不多少，我们直接开始： 1、选择语言showImg(https:...

ybak 2019-08-22 16:27 评论0 收藏0
【牛客网】-- 日日刷(第五天)

还剩11天 ========================================================================= 1、抽象类方法的访问权限默认都是public。(√) 在Java1.8以前，抽象类方法默认的访问权限为protected在Java1.8以后，抽象类方法默认的访问权限为default ============================...

ARGUS 2019-08-16 18:23 评论0 收藏0