矩阵中求最大递增路径 二
发表于:2019-04-01 17:12:22 分类:JAVA 阅读:727次
题目如上:在上次的基础上用map缓存了已扫描过的路径,但是还是超时。
public class IncrementalPathTest { private int[][] nums; private int x; private int y; private List<Integer> bestRoad = new ArrayList<>(); private Map<String,List<Integer[]>> pointResult = new HashMap<>(); public IncrementalPathTest(int[][] nums){ this.nums = nums; } public static void main(String[] args) { // int mx =600; // int my =600; // int[][] nums = new int[mx][my]; //// int[] x0 = {9,9,4}; //// int[] x1 = {6,6,8}; //// int[] x2 = {2,1,1}; //// nums[0] = x0; //// nums[1] = x1; //// nums[2] = x2; // for (int x=0;x<nums.length;x++){ // for(int y=0;y<nums[0].length;y++){ // nums[x][y] = (int)(Math.random()*100); // } // } // String jsonString = JSONArray.toJSONString(nums); // System.out.println(jsonString); int[][] nums = jsonToTwoArr(getArrStr(),600); IncrementalPathTest test = new IncrementalPathTest(nums); test.printNums(); long startTime = System.currentTimeMillis(); test.run(); System.out.println(test.getMaxStep()); long endTime = System.currentTimeMillis(); System.out.println("耗时:"+(endTime-startTime)); List<Integer> bestRoad = test.getBestRoad(); System.out.println("最大递增路径为:"+bestRoad); } public void run(){ for (int x=0;x<nums.length;x++){ for(int y=0;y<nums[0].length;y++){ this.x = x; this.y = y; ArrayList<Integer[]> points = new ArrayList<>(); points.add(new Integer[]{x,y}); canMove(x, y,points); } } } public void printNums(){ for (int x=0;x<nums.length;x++){ for(int y=0;y<nums[0].length;y++){ int num = nums[x][y]; System.out.printf(num+" "); if(num<10){ System.out.printf(" "); } } System.out.println(); } } public void canMove(int x,int y,List<Integer[]> points){ boolean canLeft = canLeft(x, y); boolean canRight = canRight(x, y); boolean canUp = canUp(x, y); boolean canDown = canDown(x, y); List<Integer[]> indexOld = pointResult.get(this.x + "," + this.y); if(!canLeft&&!canRight&&!canUp&&!canDown){ writeCache(indexOld,points); }else{ List<Integer[]> old = pointResult.get(x + "," + y); if(old!=null){ readCache(indexOld,old,points); return; } } if(canLeft){ move(x,y,1,points); } if(canRight){ move(x,y,2,points); } if(canUp){ move(x,y,3,points); } if(canDown){ move(x,y,4,points); } } private void readCache(List<Integer[]> indexOld, List<Integer[]> old, List<Integer[]> points) { points.remove(points.size()-1); points.addAll(old); if(indexOld!=null){ if(indexOld.size()<points.size()){ pointResult.put(this.x + "," + this.y,points); } }else{ pointResult.put(this.x + "," + this.y,points); } } private void move(int x,int y,int direction,List<Integer[]> points){ int mx=x; int my=y; List<Integer[]> have = isHave(points, new Integer[]{mx, my}); switch (direction){ case 1: my = my - 1; break; case 2: my = my + 1; break; case 3: mx = mx - 1; break; case 4: mx = mx + 1; break; default: throw new RuntimeException("程序异常!"); } have.add(new Integer[]{mx,my}); canMove(mx,my,have); } private void writeCache(List<Integer[]> indexOld, List<Integer[]> points){ if(indexOld!=null){ if(indexOld.size()<points.size()){ pointResult.put(this.x + "," + this.y,points); } }else{ pointResult.put(this.x + "," + this.y,points); } } private List<Integer[]> isHave(List<Integer[]> target,Integer[] point){ for (int i=0;i<target.size();i++) { Integer[] integers = target.get(i); if((integers[0]-point[0]==0)&&(integers[1]-point[1]==0)){ List<Integer[]> subList = target.subList(0, i+1); return new ArrayList<>(subList); } } target.add(point); return target; } private boolean canLeft(int x,int y){ if(y>0&&nums[x][y]<nums[x][y-1]){ return true; } return false; } private boolean canRight(int x,int y){ if(y<nums[0].length-1&&nums[x][y]<nums[x][y+1]){ return true; } return false; } private boolean canUp(int x,int y){ if(x>0&&nums[x][y]<nums[x-1][y]){ return true; } return false; } private boolean canDown(int x,int y){ if(x<nums.length-1&&nums[x][y]<nums[x+1][y]){ return true; } return false; } public int getMaxStep() { int maxStep = 0; List<Integer[]> best = null; Set<String> keySet = pointResult.keySet(); for (String key : keySet) { List<Integer[]> integers = pointResult.get(key); if (maxStep < integers.size()) { maxStep = integers.size(); best= integers; } } createBaseRoad(best); return maxStep; } private void createBaseRoad(List<Integer[]> best) { bestRoad = new ArrayList<>(best.size()); for (Integer[] point:best) { bestRoad.add(nums[point[0]][point[1]]); } } public List<Integer> getBestRoad() { return bestRoad; } public static int[][] jsonToTwoArr(String jsonStr, int length) { int[][] weightGetValue = new int[length][length]; JSONArray arr = JSONArray.parseArray(jsonStr); for (int i = 0; i < arr.size(); i++) { JSONArray jsonArray = (JSONArray) arr.get(i); for (int j = 0; j < jsonArray.size(); j++) { weightGetValue[i][j] = (int) jsonArray.get(j); } } return weightGetValue; } public static String getArrStr(){ File file = new File("G:/text/arr.txt" ); try { BufferedReader reader = new BufferedReader(new FileReader(file)); String s = reader.readLine(); return s; } catch (Exception e) { e.printStackTrace(); } return ""; } }
用600*600的一组随机数据测试,1秒内出结果。。。
关键词:算法,矩阵,路径