Double hands of daily practice of Li Kou 2day9

Buckle the hands of one practice every day 2Day9

In front of the word

Hello everyone ！ This article will introduce 20 The problem of day algorithm problem brushing plan , This paper will take two questions as the background , Introduce the classic double pointer , The display language is java（ The blogger's learning language is java). What about today , It's the ninth day that bloggers start to brush force buckle , If you want to start preparing for your algorithm interview , You can follow my footsteps , Common progress . We are all partners fighting side by side , Work hard together , What a long long road! , I will go up and down , I believe we can all get what we expect offer, To rush ！

Blog home page ： The blog home page of Beijing and JIUPU

Welcome to pay attention to the likes and comments

This article is original by Beijing and JIUPU ,csdn First episode ！

Series column ：java Study

Starting time ：2022 year 5 month 12 Japan

You do march and April , There will be an answer in August and September , Come on

Refer to the online programming website ： Power button

If you think the blogger's article is good , Please support the blogger for the third company

Last words , The author is a newcomer , Not doing well in many ways , Welcome the boss to correct , Study together , To rush

Navigation assistant

[TOC]

picture

Leetcode283. Move zero

Given an array  nums, Write a function that will  0  Move to end of array , While maintaining the relative order of non-zero elements .

Please note that  , You must operate on the array in place without copying it .

Example  1:

Input : nums = [0,1,0,3,12]
Output : [1,3,12,0,0]
Example  2:

Input : nums = [0]
Output : [0]


Their thinking

We create two pointers i and j, Pointer when traversing for the first time j Used to record how many non 0 Elements . That is, when traversing, every non 0 Element moves it to the left of the array , After the first traversal ,j The subscript of the pointer points to the last non 0 Element subscript . On the second traversal , The starting position is from j Start to finish , Set all the elements in the remaining section to 0.

Source code

class Solution {
 public void moveZeroes(int[] nums) {
 if(nums==null||nums.length==0){
 return;
 }
 int[] tmp=new int[nums.length];
 int j=0;
 for(int i=0;i<nums.length;i++){
 if(nums[i]!=0){
 tmp[j]=nums[i];
 j++;
 }
 }
 for(int i=0;i<nums.length;i++){
 nums[i]=tmp[i];
 }
 }
}


🥰Leetcode167. The sum of two numbers and two input a valid 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] .


Their thinking

Initially, two pointers point to the position of the first element and the position of the last element . Calculate the sum of two elements pointed to by two pointers at a time , And compare with the target value . If the sum of the two elements is equal to the target value , The only solution is found . If the sum of the two elements is less than the target value , Then move the left pointer to the right one bit . If the sum of the two elements is greater than the target value , Move the right pointer to the left by one bit . After moving the pointer , Repeat the above operation , Until you find the answer .

The essence of using double pointers is to narrow the search range . Then will the possible solutions be filtered out ？ The answer is no . hypothesis  \textit{numbers}[i]+\textit{numbers}[j]=\textit{target}numbers[i]+numbers[j]=target  It's the only solution , among  0 \leq i<j \leq \textit{numbers}.\textit{length}-10≤i<j≤numbers.length−1. Initially, the two pointers point to the subscript  00  And subscripts  \textit{numbers}.\textit{length}-1numbers.length−1, The left pointer points to a subscript less than or equal to  ii, The right pointer points to a subscript greater than or equal to  jj. Unless the left and right pointers are already in the subscript  ii  and  jj, Otherwise, the left pointer must reach the subscript first  ii  The position or right pointer reaches the subscript first  jj  The location of .

If the left pointer reaches the subscript first  ii  The location of , At this time, the right pointer is still subscript  jj  The right side of the ,\textit{sum}>\textit{target}sum>target, Therefore, the right pointer must move to the left , The left pointer cannot be moved to  ii  The right side of the .

If the right pointer reaches the subscript first  jj  The location of , At this time, the left pointer is still subscript  ii  The left side of the ,\textit{sum}<\textit{target}sum<target, Therefore, the left pointer must move to the right , The right pointer cannot move to  jj  The left side of the .

thus it can be seen , Throughout the movement , The left pointer cannot be moved to  ii  The right side of the , The right pointer cannot move to  jj  The left side of the , Therefore, possible solutions will not be filtered out . Because the question ensures that there is a unique answer , Therefore, the answer can be found by using double pointers .

🤩 Source code

class Solution {
 public int[] twoSum(int[] numbers, int target) {
 int left=0,right=numbers.length-1;
 while(left<right){
 int currentSum=numbers[left]+numbers[right];
 if(currentSum==target){
 return new int[]{left+1,right+1};
 }else if(currentSum<target){
 left++;
 }else{
 right--;
 }
 }
 return new int[]{-1,-1};
 }
}


summary

Pass these two questions , We learned about double pointers , Reviewed the knowledge of arrays and loops , So , Look forward to the next article , Make progress with me , Try harder every day , Take a bigger step

I think the article is well written , Like comments, pay attention to a wave , Love you