把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。1
2
3
4
5
6
7
8
9
10
11import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
for(int i=0; i<array.length -1; i++){
if(array[i+1] < array[i]){
return array[i+1]; //一开始没看懂这道题想问啥就按照例子写了个查找= =，后来看大佬们说是考二分法
}
}
return 0;
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int left = 0;
int right = array.length - 1;
if(array.length == 0){
return 0;
}
while(left < right){ //二分
int mid = (left + right)/2;
if(array[mid] > array[right]){
left = mid + 1;
}
else if(array[mid] < array[right]){
right = mid;
}
else{
right --;
}
}
return array[left];
}
}大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0。n<=39
1
2
3
4
5
6
7
8
9public class Solution {
public int Fibonacci(int n) {
if(n < 1){
return 0;}
if(n < 3){
return 1;}
return Fibonacci(n-1) + Fibonacci(n-2);
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//人家题目都说了这题考递归，大佬们又说递归有可能会导致栈溢出
public class Solution {
public int Fibonacci(int n) {
int pre = 1;
int prep = 0;
int result = 0;
if(n < 1){
return prep;}
if(n < 2){
return pre;}
else{
for(int i = 2; i <= n; i++){ //写循环存的少
result = pre + prep;
prep = pre;
pre = result;
}
return result;
}
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public class Solution {
public int Fibonacci(int n) {
int g = 1;
int f = 1;
if(n < 1){
return 0;}
if(n < 3){
return g;}
while(n-- > 2){ //动态规划
g += f;
f = g - f;
}
return g;
}
}一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果。
对于本题,前提只有一次1阶或者2阶的跳法。//大佬说的
a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
e.可以发现最终得出的是一个斐波那契数列.
f(1) = 1; f(2) = 2;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public int JumpFloor(int n) {
int pre = 2;
int prep = 1;
int result = 0;
if(n < 2){
return 1;}
if(n < 3){
return 2;}
else{
for(int i = 3; i <= n; i++){
result = pre + prep;
prep = pre;
pre = result;
}
return result;
}
}
}
- 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
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) = 2^(n-1)
1
2
3
4
5
6
7
public class Solution {
public int JumpFloorII(int target) {
if(target == 1){
return 1;}
return 2*JumpFloorII(target - 1);
}
}
1
2
3
4
5
public class Solution {
public int JumpFloorII(int target) {
return 1<<(target -1); ////通过移位计算2的次方。这个移位太强了！大佬们好厉害！
}
}
Java中的移位操作
>> 是带符号右移，若左操作数是正数，则高位补“0”，若左操作数是负数，则高位补“1”.
<< 将左操作数向左边移动，并且在低位补0.
>>> 是无符号右移，无论左操作数是正数还是负数，在高位都补“0”
1
2
3
4
5
public class Solution {
public int JumpFloorII(int target) {
return (int)Math.pow(2,target - 1);
}
}
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
// 我画了半天，一看讨论区，还是斐波那契！今天就过去不了！- -1
2
3
4
5
6
7
8
9
10
11
12
13
14# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
pre = 2
prep = 1
result = 0
if number <= 2:
return number
for i in range(2, number):
result = pre + prep
prep = pre
pre = result
return result