完整教程：LeetCode 刷题【81. 搜索旋转排序数组 II、82. 删除排序链表中的重复元素 II、83. 删除排序链表中的重复元素】

81. 搜索旋转排序数组 II

自己做

解：二分查找

class Solution {
public:
bool search(vector& nums, int target) {
int n = (int)nums.size();
int begin = 0;
int end = n - 1;
sort(nums.begin(), nums.end());
//调整边界
if(target >= nums[0]){              //target如果存在，则必然存在于左边,调整右边界（end）到左边
while(begin  nums[end] && nums[end] > target){
int mid = (begin + end) / 2;    //新边界
if(nums[begin] > nums[mid])         //新边界还在右边
end = mid - 1;
else                                //新边界在左边
if(nums[mid]  nums[end] && nums[begin] > target){
int mid = (begin + end) / 2;    //新边界
if(nums[begin] > nums[mid])         //新边界还在左边
begin = mid + 1;
else                                //新边界在左边
if(nums[mid] > target)          //跳过头了
end = mid - 1;
}
}
//二分查找
while(begin  target)          //往小处找
end = mid - 1;
if(nums[mid] < target)          //往大处找
begin = mid + 1;
}
//没找到
return false;
}
};

82. 删除排序链表中的重复元素 II

自己做

解：计数法

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
vector count(200, 0);                  //计数数组
ListNode* p = head;
//遍历计数
while(p != nullptr){
count[p->val + 100]++;
p = p->next;
}
//首先删除开头部分（涉及头结点更改）
while(head != nullptr && count[head->val + 100] > 1)
head = head->next;
if(head == nullptr)                          //删完了
return head;
//删除结点
p = head;
ListNode* q = p->next;
while(q != nullptr){
if(count[q->val + 100] > 1)
p->next = q->next;
else
p = p->next;
q = p->next;
}
return head;
}
};

83. 删除排序链表中的重复元素

自己做

解：前后指针

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
//删除开头重复部分
while(head != nullptr && head->next != nullptr && head->val == head->next->val)
head = head->next;
if(head == nullptr)         //删完了或者本身为空
return head;
//删除中间部分
ListNode* p = head;
while(p->next != nullptr){
if(p->val == p->next->val)              //有重复
p->next = p->next->next;
else                                    //无重复
p = p->next;
}
return head;
}
};