两道算法

好久没写算法了,突然一写发现有些生疏了。比如这两道算法题一眼看起来很简单,但是实际写起来却很麻烦。

矩阵全排列问题

1
2
3
4
给定一个矩阵,从每一行里面选出一个数字,输出该矩阵的全排列
       |1,3,4|
比如   |2,3,5,6| 输出  {1,2,4},{1,2,7},{1,2,8},{1,3,4},{1,3,7},{1,3,8} ........
       |4,7,8|

这道题猛一看很简单,直接循环搞定,但是实际上需要通过递归来处理问题, 而递归的关键点则是: 每次扫到最后一行的元素时,输出临时结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
    private static void printMatrix(int[][]matrix, int start, HashMap<Integer,Integer>tempResult){

        //when reach the last row, we should print temp result
        if(matrix.length == start){
            printResult(tempResult);
            return;
        }

        for(int i = 0; i < matrix[start].length;i++){
            tempResult.put(start,matrix[start][i]);
            printMatrix(matrix, start + 1, tempResult);
        }
    }

    private static void printResult(HashMap<Integer,Integer> result){
        StringBuilder temp = new StringBuilder();
        for(Integer key : result.keySet()){
            temp.append(result.get(key)).append(" ");
        }
        System.out.println(temp.toString());

    }

    public static void printMatrix(int[][]matrix){
         HashMap<Integer,Integer> tempResult = new LinkedHashMap<Integer, Integer>();
         printMatrix(matrix,0,tempResult);
    }

    public static void main(String[] args) {
        int testcase1[][] = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 0, 11, 12},
                {13, 14, 15, 0}
        };

        printMatrix(testcase1);

        int testcase2[][] = {
                {1, 2, 3},
                {5, 6, 7, 8},
                {9, 0, 11, 12},
                {13, 14, 15, 0}
        };

        printMatrix(testcase2);

        int testcase3[][] = {
        };

        printMatrix(testcase3);

        int testcase4[][] = {
            {1, 2, 3}
        };

        printMatrix(testcase4);

    }

多边形周长求等分点问题

1
给定一个多边形,求多边形周长的 n 等分点。

这题目的解题思路也很直观,

先求多边形周长,确定等分点长度,然后顺序扫描每一条边,如果边长度 > 等分点长度,那么在该边上选取等分点,如果不够,则在下一条边上选取等分点。

但是实际写起来就很麻烦了,比如求等分点需要 计算圆和直线的交点,直接导致我重新推导一遍公式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
    public static List<Point> split(List<Point> points, int n){
        double oneDistance = getPerimeter(points) /n;
        List<Point> res = new LinkedList<Point>();

        double target = oneDistance;
        for(int i = 0; i < points.size(); i++){
            Point cur = points.get(i);
            Point next = i+1 >= points.size() ? points.get(0) : points.get(i+1);

            Point p = getPointBetweenPointAB(cur,next,target);

            while (p != null){
               target = oneDistance;
               res.add(p);
               cur = p;
               p = getPointBetweenPointAB(p,next,target);
            }

            target = oneDistance - getTwoPointDistance(cur,next);
        }

        return res;
    }

    private static Point getPointBetweenPointAB(Point a, Point b, double distance){
        double abDistance = getTwoPointDistance(a,b);
        if(abDistance < distance)
            return null;
        else{
            double slope = getSlope(a,b);
            if(slope == Double.NEGATIVE_INFINITY){
                return new Point(a.x, a.y + distance) ;
            }
            double base = Math.sqrt(Math.pow(distance,2)/(Math.pow(slope,2)+1));

            base = slope >= 0 ? - base : base;

            return new Point(a.x + base,a.y + base*slope);
        }
    }

    private static double getSlope(Point a, Point b){
        return (a.y -b.y)/(a.x - b.x);
    }

    private static double getPerimeter(List<Point> points){
        double res = 0.0;
        for(int i = 0; i < points.size();i++){
            int next = i + 1 ;
            if(next == points.size())
                next = 0;
            res += getTwoPointDistance(points.get(i),points.get(next));
        }

        return res;
    }

    private static double getTwoPointDistance(Point a, Point b){
        return Math.sqrt(Math.pow(a.x- b.x,2) + Math.pow(a.y- b.y,2));
    }

    public static void main(String[] args) {
        List<Point> points = new LinkedList<Point>();
        points.add(new Point(0.0,0.0));
        points.add(new Point(0.0,3.0));
        points.add(new Point(4.0,0.0));

        List<Point> splitPoints = split(points,5);

        for(Point p : splitPoints){
            p.print();
        }
    }

结论

自己算法太弱了,需要苦练一下 T_T