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;
}
};