1、斐波那契数列
【题目】
大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。
（视频教程推荐：java课程）
【代码】
package swear2offer.array;
public class FeiBoNaQi {
/**
* 大家都知道斐波那契数列，现在要求输入一个整数 n，
* 请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。
* 0,1,1,2,3,5
* n2) {
int[] a = new int[n+1];
a[0] = 0;
a[1] = 1;
a[2] = 1;
for (int i=3; i<p>2、矩形覆盖</p><p>【题目】</p><p>我们可以用 21 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 21 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？</p><p>比如 n=3 时，2*3 的矩形块有 3 种覆盖方法：</p><p><img src="https://img.php.cn/upload/image/284/967/245/1604906618624869.png?x-oss-process=image/resize,p_40" title="1604906618624869.png" alt="12711bde10f197c3e9af47c34b0cc46.png"></p><p>代码：</p><pre class="brush:php;toolbar:false">package swear2offer.array;
public class Rectangle {
/**
* f[0] = 0;
* f[1] = 1;
* f[2] = 2;
* f[3] = 3;
* f[4] = 5;
* f[5] = 8;
* f[n] = f[n-1] + f[n-2]
* */
public int RectCover(int target) {
if (target <p>【思考】</p><p>最直白的结题方式就是找规律，从总结的规律可以看出这是斐波那契数列的实现方式；另一种就是根据题意来解答，求n的方法，这类问题很容易想到是从n-1来求解，而第一个块是横（f[n-2]）是竖(f[n-1])，分别对应不同的情况</p><p>（更多相关面试题推荐：<a href="https://www.php.cn/java/interview/" target="_blank">java面试题及答案</a>）</p><p>3、二进制中 1 的个数</p><p>【题目】</p><p>输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。</p><p>【代码】</p><pre class="brush:php;toolbar:false">package swear2offer.array;
public class Binary {
/**
* 输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。
* */
public int NumberOf1(int n) {
int count;
count = 0;
while(n != 0) {
n = n & (n-1);// 与操作就是二进制的操作，适用原码和补码
count ++;
}
return count;
}
}
【思考】
负数的反码： 符号位不变,其余各位按位取反负数的补码：在其反码的基础上+1
如果一个整数不为 0，那么这个整数至少有一位是 1。如果我们把这个整数减 1，那么原来处在整数最右边的 1 就会变为 0，原来在 1 后面的所有的 0 都会变成 1 (如果最右边的 1 后面还有 0 的话)。其余所有位将不会受到影响。
举个例子：一个二进制数 1100，从右边数起第三位是处于最右边的一个 1。减去 1 后，第三位变成 0，它后面的两位 0 变成了 1，而前面的 1 保持不变，因此得到的结果是 1011. 我们发现减 1 的结果是把最右边的一个 1 开始的所有位都取反了。这个时候如果我们再把原来的整数和减去 1 之后的结果做与运算，从原来整数最右边一个 1 那一位开始所有位都会变成 0。如 1100&1011=1000. 也就是说，把一个整数减去 1，再和原整数做与运算，会把该整数最右边一个 1 变成 0. 那么一个整数的二进制有多少个 1，就可以进行多少次这样的操作。
4、数值的整数次方
【题目】
给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。
保证 base 和 exponent 不同时为 0
【代码】
package swear2offer.array;
public class Power {
public double Power(double base, int exponent) {
if (base == 0) return 0;
if (exponent == 0) return 1;
int count;
boolean flag;
double temp;
count = 1;
temp = base;
flag = true;// 标记正负
if (exponent <p>【思考】</p><p>本题难度并不大，算法也不是很复杂，但是边边角角很容易遗漏，</p><p>第一点就是exponent的正负，很容易就漏掉负数的情况</p><p>其次，base==0和exponent==0的情况是不一样的</p><p>最后，base累乘的时候，是不能用本身的，因为base是不断变大的。</p><p>5、调整数组顺序使奇数位于偶数前面</p><p>【题目】</p><p>输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。</p><p>【代码】</p><pre class="brush:php;toolbar:false">package swear2offer.array;
import java.util.Arrays;
public class OddEven {
/**
* 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
* 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
* 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
*
* 时空复杂度较高的算法：
* 新建一个数组b，用来保存奇数，在重新变量一次，保存偶数
* 时空复杂度0(n)
* */
public void reOrderArray1(int [] array) {
int n,i,j;
n = array.length;
int[] b = new int[n];
j = 0;// 用来保存数组B的下标
for (i=0; i<n>i; p--) {
array[p] = array[p-1];
}
array[i] = temp;
// 此时把i,j标记到 未交换前的偶数位置的下一个
i ++;
j = i;
}
}
}
public static void main(String[] args) {
int[] a = {1,4,6,3,2,5,8};
int[] b = {2,4,6,1,3,5,7};
new OddEven().reOrderArray(b);
System.out.println(Arrays.toString(b));
}
}</n>
【思考】
显然，创建新数组的方式，是一种取巧的方式，题目要求是需要在本数组上进行操作，第二种方式就是采用在本数组上进行操作的，而这种双游标递进的方式跟快速排序的思想很接近。
相关推荐：java入门
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
