LeetCode 之双指针 two pointers

2023-11-01 15:48

本文主要是介绍LeetCode 之双指针 two pointers,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 3Sum

Given an array S of n integers, are there elements abc in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},A solution set is:(-1, 0, 1)(-1, -1, 2)
two pointer scan

遍历数组,双指针维护一个区间进行加和比较。

vector<vector<int> > threeSum(vector<int> &num) {vector<vector<int>> result;sort(num.begin(),num.end());for(int i=0; i<num.size(); i++){int target = 0-num[i];int start = i+1;int end = num.size()-1;while(start<end){if(num[start]+ num[end] == target){vector<int> solution;solution.push_back(num[i]);solution.push_back(num[start]);solution.push_back(num[end]);result.push_back(solution);start++, end--;while(start<end && num[start] == num[start-1]) start++;while(start<end && num[end] == num[end+1]) end--;}else if(num[start] + num[end] >target)end--;elsestart++;}while(i<num.size() && num[i] == num[i+1]) i++;}return result;
}
其中18,19行 去除前后的重复 比如[-2,-2,-2,0,2,3,4,4,4]

26行去除遍历时的重复 比如[2,2,3,3,5]

2. 3Sum Closet

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

与3Sum 类似,需要加一个记录最小距离的变量

int threeSumClosest(vector<int> &num, int target) {int result;vector<int> solution;sort(num.begin(), num.end());int minD = INT_MAX;for(int i=0; i<num.size()-2;i++){int start = i+1;int end = num.size()-1;while(start < end){int sum = num[i]+num[start]+num[end];if(sum == target){minD = 0;result = sum;return result;}else if(sum<target){if(target-sum < minD){minD = target-sum;result = sum;}start++;}else{if(sum-target < minD){minD = sum-target;result = sum;}end--;}}while(i<num.size() && num[i] == num[i+1]) i++;}return result;
}

3. 4Sum

Given an array S of n integers, are there elements abc, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.A solution set is:(-1,  0, 0, 1)(-2, -1, 1, 2)(-2,  0, 0, 2)

上述问题其实可以归纳为K sum问题,解题思路都比较相似。

都是要求, N个数字中,找出k个数字之和 == target (去重复)

解法:

排序,头尾两指针扫描找到相应的求和

3sum 可以化成 2sum, 4sum 可以化成3sum

比如:

排好序后数字为a b c d e f g h

先枚举a, 然后再b--h中查询

再枚举b 在c-h中查询

以此类推

这里有一篇博文总结的很好,来自烟客旅人

http://tech-wonderland.net/blog/summary-of-ksum-problems.html


vector<vector<int> > fourSum(vector<int> &num, int target) {vector<vector<int>> result;sort(num.begin(), num.end());for(int i=0; i<num.size();i++){int target1 = target- num[i];for(int j=i+1; j<num.size();j++){int target2 = target1-num[j];int start = j+1;int end = num.size()-1;while(start<end){if(num[start]+num[end]==target2){vector<int> solution;solution.push_back(num[i]);solution.push_back(num[j]);solution.push_back(num[start]);solution.push_back(num[end]);result.push_back(solution);start++, end--;while(start<end && num[start] == num[start-1]) start++;while(start<end && num[end] == num[end+1]) end--;}else if(num[start] + num[end] >target2)end--;elsestart++;}while(j<num.size() && num[j] == num[j+1]) j++;}while(i<num.size() && num[i] == num[i+1]) i++;}return result;
}

4.Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

实现题, 双指针操作,

string addBinary(string a, string b) {string result;reverse(a.begin(),a.end());reverse(b.begin(),b.end());int maxL = a.size()>b.size() ? a.size() : b.size();int carry = 0;for(int i=0; i<maxL; i++){int la = i<a.size()? a[i]-'0':0;int lb = i<b.size()? b[i]-'0':0;int sum = (la+lb+carry)%2;carry = (la+lb+carry)/2;result.insert(result.begin(),sum+'0');}if(carry == 1)result.insert(result.begin(),'1');return result;
}

5. Add two numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8


和 add binary 类似,指针操作不同

v1

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {int carry = 0;ListNode *result = new ListNode(-1);ListNode *head = result;ListNode *p1 = l1;ListNode *p2 = l2;while(p1!=NULL && p2!=NULL){int sum = (p1->val+p2->val+carry)%10;carry = (p1->val+p2->val+carry)/10;ListNode *didgt = new ListNode(sum);head->next = didgt;head = head->next;p1 = p1->next, p2 = p2->next;}while(p1!=NULL){int sum = (p1->val+carry)%10;carry = (p1->val+carry)/10;ListNode *didgt = new ListNode(sum);head->next = didgt;head = head->next;p1 = p1->next;}while(p2!=NULL){int sum = (p2->val+carry)%10;carry = (p2->val+carry)/10;ListNode *didgt = new ListNode(sum);head->next = didgt;head = head->next;p2 = p2->next;}if(carry!=0){ListNode *didgt = new ListNode(carry);head->next = didgt;}return result->next;
}


v2

ListNode *addTwoNumbersS2(ListNode *l1, ListNode *l2) {int carry = 0;ListNode *result = new ListNode(-1);ListNode *head = result;ListNode *p1 = l1;ListNode *p2 = l2;while(p1!=NULL || p2!=NULL){int av = p1 !=NULL? p1->val :0;int bv = p2 !=NULL? p2->val :0;int sum = (av+bv+carry)%10;carry = (av+bv+carry)/10;ListNode *didgt = new ListNode(sum);head->next = didgt;head = head->next;p1 = p1 !=NULL? p1->next:NULL;p2 = p2 !=NULL? p2->next:NULL;}if(carry!=0){ListNode *didgt = new ListNode(carry);head->next = didgt;}head = result->next;delete result;return head;
}

6.Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

int removeElement(int A[], int n, int elem) {int cur =0;for(int i=0;i<n;i++){if(A[i]==elem)continue;A[cur] = A[i];cur++;}return cur;
}



未完待续

这篇关于LeetCode 之双指针 two pointers的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/324050

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员,我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书,我不敢乱推荐,尤其是国内作者写的书,往往七拼八凑,漏洞百出。 但是,李忠老师的《C语言非常道》值得一读。对了,李老师有个官网,网址是: 李忠老师官网 最棒的是,有配套的教学视频,可以试看。 试看点这里 接下来言归正传,讲解指针。以下内容很多都参考了李忠老师的《C语言非

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划