剑指offer读书笔记：第二章，面试基本知识03

待我称王封你为后i 2022-05-30 09:05 154阅读 0赞

# 问题01 排序算法 && 旋转数组 #

![这里写图片描述][70]  
上面的做法是基于统计来实现排序。

![这里写图片描述][70 1]

很明显最直接的方法就是暴力遍历，复杂度是O(n)，但是这显然不是面试官想要的做法，这明显是考察二分查找。可以**看出每次根据low和high求出mid后，mid左边（\[low, mid\]）和右边（\[mid, high\]）至少一个是有序的。这个才是解决本问题的关键的地方**，那么可以得到如下的流程：

仔细分析该问题，可以发现，每次根据low和high求出mid后，mid左边（[low, mid]）和右边（[mid, high]）至少一个是有序的。
    a[mid]分别与a[left]和a[right]比较，确定哪一段是有序的。
    如果左边是有序的，若x<a[mid]且x>a[left], 则right=mid-1；
    其他情况，left =mid+1；
    
    如果右边是有序的，若x> a[mid] 且x<a[right] 则left=mid+1；
    其他情况，right =mid-1
    代码如下：
    
    int binary_search_rotate_arry(int *a, int n, int x)
    {
        int low = 0, high = n - 1, mid;
        while(low <= high)
        {
            mid = low + ((high - low) >> 1);
            if(a[mid] == x)
                return mid;
            if(a[mid] >= a[low])
            {//左边有序
                if(x < a[mid] && x >= a[low])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            else //右边有序
            {
                if(x > a[mid] && x <= a[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            //cout << low << " " << mid << " " << high << endl;
        }
        return -1;
    }

# 问题02 斐波那契序列 #

![这里写图片描述][70 2]  
![这里写图片描述][70 3]

直接递归即可

# 问题03 位运算 #

![这里写图片描述][70 4]

就这么做吧，这道题已经烂遍街了

int count_one(int num)
    {
        int count = 0;
        while (num)
        {
            if (num % 2 == 1)
            {
                count++;
            }
            num = num / 2;
        }
        return count;
    }

其他的变形问题也要类似考虑：  
![这里写图片描述][70 5]

[70]: /images/20220530/254af4002fd740269b80d199ecf4e8c5.png
[70 1]: /images/20220530/df5ff0ece74d4a47868a173bb5803bca.png
[70 2]: /images/20220530/c6388d246a6e40a69244ab183d747b8c.png
[70 3]: /images/20220530/7e0ca8166be74daf8013bd76a9ed9b5e.png
[70 4]: /images/20220530/b23779081f1c4cfb8fff85f1a29af4bf.png
[70 5]: /images/20220530/04b252bb97714ffdae7315ba6ec9fe18.png