current position:Home>leetcode 69. Sqrt(x)(python)
leetcode 69. Sqrt(x)(python)
2022-01-29 19:23:12 【Wang Daya】
Little knowledge , Great challenge ! This article is participating in “ A programmer must have a little knowledge ” Creative activities .
describe
Given a non-negative integer x, compute and return the square root of x.
Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.
Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.
Example 1:
Input: x = 4
Output: 2
Copy code
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
Copy code
Note:
0 <= x <= 2^31 - 1
Copy code
analysis
Give a number in the title x , Ask to find out the square result of it , If it is an integer, the result will be returned directly , If it is a decimal result, only the integer part is returned , The idea is simple ( It's careless , Submitted several times and burst ERROR 了 , It's really a shame ):
- Direct traversal [0, x // 2 + 2] Every integer in the range i
- If i * i == x , Go straight back to i
- If i * i > x , Go straight back to i-1
Even more humiliating is , The solution finally timed out , Read the requirements in the title , x The magnitude of is really too big ...
answer
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
for i in range(0, x // 2 + 2):
if i * i == x:
return i
if i * i > x:
return i - 1
Copy code
Running results
Memory Limit Exceeded
Copy code
analysis
Of course, you can directly use the binary search method to find .
answer
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
l, r = 0, x
while l <= r:
mid = (l + r) // 2
if mid ** 2 <= x < (mid + 1) ** 2:
return mid
elif x < mid ** 2:
r = mid - 1
else:
l = mid + 1
Copy code
Running results
Runtime: 37 ms, faster than 37.53% of Python online submissions for Sqrt(x).
Memory Usage: 13.3 MB, less than 66.04% of Python online submissions for Sqrt(x).
Copy code
analysis
Of course, using built-in functions can also , But more opportunistic .
answer
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
return int(sqrt(x))
Copy code
Running results
Runtime: 25 ms, faster than 61.40% of Python online submissions for Sqrt(x).
Memory Usage: 13.3 MB, less than 66.04% of Python online submissions for Sqrt(x).
Copy code
Original link :leetcode.com/problems/sq…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201291923108400.html
The sidebar is recommended
- Compile D + +, and use d to call C from python
- Install tensorflow and python 3.6 in Windows 7
- Python collects and monitors system data -- psutil
- Python collects and monitors system data -- psutil
- Finally, this Python import guide has been sorted out. Look!
- Quickly build Django blog based on function calculation
- Getting started with Python - object oriented - special methods
- Teach you how to use Python to transform an alien invasion game
- You can easily get started with Excel. Python data analysis package pandas (VI): sorting
- Implementation of top-level design pattern in Python
guess what you like
-
Using linear systems in python with scipy.linalg
-
Python tiktok 5000+ V, and found that everyone love this video.
-
Using linear systems in python with scipy.linalg
-
How to get started quickly? How to learn Python
-
Modifying Python environment with Mac OS security
-
You can easily get started with Excel. Python data analysis package pandas (XI): segment matching
-
Advanced practical case: Javascript confusion of Python anti crawling
-
Better use atom to support jupyter based Python development
-
Better use atom to support jupyter based Python development
-
Fast power modulus Python implementation of large numbers
Random recommended
- Python architects recommend the book "Python programmer's Guide" which must be read by self-study Python architects. You are welcome to take it away
- Decoding the verification code of Taobao slider with Python + selenium, the road of information security
- Python game development, pyGame module, python implementation of skiing games
- This paper clarifies the chaotic switching operation and elegant derivation of Python
- You can easily get started with Excel. Python data analysis package pandas (3): making score bar
- Test Development: self study Dubbo + Python experience summary and sharing
- Python + selenium automated test: page object mode
- You can easily get started with Excel. Python data analysis package pandas (IV): any grouping score bar
- Opencv skills | saving pictures in common formats as transparent background pictures (with Python source code) - teach you to easily make logo
- You can easily get started with Excel. Python data analysis package pandas (V): duplicate value processing
- Python ThreadPoolExecutor restrictions_ work_ Queue size
- Python generates and deploys verification codes with one click (Django)
- With "Python" advanced, you can catch all the advanced syntax! Advanced function + file operation, do not look at regret Series ~
- At the beginning of "Python", you must see the series. 10000 words are only for you. It is recommended to like the collection ~
- [Python kaggle] pandas basic exercises in machine learning series (6)
- Using linear systems in python with scipy.linalg
- The founder of pandas teaches you how to use Python for data analysis (mind mapping)
- Using Python to realize national second-hand housing data capture + map display
- Python image processing, automatic generation of GIF dynamic pictures
- Pandas advanced tutorial: time processing
- How to make Python run faster? Six tips!
- Django: use of elastic search search system
- Fundamentals of Python I
- Python code reading (chapter 35): fully (deeply) expand nested lists
- Python 3.10 official release
- Solution of no Python 3.9 installation was detected when uninstalling Python
- This pandas exercise must be successfully won
- [Python homework] coupling network information dissemination
- Python application software development tool - tkinterdesigner v1.0 5.1 release!
- [Python development tool Tkinter designer]: Lecture 2: introduction to Tkinter designer's example project
- [algorithm learning] sword finger offer 64 Find 1 + 2 +... + n (Java / C / C + + / Python / go / trust)
- leetcode 58. Length of Last Word(python)
- Problems encountered in writing the HTML content of articles into the database during the development of Django blog
- leetcode 1261. Find Elements in a Contaminated Binary Tree(python)
- [algorithm learning] 1486 Array XOR operation (Java / C / C + + / Python / go / trust)
- Understand Python's built-in function and add a print function yourself
- Python implements JS encryption algorithm in thousands of music websites
- leetcode 35. Search Insert Position(python)
- leetcode 1829. Maximum XOR for Each Query(python)
- [introduction to Python visualization]: 12 small examples of complete data visualization, taking you to play with visualization ~