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

持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第12天，点击查看活动详情

一：搜索旋转排序数组

1.题目

题目链接

2.代码实现

代码语言：javascript复制

class Solution {
public:
    int search(vector<int>&amp; 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.代码实现

代码语言：javascript复制

/**
 * 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

ps return target

0 人点赞