锁定老帖子 主题:几道算法题
精华帖 (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)); } } 得到出现次数了,再算面积就简单了吧! 感觉这样做确实可以,不过觉得是不是还有非递归、时间复杂度更好的算法 时间复杂度已经是最小了,你仔细看下吧!它遍历的只是颜色相同的次数+包围该颜色相邻颜色的次数。 |
|
返回顶楼 | |
发表时间: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)); } } 得到出现次数了,再算面积就简单了吧! 感觉这样做确实可以,不过觉得是不是还有非递归、时间复杂度更好的算法 时间复杂度已经是最小了,你仔细看下吧!它遍历的只是颜色相同的次数+包围该颜色相邻颜色的次数。 额,请教下,包围该颜色相邻颜色的次数,这句话啥意思的 |
|
返回顶楼 | |
发表时间:2010-12-30
基本上都见过。所以多面试&多看面试题还是有好处的。
|
|
返回顶楼 | |