剑指offer（五）

剑指offer刷题(五)——旋转数组的最小数字

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路

数组的最小值相当于作为两个非递减排序数组的分界,且第一个数组里的元素永远都大于等于第二个数组里的元素.也就是说我们得到一个序列,该序列的第一个元素肯定大于等于最后一个元素.我们可以考虑二分查找法.先找中间数,中间数若大于等于原序列的第一个元素且小于原序列的最后一个元素则这个中间数包含在第一个非递减数组中,所以最小元素在中间数的右侧序列中.反之则在左侧序列中.应该也会遇到这种情况:中间数等于第一个数和最后一个数.这样无法得到最小元素会在左侧还是右侧,则只能顺序查找了

C++

#include<iostream>
#include<vector>
using namespace std;


class Solution{
public:
    int getmin(vector<int>arr)
    {
        int number=arr.size();
        if(number==1)
        {
            return number;
        }
        else if(number==0)
        {
            return 0;
        }
        else{
            int mid=number/2;
            int left=0;
            int right=number-1;
            if(arr[left]<arr[right])
            {
                cout<<"非旋转数组。"<<endl;
            }
            else if(arr[left]>arr[right])
            {
                if(arr[left]>arr[mid])
                {
                    vector<int> newarr;
                    for(int i=0;i<mid;i++)
                    {
                        newarr.push_back(arr[i]);
                    }
                    return getmin(newarr);
                }
                else{
                    vector<int> newarr;
                    for(int i=mid;i<number;i++)
                    {
                        newarr.push_back(arr[i]);
                    }
                    return getmin(newarr);
                }

            }
            else
            {
                if(arr[left]>arr[mid])
                {
                    vector<int> newarr;
                    for(int i=0;i<mid;i++)
                    {
                        newarr.push_back(arr[i]);
                    }
                    return getmin(newarr);
                }
                else if(arr[left]<arr[mid])
                {
                     vector<int> newarr;
                    for(int i=mid;i<number;i++)
                    {
                        newarr.push_back(arr[i]);
                    }
                    return getmin(newarr);
                }
                else
                {
                    int mini=arr[0];
                    for(int i=1;i<number;i++)
                    {
                        if(arr[i]<mini)
                            mini=arr[i];
                    }
                    return mini;
                }
            }
        }


    }


};


int main()
{
    int a[]={1,1,1,0,1};
    vector<int> arr;
    for(int i=0;i<5;i++)
    {
        arr.push_back(a[i]);
    }
    Solution s;
    int n=s.getmin(arr);
    cout<<n;
    return 0;
}
Python
重新思考了一下这个问题,只需要找出list里最大的那个数,当然这个数可能有多个,要找最大那个,并且是最后面的那一个,那么这个数的下一个一定是最小的那个数
```python
class Solution:
    def findpos(self,rotateArray):
        length=len(rotateArray)

        if(length==1):
            return 0
        midpos=int(length/2)
        if(rotateArray[midpos]>rotateArray[0]):
            return midpos+self.findpos(rotateArray[midpos:])
        elif(rotateArray[midpos]<rotateArray[0]):
            return self.findpos(rotateArray[:midpos])
        elif((rotateArray[midpos]==rotateArray[0])and(rotateArray[midpos]!=rotateArray[length-1])):
            return midpos+self.findpos(rotateArray[midpos:])
        else:
            a=self.findpos(rotateArray[:midpos])
            b=midpos+self.findpos(rotateArray[midpos:])
            if(rotateArray[(a+1)%length]>rotateArray[(b+1)%length]):
                return a
            else:
                return b
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        length=len(rotateArray)
        if(length==0):
            return 0
        maxpos=self.findpos(rotateArray)
        print(maxpos)
        return rotateArray[(maxpos+1)%length]

#剑指offer刷题(六)——斐波那契数列
##题目
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。（n<=39）
斐波那契数列公式为:
$$
f(n)=
\begin{cases}
0 \ \ \ \ \ n=0\\
1 \ \ \ \ \ n=1\\
f(n-1)+f(n-2) \ \ \ \ \ n＞1\\
\end{cases}
$$
##思路
该题的递归写起来很简便,但存在很严重的效率问题.我们以求解f(10)为例分析递归的求解过程.想求f(10),需要先求得f(9)和f(8).同样,想求得f(9),需要先求得f(8)和f(7)...我们可以用树形结构来表示这种依赖关系.如下图所示：
![pic1](pic1.png)
我们不难发现在这棵树中有很多结点是重复的，而且重复的结点数会随着n的增加而急剧增加，这意味计算量会随着n的增加而急剧增大。事实上，递归方法计算的时间复杂度是以n的指数的方式递增的。

##C++
```C++
#include<iostream>
using namespace std;

class Solution{
public:
    int Fibonacci(int n){
        if(n<=0)
            return 0;
        else if(n==1)
            return 1;
        else
        {
            int a=0;
            int b=1;
            int c=0;
            for(int i=2;i<=n;i++)
            {
                c=a+b;
                a=b;
                b=c;
            }
            return c;
        }

    }



};

int main()
{
    Solution s;
    for(int i=0;i<39;i++)
        cout<<s.Fibonacci(i)<<endl;
    return 0;
}

Python

class Solution:
    def Fibonacci(self, n):
        # write code here
        A=[0,1,1]
        if(n<=2):
            return A[n]
        else:
            for i in range(3,n+1):
                A.append(A[i-1]+A[i-2])
            return A[n]

剑指offer刷题(七)——跳台阶

题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路

已知青蛙得跳分为两种,跳一级与跳两级.我们现在要求跳到第n级有几种跳法？因为跳到n级的前一步只可能出现在第n-1级和第n-2级.所以也有斐波那契形式f(n)=f(n-1)+f(n-2)

C++

#include<iostream>
using namespace std;

class Solution{
public:
    int method(int n)
    {
        if(n<=0)
        {
            cout<<"wrong number!"<<endl;
        }
        else if(n==1)
        {
            return 1;
        }
        else if(n==2)
        {
            return 2;
        }
        else{
            return method(n-1)+method(n-2);
        }
    }
    int method2(int n)
    {
        if(n<=0)
        {
            cout<<"wrong number!"<<endl;
        }
        else if(n==1)
        {
            return 1;
        }
        else if(n==2)
        {
            return 2;
        }
        else
        {
            int a=1;
            int b=2;
            int c=0;
            for(int i=3;i<=n;i++)
            {
                c=a+b;
                a=b;
                b=c;
            }
            return c;
        }
    }


};
int main()
{
    Solution s;
    cout<<s.method(9)<<endl;
    cout<<s.method2(9)<<endl;

    return 0;
}

Python
斐波那契的变体

class Solution:
    def jumpFloor(self, number):
        # write code here
        A=[0,1,2]
        if(number<=2):
            return A[number]
        for i in range(3,number+1):
            A.append(A[i-1]+A[i-2])
        return A[number]

剑指offer刷题(八)——变态跳台阶

题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路

已知:
f(n)=f(n-1)+f(n-2)+…+f(1)+1
f(n-1)=f(n-2)+…..+f(1)+1
则:
f(n)=2(f(n-2)+…+f(1)+1)
推导可得
$f(n)=2^{(n-1)}$
所以求解该跳法有直接的公式可以得出

C++

#include<iostream>
using namespace std;
class Solution{
public:
    int Jump(int n)
    {
        if(n<0)
        {
            cout<<"Wrong number!";
        }
        else if(n==0)
        {
            return 0;
        }
        else{
            int total=1;
            for(int i=1;i<n;i++)
            {
                total=total*2;
            }
            return total;
        }
    }

};


int main()
{
    Solution s;
    cout<<s.Jump(7)<<endl;

    return 0;
}

Python
也是斐波那契的变体,注意要加上1,1是一下子直接跳上N

class Solution:
    def jumpFloorII(self, number):
        # write code here
        A=[0,1,2,4]
        if(number<=3):
            return A[number]
        else:
            for i in range(4,number+1):
                A.append(sum(A)+1)
            return A[number]