当前位置：网站首页>Review of double pointer problems
Review of double pointer problems
2022-07-06 05:01:00 【Xiaozhi re0】
List of articles
- 1. Power button [344] Reverse string
- 2. Power button 345: Reverse vowels in a string
- 3. Power button 125: Verify the palindrome string
- 4. Power button : Sum of two numbers II - Input an ordered array
- 5. Power button [11] The container with the most water
- 6. Power button [15] : Sum of three numbers
- 7. Power button [16] : The sum of three close numbers
- 8. Power button [18] Sum of four numbers
- 9. Power button [881] lifeboat
- 10. Power button [633] Sum of squares
Commonly used double pointer ;
- Collide with the pointer : The beginning and end of a piece of data , The two pointers start separately ;
- Speed pointer : The two pointers start from the left end at the same time ; A pointer moves fast , A pointer moves slowly ;
Practice using
1. Power button [344] Reverse string
Write a function , Its function is to invert the input string .
Input string as character array s Given in the form of .
Do not allocate extra space to another array ,
You have to modify the input array in place 、 Use O(1) To solve this problem .
Example 1：
Input ：s = ["h","e","l","l","o"]
Output ：["o","l","l","e","h"]
Example 2：
Input ：s = ["H","a","n","n","a","h"]
Output ：["h","a","n","n","a","H"]
Tips ：
1 <= s.length <= 105
s[i] All are ASCII Printable characters in code table
source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/reverse-string
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
class Solution {
public void reverseString(char[] s) {
// Simple collision pointer ;
int left =0;
int right =s.length-1;
while(left<right){
// Exchange the characters corresponding to the two pointers ;
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left ++;
right --;
}
}
}
2. Power button 345: Reverse vowels in a string
Original position : Reverse vowels in a string
Give you a string s , Invert only all vowels in the string , And return the result string .
Vowels include 'a'、'e'、'i'、'o'、'u', And may appear in both case .
Example 1：
Input ：s = "hello"
Output ："holle"
Example 2：
Input ：s = "leetcode"
Output ："leotcede"
Tips ：
1 <= s.length <= 3 * 105
s from Printable ASCII Character composition
source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/reverse-vowels-of-a-string
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
class Solution {
public String reverseVowels(String s) {
char[] c = s.toCharArray();
// Simple collision double pointer ;
int left = 0;
int right = c.length-1;
// Only for vowels :'a' 'e' 'i' 'o' 'u' reverse ;
while(true){
// You need to verify whether the current character is a vowel ;
while(left < c.length && !isYuanYin(c[left])){
left++;
}
while(right>=0 && !isYuanYin(c[right])){
right--;
}
if(left <right){
// Exchange method ;
swap(c,left,right);
left++;
right--;
}else{
// If not , End the current cycle ;
break;
}
}
// end ;
return new String(c);
}
// Determine if it's a vowel ;
private boolean isYuanYin(char s){
if(s=='a'||s=='e'||s=='i'||s=='o'||s=='u'||
s=='A'||s=='E'||s=='I'||s=='O'||s=='U'){
return true;
}
return false;
}
// Exchange two elements ;
private void swap(char[] c,int a,int b){
char temp = c[a];
c[a] = c[b];
c[b] = temp;
}
}
3. Power button 125: Verify the palindrome string
Original position : Verify the palindrome string
Given a string , Verify that it is a palindrome string , Consider only alphabetic and numeric characters , The case of letters can be ignored .
explain ： In this question , We define an empty string as a valid palindrome string .
Example 1:
Input : "A man, a plan, a canal: Panama"
Output : true
explain ："amanaplanacanalpanama" It's a palindrome string
Example 2:
Input : "race a car"
Output : false
explain ："raceacar" It's not a palindrome string
Tips ：
1 <= s.length <= 2 * 105
character string s from ASCII Character composition
source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/valid-palindrome
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Use colliding double pointers to solve ;
class Solution {
public boolean isPalindrome(String s) {
int n = s.length();
// Special use cases exclude ;
if(s==null || n == 0){
return true;
}
// Capitalize to lowercase , Other characters are ignored ;
s = s.toLowerCase();
// Collide with the pointer ;
int left = 0;
int right = n-1;
while(left<right){
// Use isLetterOrDigit Method to remove non alphanumeric ;
while(left<right && !Character.isLetterOrDigit(s.charAt(left))){
left++;
}
while(left<right && !Character.isLetterOrDigit(s.charAt(right))){
right--;
}
// If it does not match, exit directly ;
if(s.charAt(left)!=s.charAt(right)){
return false;
}
// The pointer moves smoothly ;
left++;
right--;
}
return true;
}
}
4. Power button : Sum of two numbers II - Input an ordered array
Original position : Sum of two numbers II - Input an ordered array
I'll give you a subscript from 1 The starting array of integers numbers , The array has been pressed Non decreasing order ,
Please find out from the array that the sum satisfying the addition is equal to the target number target Two numbers of .
Let these two numbers be numbers[index1] and numbers[index2] ,
be 1 <= index1 < index2 <= numbers.length .
In length 2 Array of integers for [index1, index2] Returns the subscript of these two integers in the form of index1 and index2.
You can assume that each input Only corresponding to the only answer , And you Can not be Reuse the same elements .
The solution you design must use only constant level extra space .
Example 1：
Input ：numbers = [2,7,11,15], target = 9
Output ：[1,2]
explain ：2 And 7 The sum is equal to the number of targets 9 . therefore index1 = 1, index2 = 2 . return [1, 2] .
Example 2：
Input ：numbers = [2,3,4], target = 6
Output ：[1,3]
explain ：2 And 4 The sum is equal to the number of targets 6 . therefore index1 = 1, index2 = 3 . return [1, 3] .
Example 3：
Input ：numbers = [-1,0], target = -1
Output ：[1,2]
explain ：-1 And 0 The sum is equal to the number of targets -1 . therefore index1 = 1, index2 = 2 . return [1, 2] .
Tips ：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers Press Non decreasing order array
-1000 <= target <= 1000
There is only one valid answer
source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Collision pointer can also be used to solve ;
class Solution {
public int[] twoSum(int[] numbers, int target) {
// Use simple collision pointer ;
int left = 0;
int right = numbers.length-1;
while(left<right){
int sum = numbers[left] + numbers[right];
// If equal , Direct output ;
if(sum == target){
return new int[]{
left+1,right+1};
}else if(sum<target){
// If the current sum is smaller ; Move the left pointer to the right ;
left++;
}else{
right--;
}
}
// If you don't find it, go back -1,-1;
return new int[]{
-1,-1};
}
}
5. Power button [11] The container with the most water
Original position :
Here you are. n Nonnegative integers a1,a2,...,an, Each number represents a point in the coordinate (i, ai) .
Draw in coordinates n Bar vertical line , Vertical line i The two endpoints of are (i, ai) and (i, 0) .
Find two of them , Make them x A container of shafts can hold the most water .
explain ： You can't tilt the container .
Example 1：
Input ：[1,8,6,2,5,4,8,3,7]
Output ：49
explain ： The vertical line represents the input array [1,8,6,2,5,4,8,3,7].
In this case , The container can hold water （ In blue ） The maximum value of is 49.
Example 2：
Input ：height = [1,1]
Output ：1
Example 3：
Input ：height = [4,3,2,1,4]
Output ：16
Example 4：
Input ：height = [1,2,1]
Output ：2
Tips ：
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
It is also a collision pointer solution ;
class Solution {
public int maxArea(int[] height) {
int n = height.length;
// Use double pointer ;
int left = 0;
int right = n-1;
// result ;
int res =0;
while(left<right){
// Barrel short board effect ; Calculate according to the shortest plate in the current interval ;
int curWater = (right - left) * Math.min(height[left],height[right]);
// Note that the previous water tank should also be considered at this time ;
res = Math.max(res,curWater);
if(height[left]<height[right]){
left ++;
}else{
right --;
}
}
return res;
}
}
6. Power button [15] : Sum of three numbers
Original position : Sum of three numbers
Give you one containing n Array of integers nums, Judge nums Are there three elements in a,b,c ,
bring a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .
Be careful ： Answer cannot contain duplicate triples .
Example 1：
Input ：nums = [-1,0,1,2,-1,-4]
Output ：[[-1,-1,2],[-1,0,1]]
Example 2：
Input ：nums = []
Output ：[]
Example 3：
Input ：nums = [0]
Output ：[]
Tips ：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/3sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
int n = nums.length;
// Exclude special exceptions ;
if(n<3){
return list;
}
// Sort the array first ;
Arrays.sort(nums);
for(int i =0;i<n;i++){
// If the current number is greater than 0, You just quit ;
if(nums[i]>0){
break;
}
// For repeated data , Skip the loop ;
if(i>0 && nums[i] == nums[i-1]){
continue;
}
// Use double pointer ;
int left = i+1;
int right = n-1;
// Double pointer inner loop ;
while(left<right){
// Calculate the temporary sum ;
int sum = nums[i]+nums[left]+nums[right];
if(sum == 0){
// Record in the set at this time ;
list.add(Arrays.asList(nums[i],nums[left],nums[right]));
// At the same time, prune the left pointer and the right pointer ;
while(left<right && nums[left]==nums[left+1]){
left++;
}
while(left<right && nums[right]==nums[right-1]){
right--;
}
// Note the need to move the pointer ;
left++;
right--;
}
// The other two cases ;
else if(sum<0){
// Because the array has been sorted ; Ruohe small , Move to the right ;
left++;
}else{
right--;
}
}
}
return list;
}
}
7. Power button [16] : The sum of three close numbers
Original position : The closest sum of three
Give you a length of n Array of integers for nums and A target value target.
Please start from nums Choose three integers , Make their sum with target Nearest .
Returns the sum of the three numbers .
It is assumed that there is only exactly one solution for each set of inputs .
Example 1：
Input ：nums = [-1,2,1,-4], target = 1
Output ：2
explain ： And target The closest and 2 (-1 + 2 + 1 = 2) .
Example 2：
Input ：nums = [0,0,0], target = 1
Output ：0
Tips ：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/3sum-closest
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
class Solution {
public int threeSumClosest(int[] nums, int target) {
// In the previous classic sum of three problem , It is necessary to calculate the sum of the three numbers as 0 All combinations of ;
// Here is the sum of three numbers target The target ;
int n = nums.length;
// Array sorting ;
Arrays.sort(nums);
// The sum of the first three numbers of the array ;
int initSum = nums[0]+nums[1]+nums[2];
for(int i=0;i<n;i++){
// Double pointers are also required ;
int left = i+1;
int right = n-1;
while(left<right){
int sum = nums[i]+nums[left]+nums[right];
// A tree that matches the current value with the target value Compare Compare the initial value with the similar number with the target value ;
if(Math.abs(target-sum)-Math.abs(target - initSum)<0){
// Then assign it to the current number ;
initSum = sum;
}
else if(sum > target){
// The current sum is greater than the target value ;
right --;
}
else if(sum < target){
// The current sum is less than the target value ;
left ++;
}else{
// otherwise , Directly return the target value ;
return sum;
}
}
}
// Return the initial operation value ;
return initSum;
}
}
8. Power button [18] Sum of four numbers
Here you are n An array of integers nums , And a target value target .
Please find and return the quads that meet all the following conditions and are not repeated
[nums[a], nums[b], nums[c], nums[d]]
( If two Quad elements correspond to each other , It is considered that two quads repeat ）：
0 <= a, b, c, d < n
a、b、c and d Different from each other
nums[a] + nums[b] + nums[c] + nums[d] == target
You can press In any order Return to the answer .
Example 1：
Input ：nums = [1,0,-1,0,-2,2], target = 0
Output ：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2：
Input ：nums = [2,2,2,2,2], target = 8
Output ：[[2,2,2,2]]
Tips ：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
Actually, it is outside the sum of three numbers Add a cycle , Find another number that matches ;
import java.util.*;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
int n = nums.length;
if(n<4){
return list;
}
// Array sorting ;
Arrays.sort(nums);
// You can also use double pointers ;
// First, the first number ;
for(int i=0;i<n-3;i++){
// In fact, you can rule out whether you can continue to search here ;
if( (long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target ){
break;
}
// Remove the number of duplicates , Avoid cycling again ;
if(i>0 && nums[i] == nums[i-1]){
continue;
}
// Find the following numbers ; This is actually a similar practice of the sum of three ;
for(int j = i+1;j< n -2;j++){
// similarly , Let's go first ;
if(j>i+1 && nums[j]==nums[j-1]){
continue;
}
// Double pointer ;
int left = j+1;
int right = n-1;
while(left<right){
int sum = nums[i]+nums[j]+nums[left]+nums[right];
if(sum == target){
list.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
// You can remove the weight for the left and right pointers ;
while(left < right && nums[left]==nums[left+1]){
left++;
}
while(left < right && nums[right]==nums[right-1]){
right--;
}
left ++;
right--;
}
// The other two cases ;
else if(sum < target){
left++;
}else{
right--;
}
}
}
}
return list;
}
}
9. Power button [881] lifeboat
Given array people .people[i] It means the first one i Personal weight ,
There is no limit to the number of ships , The maximum weight that each ship can carry is limit.
Each ship can carry up to two people at the same time , But the condition is that the sum of these people's weights is at most limit.
return The minimum number of ships required to carry the owner .
Example 1：
Input ：people = [1,2], limit = 3
Output ：1
explain ：1 Ship load (1, 2)
Example 2：
Input ：people = [3,2,2,1], limit = 3
Output ：3
explain ：3 Ships carry (1, 2), (2) and (3)
Example 3：
Input ：people = [3,5,3,4], limit = 5
Output ：4
explain ：4 Ships carry (3), (3), (4), (5)
Tips ：
1 <= people.length <= 5 * 104
1 <= people[i] <= limit <= 3 * 104
Pay attention to the meaning of the question , Two people in a boat ;
As long as the current weight limit is not exceeded , Can be shipped ;
class Solution {
public int numRescueBoats(int[] people, int limit) {
int n = people.length;
int left = 0;
int right = n-1;
int good = 0;
Arrays.sort(people);
while(left<=right){
int sum = people[left]+people[right];
// If the limit is met ; Then transport ;
if(sum <= limit){
// Add people ;
left++;
}
// The number of people is decreasing ;
right--;
good++;
}
return good;
}
}
10. Power button [633] Sum of squares
Given a nonnegative integer c , You have to decide if there are two integers a and b, bring a2 + b2 = c .
Example 1：
Input ：c = 5
Output ：true
explain ：1 * 1 + 2 * 2 = 5
Example 2：
Input ：c = 3
Output ：false
Tips ：
0 <= c <= 231 - 1
Note the type of data ;
class Solution {
public boolean judgeSquareSum(int c) {
if (c == 0) {
return true;
}
// Double pointer ; The right boundary is a number c prescribing ;
long left = 0;
long right =(long)Math.sqrt(c);
while(left <= right){
long temp = left*left + right*right;
if(temp == c){
return true;
}else if(temp > c){
right--;
}else{
left++;
}
}
return false;
}
}
边栏推荐
- Postman test report
- 關於Unity Inspector上的一些常用技巧，一般用於編輯器擴展或者其他
- Summary of redis AOF and RDB knowledge points
- RTP gb28181 document testing tool
- Luogu deep foundation part 1 Introduction to language Chapter 2 sequential structure programming
- JS quick start (II)
- win10电脑系统里的视频不显示缩略图
- ISP学习（2）
- Upload nestjs configuration files, configure the use of middleware and pipelines
- What are the advantages of the industry private network over the public network? What specific requirements can be met?
猜你喜欢
Codeforces Round ＃804 (Div. 2)
Summary of redis basic knowledge points
![[FreeRTOS interrupt experiment]](/img/8f/54422d346bb54d23fab824be2f17a3.jpg)
[FreeRTOS interrupt experiment]
GAMES202-WebGL中shader的编译和连接（了解向）
ORM aggregate query and native database operation
Delete subsequence ＜ daily question ＞
SQL injection vulnerability (MSSQL injection)
GAMES202-WebGL中shader的編譯和連接（了解向）
RT thread analysis - object container implementation and function
Weng Kai C language third week 3.1 punch in
随机推荐
驱动开发——HelloWDM驱动
It is also a small summary in learning
饼干（考试版）
ISP学习（2）
Set detailed map + interview questions
驱动开发——第一个HelloDDK
Request (request object) and response (response object)
Collection + interview questions
SQL注入漏洞（MSSQL注入）
Sorting out the knowledge points of multicast and broadcasting
内核判断i2c地址上是否挂载外设
Acwing week 58
Realize a binary read-write address book
你需要知道的 TCP 三次握手
RT thread analysis - object container implementation and function
优秀PM必须经历这3层蜕变！
2021robocom robot developer competition (Preliminary)
比尔·盖茨晒18岁个人简历，48年前期望年薪1.2万美元
程序员在互联网行业的地位 | 每日趣闻
yolov5 tensorrt加速