面试题目......

题目一:

1、从n个人中选择任意数量的人员组成一支队伍，然后从一支队伍中选出一位队长，不同的队长算不同的组合，问这样的组合的数量对10^9+7取模。

数据范围：1 <= n <= 1000000000;

示例

输入：n = 2

输出：4

解释,(1),(2)(1,2),(2,1)四种，括号第一个为队长

import java.util.Scanner;

public class Main {
    static int mod = 1000000007;

    static long binaryPow(long a) {
        if (a == 0)
            return 1;// 2^0=1 b==0
        long mul = binaryPow(a/2);
        if ((a & 1) == 0) {//偶数
            return (mul * mul) % mod;
        } else {
            return (2 * mul * mul) % mod;
        }
        /**
         * $n*2^{n-1}n∗2 
            n−1
             $
            要求2^n - 1，O(logN)复杂度，经典的快速幂算法。
            2*n-1= n*n-1 ==> n*n/2
            2*n-1= n*n-1 ==> n/2*n/2
         */
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x = n;
        System.out.println((binaryPow(n - 1) * n) % mod);
    }
}

题目2:

一个地图n*m，包含1个起点，1个终点，其他点包括可达点和不可达点。每一次可以：上下左右移动，或使用1点能量从（i,j)瞬间移动到（n-1-i, m-1-j)，最多可以使用5点能量。

数据范围：2 <= n,m <= 500;

示例

输入：

4 4

#S..

E#..

....

....
输出：

4

解释:S(0,1)先瞬移到(3, 2)，然后往上一步，往右一步，瞬移到E，一共4步

思路: 就是简单的走迷宫BFS

public class BFS {
    static int n = 0;
    static int m = 0;
    static char map[][] = new char[100][100];
    static int ex;
    static int ey;
    static int X[] = new int[] { 0, 0, 1, -1 };
    static int Y[] = new int[] { 1, -1, 0, 0 };

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for (int i = 0; i < n; i++) {
            map[i] = in.next().toCharArray();
        }
        Queue<Node> queue = new LinkedList<Node>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'S') {
                    Node startnode = new Node(i, j);
                    queue.add(startnode);
                    System.out.print(i + " => ");
                    System.out.println(j);
                    map[i][j] = 'X';
                }
                if (map[i][j] == 'E') {
                    ex = i;
                    ey = j;
                    System.out.print(i + " => ");
                    System.out.println(j);
                }
            }
        }
        new BFS().bfs(queue);
    }

    private void bfs(Queue<Node> queue) {
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Node topnode = queue.poll();
                if (topnode.x == ex && topnode.y == ey) {
                    System.out.println(topnode.step);
                    return;
                }
                for (int i = 0; i < 4; i++) {
                    int curx = topnode.x + X[i];
                    int cury = topnode.y + Y[i];
                    if (check(curx, cury)) {
                        Node newnode = new Node(curx, cury);
                        newnode.step = topnode.step + 1;
                        queue.add(newnode);
                        map[curx][cury] = 'X';
                    }
                }
                // （n-1-i, m-1-j)，
                int flyx = n - 1 - topnode.x;
                int flyy = m - 1 - topnode.y;
                if (check(flyx, flyy) && topnode.fly < 5) {
                    Node flynode = new Node(flyx, flyy);
                    flynode.step = topnode.step + 1;
                    flynode.fly = topnode.fly + 1;
                    queue.add(flynode);
                    map[flyx][flyy] = 'X';
                }
            }
        }
    }

    private boolean check(int curx, int cury) {
        if (curx < 0 || curx >= n || cury < 0 || cury >= m)
            return false;
        if ((map[curx][cury] != '.' && map[curx][cury] != 'E'))
            return false;
        return true;
    }
}

class Node {
    int x;
    int y;
    int step;
    int fly;

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