首页 > 其他 > 详细

题解 双指针

时间:2020-05-10 00:08:15      阅读:59      评论:0      收藏:0      [点我收藏+]

1.Remove Nth Node From End of List

(https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)

刚看到题目的想法是使用两次遍历,第一次确定该链表的长度,再减去n,进行第二次遍历,从而删除对应位置的元素。

因此,可以使用双指针来实现,第一个指针先移动n+1位,第二个指针再从头移动,当第一个指针到达结尾时,第二个指针的下一个元素便是需要删除的元素

 1  ListNode* removeNthFromEnd(ListNode* head, int n) {
 2             
 3         if(n==0)return head;
 4          ListNode *p=head;
 5         ListNode *q=head;
 6         for(int i=0;i<n+1;i++){
 7         if(q)
 8             q=q->next;
 9             else return head->next;//如果q直到末位循环还未结束,说明n=链表长度(题目说明了n是有效的)。其需要删除第一个元素
10         }
11         while(q){
12             p=p->next;
13             q=q->next;
14         }
15         ListNode *s=p->next;
16         p->next=s->next;
17         delete s;
18         return head;    
19     }

写完以后发现执行时间12ms,o(╥﹏╥)o

就去看了看0ms的代码,和我的思路一样,不同的地方在于,其在开始建立一个空的头结点,放在head的前面

1  ListNode dummy = new ListNode(0);
2     dummy.next = head;

2.Remove Duplicates from Sorted Array

(https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/)

此题也是采用双指针的方式,刚开始陷入一个错误的思路:就是两个指针同时移动,一个前i一个后j,一旦发现前指针i和该指针前面i-1的一样,就把后指针j赋值给前指针i。(这种做法仅仅是将数据往前移动,并未消除重复项)(傻傻的做法)

而应当前指针i只有在后指针发现和i不同的元素以后再往后移动,并进行赋值操作。

 1     int removeDuplicates(vector<int>& nums) {
 2         int i=0;
 3         int j=1;
 4         if(nums.size()==0)return 0;//如果vector为空
 5        // if(nums.size()==1)return 1;
 6         while(j<nums.size()){
 7             if(nums[i]==nums[j]){//当两指针的值相等时,i不移动
 8                 j++;
 9             }
10             else{
11                 i++;//i往后移动一位
12                nums[i]=nums[j];//将第一个与i-1不同的数字赋值给i
13                 j++;
14             }
15         }
16         return i+1;
17         
18     }

 

3.Remove Element

(https://leetcode-cn.com/problems/remove-element/)

这题和前面那题十分相似,几乎可以是同一种方法

 1    int removeElement(vector<int>& nums, int val) {
 2           int i=0,j=0;
 3         int m=0;
 4         while(j<nums.size()&&i<nums.size()){
 5             if(nums[i]!=val){
 6                 i++;m++;//m用于记录元素个数
 7             }
 8             else{
 9                  j=i+1;
10                 while(j<nums.size()){
11                   if(nums[j]!=val) {nums[i]=nums[j];nums[j]=val;break;} 
12                     j++;
13                 }
14             }
15         }
16         return m;
17     }

在官方解法中只使用了一次遍历,并对其进行了优化!

 

题解 双指针

原文:https://www.cnblogs.com/liujiuba/p/12861146.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!