不想再受伤 發表於 2022-9-22 14:54:12

LeetCode 题解 Swift 有效的完全平方数

<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li>题目</li><li>方法一：使用内置的库函数</li><ul class="second_class_ul"><li>思路及解法</li><li>复杂度分析</li></ul><li>方法二：暴力</li><ul class="second_class_ul"><li>思路及解法</li><li>代码</li><li>复杂度分析</li></ul><li>方法三：二分查找</li><ul class="second_class_ul"><li>思路及解法</li><li>细节</li><li>代码</li><li>复杂度分析</li></ul></ul></div><p class="maodian"></p><h2>题目</h2>
<p>给定一个 <strong>正整数</strong> <code>num</code>，编写一个函数，如果 <code>num</code> 是一个完全平方数，则返回 <code>true</code>，否则返回 <code>false</code>。</p>
<p>进阶：<strong>不要</strong> 使用任何内置的库函数，如&nbsp;<code>sqrt</code>。</p>
<p><strong>示例 1：</strong></p>
<blockquote><p><strong>输入：</strong> num = 16</p>
<p><strong>输出：</strong> true</p></blockquote>
<p><strong>示例 2：</strong></p>
<blockquote><p><strong>输入：</strong> num = 14</p>
<p><strong>输出：</strong> false</p></blockquote>
<p class="maodian"></p><h2>方法一：使用内置的库函数</h2>
<p class="maodian"></p><p class="maodian"></p><p class="maodian"></p><h3>思路及解法</h3>
<p>根据完全平方数的性质，我们只需要直接判断 num\textit{num}num 的平方根 xxx 是否为整数即可。对于不能判断浮点数的值是否等于整数的语言，则可以通过以下规则判断：</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202209/20220922083838036.png" /></p>
<div class="jb51code"><pre class="brush:java;">class Solution {
    func isPerfectSquare(_ num: Int) -&gt; Bool {
      let x: Int = Int(sqrt(Double(num)))
      return x * x == num
    }
}
</pre></div>
<p class="maodian"></p><p class="maodian"></p><p class="maodian"></p><h3>复杂度分析</h3>
<p>代码中使用的 pow 函数的时空复杂度与 <code>CPU</code> 支持的指令集相关，这里不深入分析。</p>
<p class="maodian"></p><h2>方法二：暴力</h2>
<h3>思路及解法</h3>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202209/20220922083838037.png" /></p>
<p class="maodian"></p><p class="maodian"></p><h3>代码</h3>
<div class="jb51code"><pre class="brush:java;">class Solution {
    func isPerfectSquare(_ num: Int) -&gt; Bool {
      var x: Int = 1
      var square: Int = 1
      while square &lt;= num {
            if square == num {
                return true
            }
            x += 1
            square = x * x
      }
      return false
    }
}
</pre></div>
<h3>复杂度分析</h3>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202209/20220922083838038.png" /></p>
<p class="maodian"></p><h2>方法三：二分查找</h2>
<h3>思路及解法</h3>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202209/20220922083838039.png" /></p>
<p class="maodian"></p><h3>细节</h3>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202209/20220922083838040.png" /></p>
<h3>代码</h3>
<div class="jb51code"><pre class="brush:java;">class Solution {
    func isPerfectSquare(_ num: Int) -&gt; Bool {
      var left: Int = 0
      var right: Int = num
      while left &lt;= right {
            let mid = (right - left) / 2 + left
            let square = mid * mid
            if square &lt; num {
                left = mid + 1
            } else if square &gt; num {
                right = mid - 1
            } else {
                return true
            }
      }
      return false
    }
}
</pre></div>
<h3>复杂度分析</h3>
<ul><li>时间复杂度：O(log⁡n)，其中 n为正整数 num 的最大值。</li><li>空间复杂度：O(1)。</li></ul>
<p>以上就是LeetCode 题解 Swift 有效的完全平方数的详细内容，更多关于Swift 有效完全平方数的资料请关注琼殿技术社区其它相关文章！</p>
                           
                            <div class="art_xg">
                              <b>您可能感兴趣的文章:</b><ul><li>前端算法题解leetcode49-字母异位词分组</li><li>前端算法题解 leetcode50-Pow(x, n)</li><li>前端算法leetcode109题解有序链表转换二叉搜索树</li><li>前端算法题解leetcode114二叉树展开为链表</li><li>LeetCode 刷题 Swift 两个数组的交集</li><li>前端算法题解leetcode36-有效的数独示例</li></ul>
                            </div>

                        </div>
                        <!--endmain-->
頁: [1]
查看完整版本: LeetCode 题解 Swift 有效的完全平方数