第一道算法题（250分） 话说你在走路上班时，经过一片种植萝卜的农田。这块田地的形状是一个矩形的网格。field的第i个元素的第j个字符，表示田地的第i 行第j列的格子里包含的萝卜的数目。我们定义一个格子的特殊程度为它周围所有格子的萝卜个数的和; 它周围的格子包含它上下左右以及对角相邻的格子，最多有8个，在田地的边界上的格子会少一些。如果一个格子周围没有别的格子，则它的特殊程度为0。 请返回田地中特殊程度在A和B之间的所有格子的数目（包含A,B）。
下面是我的解法,由于不懂C#,所以就使用与其相近的Java来编写，简单说明下，就是引入一个辅助标记二维数组，若数组中某一个数其值大于范围的最大值，则说明其本身和周围位置（最多八个）都是不再需要进行统计的，所以这里进行一个剪枝操作，设置标记值表示此处不需要进行判断，减少搜索的范围，从而提高算法速度，最后测试运算10万次，用时为937毫秒，具体的测试用例见原帖中。
复制代码
/** * @author phinecos * @since -6-1 */ public class NumberField { private static int min; private static int max; private static int height; private static int width; private static boolean flag[][];//辅助标志 private static void markNoSpecial(String[] field, int i, int j) {//设置false标记，无需再对其周围进行检测 int k,m; int num; for (k = i-1; k <= i+1 && k < height; ++k) { if (k < 0) {//越过边界 k = i; } String tmp = field[k]; for (m = j-1; m <= j+1 && m < width; ++m) { if (m < 0) {//越过边界 m = j; } if (k != i || m != j) { num = tmp.charAt(m) - '0'; if (num > max && flag[k][m] != false) { flag[k][m] = false; } } } } } private static int getSpecialNumber(String[] field, int i,int j) {//计算field[i][j]的特殊程度 int count = 0; int height = field.length;//高度 int width = field[0].length();//宽度 int num = 0; int k,m; for (k = i-1; k <= i+1 && k < height; ++k) { if (k < 0) {//越过边界 k = i; } String tmp = field[k]; for (m = j-1; m <= j+1 && m < width; ++m) { if (m < 0) {//越过边界 m = j; } if (k != i || m != j) { num = tmp.charAt(m) - '0'; if (num >=max) {//比最大值要大，肯定不行的，置为false标记 flag[k][m] = false; } count += num; } } } return count; } public static int countSpecialNumbers(String[] field,int A,int B) { int count = 0; int i,j,num = 0; for (i = 0; i < field.length; ++i) { for (j = 0; j < field[i].length(); ++j) { if (flag[i][j] != false) {//不是false标记 num = getSpecialNumber(field,i,j); if (num >= A && num <= B) ++count; } else {//本身是false标记，则将其周围都置为false标记 markNoSpecial(field,i,j); } } } return count; }
/** * @param args */ public static void main(String[] args) { String[] data = {"1234567890", "1234567890", "1234567890", "1234567890", "1234567890", "1234567890", "1234567890", "1234567890", "1234567890", "1234567890", "1234567890"};
long begin = System.currentTimeMillis(); height = data.length; width = data[0].length(); flag = new boolean[height][width]; int i,j; for (i = 0; i < height; ++i) { for (j = 0; j < width; ++j) { flag[i][j] = true; } } min = 3; max = 18; System.out.println(countSpecialNumbers(data,min,max));
for (i = 0; i < 100000; i++) { countSpecialNumbers(data, min, max); } long end = System.currentTimeMillis(); long time = end - begin; System.out.println("耗时"+time);
} }
复制代码 第二道算法题（500分）
题目要求：双倍超立方数是指一个正整数可以正好被拆分为两种不同的a^3+b^3的方式，其中a,b均为整数且0<a<=b。对于任何一个指定的 int n, 返回所有的小于等于n的双倍超立方数的个数。
复制代码 import java.util.ArrayList; import java.util.Hashtable; import java.util.List; import java.util.Map; import java.util.Set; import java.util.Map.Entry;
public class TwiceSuperCubic { private static Map<Integer,Integer> cache = new Hashtable<Integer, Integer>();//键为立方和，值为次数 public static int count(int n) { if (n<1 || n>1000000000) return 0; int count = 0; int max = (int) java.lang.Math.pow(n, 1.0f/3.0f); for (int a = 1; a <= max; a++) { for (int b = a; b <= max; b++) { int tmp = a * a * a + b * b * b; if (cache.get(tmp) == null) { cache.put(tmp, 1); } else { int num = cache.get(tmp); cache.put(tmp, num+1); } } } Set<Entry<Integer,Integer>> entrys = cache.entrySet(); for (Entry<Integer,Integer> entry : entrys) { int key = entry.getKey(); int value = entry.getValue(); if (key <= n && value==2) ++count; } return count; }
/** * @param args */ public static void main(String[] args) { long t1 = System.currentTimeMillis(); int n = 1000000000; System.out.println(count(n)); long t2 = System.currentTimeMillis(); System.out.println(t2-t1); }
} 复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：/phinecos/archive//06/01/1494007.html，如需转载请自行联系原作者
