80. Remove Duplicates from Sorted Array II
题目
分析:简单的操作,代码如下:
1 class Solution { 2 public: 3 int removeDuplicates(vector & nums) { 4 int n = nums.size(); 5 if(0==n) 6 return 0; 7 8 int i=0; 9 int temp;10 int res = n;11 vector result;12 int count;13 for(i=0;i2)25 {26 res = res-(count-2);27 result.push_back(temp);28 result.push_back(temp);29 30 }31 else32 while(count--)33 {34 result.push_back(temp);35 }36 37 }38 nums = result;39 return res;40 41 }42 };
---------------------------------------------------------------------------------分割线-----------------------------------------------------------------
81. Search in Rotated Sorted Array II
题目
分析:题目和33题很相识,代码如下:
1 class Solution { 2 public: 3 bool search(vector & nums, int target) { 4 int n=nums.size(); 5 vector A=nums; 6 if(0 == n) return false; 7 int left = 0; 8 int right = n - 1; 9 while(left <= right)10 {11 int midle = (left + right) >> 1;12 if(A[midle] == target) return true;13 if(A[left] == A[midle] && A[midle] == A[right])14 {15 ++left;16 --right;17 }18 else if(A[left] <= A[midle])19 {20 if(A[left] <= target && target < A[midle])21 {22 right = midle - 1;23 }24 else25 left = midle + 1;26 }27 else {28 if(A[midle] < target && target <= A[right])29 left = midle + 1;30 else31 right = midle - 1;32 }33 }34 return false;35 }36 };
--------------------------------------------------------------------------------分割线-----------------------------------------------------------------
82. Remove Duplicates from Sorted List II
题目
分析:这道题主要是考察指针操作,为了方便,在处理之前,对链表添加一个头节点,以便处理起来更加方便,代码如下
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode* deleteDuplicates(ListNode* head) {12 if(NULL == head)13 return NULL;14 15 ListNode *pre,*current;16 ListNode *pHead = new ListNode(0);17 pHead->next = head;//添加头节点18 pre = pHead;19 current = head;20 int key;21 bool flag = false;22 while(current!= NULL)23 {24 key = current->val;25 current = current->next;26 while( current != NULL && current->val == key)27 {28 flag = true;29 current = current->next;30 }31 if(flag)32 {33 pre->next = current;34 flag = false;35 }36 else37 pre = pre->next;38 }39 40 return pHead->next;41 42 }43 };
-------------------------------------------------------------------------分割线-------------------------------------------------------------------------
83. Remove Duplicates from Sorted List
分析:这一题和82题类似,代码如下:
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution10 {11 public:12 ListNode *deleteDuplicates(ListNode *head)13 {14 if(head==NULL || head->next==NULL) return head;15 ListNode *helper = new ListNode(-100000);16 ListNode *ret=head;17 while(ret)18 {19 ListNode *next=ret->next;20 if(ret->val!=helper->val)21 {22 helper->next=ret;23 helper=ret;//将helper指新链表的尾结点24 helper->next=NULL;//尾指向空,因为后面的结点有可能被删去了,它不知道下一个指向谁25 }26 else delete ret;27 ret=next;28 }29 return head;30 }31 };