笔试题解答

/**
 * @author shishusheng
 * @date 2018/8/22 23:35
 */
import java.util.ArrayList;

public class ReverseList {

    private class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    ArrayList<Integer> arrayList = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null){
            this.printListFromTailToHead(listNode.next);
            arrayList.add(listNode.val);
        }
        return arrayList;
    }
}

显然是斐波那契数列

/**
 * @author shishusheng
 * @date 2018/8/22 23:35
 */
import java.util.ArrayList;

public class JumpFloor {

    public int JumpFloorII(int N) {
        int[] stepArr = new int[N];
        stepArr[0] = 1;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                stepArr[i] += stepArr[j];
            }
            stepArr[i]+=1;
        }
        return stepArr[N - 1];
    }
}

/**
 * @author shishusheng
 * @date 2018/8/22 23:35
 */

public class JudgeTriAngle {

    public String judgeTriAngle(int a, int b, int c) {
        if (a + b > c && b + c > a && c + a > b) {
            return "成立";
        }
        return "不成立";
    }

}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author shishusheng
 * @date 2018/8/22 23:35
 */

public class HourseRun {

    private class Point {
        private int x;
        private int y;
        private int shortest;

        public Point() {
        }

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public int getShortest() {
            return shortest;
        }

        public void addShortest(Point point) {
            this.shortest = point.getShortest() + 1;
        }
    }

    private static final int MAX_SIZE = 8;
    private static final int MIN_SIZE = 1;
    private Point start;
    private Point end;

    private List<Point> direction = new ArrayList<>();
    private LinkedList<Point> unVisitedPoint = new LinkedList<>();
    private int[][] markVisited = new int[9][9];

    public HourseRun(Point start, Point end) {
        this.start = start;
        this.end = end;
        init();
    }

    public void init() {
        direction.add(new Point(2, 1)); //right up horizontal
        direction.add(new Point(2, -1)); //right down horizontal
        direction.add(new Point(1, -2)); //right down vertical
        direction.add(new Point(-1, -2)); //left down vertical
        direction.add(new Point(-2, -1)); //left down horizontal
        direction.add(new Point(-2, 1)); //left up horizontal
        direction.add(new Point(-1, 2)); //left up vertical
        direction.add(new Point(1, 2)); //right up vertical
    }

    private int bfs() {
        Point current = new Point();
        while (!unVisitedPoint.isEmpty()) {
            current = unVisitedPoint.poll();
            markVisited[current.getX()][current.getY()] = 1;

            if (current.getX() == end.getX() && current.getY() == end.getY()) {
                break;
            }

            for (Point aDirection : direction) {
                Point next = new Point(current.getX() + aDirection.getX(), current.getY() + aDirection.getY());
                next.addShortest(current);

                if (next.getX() < MIN_SIZE || next.getX() > MAX_SIZE || next.getY() < MIN_SIZE || next.getY() > MAX_SIZE) {
                    continue;
                }

                if (markVisited[next.getX()][next.getY()] == 0) {
                    unVisitedPoint.add(next);
                }
            }

        }
        return current.getShortest();
    }

    public int find() {
        this.unVisitedPoint.add(start);
        return bfs();
    }


}