The advanced version of the cattle brushing series (search for rotating sorted arrays, inversion of the specified range in the linked list)

很多小伙伴为了刷题发愁
今天为大家推荐一款刷题神奇哦：刷题面试神器牛客
各大互联网大厂面试真题.从基础到入阶乃至原理刨析类面试题 应有尽有,赶快来装备自己吧！助你面试稳操胜券,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)//当twhen the array on the right
            {
    
                if(nums[mid]>=nums[0]) //当mid左边时,需要将left=mid+1
                nums[mid] = -10001;
            }
            else//当twhen the array on the left
            {
    
                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.思路和注意事项

• The idea is to simulate binary search to achieve

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. When we find that in special casesright 要变成mid-1时,我们就可以用 nums[mid] = 10001;来模拟 这种情况.
4. See the code comments for details（主要是看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.思路和注意事项

The main idea is to reverse again and again

• It should be noted that a virtual head node should be set,In case the head node changes

ps

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