牛客剑指offer刷题记录（二）

以你之姓@ 2022-06-12 20:25 169阅读 0赞

--------------------

## **旋转数组的最小数字** ##

旋转数组是指有序数组进行右移之后的得到数组。

要求数组中的最小数字，O(n)复杂度就可以搞定，如果要高效一点，需要用到二分查找的思路。

事实上，除了处理简单`45123`这样的序列，还得考虑有重复数字出现的旋转数组，例如`11000`

class Solution {
    public:
        int minNumberInRotateArray(vector<int> rotateArray) {
            int l=0;
            int r=rotateArray.size()-1;
            int m=0;
            while(l<r)
            {
                m=l+(r-l)/2;
                if(rotateArray[m]<rotateArray[r])
                {
                    r=m;
                }
                else if(rotateArray[m]>rotateArray[r])
                {
                    l=m+1;
                }
                else//相等只有减小Upper Bound
                {
                    --r;
                }
            }
            return rotateArray[l];
    
        }
    };

--------------------

## **斐波拉切数列** ##

f(n)=f(n−1)\+f(n−2)  
这是斐波拉切数列的方程，可以直接递归去做，也可以迭代计算，我这里用迭代的方式做：

class Solution {
        public:
        int Fibonacci(int n) 
        {
            if(0==n)
                return 0;
            if(1==n)
                return 1;
    
            int a1=1;
            int a0=0;
            int res;
            for(int i=2;i<=n;++i)
            {
                res=a0+a1;
                a0=a1;
                a1=res;
            }
            return res;
    
        }
    };

--------------------

## **跳台阶** ##

理解一下题意的话，就是斐波拉切数列的变种。

class Solution {
    public:
        int jumpFloor(int number) {
            if(1==number)
                return 1;
            if(2==number)
                return 2;
            int n1=1;
            int n2=2;
            for(int i=0;i<number-2;++i){
                int tmp=n2;
                n2+=n1;
                n1=tmp;
            }
            return n2;
        }
    };

--------------------

## **变态跳台阶** ##

f(n)=f(n−1)\+...f(1)\+f(0)  
f(n−1)=f(n−2)\+...f(1)\+f(0)  
推出：  
f(n)=2∗f(n−1)  
推出：  
f(n)=2(n−1)

class Solution {
    
    public:
        int jumpFloorII(int number) {
            if(number<=0)
                return 0;
            return pow(2,number-1);
        }
    };

--------------------

## **矩形覆盖** ##

同样是斐波拉契数列

class Solution {
    public:
        int rectCover(int number) {
            //number==1 1
            //number==2 2
            if(number<=0)
                return 0;
            if(number==1)
                return 1;
            if(number==2)
                return 2;
            int n1=1;
            int n2=2;
            for(int i=0;i<number-2;++i){
                int tmp=n2;
                n2+=n1;
                n1=tmp;
            }
            return n2;
    
        }
    };

--------------------

## **二进制有多少个1** ##

通过`n&n-1`这个操作可以把原来n所表示的二进制中最右边的1变成0，那么有多少次这样的操作，就表示有多少个1.

class Solution {
    public:
         int  NumberOf1(int n) {
             int count=0;
             while(n)
             {
                 ++count;
                 n=n&(n-1);
             }
             return count;
    
         }
    };

--------------------

## **数值的整数次方** ##

这题就是自己实现一个pow函数，并不难，在于优化。

比如2的4次方，可以两组两组相乘，2的5次方可以两组两组相乘之后再乘以基数。这就是考虑奇数与偶数次幂的情况了。

class Solution {
        double help(double base, int exponent)
        {
            if (exponent == 0)
                return 1;
            if (exponent == 1)
                return base;
            double tmp = help(base, exponent / 2);
            tmp*=tmp;
            if ((exponent & 1) == 1)
                tmp *= base;
            return tmp;
        }
    public:
        double Power(double base, int exponent) {
            int flag = false;
            if (exponent < 0)
            {
                exponent = -exponent;
                flag = true;
            }
            double res = help(base, exponent);
            if (flag)
                res = 1 / res;
            return res;
    
        }
    };

--------------------

## **奇数位于偶数之前** ##

剑指offer上的解法不能保证原有次序，思路是：  
1.从前往后找到第一个偶数  
2.从后往前找到第一个奇数

交换之。

class Solution {
    public:
        void reOrderArray(vector<int> &array) {
            int odd = 0;
            int even = array.size() - 1;
            while (odd < even)
            {
                while (odd < even && (array[odd] & 1) == 1)
                    ++odd;
                while (odd < even && (array[even] & 1) == 0)
                    --even;
                if (odd < even)
                {
                    swap(array[odd], array[even]);
                }
            }
        }
    };

而牛客上面要求新的序列不改变原来的次序，这样的话，可以重新开辟一个新的数组来保存。

class Solution {
    public:
        void reOrderArray(vector<int> &array) {
            vector<int>tmp;
            tmp.reserve(array.size());
            for(int i=0;i<array.size();++i){
                if((array[i]&0x1)==1)
                    tmp.push_back(array[i]);
            }
            for(int i=0;i<array.size();++i){
                if((array[i]&0x1)==0)
                    tmp.push_back(array[i]);
            }
            array.swap(tmp);
        }
    };

--------------------

## **链表中的倒数第K个节点** ##

一个简单的办法就是，倒数第K个节点实际上就是顺数第n-K+1个节点，于是需要遍历两次。

有一个思路是，需要两个指针，第一个指针先走k-1步到第k个节点，第二个指针不动，然后两个指针再一起往后直到链表结尾，那么第二个指针便是倒数第k个节点了。

因为第k个节点是倒数n-k+1个节点，走到头，需要走n-k步，第一个个指针同时走n-k步就到了n-k+1个节点了。

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
                val(x), next(NULL) {
        }
    };*/
    class Solution {
    public:
        ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
            ListNode*p=pListHead;
            int i=k;
            while(i--){
                if(NULL==p)
                    return NULL;
                p=p->next;
            }
            ListNode*r=pListHead;
            while(p!=NULL){
                p=p->next;
                r=r->next;
            }
            return r;
        }
    };