给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
/**
* 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* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}
ListNode* merge(vector <ListNode*> &lists, int l, int r) {
if (l == r) return lists[l];
if (l > r) return nullptr;
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
};
给定一个排序数组，你需要在 原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地 修改输入数组并在使用 O(1) 额外空间的条件下完成。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty())return 0;
int pre=0;
for(int cur=1;cur<nums.size();cur++)
{
if(nums[cur]!=nums[pre])
{
pre++;
if(cur-pre>=1)
{
nums[pre]=nums[cur];
}
}
}
return pre+1;
}
};
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty())return 0;
int pre=0;
for(int cur=1;cur<nums.size();cur++)
{
if(nums[cur]!=nums[pre])
{
pre++;
if(cur-pre>=1)
{
nums[pre]=nums[cur];
}
}
}
return pre+1;
}
};
升序排列的整数数组nums在预先未知的某个点上进行了旋转（例如，[0,1,2,4,5,6,7]经旋转后可能变为[4,5,6,7,0,1,2]）。
请你在数组中搜索target，如果数组中存在这个目标值，则返回它的索引，否则返回-1。
class Solution {
public:
int search(vector<int>& nums, int target) {
//考虑折半查找找到最小元素位置，再找target是否存在
int n=nums.size();
if (!n) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
};
