1. 变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析
关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:
f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。
f(3) = f(3-1) + f(3-2) + f(3-3)
...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
说明：
1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。
2）n = 1时，只有1种跳法，f(1) = 1
n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1） ，f(2) = f(2-1) + f(2-2)
n = 3时，会有三种跳得方式，1阶、2阶、3阶，
那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)
因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
- n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
- 由以上已经是一种结论，但是为了简单，我们可以继续简化：
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出：
f(n) = 2*f(n-1)
- 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：
| 1 ,(n=0 )
f(n) = | 1 ,(n=1 )
| 2*f(n-1),(n>=2)
代码
public class Solution {
public int JumpFloorII(int target) {
if(target<=0){
return -1;
}else if(target==1){
return 1;
}else{
return 2*JumpFloorII(target-1);
}
}
}
2. 矩形覆盖
题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法
分析
斐波那契数列递归
代码
public class Solution {
public int RectCover(int target) {
if(target<=0){
return 0;
}else if(target==1||target==2){
return target;
}else{
return RectCover(target-1)+RectCover(target-2);
}
}
}
3. 二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
分析
定义一个变量count,记录二进制中1的个数
(n & 1)把n与1按位与，因为1除了最低位，其他位都为0，所以按位与结果取决于n最后一位，如果n最后一位是1，则结果为1.反之结果为0。用count+=(n & 1)来记录
每次按位于后把n向右移一位n>>>=1
代码
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n!=0){
count+=(n & 1);
System.out.println(n);
n>>>=1;
}
return count;
}
}
4. 数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
分析
- 把exponent取绝对值进行*=保留结果
- 如果exponent<0对结果取倒
代码
public class Solution {
public double Power(double base, int exponent) {
double ss = 1;
for (int i = 0; i < Math.abs(exponent); i++) {
ss *= base;
}
if(exponent<0){
ss = 1/ss;
}
return ss;
}
}
5. 调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
分析
可以用冒泡排序的思路前一位是偶数后一位是奇数时进行交换
代码
public class Solution {
public void reOrderArray(int [] array) {
int temp = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length-i-1; j++) {
if(array[j]%2==0&&array[j+1]%2!=0){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
6. 链表中倒数第k个节点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
分析
- 遍历得到链表的总长度count
- 倒数第k个即为正数第count-k个
- 当链表总长度小于k时返回null
代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
int count = 0;
ListNode temp = head;
while(temp!=null){
count++;
temp = temp.next;
}
if(count<k){
return null;
}
temp = head;
for (int i = 0; i <count-k; i++) {
temp = temp.next;
}
return temp;
}
}
三种移位运算符的移动规则和使用如下所示：
<<运算规则：按二进制形式把所有的数字向左移动对应的位数，高位移出（舍弃），低位的空位补零。
语法格式：
需要移位的数字 << 移位的次数
例如： 3 << 2，则是将数字3左移2位
计算过程：
3 << 2
首先把3转换为二进制数字0000 0000 0000 0000 0000 0000 0000 0011，然后把该数字高位（左侧）的两个零移出，其他的数字都朝左平移2位，最后在低位（右侧）的两个空位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 1100，则转换为十进制是12.数学意义：在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方。
>>运算规则：按二进制形式把所有的数字向右移动对应巍峨位数，低位移出（舍弃），高位的空位补符号位，即正数补零，负数补1.
语法格式：
需要移位的数字 >> 移位的次数
例如11 >> 2，则是将数字11右移2位
计算过程：11的二进制形式为：0000 0000 0000 0000 0000 0000 0000 1011，然后把低位的最后两个数字移出，因为该数字是正数，所以在高位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010.转换为十进制是3.数学意义：右移一位相当于除2，右移n位相当于除以2的n次方。
>>>运算规则：按二进制形式把所有的数字向右移动对应巍峨位数，低位移出（舍弃），高位的空位补零。对于正数来说和带符号右移相同，对于负数来说不同。
其他结构和>>相似。
