你好,游客 登录
背景:
阅读新闻

Twitter算法面试题详解(Java实现)

[日期:2016-11-24] 来源:极客头条  作者: [字体: ]

最近在网上看到一道Twitter的算法面试题,网上已经有人给出了答案,不过可能有些人没太看明白(我也未验证是否正确),现在给出一个比较好理解的答案。先看一下题目。

图1

先看看这个图。可以将方块看做砖。题干很简单,问最多能放多少水。例如,图2就是图1可放的最多水(蓝色部分),如果将一块砖看做1的话,图2就是能放10个单位的水。

图2 

再看个例子

图3

图3可以放17个单位的水。

上面每一个图的砖墙用int数组表示,每一个数组元素表示每一列砖墙的砖数(高度),例如,图3用数组表示就是int[] wallHeights = new int[]{ 2, 5, 1, 3, 1, 2, 1, 7, 7, 6 }; 

这里某人给出了python的算法 点击打开链接 ,不过有人说有问题,有python环境的可以验证。现在给出我的Java算法。 

算法原理

其实很简单,我的算法并不是累加的,而是用的减法,先用图3为例。只需要找到所有墙中最高的,然后再找出第二高的。如果两堵墙紧邻者,就忽略它,否则算一下如果墙之间没有任何其他的砖的情况下可以有多少水(只是一个乘法而已),然后扫描两堵墙之间有多少块砖,减去这个砖数就可以了。最后用递归处理。将两堵墙两侧到各自的左右边界再重新进行前面的操作(递归处理)。直到无墙可处理。 用递归方法很容易理解。下面看一下算法的详细代码。

public class Test
{
    static int result = 0//  最终结果
    static int[] wallHeights = new int[]
    {1,6,1,2,3,4,100,1,9};  //  表示所有的墙的高度
 
    public static void process(int start, int end)
    {
        //  first:start和end之间最高的墙
        //  second:start和end之间第二高的墙
        int first = 0, second = 0;
        //  firstIndex:第一高的墙在wallHeights中的索引
        //  secondIndex:第二高的墙在wallHeights中的索引
        int firstIndex = 0, secondIndex = 0;
        //  两堵墙必须至少有一堵墙的距离
        if (end - start <= 1)
            return;
        //  开始获取第一高和第二高墙的砖数
        for (int i = start; i <= end; i++)
        {
            if (wallHeights[i] > first)
            {
                second = first;
                secondIndex = firstIndex;
                first = wallHeights[i];
                firstIndex = i;
            }
            else if (wallHeights[i] > second)
            {
                second = wallHeights[i];
                secondIndex = i;
            }
        }
 
        //  获取左侧墙的索引
        int startIndex = Math.min(firstIndex, secondIndex);
        //  获取右侧墙的索引
        int endIndex = Math.max(firstIndex, secondIndex);
        //  计算距离
        int distance = endIndex - startIndex;
        //  如果第一高的墙和第二高的墙之间至少有一堵墙,那么开始计算这两堵墙之间可以放多少个单位的水
        if (distance > 1)
        {
            result = result + (distance - 1) * second;
            //  减去这两堵墙之间的砖数
            for (int i = startIndex + 1; i < endIndex; i++)
            {
                result -= wallHeights[i];
            }
            
        }
        //  开始递归处理左侧墙距离开始位置能放多少水
        process(start, startIndex);
        //  开始递归处理右侧墙距离结束位置能放多少水
        process(endIndex, end);
    }
 
    public static void main(String[] args)
    {
        process(0, wallHeights.length - 1);
        System.out.println(result);
 
    }
 
}

代码中的测试用例的结果是22。下面是几组测试用例。

[ 2 , 5 , 1 , 2 , 3 , 4 , 7 , 7 , 6
]   结果:10

[ 2 , 5 , 1 , 3 , 1 , 2 , 1 , 7 , 7 , 6
]  结果:17

[ 6 , 1 , 4 , 6 , 7 , 5 , 1 , 6 , 4 ]  结果:13
[9,6,1,2,3,4,50,1,9]  结果:37

有其他算法的(语言不限)欢迎跟帖

收藏 推荐 打印 | 录入:admin | 阅读:
相关新闻      
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款