目录

二分查找变种

 二进制转整数

链表内指定区间反转

链表前缀和暴力解法

二分查找变种

搜索旋转排序数组

思路：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right)
        {
            int mid=left+right>>1;
            if(nums[mid]==target) return mid;
            else if(nums[mid]<nums[right])    //右半段有序
            {
                //如果target在有序区间范围内，则搜索有序半边，否则搜索无序
                if(nums[mid]<target&&target<=nums[right]) left=mid+1;
                else right=mid-1;
            }
            else    //左半段有序
            {
                if(nums[left]<=target&& target<nums[mid]) right=mid-1;
                else left=mid+1;
            }
        }
        return -1;
    }
};

 二进制转整数

二进制链表转整数

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int ans=0;
        while(head!=NULL)
        {
            ans=ans*2+head->val;
            head=head->next;
        }
        return ans;
    }
};

链表内指定区间反转

链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)

思路：

此题主要考察单链表的反转操作，核心思路主要是借助临时头结点，找到需要翻转链表的前驱位置，然后将要翻转链表的节点摘下进行子链表的头部插入即可

即令m为头结点，将后面n-m个节点进行头插

 

举个栗子：

1. 因为要把节点3插到1、2之间，所以令temp=节点3；
2. 将结点2的指针连到4；
3. 将结点3的指针连到2；
4. 将结点1的指针连到3；

实现对m位置节点的头插，循环n-m次完成区间反转

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
         //加个表头
        ListNode* res = new ListNode(-1);
        res->next = head;
        //前序节点
        ListNode* pre = res; 
        //当前节点
        ListNode* cur = head; 
        //找到m
        for(int i = 1; i < m; i++){ 
            pre = cur;
            cur = cur->next;
        }
        //从m反转到n，头插n-m个
        for(int i = m; i < n; i++){ 
            ListNode* temp = cur->next;
            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        //返回去掉表头
        return res->next; 
    }
};

反转链表_牛客题霸_牛客网 (nowcoder.com)

普通单链表反转

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		ListNode* res=new ListNode(-1);
		res->next=pHead;
		ListNode* pre=res;

		while(pHead&&pHead->next!=nullptr)
		{
			ListNode* temp=pHead->next;
			pHead->next=temp->next;
			temp->next=pre->next;
			pre->next=temp;
		}
		return res->next;
	}
};

链表前缀和暴力解法

从链表中删去总和值为零的连续节点

思路：

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) 
    {
        //初始化一个空结点，初始赋值为0，并且list的下一个next指针指向head
        ListNode* dummyhead = new ListNode(0, head);
        ListNode* cur = dummyhead;
        int sum = 0;
        while (cur != nullptr)
        {
            ListNode* search = cur->next;
            sum = 0;
            while (search != nullptr)
            {
                sum += search->val;
                if (sum == 0) cur->next = search->next;
                search = search->next;
            }
            cur = cur->next;
        }
        ListNode* ret = dummyhead->next;
        delete dummyhead;
        return ret;
    }
};

最后

以上就是任性鼠标为你收集整理的leetcode之旅 - Day1二分查找变种 二进制转整数链表内指定区间反转链表前缀和暴力解法的全部内容，希望文章能够帮你解决leetcode之旅 - Day1二分查找变种 二进制转整数链表内指定区间反转链表前缀和暴力解法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。