面试题10：斐波那契数列
题目一：斐波那契数列
题目一：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：
f(x) =
\begin{cases}
0 & n=0 \\
1 & n=1 \\
f(n-1)+f(n-2) &{n>1}\\
\end{cases} - 算法：循环，并把结果取模防止溢出
测试：力扣
public int fib(int n) {
if (n < 0) {
return -1;
}
if (n < 2) {
return n;
}
int fibMinusOne = 1;
int fibMinusTwo = 0;
int fibN = 0;
for (int i = 2; i <= n; i++) {
fibN = (fibMinusOne + fibMinusTwo) % 1000000007; // 避免溢出；如果放到最后取模可能会在这一步发生溢出使最终结果错误
fibMinusTwo = fibMinusOne;
fibMinusOne = fibN;
}
return fibN;
} - 算法：使用long数据类型
public long fibonacci(int n) {
if (n < 0) {
return -1;
}
if (n < 2) {
return n;
}
long fibOne = 0;
long fibTwo = 1;
long finN = 0;
for (int i = 2; i <= n; i++) {
finN = fibOne + fibTwo;
fibOne = fibTwo;
fibTwo = finN;
}
return finN;
} - 算法：自下向上和自上向下的动态规划
// DP-bottom up time-O(n) space-O(n)
public int fib_(int n) {
if (n < 0) {
return -1;
}
if(n < 2)
return n;
int[] fib = new int[n + 1];
fib[1] = 1;
for(int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
// DP-top down time-O(n) space-O(n)
public int fib(int n) {
if (n < 0) {
return -1;
}
int[] fib = new int[n+1];
return fibDP(n, fib);
}
public int fibDP(int n, int[] fib) {
if(n < 2)
return n;
else if(fib[n] != 0)
return fib[n];
else
return fib[n] = fib(n - 1) + fib(n - 2);
} - 算法：矩阵运算
算法：用归纳法可以证明以下数学公式：
\left[ \begin{matrix} f(n) & f(n-1) \\ f(n-1) & f(n-2) \\ \end{matrix} \right] = {\left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right]}^{n-1}然后初始矩阵的乘方可以通过以下递归实现O(logn)时间的算法
a^n = \begin{cases} a^{\frac{n}{2}} * a^{\frac{n}{2}} & n为偶数\\ a^{\frac{n-1}{2}} * a^{\frac{n-1}{2}} * a & n为奇数\\ \end{cases}
测试：自测
public long fibonacci_(int n) {
if (n < 0) {
return -1;
}
if (n < 2) {
return n;
}
Matrix2By2 matrix2By2 = MatrixPower(n-1);
return matrix2By2.m00;
}
class Matrix2By2 {
long m00;long m01;long m10;long m11;
Matrix2By2() {}
Matrix2By2(long x, long y, long z, long w) { m00 = x;m01 = y;m10 = z;m11 = w;}
}
private Matrix2By2 MatrixMultiply(Matrix2By2 matrix1, Matrix2By2 matrix2) {
return new Matrix2By2(matrix1.m00 * matrix2.m00 + matrix1.m01 * matrix2.m10,
matrix1.m00 * matrix2.m01 + matrix1.m01 * matrix2.m11,
matrix1.m10 * matrix2.m00 + matrix1.m11 * matrix2.m10,
matrix1.m10 * matrix2.m01 + matrix1.m11 * matrix2.m11);
}
private Matrix2By2 MatrixPower(int n) {
Matrix2By2 matrix = new Matrix2By2();
if (n == 1) {
matrix = new Matrix2By2(1, 1, 1, 0);
} else if(n % 2 == 0) {
matrix = MatrixPower(n / 2);
matrix = MatrixMultiply(matrix, matrix);
} else if(n % 2 == 1) {
matrix = MatrixPower((n - 1) / 2);
matrix = MatrixMultiply(matrix, matrix);
matrix = MatrixMultiply(matrix, new Matrix2By2(1, 1, 1, 0));
}
return matrix;
} 题目二：青蛙跳台阶1
题目二：一个青蛙一次可以跳上一级台阶，也可以跳上两级台阶。求该青蛙跳上n级台阶总共有多少种跳法。
算法：同斐波那契数列，但初始项为f(1) = 1; f(2) = 2;，且不能再用矩阵来计算
题目三：青蛙跳台阶2
题目三：一个青蛙一次可以跳上一级台阶，也可以跳上两级台阶······也可以跳上n级台阶。求该青蛙跳上n级台阶总共有多少种跳法。
算法：f(n) = f(1)+f(2)+···+f(n-1)+1
f(n) = 2^(n-1)
题目四：2X1矩形覆盖2Xn矩形
题目四：用2X1的小矩形横着或竖着去覆盖2Xn的大矩形总共有多少种方法。
算法：最左边第一块竖着放，则剩余2X(n-1);最左边第一块横着放，则必须再来一块横着放与它对齐，则剩余2X(n-2)；所以f(n)=f(n-1)+f(n-2);f(1)=1;f(2)=2；
面试题11：旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
测试：力扣
public int minArray(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return -1;
}
int index1 = 0;
int index2 = numbers.length - 1;
int indexMid = (index1 + index2) >> 1;
if (numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1]) {
return minArrayInorder(numbers);
}
indexMid = index1;
while (numbers[index1] >= numbers[index2]) {
if (index2 - index1 <= 1) {
return numbers[index2];
}
indexMid = (index1 + index2) >> 1;
if (numbers[indexMid] >= numbers[index1]) {
index1 = indexMid;
}
if (numbers[indexMid] <= numbers[index2]) {
index2 = indexMid;
}
}
return numbers[indexMid];
}
private int minArrayInorder(int[] numbers) {
int res = numbers[0];
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] < res) {
res = numbers[i];
}
}
return res;
} 面试题12：矩阵中的路径
题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
A B T G
C F C S
J D E H
测试：力扣
public boolean exist(char[][] board, String word) {
// 排除异常输入
if (board == null || board.length == 0) {
return false;
}
for (int i = 0; i < board.length; i++) {
if (board[i] == null || board[i].length == 0) {
return false;
} else {
if (i > 0 && board[i].length != board[i-1].length) {
return false;
}
}
}
if (word == null || word.length() == 0) {
return true;
}
int rows = board.length;
int cols = board[0].length;
boolean[][] visited = new boolean[rows][cols];
int pathLength = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (hasPathCore(board, i, j, word, pathLength, visited)) {
return true;
}
}
}
return false;
}
private boolean hasPathCore(char[][] board, int row, int col, String word, int pathLength, boolean[][] visited) {
if (pathLength == word.length()) {
return true;
}
boolean hasPath = false;
if (row >= 0 && row < board.length && col >= 0 && col < board[0].length &&
board[row][col] == word.charAt(pathLength) && !visited[row][col]) {
pathLength++;
visited[row][col] = true;
hasPath = hasPathCore(board, row, col+1, word, pathLength, visited) ||
hasPathCore(board, row, col-1, word, pathLength, visited) ||
hasPathCore(board, row+1, col, word, pathLength, visited) ||
hasPathCore(board, row-1, col, word, pathLength, visited);
if (!hasPath) {
pathLength--;
visited[row][col] = false;
}
}
return hasPath;
} 面试题13：机器人的运动范围
题目：地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动，它每一次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格(35,37)，因为3+5+3+7=18。但它不能进入方格(35,38)，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
- 算法：
- visited数组 + 递归
- 任意位置可运动范围等于当前这个位置加上四个方向的运动范围
public int movingCount(int rows, int cols, int threshold) {
if (rows <= 0 || cols <= 0 || threshold < 0) {
return 0;
}
boolean[][] visited = new boolean[rows][cols];
return movingCountCore(rows, cols, 0, 0, visited, threshold);
}
private int movingCountCore(int rows, int cols, int row, int col, boolean[][] visited, int threshold) {
int count = 0;
if (check(rows, cols, row, col, visited, threshold)) {
visited[row][col] = true;
// all together how many grids the root can arrive
count = 1 + movingCountCore(rows, cols, row, col+1, visited, threshold)
+ movingCountCore(rows, cols, row, col-1, visited, threshold)
+ movingCountCore(rows, cols, row+1, col, visited, threshold)
+ movingCountCore(rows, cols, row-1, col, visited, threshold);
}
return count;
}
private boolean check(int rows, int cols, int row, int col, boolean[][] visited, int threshold) {
if (row >= 0 && row < rows && col >= 0 && col < cols &&
!visited[row][col] && getDigitSum(row) + getDigitSum(col) <= threshold) {
return true;
}
return false;
}
private int getDigitSum(int x) {
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
return sum;
} 面试题14：剪绳子
题目：给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m≥1）。每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1]…*k[m]可能的最大乘积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。
- 算法：动态规划
测试：力扣
public int cuttingRope(int n) {
// 异常输入
if (n < 0) {
return -1;
}
// 特殊输入
if (n < 2) {
return 0;
}
if (n < 4) {
return n - 1;
}
int[] product = new int[n+1];
product[0] = 0; // 注意这里的product[x]的初始化不是n=x的结果，而是动态规划的初始状态
product[1] = 1;
product[2] = 2;
product[3] = 3;
for (int i = 4; i <= n; i++) {
int max = 0;
for (int j = 1; j <= i >> 1; j++) {
int products = product[j]*product[i-j];
if (max < products) {
max = products;
}
}
product[i] = max;
}
return product[n];
} - 算法：贪婪算法
算法：当n≥5时，尽可能多地剪长度为3的绳子；当剩下的绳子为4时，把绳子剪成两段长度为2的绳子。
证明：当n≥5时，可以证明2(n-2)>n并且3(n-3)>n，也就是说，当绳子长度大于等于5时，就把它剪成长度为3或者2的绳子段；另外3(n-3)>2(n-2)，因此应该尽可能地多剪长度为3的绳子段；当绳子的长度为4时，显然2×2>3×1；因为2×2=4，也可以选择不剪。
测试：力扣
public int cuttingRope(int n) {
// 异常输入
if (n < 0) {
return -1;
}
// 特殊输入
if (n < 2) {
return 0;
}
if (n < 4) {
return n - 1;
}
int timeOf3 = n / 3;
if (n == 1 + timeOf3 * 3) {
timeOf3 -= 1;
}
int timeOf2 = (n - timeOf3 * 3) / 2;
return (int)(Math.pow(3, timeOf3) * Math.pow(2, timeOf2));
} 说明：另一种形式的贪婪算法
测试：力扣
public int cuttingRope_1(int n) {
// 异常输入
if (n < 0) {
return -1;
}
int[] product = new int[60];
product[0] = 0;
product[1] = 0;
product[2] = 1;
product[3] = 2;
product[4] = 4;
product[5] = 6;
product[6] = 9;
for (int i = 7; i <= n; i++) {
product[i] = product[i-3] * 3;
}
return product[n];
} - 算法：取余避免溢出
public int cuttingRope(int n) {
// 异常输入
if (n < 0) {
return -1;
}
// 特殊输入
if (n < 2) {
return 0;
}
if (n < 4) {
return n - 1;
}
int timeOf3 = n / 3;
if (n == 1 + timeOf3 * 3) {
timeOf3 -= 1;
}
int timeOf2 = (n - timeOf3 * 3) / 2;
long res = 1; // long数据类型避免中间状态溢出
for (int i = 0; i < timeOf3; i ++) {
res *= 3;
res %= 1000000007;
}
for (int i = 0; i < timeOf2; i ++) {
res *= 2;
res %= 1000000007;
}
return (int)res;
} 面试题15：二进制中1的个数
题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。
- 算法：和n-1做按位与
public int numberOf1(int n) {
int count = 0;
while (n != 0) {
count++;
n &= n-1;
}
return count;
} - 算法：和2的幂逐个做按位与
public int numberOf1(int n) {
int count = 0;
int flag = 1;
while (flag != 0) {
if ((n & flag) != 0) {
count++;
}
flag <<= 1;
}
return count;
} - 算法：逐位进行逻辑右移
public int numberOf1(int n) {
int count = 0;
while (n != 0) {
if ((n & 1) == 1) {
count++;
}
n >>>= 1;
}
return count;
} 
京公网安备 11010502036488号