论坛首页 综合技术论坛

几道算法题

浏览 13430 次
锁定老帖子 主题:几道算法题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间: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));
    }
}


得到出现次数了,再算面积就简单了吧!

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


时间复杂度已经是最小了,你仔细看下吧!它遍历的只是颜色相同的次数+包围该颜色相邻颜色的次数。
0 请登录后投票
   发表时间: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));
    }
}


得到出现次数了,再算面积就简单了吧!

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


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

额,请教下,包围该颜色相邻颜色的次数,这句话啥意思的
0 请登录后投票
   发表时间:2010-12-30  
基本上都见过。所以多面试&多看面试题还是有好处的。
0 请登录后投票
论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics