Front end algorithm interview must brush questions series [14]

Wenbin big bird 2021-02-23 04:05:42
end algorithm interview brush questions


There's nothing in this series , It's pure leetcode Topic analysis , Don't seek to use a coquettish line or niche solution , But with clear code and simple enough ideas to help you clear up the topic . Let you no longer be afraid of the written test in the interview .

24. Find the first and last positions of the elements in the sort array (find-first-and-last-position-of-element-in-sorted-array)

label

  • Two points search
  • secondary

subject

leetcode Portal

There's no point here ,leetcode Just open it , The main idea of the topic :

Give a Orderly Array nums And a number target, It is required to find the first element subscript equal to this element in the array , The last element subscript equal to this element .

The basic idea

See ascending order , Ordered arrays think of binary search

Look at this article Two points search

This is a classic binary search variant . Binary search has 4 Big basic variety problem :

  1. Find the first element whose value is equal to the given value
  2. Find the last element whose value is equal to the given value
  3. Find the first element greater than or equal to the given value
  4. Find the last element less than or equal to the given value

We use the front 2 Variety , Merger will solve the problem .

step

  1. Find the subscript of the first element whose value is equal to the given value
  2. Find the subscript of the last element whose value is equal to the given value
  3. combined

The writing method realizes

Looking at the long , It's really simple , Don't panic.

// Dichotomous search for the first and target Equal elements , Time complexity O(logn)
let searchFirstEqualElement = (nums, target) => {
let [left, right] = [0, nums.length-1]
while (left <= right) {
pivot = left + Math.floor((right - left) / 2)
if (nums[pivot] > target) {
right = pivot - 1
} else if (nums[pivot] < target) {
left = pivot + 1
} else {
// All of the above is the basic code of binary search , As like as two peas 
// The difference is equal to , We want to find the first one with target Equal elements 
if ((pivot === 0) || (nums[pivot-1] !== target)) {
// When these two things happen, we find 『 Left boundary 』
// 1. index be equal to 0, There's nothing to say 
// 2. When nums[pivot-1] One more element on the left doesn't equal target It means we've reached the left border 
return pivot
}
// Or move to the right and left , That is the pivot look forward 
right = pivot - 1
}
}
return -1
}
// Binary search for the last one and target Equal elements , Time complexity O(logn)
let searchLastEqualElement = (nums, target) => {
let [left, right] = [0, nums.length-1]
while (left <= right) {
pivot = left + Math.floor((right - left) / 2)
if (nums[pivot] > target) {
right = pivot - 1
} else if (nums[pivot] < target) {
left = pivot + 1
} else {
// All of the above is the basic code of binary search , As like as two peas 
// The difference is equal to , We want to find the last one with target Equal elements 
if ((pivot === nums.length-1) || (nums[pivot+1] != target)) {
// When these two things happen, we find 『 Right border 』
// There's a way of doing that , I don't want to repeat this 
return pivot
}
left = pivot + 1
}
}
return -1
}
// Finally, just merge 
var searchRange = function(nums, target) {
return [searchFirstEqualElement(nums, target), searchLastEqualElement(nums, target)]
};
console.log(searchRange([5,7,7,8,8,10], 8))
 Copy code 

in addition , If you can't remember how to write two points in the interview , Forced writing is OK , The realization is the most important .

That's OK. , Notice that you're using js, Make good use of tools , It's also ability .

Efficient answers > Write out > I can't write

let searchRange = (nums, target) => {
return [nums.indexOf(target), nums.lastIndexOf(target)]
};
 Copy code 

There is not much time today , Just one

In addition, I'd like to recommend this elder brother's article to you , It's very simple , It is very useful for advanced students , Wall crack recommendation !!! Core concepts and algorithms

That's all for today , If you want to brush the topic with me, you can add my wechat Search my wechat infinity_9368, You can chat and say Add my code " Heavenly King Gedi tiger " The next sentence is english , Please send me the verification message presious tower shock the rever monster, I see it through , The code is not right, no, No , After that, I'll do my best to help you , But pay attention to the way you ask questions , I suggest you read this article first : The wisdom of asking questions

版权声明
本文为[Wenbin big bird]所创,转载请带上原文链接,感谢
https://qdmana.com/2021/02/20210223024104460P.html

  1. JavaScript advanced: Javascript object-oriented, JavaScript built-in object, JavaScript BOM, JavaScript encapsulation
  2. JavaScript advanced: Javascript object-oriented, JavaScript built-in object, JavaScript BOM, JavaScript encapsulation
  3. Vue determines whether the El form in the elementui is updated or changed. If it changes, it will prompt whether to save it. If it does not change, it will leave directly
  4. Algorithm problem: sum of two numbers -- JavaScript and Java implementation
  5. High performance nginx HTTPS tuning
  6. JQuery advanced
  7. day 30 jQuery
  8. JQuery:JQuery Basic syntax, jQuery selector, jQuery DOM, comprehensive case check box, comprehensive case random picture
  9. TCP/IP 开胃菜 之 HTTP
  10. JQuery:JQuery Basic syntax, jQuery selector, jQuery DOM, comprehensive case check box, comprehensive case random picture
  11. JavaScript data type
  12. [micro front end] the final chapter of micro front end - Qiankun guide and overall exploration of micro front end
  13. Solve Ajax cross domain problem [5 solutions]
  14. HTTP of TCP / IP appetizer
  15. Optimization of pod creation efficiency in serverless scenario
  16. Iqiyi Sports: experience the ultimate expansion and contraction of serverless, and increase the utilization rate of resources by 40%
  17. First knowledge of HTTP / 1.1
  18. First knowledge of HTTP / 1.1
  19. Webpack learning notes series 05 devserver
  20. Webpack learning notes series 04 - resource processing optimization
  21. How to build a high performance front end intelligent reasoning engine
  22. How to become a professional front end engineer in 2021?
  23. How to transform single / micro service application into serverless application
  24. How to transform single / micro service application into serverless application
  25. How to transform single / micro service application into serverless application
  26. How to connect the ground gas to the micro front end?
  27. How to connect the ground gas to the micro front end?
  28. How to connect the ground gas to the micro front end?
  29. Vue server rendering principle analysis and introduction
  30. Realize the correct loading of text message
  31. Building my own project scaffolding with yeoman
  32. JavaScript advanced prototype and prototype chain
  33. React background management front end system (based on open source framework development) start
  34. JS practical skills breakpoint debugging
  35. I'd like to share with you 20 super easy-to-use Chrome extension plug-ins
  36. Get page element location
  37. Use the powerful API of modern browser to record any interface in the browser and realize export, save and management
  38. Delayed code execution in flutter
  39. Reconfiguration experience of KOA middleware system
  40. Add comments to your blog
  41. Svg editor -- new path
  42. Detailed explanation of debounce and throttle of JavaScript function
  43. Anti shake and throttling and corresponding react hooks package
  44. C2m: the first CSDN article moved to MOOC script 5000 words, detailed painstaking development process, there are renderings and source code at the end of the article
  45. Front end, school recruitment, Taobao, guide
  46. [vue2 & G6] get started quickly
  47. Canvas from the beginning to the pig
  48. Take five minutes to standardize the code comments?
  49. Some thoughts on sass
  50. what?! You haven't filled in the award information yet
  51. How to get the interface + tsdoc needed by TS through swagger
  52. Binary tree
  53. Canvas drawing method in Web screenshot
  54. Front end docker image volume optimization (node + nginx / node + multi-stage construction)
  55. Become a big influence of technology? Coding pages quickly build personal blog
  56. Object and array deconstruction, spread operator, rest operator
  57. Analysis of Axios source code
  58. Two ways to delete useless code in project (Practical)
  59. Edit your picture with canvas
  60. Today's chat: 2-4 years to walk out of the resignation dilemma and comfort zone