矩阵中求最大递增路径 二-查看文章

矩阵中求最大递增路径 二

发表于:2019-04-01 17:12:22 分类:JAVA 阅读:724次

123456.png

题目如上:在上次的基础上用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秒内出结果。。。

关键词:算法,矩阵,路径


验证码: