<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 0263. 丑數 ## 題目地址(263. 丑數) <https://leetcode-cn.com/problems/ugly-number/> ## 題目描述 ``` <pre class="calibre18">``` 編寫一個程序判斷給定的數是否為丑數。 丑數就是只包含質因數 2, 3, 5 的正整數。 示例 1: 輸入: 6 輸出: true 解釋: 6 = 2 × 3 示例 2: 輸入: 8 輸出: true 解釋: 8 = 2 × 2 × 2 示例 3: 輸入: 14 輸出: false 解釋: 14 不是丑數,因為它包含了另外一個質因數 7。 說明: 1 是丑數。 輸入不會超過 32 位有符號整數的范圍: [?231, 231 ? 1]。 ``` ``` ## 前置知識 - 數學 - 因數分解 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 題目要求給定一個數字,判斷是否為“丑陋數”(ugly number), 丑陋數是指只包含質因子2, 3, 5的正整數。 ![](https://img.kancloud.cn/94/dd/94dd53d411c5257414b7b1d25b3f8afb_629x339.jpg) 根據定義,我們將給定數字除以2、3、5(順序無所謂),直到無法整除。 如果得到1,說明是所有因子都是2或3或5,如果不是1,則不是丑陋數。 這就好像我們判斷一個數字是否為n(n為大于1的正整數)的冪次方一樣,我們只需要 不斷除以n,直到無法整除,如果得到1,那么就是n的冪次方。 這道題的不同在于 它不再是某一個數字的冪次方,而是三個數字(2,3,5),不過解題思路還是一樣的。 轉化為代碼可以是: ``` <pre class="calibre18">``` <span class="hljs-keyword">while</span>(num % <span class="hljs-params">2</span> === <span class="hljs-params">0</span>) num = num / <span class="hljs-params">2</span>; <span class="hljs-keyword">while</span>(num % <span class="hljs-params">3</span> === <span class="hljs-params">0</span>) num = num / <span class="hljs-params">3</span>; <span class="hljs-keyword">while</span>(num % <span class="hljs-params">5</span> === <span class="hljs-params">0</span>) num = num / <span class="hljs-params">5</span>; <span class="hljs-keyword">return</span> num === <span class="hljs-params">1</span>; ``` ``` > 我下方給出的代碼是用了遞歸實現,只是給大家看下不同的寫法而已。 ## 關鍵點 - 數論 - 因數分解 ## 代碼 - 語言支持:JS, C++, Java, Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=263 lang=javascript * * [263] Ugly Number */</span> <span class="hljs-title">/** * @param {number} num * @return {boolean} */</span> <span class="hljs-keyword">var</span> isUgly = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">num</span>) </span>{ <span class="hljs-title">// TAG: 數論</span> <span class="hljs-keyword">if</span> (num <= <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">if</span> (num === <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">const</span> list = [<span class="hljs-params">2</span>, <span class="hljs-params">3</span>, <span class="hljs-params">5</span>]; <span class="hljs-keyword">if</span> (list.includes(num)) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i <span class="hljs-keyword">of</span> list) { <span class="hljs-keyword">if</span> (num % i === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> isUgly(<span class="hljs-params">Math</span>.floor(num / i)); } <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; }; ``` ``` **復雜度分析** - 時間復雜度:O(logN)O(logN)O(logN) - 空間復雜度:O(logN)O(logN)O(logN) C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isUgly</span><span class="hljs-params">(<span class="hljs-keyword">int</span> num)</span> </span>{ <span class="hljs-keyword">int</span> ugly[] = {<span class="hljs-params">2</span>,<span class="hljs-params">3</span>,<span class="hljs-params">5</span>}; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> u : ugly) { <span class="hljs-keyword">while</span>(num%u==<span class="hljs-params">0</span> && num%u < num) { num/=u; } } <span class="hljs-keyword">return</span> num == <span class="hljs-params">1</span>; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isUgly</span><span class="hljs-params">(<span class="hljs-keyword">int</span> num)</span> </span>{ <span class="hljs-keyword">int</span> [] ugly = {<span class="hljs-params">2</span>,<span class="hljs-params">3</span>,<span class="hljs-params">5</span>}; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> u : ugly) { <span class="hljs-keyword">while</span>(num%u==<span class="hljs-params">0</span> && num%u < num) { num/=u; } } <span class="hljs-keyword">return</span> num == <span class="hljs-params">1</span>; } } ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># 非遞歸寫法</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isUgly</span><span class="hljs-params">(self, num: int)</span> -> bool:</span> <span class="hljs-keyword">if</span> num <= <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> (<span class="hljs-params">2</span>, <span class="hljs-params">3</span>, <span class="hljs-params">5</span>): <span class="hljs-keyword">while</span> num % i == <span class="hljs-params">0</span>: num /= i <span class="hljs-keyword">return</span> num == <span class="hljs-params">1</span> ``` ``` **復雜度分析** - 時間復雜度:O(logN)O(logN)O(logN) - 空間復雜度:O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看