请教大家两道算法题,实在是想不出来了( д`) - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请 &nsp;登录
angcz
V2EX    问与答

请教大家两道算法题,实在是想出来了( д`)

  •  
  •   angcz 2018-07-17 23:14:51 +08:00 2378 次点击
    这是一个创建于 2650 天前的主题,其中的信息可能已经有所发展或是发生改变。

    1.
    给出一个已知长宽的二维数组 以斜着的 z 字型遍历该数组
    比如:
    {{1,2,3},
    {4,5,6},
    {7,8,9}}
    输出为:
    1 2 4 7 5 3 6 8 9
    再比如:
    {{1,2,3,4},
    {5,6,7,8},
    {9,10,11,12}}
    输出为:
    1 2 5 9 6 3 4 7 10 11 8 12

    2.
    给出一个已知长度的无序的一维数组 求出该数组任意两个元素值的最大差值 设这两个元素为 a,b 必须满足 a 的下标比 b 的下标小这一条件 时间复杂度要求 O(n) 空间复杂度要求 O(1)

    在面试中遇到的两道题 太菜了 想了很久 最后只想出来了低效率方法或者笨办法 没有办法 只能请教大家了( д`)

    第 1 条附言    2018-07-18 00:29:44 +08:00
    第二题表述有点问题 修改一下 就是给定 array[n] n 已知 求 array[i]-array[j]的最大值( n>i>j>=0 )
    23 条回复    2018-07-18 09:27:59 +08:00
    mathzhaoliang
        1
    mathzhaoliang  
       2018-07-17 23:36:38 +08:00
    第二个问题是否应该表述为:求出数组元素两两之差的最大值?
    mikeguan
        2
    mikeguan  
       2018-07-17 23:41:25 +08:00 via Android
    第二个问题如果我用两次冒泡求一个最大值和一个最小值 时间复杂度是 O(n)吗?
    mathzhaoliang
        3
    mathzhaoliang  
       2018-07-17 23:48:35 +08:00
    第一个题目其实不难,你只要找出位于 (i, j) 处的元素在输出序列中的下标即可(用 i, j 表示)
    msg7086
        4
    msg7086  
       2018-07-17 23:48:47 +08:00
    1.
    matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    1.upto(matrix.size + matrix.first.size - 1) do |l|
    col = matrix.take(l).map(&:shift).compact
    col.reverse! if l.odd?
    p col
    end

    [1]
    [2, 4]
    [7, 5, 3]
    [6, 8]
    [9]
    xml123
        5
    xml123  
       2018-07-17 23:49:43 +08:00 via iPhone
    第二个的意思是“求 a_i-a_j 的最大值( i>j )”吧
    Xs0ul
        6
    Xs0ul  
    2018-07-17 23:56:01 +08:00
    第二题先不管空间的,等于需要知道,给定每个下标,返回这个下标右边的最小值,这个从右到左扫一轮就行。然后再每个位置的值减它右边的最小值,这 n 个结果里面留一个最大的就行。

    再优化空间复杂度,可以扫一个算一个差值,于是需要的变量是当前右侧最小值和最大的差值
    xml123
        7
    xml123  
       2018-07-17 23:59:00 +08:00 via iPhone
    5l 写错了一个地方,应该是 i<j
    然后如果这个理解是正确的话,最大的差值肯定产生于某个极大值和它之后的某个极小值之差。读一边列表,维护 3 个数,过去出现的最大的数,最大数之后出现的最小数,以及最大的差值,应该就能满足要求了。(不过如果数组是递增的话好像还是会有 bug,这种情况额外处理一下吧)
    xwyam
        8
    xwyam  
       2018-07-18 00:11:02 +08:00 via Android
    第一题 python 实现
    ZGVmIGdlbihtLCBuKToKICAgIGZvciBzIGluIHJhbmdlKG0gKyBuIC0gMSk6CiAgICAgICAgaSwg
    aiA9IChzLCAwKSBpZiBzIDwgbSBlbHNlIChtIC0gMSwgcyAtIG0gKyAxKQogICAgICAgIHgsIHkg
    ID0gKDAsIHMpIGlmIHMgPCBuIGVsc2UgKHMgLSBuICsgMSwgbiAtIDEpCiAgICAgICAgd2hpbGUg
    aSA+PSB4IGFuZCBqIDw9IHk6CiAgICAgICAgICAgIHlpZWxkIChpLCBqKQogICAgICAgICAgICBp
    LCBqID0gaSAtIDEsIGogKyAx
    msg7086
        9
    msg7086  
       2018-07-18 00:13:02 +08:00
    第二题相当于是 Trapping Rain Water 的一个特例,最直观的做法是新开两个数组存覆盖结果,然后再相减。
    空间复杂度 O(1)不知道能不能实现,回头我想一下然后贴代码上来。
    xwyam
        10
    xwyam  
       2018-07-18 00:18:51 +08:00 via Android
    第二题一个简单的思路,扫描两趟,第一趟找出最大值 A 和最小值 V,第二趟找出最小值之后的最大值 M 和最大值之前的最小值 W,A-W 和 M-V 中较大数即是所求
    xwyam
        11
    xwyam  
       2018-07-18 00:20:09 +08:00 via Android
    @mikeguan 是 O(n)
    angcz
        12
    angcz  
    OP
       2018-07-18 00:21:19 +08:00
    @mathzhaoliang 是的 你的理解是对的 我表述得有些问题
    angcz
        13
    angcz  
    OP
       2018-07-18 00:23:04 +08:00
    @xml123 呃 5L 的理解是对的 就是给定 array[n] 求 array[i]-array[j]的最大值( i > j )
    xml123
        14
    xml123  
       2018-07-18 00:34:07 +08:00 via Android
    @angcz 那把 7l 的方法反过来就行了(大和小换一下,或者逆序遍历数组)
    msg7086
        15
    msg7086  
       2018-07-18 00:50:03 +08:00
    #10 @xwyam [-1, 10, -8, 8, -10, 1]
    ihainan
        16
    ihainan  
       2018-07-18 01:01:11 +08:00
    第一题,我想到的笨方法是,因为对角线行号列号之和相同,所以可以外层循环穷举所有可能的和,内层循环穷举在这个和之下所有可能的行号。

    第二题,从左往右,记录当前左侧最小值,计算当前值和最小值的差值,再记录当前位置的最大差值。注意数组为空和只有一个元素的情况。
    timle1029
        17
    timle1029  
       2018-07-18 01:03:44 +08:00
    第一题是 leetcode 原题 https://leetcode.com/problems/diagonal-traverse/description/

    第二题没有这么复杂吧,从后往前扫,记录一个 maxValue, 遇到更大的就替换,遇到比这个 Value 小的就计算比较结果
    public int maxDifference(int[] nums) {
    int len = nums.length;
    int maxValue = nums[len - 1];
    int res = 0;
    for (int i = len - 2; i >= 0; i--) {
    if (nums[i] < maxValue) {
    res = Math.max(maxValue - nums[i], res);
    } else {
    maxValue = Math.max(mavValue, nums[i]);
    }
    }
    return res;
    }
    kj
        18
    kj  
       2018-07-18 01:06:50 +08:00 via Android
    第二题,两个指针,一个从左往右找更小的,一个从右往左找更大的
    Andiry
        19
    Andiry  
       2018-07-18 01:17:22 +08:00   1
    LC498
    LC121
    msg7086
        20
    msg7086  
       2018-07-18 01:25:39 +08:00   2
    第二题的解题思路:

    首先是笨办法穷举,这个就不多说了。

    接下来看优化方法。
    首先我们知道最优解的大值在右边,小值在左边,那么小值可以覆盖大值左边的任意数据,大值可以覆盖小值右边的任意数据,而使得最优解不变。

    比如说 [0, -5, -10, -5, 0, 5, 10, 5, 0] 的最优结果与 [0, -5, -10, -10, -10, -10, 10, 5, 0] 的结果是相同的,和 [0, -5, -10, 10, 10, 10, 10, 5, 0]的结果也是相同的。我这里把这种做法叫做极值覆盖。

    那么解法就很简单了,生成两个极值覆盖数组,分别是小值向右覆盖,和大值向左覆盖:
    min_array = [0, -5, -10, -10, -10, -10, -10, -10, -10]
    max_arrray = [10, 10, 10, 10, 10, 10, 10, 5, 0]
    然后对于每个下标,求最大差值即可。

    代码如下:
    input = [-1, 10, -8, 8, -10, 1]

    min_array = input.dup
    max_array = input.dup
    1.upto(input.size-1) { |i| min_array[i] = [min_array[i-1], min_array[i]].min }
    (input.size-1).downto(1) { |i| max_array[i-1] = [max_array[i-1], max_array[i]].max }
    diff_array = input.size.times.map { |i| max_array[i] - min_array[i] }
    max_diff = diff_array.max
    p min_array
    p max_array
    p diff_array
    puts max_diff


    # [-1, -1, -8, -8, -10, -10]
    # [10, 10, 8, 8, 1, 1]
    # [11, 11, 16, 16, 11, 11]
    # 16

    时间复杂度三次线性遍历 O(n),空间复杂度两次复制数组 O(n)。

    接下来是继续优化空间复杂度。
    我们看到大值覆盖是没有必要去计算的,直接用原始输入数据求值就行了,所以优化成:
    min_array = input.dup
    1.upto(input.size-1) { |i| min_array[i] = [min_array[i-1], min_array[i]].min }
    diff_array = input.size.times.map { |i| input[i] - min_array[i] }
    max_diff = diff_array.max
    p min_array
    p diff_array
    puts max_diff

    # [-1, -1, -8, -8, -10, -10]
    # [0, 11, 0, 16, 0, 11]
    # 16

    时间复杂度两次线性遍历 O(n),空间复杂度一次复制数组 O(n)。

    再接下来我们发现小值覆盖也没有必要生成整个数组,而是只要记录至今为止的最小值即可,因为小值总是只会更小,后续计算不会涉及到历史值,因此优化成:

    min = input.first
    max_diff = 0
    input.each do |n|
    min = n if n < min
    max_diff = n - min if n - min > max_diff
    end
    puts max_diff

    # 16

    时间复杂度一次线性遍历 O(n),空间复杂度 O(1)。

    同类型的 Trapping Rain Water 可以用第一种优化方法扫描覆盖极值来求解,有兴趣可以去挑战一下。
    xwyam
        21
    xwyam  
       2018-07-18 07:53:48 +08:00 via Android
    @msg7086。。。之前想法好像确实不行。。。
    yidinghe
        22
    yidinghe  
       2018-07-18 08:37:19 +08:00 via Android
    第二题怎么看都是找数组的最大最小值啊。
    ihainan
        23
    ihainan  
       2018-07-18 09:27:59 +08:00
    关于     帮助文档     自助推广系统     博客     API     FAQ     Solana     2731 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 26ms UTC 13:59 PVG 21:59 LAX 06:59 JFK 09:59
    Do have faithin what you're doing.
    ubao msn snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86