T69. Sqrt(x)【Easy】
写方法 int sqrt(int x)
计算并返回 x 的平方根
哇这是数学啊！为难死我了！忘记了数学！
① 找到一个平方> x 的 r ,然后 把 r 减小凑出正确的解
② 若是简单的 -1 然后得到正确的值会超时
③ 所以要找到一个快速而又不会减的太快的方法
怎么找呢？咳，数学公式来说话（我竟然还记得一点数学）：
所以用下面的公式就很棒！
r = (r + x/r) / 2;
代码取自 Top Solution，稍作注释
public int mySqrt(int x) {
// 要用long,因为后面要r*r会超过int
long r = x;
// 数学推导，慢慢减少
while (r*r > x)
r = (r + x/r) / 2;
return (int) r;
}
上一题：LeetCode第12题: intToRoman(C语言） 本系列文章，旨在打造LeetCode题目解题方...
上一题：LeetCode第3题:lengthOfLongestSubstring(C语言） 思路：利用归并排序的思...
上一题：LeetCode第14题: longestCommonPrefix(C语言） 求助：本地运行没问题，但是在...
T104. Maximum Depth of Binary Tree【Easy】 题目 给定一个二叉树，求它的最大...
T103. Binary Tree Zigzag Level Order Traversal【Medium】 题目...
T105. Construct Binary Tree from Preorder and Inorder Tra...
T101. Symmetric Tree【Easy】 题目 给一个二叉树，确认这个是不是自己的镜像（即围绕其中心对...
T70. Climbing Stairs【Easy】 题目 你要爬楼梯。你面对的是一个 n 步可以走上去的楼梯。 ...
T102. Binary Tree Level Order Traversal【Medium】 题目 给出一个二叉...
T54. Spiral Matrix【Medium】 题目 给一个 m × n 的矩阵（m 行，n 列），按螺旋顺...
本文标题：每天一题LeetCode【第50天】
本文链接：https://www.haomeiwen.com/subject/wouzattx.html
网友评论