## Leetcode 27 removes elements 28 implements division of strstr() & 29

Big sai 2020-11-13 06:06:59
leetcode removes elements implements division

Protect the happiness and hardship , Welcome to pay attention to official account if there is a daily attendance. `bigsai` Reply to the group , Welcome if you have any help give the thumbs-up Support ！

## Remove elements

Give you an array nums And a value val, You need In situ Remove all values equal to val The elements of , And return the new length of the array after removal .
Don't use extra array space , You have to use only O(1) Additional space and In situ Modify input array .
The order of elements can be changed . You don't need to think about the elements in the array that follow the new length .

Example 1:

Given nums = [3,2,2,3], val = 3,
Function should return the new length 2, also nums The first two elements in are 2.
You don't need to think about the elements in the array that follow the new length .

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,
Function should return the new length 5, also nums The first five elements in are 0, 1, 3, 0, 4.
Note that these five elements can be in any order .
You don't need to think about the elements in the array that follow the new length .

explain :

Why is the return value an integer , But the output answer is array ?
Please note that , The input array is based on 「 quote 」 By way of transmission , This means that modifying the input array in a function is visible to the caller .
You can imagine the internal operation as follows :
// nums In order to “ quote ” By way of transmission . in other words , Do not make any copies of the arguments
int len = removeElement(nums, val);
// Modifying the input array in a function is visible to the caller .
// Based on the length returned by your function , It prints out the array Within this length All elements of .
for (int i = 0; i < len; i++) {
print(nums[i]);
}

analysis ：
Use one index Mark the current real position , In the process of traversal, if the current position value and the target value are not equal, then the value is assigned , If it is equal to the data to be deleted, skip no assignment . This is the process of traversing a revaluation .

ac The code is ：

``````public int removeElement(int[] nums, int val) {

int index=0;
for(int i=0;i<nums.length;i++)
{

if(nums[i]==val)
continue;
nums[index++]=nums[i];
}
return index;
}
``````

## Realization strStr()

Title Description ：

Given a haystack String and a needle character string , stay haystack Find in string needle The first place the string appears ( from 0 Start ). If it doesn't exist , Then return to -1.

Example 1:

Input : haystack = “hello”, needle = “ll”
Output : 2

Example 2:

Input : haystack = “aaaaa”, needle = “bba”
Output : -1

explain :

When needle When it's an empty string , What value should we return ？ This is a good question in an interview .
For this question , When needle When it's an empty string, we should return 0 . This is related to C Linguistic strstr() as well as Java Of indexOf() The definition matches

analysis
Because of the amount of data , Use of this question KMP The efficiency of the algorithm is not very good (KMP Preprocessing is required ), On the contrary, using common methods is very efficient . Use sunday The effect of the algorithm is also relatively common , It's amazing .

Normal matching Also known as double pointer or something, it's actually a violent match , But it's much faster to match violence with official methods , The personal style is ：

``````public int strStr(String haystack, String needle) {

if(needle==null||"".equals(needle))
return 0;
char a[]=haystack.toCharArray();
char b[]=needle.toCharArray();
for(int i=0;i<a.length-b.length+1;i++)
{

int j=-1;
while(j++<b.length)
{

if(a[i+j]!=b[j])
{

break;
}
if(j==b.length-1)
return i;
}
}
return -1;
}
``````

Official concise writing ：

``````public int strStr(String haystack, String needle) {

int L = needle.length(), n = haystack.length();
for (int start = 0; start < n - L + 1; ++start) {

if (haystack.substring(start, start + L).equals(needle)) {

return start;
}
}
return -1;
}
``````

kmp Methods the author also realized , However, due to data problems, the effect is not so good , Of course kmp The algorithm will not be introduced in detail here ：

`````` public int[] getNext(String needle) {

char[] p = needle.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length - 1) {

if (k == -1 || p[j] == p[k]) {

next[++j] = ++k;
} else {

k = next[k];
}
}
return next;
}
public int KMP(String haystack, String needle) {

char[] t = haystack.toCharArray();
char[] p = needle.toCharArray();
int i = 0; // The position of the main string
int j = 0; // The location of the pattern string
int[] next = getNext(needle);
while (i < t.length && j < p.length) {

if (j == -1 || t[i] == p[j]) {
// When j by -1 when , To move is i, Of course j I want to return 0
i++;
j++;
} else {

// i There's no need to go back
// i = i - j + 1;
j = next[j]; // j Go back to the designated location
}
if(j==p.length) {
return i-j;}
}
return -1;
}
public int strStr(String haystack, String needle) {

if(needle==null||"".equals(needle))
return 0;
return KMP(haystack, needle);
}
``````

Also use sunday Algorithm ( I'll talk about it later ) The effect is also average

`````` public int strStr(String haystack, String needle) {

if(needle==null||"".equals(needle))
return 0;
int lastchar[]=new int [200];
char a[]=haystack.toCharArray();
char p[]=needle.toCharArray();
for(int i=0;i<p.length;i++)
{

lastchar[p[i]]=i+1;
}
int i=0;
int j=0;
int len=a.length-p.length+1;
while (i<a.length) {

int index=i-(lastchar[a[i]]-1);//a[i] character
if(lastchar[a[i]]!=0&&index>=0&&index<len)// Can match
{

while (j<p.length) {
// Try to match
if(p[j]!=a[index+j])
break;
j++;
}
if(j==p.length)
{

return index;
}
else {

i=index+p.length;
j=0;
}
}
else {

i++;
}
}
return -1;
}
``````

## Divide two numbers

Title Description

Given two integers , Divisor dividend And divisor divisor. Divide two numbers , Multiplication is not required 、 Division and mod Operator .
Return dividend dividend Divide by divisor divisor Get the business .
The result of integer division should be truncated （truncate） Its decimal part , for example ：truncate(8.345) = 8 as well as truncate(-2.7335) = -2

Example 1:

Input : dividend = 10, divisor = 3
Output : 3
explain : 10/3 = truncate(3.33333…) = truncate(3) = 3

Example 2:

Input : dividend = 7, divisor = -3
Output : -2
explain : 7/-3 = truncate(-2.33333…) = -2

Tips ：

Both dividend and divisor are 32 Bit signed integer .
The divisor is not 0.
Suppose our environment can only store 32 Bit signed integer , The value range is `[−2^31, 2^31 − 1]`. In this question , If the division result overflows , Then return to `2^31 − 1`.

analysis
What is the value of the division that needs to be calculated , And there are also the following problems ：

• The value may be out of bounds
• You can't use multiplication and division

The numerical boundary crossing problem can be considered in special cases . But if you can't use multiplication and division, how do you know what the result of division is ？

Law 1 ： Addition and accumulation
This is probably the dumbest way , Divided by a few , Use this number to add up to find the result .

Of course, if the number is large , Divisor is 1,2 This one will be slow , Only reluctantly ac.

``````public static int divide(int dividend, int divisor) {

int zhengfu=1;
long divd=dividend,divs=divisor;
if(dividend>0&&divisor<0)
{

divs=-divisor;zhengfu=-1;
}
else if(dividend<0&&divisor>0)
{

divd=-divd;zhengfu=-1;
}
else if (dividend<0&&divisor<0) {

divd=-divd;divs=-divs;
}
if(Math.abs(divd)<Math.abs(divs))return 0;
long i=0,index=0;
if(divs==1)i=divd+1;
else
while (index<=divd) {

i++;index+=divs;
}
long va=(zhengfu==1?(i-1):(1-i));
if(va>Integer.MAX_VALUE)return Integer.MAX_VALUE;
if(va<Integer.MIN_VALUE)return Integer.MIN_VALUE;
return (int) va;
}
``````

What method can be used to optimize the algorithm ？ This involves the problem of binary . In binary ：

• 2=0010 Express 2 individual 1
• 4=0100 Express 4 individual 1
• 6=0110 Express 4+2 individual 1

Similarly, any number can be represented in binary ,1101 Express 8+4+1. In the same way, we bring this idea to this problem for calculation , But the basic unit is not 1 nothing more

Because we use addition to multiply a number by two , So use this to find the maximum number of ranges at a time ( At the same time, other variables are required to count the number of times ). Then, after processing this part of data, continue to operate the remaining values until it stops . Of course, pruning can be considered in the specific implementation ( Divisor is ±1 When , At the same time, we should properly solve the problems of positive and negative numbers and cross-border , Here is to use long Handle , Then mark them all with a positive number ).

The implementation code is ：

``````public static int divide(int dividend, int divisor)
{

if(divisor==1)return dividend;
if(divisor==-1)return dividend==Integer.MIN_VALUE?Integer.MAX_VALUE:-dividend;
long value=0;// Record the total number of results
int time=1;// Number of temporary times
long divd=dividend,divs=divisor;// Turn into long Handle
int zhengfu=1;// Judge whether it is positive or negative
if(divd<0)
{

divd=-divd;zhengfu=-zhengfu;
}
if(divs<0)
{

divs=-divs;zhengfu=-zhengfu;
}
long team=divs;// Temporary data 2 Fold superposition
while (team<=divd) {

if(team+team>divd)
{

value+=time;
divd-=team;
team=divs;
time=1;
continue;
}
team+=team;
time+=time;
}
return (int) (zhengfu==1?value:-value);
}
``````

## Conclusion

ok , This time the clock out is over , Welcome to support , Welcome daily attendance if you punch in official account. `bigsai` Reply to the group to join the punch in .