Leetcode题解（26）

80. Remove Duplicates from Sorted Array II

题目

分析：简单的操作，代码如下：

 class Solution {
 public:
     int removeDuplicates(vector<int>& nums) {
         int n = nums.size();
         if(==n)
             return ;         int i=;
         int temp;
         int res = n;
         vector<int> result;
         int count;
         for(i=;i<n;)
         {
             temp=nums[i];
             count=;
             i++;
             while(i<n&&nums[i] == temp)
             {
                 count++;
                 i++;
             }             if(count>)
             {
                 res = res-(count-);
                 result.push_back(temp);
                 result.push_back(temp);             }
             else
                 while(count--)
                 {
                     result.push_back(temp);
                 }         }
         nums = result;
         return res;     }
 };

———————————————————————————分割线—————————————————————–

81. Search in Rotated Sorted Array II

题目

分析：题目和33题很相识，代码如下：

 class Solution {
 public:
     bool search(vector<int>& nums, int target) {
         int n=nums.size();
         vector<int> A=nums;
          if( == n) return false;
         int left = ;
         int right = n - ;
         while(left <= right)
         {
             int midle = (left + right) >> ;
             if(A[midle] == target) return true;
             if(A[left] == A[midle] && A[midle] == A[right])
             {
                ++left;
                --right;
             }
             else if(A[left] <= A[midle])
             {
                 if(A[left] <= target && target  < A[midle])
                 {
                     right = midle - ;
                 }
                 else
                 left = midle + ;
             }
             else {
                 if(A[midle] < target && target <= A[right])
                     left = midle + ;
                 else
                     right = midle - ;
             }
         }
         return false;
     }
 };

——————————————————————————–分割线—————————————————————–

82. Remove Duplicates from Sorted List II

题目

分析：这道题主要是考察指针操作，为了方便，在处理之前，对链表添加一个头节点，以便处理起来更加方便，代码如下

 /**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
 class Solution {
 public:
     ListNode* deleteDuplicates(ListNode* head) {
         if(NULL == head)
             return NULL;         ListNode *pre,*current;
         ListNode *pHead = new ListNode();
         pHead->next = head;//添加头节点
         pre = pHead;
         current = head;
         int key;
         bool flag = false;
         while(current!= NULL)
         {
             key = current->val;
             current = current->next;
             while( current != NULL && current->val == key)
             {
                 flag = true;
                 current = current->next;
             }
             if(flag)
             {
                 pre->next = current;
                 flag = false;
             }
             else
             pre = pre->next;
         }         return pHead->next;     }
 };

————————————————————————-分割线————————————————————————-

83. Remove Duplicates from Sorted List

分析：这一题和82题类似，代码如下：

 /**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
 class Solution
 {
 public:
     ListNode *deleteDuplicates(ListNode *head)
     {
         if(head==NULL || head->next==NULL) return head;
         ListNode *helper = new ListNode(-);
         ListNode *ret=head;
         while(ret)
         {
             ListNode *next=ret->next;
             if(ret->val!=helper->val)
             {
                 helper->next=ret;
                 helper=ret;//将helper指新链表的尾结点
                 helper->next=NULL;//尾指向空，因为后面的结点有可能被删去了，它不知道下一个指向谁
             }
             else delete ret;
             ret=next;
         }
         return head;
     }
 };