Maybe you and I have never met, but we may not have met. I am a head fish

1.# Dachang high-frequency algorithm ATOI

Some time ago and a few boiled water group of old colleagues about rub a self-service hot pot, taste good, can unlimited dry meat, but also self-help milk tea XXX… Skip 😋

Some of them went to small and medium-sized companies when the leader, but also several to byte, byte must test the algorithm, and not ask you to do how hard the topic, but mind if you brush the algorithm… It’s basically hard to pass without a brush, and one of the medium-difficulty algorithm problems, string converted integers (AToi), has been asked several times. Take a look

2.# String conversion integer (atoi)

2.1# The topic is very long, let’s read it patiently

MyAtoi (string s) converts a string to a 32-bit signed integer (similar to atoi in C/C++).

MyAtoi (string s)

  1. Read in the string and discard useless leading whitespace
  2. Checks whether the next character (assuming it has not reached the end of the character) is a plus or minus sign and reads that character (if any). Determine whether the final result is negative or positive. If neither exists, the result is assumed to be positive.
  3. Read the next character until the next non-numeric character is reached or the end of the input is reached. The rest of the string is ignored.
  4. Convert the numbers read in the previous steps to integers (that is, “123” -> 123, “0032” -> 32). If no number is read in, the integer is 0. Change symbols as necessary (starting with Step 2).
  5. If the number of integers exceeds the range of 32-bit signed integers [−231, 231 − 1], truncate the integer to keep it within the range. Specifically, integers less than −231 should be fixed to −231 and integers greater than 231 − 1 to 231 − 1.
  6. Returns an integer as the final result.

Note:

  • Whitespace characters in this case include only the space character ‘ ‘.
  • Do not omit any characters other than those following a leading space or number.

The 2.2# example is also quite long, and I’ll get through it in no time

Example 1:

Enter: s ="42"Output:42Explanation: The string in bold is the character already read, the caret is the character currently read. The first1Step:"42"(Currently no character is read in because there is no leading space) ^ first2Step:"42"No character is currently being read in because it does not existThe '-'or'+') ^3Step:"42"(read"42"^ Parse to an integer42. Due to the"42"In the range [...231.231 - 1], the final result is42 。

Copy the code

Example 2:

Enter: s ="- 42"Output: -42Explanation: the first1Step:"- 42"(read leading space, but ignore) ^ first2Step:"- 42"(readThe '-'Character, so the result should be negative) ^ first3Step:"- 42"(read"42"^ Resolves to an integer -42. Due to the"- 42"In the range [...231.231 - 1], the final result is -42 。

Copy the code

Example 3:

Enter: s ="4193 with words"Output:4193Explanation: the first1Step:"4193 with words"(Currently no character is read in because there is no leading space) ^ first2Step:"4193 with words"No character is currently being read in because it does not existThe '-'or'+') ^3Step:"4193 with words"(read"4193"; Since the next character is not a number, the reading is stopped) ^ parses to an integer4193. Due to the"4193"In the range [...231.231 - 1], the final result is4193 。

Copy the code

3.# I suspect you’re testing my patience

Finally finished reading the topic, do not know what you feel in the heart, ten thousand “grass mud horse” from the prairie pentium? Yes, me too, because the questions and examples are so long that I don’t even want to look at them…

I don’t think they want to hire at all… This is a long problem

# 4

This topic at a glance is more bluffing, the topic stem so long, first of all will brush off a wave of impatience to read the fire braving three zhangs elder brother. Well, it doesn’t have to be that way. Get a grip on yourself and think about it: The longer the question, the more detail it gives, the more information it provides and maybe even the solution is in the question

  1. Read in the string and discard useless leading whitespace. Condition one is telling us to remove the leading whitespace first

  2. Checks whether the next character (assuming it has not reached the end of the character) is a plus or minus sign and reads that character (if any). Determine whether the final result is negative or positive. If neither exists, the result is assumed to be positive. Condition 2 implies that we should pay attention to the “+” and “-” at the beginning.

  3. Read the next character until the next non-numeric character is reached or the end of the input is reached. The rest of the string is ignored. Condition 3 tells us to stop parsing if we encounter a non-number

  4. Convert the numbers read in the previous steps to integers (that is, “123” -> 123, “0032” -> 32). If no number is read in, the integer is 0. Change symbols as necessary (starting with Step 2). Condition 4 is telling us to be careful about removing the 0 at the head

  5. If the number of integers exceeds the range of 32-bit signed integers [−231, 231 − 1], truncate the integer to keep it within the range. Specifically, integers less than −231 should be fixed to −231 and integers greater than 231 − 1 to 231 − 1. Condition 5 is so obvious, it just tells us the range of integers

  6. Returns an integer as the final result. Condition 6 is implying that we have to be integers, not decimals

5.# parseInt

After reading this big pile of questions and meaning analysis, I suspect that the interviewer not only tests my patience but also wants me to achieve a parseInt, but I just don’t want to give you the idea, I will use parseInt to do

/ * * *@param {string} s
 * @return {number}* /
const myAtoi = function(s) {
  let result = parseInt(s)
  const max = Math.pow(2.31) - 1
  const min = -max - 1
  // parseInt('fatfish') => NaN
  // Scope limited
  return isNaN(result) ? 0 : (result > max ? max : (result < min ? min : result))
}

Copy the code

Don’t say, really passed all the use cases, and the grades are very good, but I guess the interviewer turned green, directly added a knife, do not allow the use of parseInt

6.# regular parsing

No way, is limited to the system API call, can only write a parser, this problem when you see to remove space, limit the number I believe you will soon also think of the use of re will be particularly convenient

6.1# step1: Remove whitespace

This is easy. One ^\s* will do it

6.2# step2: sign confirmation

Also very simple, [\+-]? It can only be + or -, and there may not even be a sign bit

6.3 step3: figure parsing

This part is the most important, take out the number part \d*, ha ha, isn’t it funny, so easy?

6.4 step4: remove the redundant 0 at the head

A + sign will do. Let’s look at an example


+'0'= >0
+'00123'= >123

Copy the code

6.5 step5: scope limitation

// Calculate the maximum value
const max = Math.pow(2.31) - 1
// Calculate the minimum value
const min = -max - 1

Copy the code

6.6 step6: return an integer

We’ll look at this in the global analysis

6.7 Regular solution

/ * * *@param {string} s
 * @return {number}* /
const myAtoi = function(s) {
  /* 1. ^\s* Matches possible Spaces step1 2. ([\+-]? \d*) match symbols and numbers step2 and step3 3. \d* non-numeric parsing */ 
  const match = s.match(/^\s*([\+-]? \d*)\D*/)
  // step5 limit the scope
  const max = Math.pow(2.31) - 1
  const min = -max - 1
  let result

  if (match) {
    // step4 remove the extra 0 in the header
    result = +match[1]
    // step6 return the integer
    result = isNaN(result) ? 0 : (result > max ? max : (result < min ? min : result))
  }

  return result
};

Copy the code

The result was better than calling parseInt directly, which surprised me

The last

I hope I can share practical, basic and advanced knowledge points with you all the time.

I look forward to your attention in nuggets: front end bighead fish, you can also find me in the public number: front end bighead fish.