<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>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 1015. 可被 K 整除的最小整數 ## 題目地址(1015. 可被 K 整除的最小整數) <https://leetcode-cn.com/problems/smallest-integer-divisible-by-k/> ## 題目描述 ``` <pre class="calibre18">``` 給定正整數 K,你需要找出可以被 K 整除的、僅包含數字 1 的最小正整數 N。 返回 N 的長度。如果不存在這樣的 N,就返回 -1。 示例 1: 輸入:1 輸出:1 解釋:最小的答案是 N = 1,其長度為 1。 示例 2: 輸入:2 輸出:-1 解釋:不存在可被 2 整除的正整數 N 。 示例 3: 輸入:3 輸出:3 解釋:最小的答案是 N = 111,其長度為 3。 提示: 1 <= K <= 10^5 ``` ``` ## 前置知識 - 循環節 ## 公司 - 暫無 ## 思路 這道題是說給定一個 K 值,能否找到一個形如 1,11,111,1111 。。。 這樣的數字 n 使得 n % K == 0。 首先容易想到的是如果 K 是 2,4,5, 6,8 結尾的話,一定是不行的。直觀的解法是從 1,11,111,1111 。。。 這樣一直除下去,直到碰到可以整除的,我們返回即可。 但是如果這個數字根本就無法整除怎么辦?沒錯,我們會無限循環下去。我們應該在什么時刻跳出循環,返回 - 1 (表示不能整除)呢? 我們拿題目給出的不能整除的 2 來說。 - 1 // 2 等于 1 - 11 // 2 等于 1 - 111 // 2 等于 1 - ... 我們再來一個不能整除的例子 6: - 1 // 6 等于 1 - 11 // 6 等于 5 - 111 // 6 等于 3 - 1111 // 6 等于 1 - 11111 // 6 等于 5 - ... 通過觀察我們發現不斷整除的過程,會陷入無限循環,對于 2 來說,其循環節就是 1。對于 6 來說,其循環節來說就是 153。而且由于我們的分母是 6,也就是說余數的可能性一共只有六種情況 0,1,2,3,4,5。 上面是感性的認識, 接下來我們從數學上予以證明。上面的算法用公式來表示就是`mod = (10 \* mod + 1) % K`。假如出現了相同的數,我們可以肯定之后會無限循環。比如 153 之后出現了 1,我們可以肯定之后一定是 35。。。 因為我們的 mod 只是和前一個 mod 有關,上面的公式是一個`純函數`。 ## 關鍵點解析 - 數學(無限循環與循環節) ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">#</span> <span class="hljs-title"># @lc app=leetcode.cn id=1015 lang=python3</span> <span class="hljs-title">#</span> <span class="hljs-title"># [1015] 可被 K 整除的最小整數</span> <span class="hljs-title">#</span> <span class="hljs-title"># @lc code=start</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">smallestRepunitDivByK</span><span class="hljs-params">(self, K: int)</span> -> int:</span> <span class="hljs-keyword">if</span> K % <span class="hljs-params">10</span> <span class="hljs-keyword">in</span> [<span class="hljs-params">2</span>, <span class="hljs-params">4</span>, <span class="hljs-params">5</span>, <span class="hljs-params">6</span>, <span class="hljs-params">8</span>]: <span class="hljs-keyword">return</span> - <span class="hljs-params">1</span> seen = set() mod = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, K + <span class="hljs-params">1</span>): mod = (mod * <span class="hljs-params">10</span> + <span class="hljs-params">1</span>) % K <span class="hljs-keyword">if</span> mod <span class="hljs-keyword">in</span> seen: <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span> <span class="hljs-keyword">if</span> mod == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> ix seen.add(mod) ``` ``` ## 相關題目 - [166. 分數到小數](https://leetcode-cn.com/problems/fraction-to-recurring-decimal/)
                  <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>

                              哎呀哎呀视频在线观看