Square root of LeetCode- 69.x (day15)

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

One, foreword

👨🎓 Author: Bug Bacteria

✏️ blog: CSDN, Nuggets, etc

💌 public account: Magic House of the Circle of the Apes

🚫 special statement: original is not easy, reprint please attach the original source link and this article statement, thank you for your cooperation.

🙏 Copyright notice: part of the text or pictures in the article may come from the Internet or Baidu Encyclopedia, if there is infringement, please contact bug bacteria processing.

Hello, little friends, I am bug bacteria 👀. Gold three silver four, brush the month again. So whether you’re looking for a career change or a career change, get your act together and do the right thing 👣. So, quickly follow the pace of bug bacteria roll up ⏰, become strong from this moment ➕🧈.

In the process of reviewing articles, if you think the articles are helpful to you at all, please don’t be too mean with your likes and bravely light up the articles 👍. Your likes (collect ⭐️+ pay attention to 👨 port + message board) are the best encouragement and support for bugs on my creation path. Time does not abandon 🏃🏻♀️, nuggets stop 💕, cheer up 🏻

Ii. Title Description:

Given a non-negative integer x, calculate and return the arithmetic square root of x. Since the return type is an integer, only the integer part of the result is retained, and the decimal part is omitted.

Note: It is not allowed to use any built-in exponential functions and operators, such as POw (x, 0.5) or x ** 0.5.

See the following example for details:

Example 1:

Input: x = 4 Output: 2Copy the code

Example 2:

Input: x = 8 Output: 2 Explanation: The arithmetic square root of 8 is 2.82842... Because the return type is an integer, the decimal part will be omitted.Copy the code

** Hint: **

0 <= x <= 231 - 1

LeetCode ⭐⭐

Iii. Analysis of Ideas:

This is a common interview question that asks you to find the integer part of the square root of x without using a function such as SQRT (x).

The general idea is as follows:

Use other mathematical functions instead of the square root function to get the exact result, taking the integer part as the answer;
Get the approximate result through the mathematical method, directly as the answer.

(n-1)^2 < target < (n+1)^2

All you have to do is satisfy this condition, and all you have to do is find n. Other methods on their own to explore ha, I generally provide ideas to everyone, the rest of their own cough up.

So the dichotomy idea is:

Animation demo:

Iv. Algorithm implementation:

Dichotomy _AC code

The specific algorithm code is as follows:

class Solution { public int mySqrt(int x) { int left = 0, right = x, ans = -1; While (left <= right) {int middle = left + (right-left) / 2; if ((long)middle * middle <= x) { ans = middle; left = middle + 1; } else { right = middle - 1; } } return ans; }}Copy the code

V. Summary:

The screenshot of the binary Leetcode submission results is as follows:

Complexity analysis:

Time complexity: O(logx), that is, the number of binary search times.
Space complexity: O(1).

To sum up: dichotomy is a very good solution to this problem, is also a common interview question, so friends need to hone ah, I also planted for the first time, there is a test case did not pass, the results found that the length of the super int. So you just multiply the two numbers and turn them into long.

If you have any better ideas or ideas, please let me know in the comments section. We can learn from each other and grow faster.

Well, that’s all for this episode and I’ll see you next time.

Six, the previous recommendation:

Leetcode -1. Sum of two numbers
Leetcode – 9. Palindrome
Leetcode -13. Roman numeral to integer
Leetcode -14. The longest public prefix
Leetcode -20. Valid parentheses
Leetcode -21. Merge two ordered lists
Leetcode -26. Remove duplicates from ordered arrays

Vii. End of article:

If you want to learn more, check out bug Bug’s LeetCode Problem of the Day column! With you brush together, each column is attached with a detailed solution, hand in hand with you to solve the problem.

One person may feel very tired and difficult to persist in brushing, but a group of people will think it is a meaningful thing to brush, urge and encourage each other, and become stronger together.

Finally send you two words, with you!

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

☘️ Be who you want to be, there is no time limit, you can start whenever you want,

🍀 You can change from now on, you can also stay the same, this thing, there are no rules to speak of, you can live the most wonderful yourself.