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;
}

 Insert picture description here

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;
}

 Insert picture description here
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);
}

 Insert picture description here
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;
}

 Insert picture description here

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 .
 Insert picture description here
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;
}

 Insert picture description here
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
 Insert picture description here
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);
}

 Insert picture description here

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 .
 Insert picture description here

版权声明
本文为[Big sai]所创,转载请带上原文链接,感谢

  1. [front end -- JavaScript] knowledge point (IV) -- memory leakage in the project (I)
  2. This mechanism in JS
  3. Vue 3.0 source code learning 1 --- rendering process of components
  4. Learning the realization of canvas and simple drawing
  5. gin里获取http请求过来的参数
  6. vue3的新特性
  7. Get the parameters from HTTP request in gin
  8. New features of vue3
  9. vue-cli 引入腾讯地图(最新 api,rocketmq原理面试
  10. Vue 学习笔记(3,免费Java高级工程师学习资源
  11. Vue 学习笔记(2,Java编程视频教程
  12. Vue cli introduces Tencent maps (the latest API, rocketmq)
  13. Vue learning notes (3, free Java senior engineer learning resources)
  14. Vue learning notes (2, Java programming video tutorial)
  15. 【Vue】—props属性
  16. 【Vue】—创建组件
  17. [Vue] - props attribute
  18. [Vue] - create component
  19. 浅谈vue响应式原理及发布订阅模式和观察者模式
  20. On Vue responsive principle, publish subscribe mode and observer mode
  21. 浅谈vue响应式原理及发布订阅模式和观察者模式
  22. On Vue responsive principle, publish subscribe mode and observer mode
  23. Xiaobai can understand it. It only takes 4 steps to solve the problem of Vue keep alive cache component
  24. Publish, subscribe and observer of design patterns
  25. Summary of common content added in ES6 + (II)
  26. No.8 Vue element admin learning (III) vuex learning and login method analysis
  27. Write a mini webpack project construction tool
  28. Shopping cart (front-end static page preparation)
  29. Introduction to the fluent platform
  30. Webpack5 cache
  31. The difference between drop-down box select option and datalist
  32. CSS review (III)
  33. Node.js学习笔记【七】
  34. Node.js learning notes [VII]
  35. Vue Router根据后台数据加载不同的组件(思考-&gt;实现-&gt;不止于实现)
  36. Vue router loads different components according to background data (thinking - & gt; Implementation - & gt; (more than implementation)
  37. 【JQuery框架,Java编程教程视频下载
  38. [jQuery framework, Java programming tutorial video download
  39. Vue Router根据后台数据加载不同的组件(思考-&gt;实现-&gt;不止于实现)
  40. Vue router loads different components according to background data (thinking - & gt; Implementation - & gt; (more than implementation)
  41. 【Vue,阿里P8大佬亲自教你
  42. 【Vue基础知识总结 5,字节跳动算法工程师面试经验
  43. [Vue, Ali P8 teaches you personally
  44. [Vue basic knowledge summary 5. Interview experience of byte beating Algorithm Engineer
  45. 【问题记录】- 谷歌浏览器 Html生成PDF
  46. [problem record] - PDF generated by Google browser HTML
  47. 【问题记录】- 谷歌浏览器 Html生成PDF
  48. [problem record] - PDF generated by Google browser HTML
  49. 【JavaScript】查漏补缺 —数组中reduce()方法
  50. [JavaScript] leak checking and defect filling - reduce() method in array
  51. 【重识 HTML (3),350道Java面试真题分享
  52. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  53. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  54. [re recognize HTML (3) and share 350 real Java interview questions
  55. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  56. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  57. 【重识 HTML ,nginx面试题阿里
  58. 【重识 HTML (4),ELK原来这么简单
  59. [re recognize HTML, nginx interview questions]
  60. [re recognize HTML (4). Elk is so simple