牛课堂算法直播题目

一、介绍

直播人:左程云老师

直播时间:2018.2.1晚上八点

二、code技巧的磨炼

【题目】荷兰国旗问题

已知一个整型数组arr,和一个整数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边。 要求:时间复杂度为O(N),额外空间复杂度O(1)。

理解:设置 l 为左边界,r 为右边界,less 为小于区域右边界,more 为大于区域左边界。将小于等于num的数都放于数组的左边,当 i 与 l 的值相等时,遍历结束。

package tmp;

public class Code_01_NetherlandsFlag {

    public static int[] partition(int[] arr, int l, int r, int p) {
        int less = l - 1;
        int more = r + 1;
        int i = l;
        while (l < more) {
            if (arr[l] < p) {
                swap(arr, ++less, l++);
            } else if (arr[l] > p) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        return new int[] { less + 1, more - 1 };
    }

    // for test
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // for test
    public static int[] generateArray() {
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 3);
        }
        return arr;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] test = generateArray();

        printArray(test);
        int[] res = partition(test, 0, test.length - 1, 1);
        printArray(test);
        System.out.println(res[0]);
        System.out.println(res[1]);

    }
}

三、算法思维的锻炼

【题目】已知一个整型数组arr,数组长度为size且size大于2,arr有size-1种可以划分成左右两部分的方案。

比如: arr = {3, 2, 3, 4, 1, 2} 第1种划分左部分为[3],右部分为[2, 3, 4, 1, 2] 第2种划分左部分为[3, 2],右部分为[3, 4, 1, 2] 第3种划分左部分为[3, 2, 3],右部分为[4, 1, 2] 第4种划分左部分为[3, 2, 3, 4],右部分为[1, 2] 第5种划分左部分为[3, 2, 3, 4, 1],右部分为[2]

每一种划分下,左部分都有最大值记为max_left,右部分都有最大值记为max_right。 求|max_left-max_right|(左部分最大值与左部分最大值之差的绝对值),最大是多少? 要求:时间复杂度为O(N),额外空间复杂度O(1)。

package tmp;

public class Code_02_MaxABSBetweenLeftAndRight {

    public static int maxABS1(int[] arr) {
        int res = Integer.MIN_VALUE;
        int maxLeft = 0;
        int maxRight = 0;
        for (int i = 0; i != arr.length - 1; i++) {
            maxLeft = Integer.MIN_VALUE;
            for (int j = 0; j != i + 1; j++) {
                maxLeft = Math.max(arr[j], maxLeft);
            }
            maxRight = Integer.MIN_VALUE;
            for (int j = i + 1; j != arr.length; j++) {
                maxRight = Math.max(arr[j], maxRight);
            }
            res = Math.max(Math.abs(maxLeft - maxRight), res);
        }
        return res;
    }

    public static int maxABS2(int[] arr) {
        int[] lArr = new int[arr.length];
        int[] rArr = new int[arr.length];
        lArr[0] = arr[0];
        rArr[arr.length - 1] = arr[arr.length - 1];
        for (int i = 1; i < arr.length; i++) {
            lArr[i] = Math.max(lArr[i - 1], arr[i]);
        }
        for (int i = arr.length - 2; i > -1; i--) {
            rArr[i] = Math.max(rArr[i + 1], arr[i]);
        }
        int max = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            max = Math.max(max, Math.abs(lArr[i] - rArr[i + 1]));
        }
        return max;
    }

    public static int maxABS3(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
        }
        return max - Math.min(arr[0], arr[arr.length - 1]);
    }

    public static int[] generateRandomArray(int length) {
        int[] arr = new int[length];
        for (int i = 0; i != arr.length; i++) {
            arr[i] = (int) (Math.random() * 1000) - 499;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = generateRandomArray(200);
        System.out.println(maxABS1(arr));
        System.out.println(maxABS2(arr));
        System.out.println(maxABS3(arr));
    }
}

四、算法基础内容的学习与拓展

【题目】定义局部最小的概念。

arr长度为1时,arr[0]是局部最小。arr的长度为N(N>1)时,如果arr[0]<arr[1],那么arr[0]是局部最小;如果arr[N-1]<arr[N-2],那么arr[N-1]是局部最小;如果0<i<N-1,既有arr[i]<arr[i-1],又有arr[i]<arr[i+1],那么arr[i]是局部最小。

给定无序数组arr,已知arr中任意两个相邻的数都不相等。写一个函数,只需返回arr中任意一个局部最小出现的位置即可。

package tmp;

public class Code_03_FindOneLessValueIndex {

    public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1; // no exist
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 6, 5, 3, 4, 6, 7, 8 };
        printArray(arr);
        int index = getLessIndex(arr);
        System.out.println("index: " + index + ", value: " + arr[index]);

    }

}

五、算法敏感度的训练

【题目】折纸条。 请把一段纸条竖着放在桌子上,然后从纸条的下边向上方对折1次,压出折痕后展开。此时折痕是凹下去的,即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次,压出折痕后展开,此时有三条折痕,从上到下依次是下折痕、下折痕和上折痕。给定一个输入参数N,代表纸条都从下边向上方连续对折N次,请从上到下打印所有折痕的方向。 例如:

N=1时,打印: down N=2时,打印: down down up

package tmp;

public class Code_04_PaperFolding {

    public static void printAllFolds(int N) {
        printProcess(1, N, true);
    }

    public static void printProcess(int i, int N, boolean down) {
        if (i > N) {
            return;
        }
        printProcess(i + 1, N, true);
        System.out.println(down ? "down " : "up ");
        printProcess(i + 1, N, false);
    }

    public static void main(String[] args) {
        int N = 4;
        printAllFolds(N);
    }
}

 提示:将此题步骤推算下来,其实就是二叉树的中序遍历问题。

六、收获

此次直播左老师从算法的原理一步步讲解和拓展,在此将我记得的关键点总结如下:

  • 学习算法还是要多刷题,至少要刷200道以上。
  • 在练习完一道算法题时,应尽量找寻它的最优解。
  • 有些大公司在面试你时会故意不把问题说清楚,这是因为他在考察你对算法的敏感度(如上述的折纸问题本质就是一个二叉树的中序遍历问题)。看你能否直接看到问题的本质。
  • 代码书写命名要规范,在保证自己理解的前提下让阅读代码的人也能够读懂。
  • 坚持。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

20:反反复复

20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字...

3818
来自专栏CDA数据分析师

开工大吉:几个让你月薪3万+的excel神技能

来源:运营圈信息流广告 职场中经常会用到哪些函数? IF函数、SUMIF函数、VLOOKUP函数、SUMPRODUCT函数...... 小编总结了8个在工作中常...

3956
来自专栏聊聊技术

原 初学数模-MATLAB Quick S

4589
来自专栏机器学习入门

POJ 刷题系列:1083. Moving Tables

POJ 刷题系列:1083. Moving Tables 传送门:POJ 1083. Moving Tables 题意: 一条走廊,两栏房间。搬运工每次从房价...

22010
来自专栏程序员叨叨叨

6.5 Swizzle 操作符

可以使用Cg语言中的swizzle操作符(.)将一个向量的成员取出组成一个新的向量。swizzle操作符被GPU硬件高效支持。swizzle操作符后接x、y、z...

2165
来自专栏磐创AI技术团队的专栏

快速学习 Python 的全套 14 张思维导图(附高清版下载)

基础知识图一包括了基本规则、Python语言特点、计算机语言、如何运行Python、变量赋值五个方面,辅助你快速掌握Python编程的基底知识。

1733
来自专栏程序员宝库

用 PHP 的方式实现的各类算法合集

项目地址: https://github.com/PuShaoWei/arithmetic-php About 如果说各种编程语言是程序员的招式,那么数据结构和...

4497
来自专栏Albert陈凯

数据结构与算法汇总

文章作者博客微信公共账号:hadoop123(微信号为:hadoop-123),分享hadoop技术内幕,hadoop最新技术进展,发布hadoop相关职位和求...

3675
来自专栏Python小屋

Python使用scipy进行多项式计算与符号计算

在扩展库numpy和scipy中都有poly1d,用法一样,实际上是同一个库,scipy是基于numpy的。有图为证 ? 本文代码主要演示如何使用poly1d进...

4826
来自专栏数说工作室

统计师的Python日记【第3天:Numpy你好】

本文是【统计师的Python日记】第3天的日记 回顾一下,第1天学习了Python的基本页面、操作,以及几种主要的容器类型;第2天学习了python的函数、循环...

45212

扫码关注云+社区

领取腾讯云代金券