牛客刷题系列之进阶版（搜索旋转排序数组，链表内指定区间反转）

很多小伙伴为了刷题发愁
今天为大家推荐一款刷题神奇哦：刷题面试神器牛客
各大互联网大厂面试真题。从基础到入阶乃至原理刨析类面试题 应有尽有，赶快来装备自己吧！助你面试稳操胜券，solo全场面试官

一：搜索旋转排序数组

1.题目

题目链接

2.代码实现

class Solution {
    
public:
    int search(vector<int>& nums, int target) {
    
        int left=0;
        int right =nums.size()-1;
        int mid;
        while(left<=right)
        {
    
            mid = (left+right)/2;

            if(nums[0]>target)//当t在右边的数组时
            {
    
                if(nums[mid]>=nums[0]) //当mid左边时，需要将left=mid+1
                nums[mid] = -10001;
            }
            else//当t在左边的数组时
            {
    
                if(nums[mid] < nums[0]) //当mid右边时，需要将right = mid-1;
                 nums[mid] = 10001;
            }

            if(nums[mid] > target)
               right = mid-1;
            else if(nums[mid] <target)
              left = mid+1;
              else
              return mid;
        }
         return -1;
    }
};

3.思路和注意事项

• 思路是模拟二分查找来实现的

1. 普通的二分查找是
   if(nums[mid] > target)
   right = mid-1;
   else if(nums[mid] <target)
   left = mid+1;
   else
   return mid;
2. nums[mid] > target时， right = mid-1; 所以我们可以用 nums[mid] = 10001;来模拟 这种情况。
3. 当我们找到在特殊情况下的right 要变成mid-1时，我们就可以用 nums[mid] = 10001;来模拟 这种情况。
4. 具体的情况看代码注释（主要是看mid和t在哪一边）
   

二：链表内指定区间反转

1.题目

题目链接

2.代码实现

/** * struct ListNode { * int val; * struct ListNode *next; * }; */

class Solution {
    
public:
    /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
    
        // write code here
        ListNode* res =new ListNode(0);
        ListNode* cur = head;
        ListNode* pre = res;
        res->next= head;
        for(int i=1;i<m;i++)
        {
    
            pre =cur;
            cur =cur->next;
        }
        for(int i=m;i<n;i++)
        {
    
           ListNode* tem =cur->next;
            cur->next = tem->next;
            tem->next  =   pre->next;
            pre->next = tem;
        }
        return res->next;;
    }
};

3.思路和注意事项

主要思路就是一次一次的反转

• 需要注意的是要设虚拟头节点，以防头节点的改变的情况

ps

想和博主一样刷优质面试和算法题嘛，快来刷题面试神器牛客吧，期待与你在牛客相见