随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

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

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

图1

     先看看图图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


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

 





Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2013-11-03 18:03 银河使者 阅读(8538) 评论(4)  编辑  收藏 所属分类: algorithm 原创

评论

# re: Twitter算法面试题详解(Java实现)  回复  更多评论   

囧,递归lol~ 贴一个自己在leetcode上的实现。因为是直接在oj上写的,不考虑额外空间问题,当然了这段代码可以重构^_^.

http://oj.leetcode.com/problems/trapping-rain-water/

class Solution {
public:
int trap(int A[], int n) {
// Note: The Solution object is instantiated only once and is reused by each test case.

// easiest and intuitive way:
// caculate the (left_max, right_max) for each element A[i]
// example:
// for the given array A = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the points whould be:
// B = [(0, 3), (1, 3), (1, 3), (2, 3), (2, 3), (2, 3), (2, 3), (3, 2), (3, 2), (3, 2), (3, 1)]
// then let SUM = sum( min(Bi) ) for i = 0 to n-1
// return SUM - sum(Ai) for i = 0 to n-1
// and hope this works!
// luckily, it works!

vector<int> left(n, 0), right(n, 0);
int max = 0;
for(int i=0; i<n; i++)
{
if(A[i] > max)
max = A[i];

left[i] = max; // don't use push_back
}

// for right
max = 0;
for(int i=n-1; i>=0; i--)
{
if(A[i] > max)
max = A[i];

right[i] = max;
}

int sum=0;
for(int i=0; i<n; i++)
{
int min = (left[i] < right[i]) ? left[i] : right[i];
sum += (min-A[i]); // don't forget to subtract A[i]
}

return sum;
}
};
2013-11-19 01:57 | zyzz

# re: Twitter算法面试题详解(Java实现)  回复  更多评论   

好东西 学习了
2013-12-05 10:23 | 左岸

# re: Twitter算法面试题详解(Java实现)[未登录]  回复  更多评论   

package yang.twitter;

/**
* @author dy35978
*
*/
public class TwitterProcess {
private static int [] wallHeights = {1,6,1,2,3,4,100,1,9};
private static int result = 0;//最多装水
private static void process(int start, int end){
int firstWall = 0;//最高墙
int secondWall = 0;//次高墙
int firstIndex = 0;//最高墙下标
int secondIndex = 0;//次高墙下标
int maxIndex = 0;//较大下标
int minIndex = 0;//较小下标
//end-start<=1 不只是等于1,注意
if(end-start<=1){
return;
}
for(int i=0;i<end+1;i++){
if(wallHeights[i]>=firstWall){
secondWall = firstWall;
secondIndex = firstIndex;
firstWall = wallHeights[i];
firstIndex = i;
}else{
if(wallHeights[i]>=secondWall){
secondIndex = i;
secondWall = wallHeights[i];
}
}
}
maxIndex = secondIndex>firstIndex?secondIndex:firstIndex;// Math.min(firstIndex, secondIndex);
minIndex = secondIndex<firstIndex?secondIndex:firstIndex;// Math.max(firstIndex, secondIndex);
if(maxIndex-minIndex>1){
result =result+ secondWall*(maxIndex-minIndex-1);
for(int i=minIndex+1;i<maxIndex;i++){
result = result-wallHeights[i];
}
}
// 开始递归处理左侧墙距离开始位置能放多少水
process(start,minIndex);
// 开始递归处理右侧墙距离结束位置能放多少水
process(maxIndex,end);
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

process(0,wallHeights.length-1);
System.out.println("wallHeights结果:"+result);
}

}
2013-12-17 11:32 | Blues

# re: Twitter算法面试题详解(Java实现)  回复  更多评论   

很难啊.
2014-07-24 13:21 | 微观互联网

只有注册用户登录后才能发表评论。


网站导航: