几道算法题

1. 在一个图里面给一个点，每个点都有颜色，要求给出与这个点相同着色且相邻的最大区域，写算法实现
2.给定一个序列如{A,B,C,D},先序关系，如<A,B>(A先于B),<C,D>,<D,A>，要求按先序关系给出整个序列的顺序，如<A,B>,<C,D>,<D,A>的顺序为C,D,A,B，
3.求证一个链表里是否有环
4.二维的空间中有很多点，要求求出所有点中最近的一对点，时间复杂度要好。
多做算法题，topcoder,pojonline，研究设计模式，msdn，底层和高层都要兼顾到
今天被bs的不行了，加油，Chris

评论

22 楼 thihy 2010-12-30  

基本上都见过。所以多面试&多看面试题还是有好处的。

21 楼 chriszeng87 2010-12-22  

izhangh 写道

chriszeng87 写道

izhangh 写道

class Question {

    /**
     * 标记该点是否遍历过，遍历过的值为1
     */
    private static int[][] flgs;

    /**
     * 
     * @param values
     *        二维数组，表示各点对应颜色值
     * @param x
     *        需比较点坐标
     * @param y
     *        点比较坐标
     * @return 与values[x][y]值相等且相邻点出现的次数
     */
    public static int run(int[][] values, int x, int y) {
        flgs = new int[values.length][values[0].length];
        Count count = new Count();
        research(values, values[x][y], count, x, y);
        return count.getCount();
    }
    /**
     * 
     * @param values二维数组
     *        ，表示各点对应颜色值
     * @param desValue比较的颜色值
     * @param count出现次数
     * @param x
     *        点坐标
     * @param y
     *        点坐标
     */
    private static void research(int[][] values, int desValue, Count count, int x, int y) {
        // 该点未遍历过,且颜色相同,继续遍历
        if (flgs[x][y] != 1 && values[x][y] == desValue) {

            // 标记该点遍历过
            flgs[x][y] = 1;
            // 计数器加一
            count.addOne();

            // 向左遍历
            if (x > 0) {
                research(values, desValue, count, x - 1, y);
            }
            // 向上遍历
            if (y > 0) {
                research(values, desValue, count, x, y - 1);
            }
            // 向右遍历
            if (x < values.length - 1) {
                research(values, desValue, count, x + 1, y);
            }
            // 向下遍历
            if (y < values[0].length - 1) {
                research(values, desValue, count, x, y + 1);
            }
        }
    }
}


public class Count {
    private int count;

    public void addOne() {
        count++;
    }
    public int getCount() {
        return count;
    }
}

class Test3Main {
    private static int[][] points = new int[][] {
            {
                    1, 1, 1, 1, 1, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 0, 1, 1, 1
            }, {
                    1, 1, 0, 0, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 0, 0, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 0, 0, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 0, 0, 1, 1
            }, {
                    1, 1, 1, 1, 1, 1, 1, 0, 1, 1
            }, {
                    1, 1, 1, 1, 1, 1, 1, 1, 1, 1
            },
    };
    public static void main(String[] args) {
         System.out.println(Question.run(points, 4, 3));
    }
}

得到出现次数了，再算面积就简单了吧！

感觉这样做确实可以，不过觉得是不是还有非递归、时间复杂度更好的算法

时间复杂度已经是最小了，你仔细看下吧!它遍历的只是颜色相同的次数+包围该颜色相邻颜色的次数。

额，请教下，包围该颜色相邻颜色的次数，这句话啥意思的

20 楼 izhangh 2010-12-22  

chriszeng87 写道

izhangh 写道

class Question {

    /**
     * 标记该点是否遍历过，遍历过的值为1
     */
    private static int[][] flgs;

    /**
     * 
     * @param values
     *        二维数组，表示各点对应颜色值
     * @param x
     *        需比较点坐标
     * @param y
     *        点比较坐标
     * @return 与values[x][y]值相等且相邻点出现的次数
     */
    public static int run(int[][] values, int x, int y) {
        flgs = new int[values.length][values[0].length];
        Count count = new Count();
        research(values, values[x][y], count, x, y);
        return count.getCount();
    }
    /**
     * 
     * @param values二维数组
     *        ，表示各点对应颜色值
     * @param desValue比较的颜色值
     * @param count出现次数
     * @param x
     *        点坐标
     * @param y
     *        点坐标
     */
    private static void research(int[][] values, int desValue, Count count, int x, int y) {
        // 该点未遍历过,且颜色相同,继续遍历
        if (flgs[x][y] != 1 && values[x][y] == desValue) {

            // 标记该点遍历过
            flgs[x][y] = 1;
            // 计数器加一
            count.addOne();

            // 向左遍历
            if (x > 0) {
                research(values, desValue, count, x - 1, y);
            }
            // 向上遍历
            if (y > 0) {
                research(values, desValue, count, x, y - 1);
            }
            // 向右遍历
            if (x < values.length - 1) {
                research(values, desValue, count, x + 1, y);
            }
            // 向下遍历
            if (y < values[0].length - 1) {
                research(values, desValue, count, x, y + 1);
            }
        }
    }
}


public class Count {
    private int count;

    public void addOne() {
        count++;
    }
    public int getCount() {
        return count;
    }
}

class Test3Main {
    private static int[][] points = new int[][] {
            {
                    1, 1, 1, 1, 1, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 0, 1, 1, 1
            }, {
                    1, 1, 0, 0, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 0, 0, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 0, 0, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 0, 0, 1, 1
            }, {
                    1, 1, 1, 1, 1, 1, 1, 0, 1, 1
            }, {
                    1, 1, 1, 1, 1, 1, 1, 1, 1, 1
            },
    };
    public static void main(String[] args) {
         System.out.println(Question.run(points, 4, 3));
    }
}

得到出现次数了，再算面积就简单了吧！

感觉这样做确实可以，不过觉得是不是还有非递归、时间复杂度更好的算法

时间复杂度已经是最小了，你仔细看下吧!它遍历的只是颜色相同的次数+包围该颜色相邻颜色的次数。

19 楼 chriszeng87 2010-12-22  

izhangh 写道

class Question {

    /**
     * 标记该点是否遍历过，遍历过的值为1
     */
    private static int[][] flgs;

    /**
     * 
     * @param values
     *        二维数组，表示各点对应颜色值
     * @param x
     *        需比较点坐标
     * @param y
     *        点比较坐标
     * @return 与values[x][y]值相等且相邻点出现的次数
     */
    public static int run(int[][] values, int x, int y) {
        flgs = new int[values.length][values[0].length];
        Count count = new Count();
        research(values, values[x][y], count, x, y);
        return count.getCount();
    }
    /**
     * 
     * @param values二维数组
     *        ，表示各点对应颜色值
     * @param desValue比较的颜色值
     * @param count出现次数
     * @param x
     *        点坐标
     * @param y
     *        点坐标
     */
    private static void research(int[][] values, int desValue, Count count, int x, int y) {
        // 该点未遍历过,且颜色相同,继续遍历
        if (flgs[x][y] != 1 && values[x][y] == desValue) {

            // 标记该点遍历过
            flgs[x][y] = 1;
            // 计数器加一
            count.addOne();

            // 向左遍历
            if (x > 0) {
                research(values, desValue, count, x - 1, y);
            }
            // 向上遍历
            if (y > 0) {
                research(values, desValue, count, x, y - 1);
            }
            // 向右遍历
            if (x < values.length - 1) {
                research(values, desValue, count, x + 1, y);
            }
            // 向下遍历
            if (y < values[0].length - 1) {
                research(values, desValue, count, x, y + 1);
            }
        }
    }
}


public class Count {
    private int count;

    public void addOne() {
        count++;
    }
    public int getCount() {
        return count;
    }
}

class Test3Main {
    private static int[][] points = new int[][] {
            {
                    1, 1, 1, 1, 1, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 0, 1, 1, 1
            }, {
                    1, 1, 0, 0, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 0, 0, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 0, 0, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 0, 0, 1, 1
            }, {
                    1, 1, 1, 1, 1, 1, 1, 0, 1, 1
            }, {
                    1, 1, 1, 1, 1, 1, 1, 1, 1, 1
            },
    };
    public static void main(String[] args) {
         System.out.println(Question.run(points, 4, 3));
    }
}

得到出现次数了，再算面积就简单了吧！

感觉这样做确实可以，不过觉得是不是还有非递归、时间复杂度更好的算法

18 楼 izhangh 2010-12-22  

上面是第一问的答案，请多多讨论。

17 楼 izhangh 2010-12-22  

class Question {

    /**
     * 标记该点是否遍历过，遍历过的值为1
     */
    private static int[][] flgs;

    /**
     * 
     * @param values
     *        二维数组，表示各点对应颜色值
     * @param x
     *        需比较点坐标
     * @param y
     *        点比较坐标
     * @return 与values[x][y]值相等且相邻点出现的次数
     */
    public static int run(int[][] values, int x, int y) {
        flgs = new int[values.length][values[0].length];
        Count count = new Count();
        research(values, values[x][y], count, x, y);
        return count.getCount();
    }
    /**
     * 
     * @param values二维数组
     *        ，表示各点对应颜色值
     * @param desValue比较的颜色值
     * @param count出现次数
     * @param x
     *        点坐标
     * @param y
     *        点坐标
     */
    private static void research(int[][] values, int desValue, Count count, int x, int y) {
        // 该点未遍历过,且颜色相同,继续遍历
        if (flgs[x][y] != 1 && values[x][y] == desValue) {

            // 标记该点遍历过
            flgs[x][y] = 1;
            // 计数器加一
            count.addOne();

            // 向左遍历
            if (x > 0) {
                research(values, desValue, count, x - 1, y);
            }
            // 向上遍历
            if (y > 0) {
                research(values, desValue, count, x, y - 1);
            }
            // 向右遍历
            if (x < values.length - 1) {
                research(values, desValue, count, x + 1, y);
            }
            // 向下遍历
            if (y < values[0].length - 1) {
                research(values, desValue, count, x, y + 1);
            }
        }
    }
}


public class Count {
    private int count;

    public void addOne() {
        count++;
    }
    public int getCount() {
        return count;
    }
}

class Test3Main {
    private static int[][] points = new int[][] {
            {
                    1, 1, 1, 1, 1, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 0, 1, 1, 1
            }, {
                    1, 1, 0, 0, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 0, 0, 0, 1, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 0, 0, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 1, 1, 1, 1
            }, {
                    1, 1, 1, 1, 1, 0, 0, 0, 1, 1
            }, {
                    1, 1, 1, 1, 1, 1, 1, 0, 1, 1
            }, {
                    1, 1, 1, 1, 1, 1, 1, 1, 1, 1
            },
    };
    public static void main(String[] args) {
         System.out.println(Question.run(points, 4, 3));
    }
}

得到出现次数了，再算面积就简单了吧！

16 楼 chriszeng87 2010-12-21  

不知道发到这里合不合适了，这道题想了好久了，也没什么思路：  对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。 求指点。

15 楼 asle 2010-12-19  

chriszeng87 写道

让记录成为一种习惯,是一个想要在以后留下点什么东西的人该做的事。记录是一个人积累的过程，看再多的书，如果没有记录下来，过一个时间后就跟没看一样。看自己写下的东西和看别人写的东西是不一样的，主要体现在理解速度上，因为中间缺少了将别人的思维翻译成自己思维的过程。

在记录中学会思考、学会探索。

记录可以消除自己烦躁的情绪。

每天抽出一到两个小时来记录自己的所学和自己的思考，这样一直的坚持那么当你回过头来看看的时候，你会发现你已经收获了很多了。

转的，说的真不错

写出来的才是真正懂了，从厚到薄，再从薄到厚

14 楼 chriszeng87 2010-12-19  

meiyoudao 写道

你这是啥职位啊????  这些东西..见都没见过

Software Design Engineer

13 楼 meiyoudao 2010-12-19  

你这是啥职位啊????  这些东西..见都没见过

12 楼 chriszeng87 2010-12-18  

kdlan 写道

1 应该是算闭包的变形吧

能不能再详细一点的，您说的闭包是不是您楼下所说的凸包啊?

11 楼 uddjatigmh199 2010-12-18  

1.对每种颜色应用凸包.....

10 楼 kdlan 2010-12-17  

1 应该是算闭包的变形吧

9 楼 生活小丑 2010-12-17  

chriszeng87 写道

让记录成为一种习惯,是一个想要在以后留下点什么东西的人该做的事。记录是一个人积累的过程，看再多的书，如果没有记录下来，过一个时间后就跟没看一样。看自己写下的东西和看别人写的东西是不一样的，主要体现在理解速度上，因为中间缺少了将别人的思维翻译成自己思维的过程。

在记录中学会思考、学会探索。

记录可以消除自己烦躁的情绪。

每天抽出一到两个小时来记录自己的所学和自己的思考，这样一直的坚持那么当你回过头来看看的时候，你会发现你已经收获了很多了。

转的，说的真不错

看再多的书，如果没有记录下来，过一个时间后就跟没看一样    这句话有感觉......

8 楼 jasin2008 2010-12-16  

算法
心中永远的痛

7 楼 chriszeng87 2010-12-16  

4在很多书上有，《编程之美》上感觉写的不太好，不过还有个扩展题：求空间中n个点中距离最远的两点，这个有人想过么? http://yinhail.ycool.com/post.4507062.html 上有解，不过我没看懂额

6 楼 lj30936 2010-12-16  

1。好像就是广度优先搜索吧
2。根据边建图，然后拓扑遍历图
3。同楼上
4。最小距离点对，网上有nlogn算法

5 楼 lykm02 2010-12-16  

1 暂没思路
2 好像是图的拓扑有序。数据结构课本里面有的吧
3 快慢指针，如果相遇说明有环
4 算法课本上有的，经典算法
ok

4 楼 chriszeng87 2010-12-16  

cectsky 写道

你的头像很像土匪

某已故日本音乐人

3 楼 chriszeng87 2010-12-16  

让记录成为一种习惯,是一个想要在以后留下点什么东西的人该做的事。记录是一个人积累的过程，看再多的书，如果没有记录下来，过一个时间后就跟没看一样。看自己写下的东西和看别人写的东西是不一样的，主要体现在理解速度上，因为中间缺少了将别人的思维翻译成自己思维的过程。

在记录中学会思考、学会探索。

记录可以消除自己烦躁的情绪。

每天抽出一到两个小时来记录自己的所学和自己的思考，这样一直的坚持那么当你回过头来看看的时候，你会发现你已经收获了很多了。

转的，说的真不错