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

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 1371.每個元音包含偶數次的最長子字符串 # 題目地址(1371. 每個元音包含偶數次的最長子字符串) <https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個字符串 s ,請你返回滿足以下條件的最長子字符串的長度:每個元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出現了偶數次。 示例 1: 輸入:s = "eleetminicoworoep" 輸出:13 解釋:最長子字符串是 "leetminicowor" ,它包含 e,i,o 各 2 個,以及 0 個 a,u 。 示例 2: 輸入:s = "leetcodeisgreat" 輸出:5 解釋:最長子字符串是 "leetc" ,其中包含 2 個 e 。 示例 3: 輸入:s = "bcbcbc" 輸出:6 解釋:這個示例中,字符串 "bcbcbc" 本身就是最長的,因為所有的元音 a,e,i,o,u 都出現了 0 次。 提示: 1 <= s.length <= 5 x 10^5 s 只包含小寫英文字母。 ``` ``` ## 前置知識 - 前綴和 - 狀態壓縮 ## 暴力法 + 剪枝 ## 公司 - 暫無 ### 思路 首先拿到這道題的時候,我想到第一反應是滑動窗口行不行。 但是很快這個想法就被我否定了,因為滑動窗口(這里是可變滑動窗口)我們需要擴張和收縮窗口大小,而這里不那么容易。因為題目要求的是奇偶性,而不是類似“元音出現最多的子串”等。 突然一下子沒了思路。那就試試暴力法吧。暴力法的思路比較樸素和直觀。 那就是`雙層循環找到所有子串,然后對于每一個子串,統計元音個數,如果子串的元音個數都是偶數,則更新答案,最后返回最大的滿足條件的子串長度即可`。 這里我用了一個小的 trick。枚舉所有子串的時候,我是從最長的子串開始枚舉的,這樣我找到一個滿足條件的直接返回就行了(early return),不必維護最大值。`這樣不僅減少了代碼量,還提高了效率。` ### 代碼 代碼支持:Python3 Python3 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">def</span> <span class="hljs-title">findTheLongestSubstring</span><span class="hljs-params">(self, s: str)</span> -> int:</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(s), <span class="hljs-params">0</span>, <span class="hljs-params">-1</span>): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(len(s) - i + <span class="hljs-params">1</span>): sub = s[j:j + i] has_odd_vowel = <span class="hljs-keyword">False</span> <span class="hljs-keyword">for</span> vowel <span class="hljs-keyword">in</span> [<span class="hljs-string">'a'</span>, <span class="hljs-string">'e'</span>, <span class="hljs-string">'i'</span>, <span class="hljs-string">'o'</span>, <span class="hljs-string">'u'</span>]: <span class="hljs-keyword">if</span> sub.count(vowel) % <span class="hljs-params">2</span> != <span class="hljs-params">0</span>: has_odd_vowel = <span class="hljs-keyword">True</span> <span class="hljs-keyword">break</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> has_odd_vowel: <span class="hljs-keyword">return</span> i <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> ``` ``` **復雜度分析** - 時間復雜度:雙層循環找出所有子串的復雜度是O(n2)O(n^2)O(n2),統計元音個數復雜度也是O(n)O(n)O(n),因此這種算法的時間復雜度為O(n3)O(n^3)O(n3)。 - 空間復雜度:O(1)O(1)O(1) ## 前綴和 + 剪枝 ### 思路 上面思路中`對于每一個子串,統計元音個數`,我們仔細觀察的話,會發現有很多重復的統計。那么優化這部分的內容就可以獲得更好的效率。 對于這種連續的數字問題,這里我們考慮使用[前綴和](https://oi-wiki.org/basic/prefix-sum/)來優化。 經過這種空間換時間的策略之后,我們的時間復雜度會降低到O(n2)O(n ^ 2)O(n2),但是相應空間復雜度會上升到O(n)O(n)O(n),這種取舍在很多情況下是值得的。 ### 代碼 代碼支持:Python3,Java Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> i_mapper = { <span class="hljs-string">"a"</span>: <span class="hljs-params">0</span>, <span class="hljs-string">"e"</span>: <span class="hljs-params">1</span>, <span class="hljs-string">"i"</span>: <span class="hljs-params">2</span>, <span class="hljs-string">"o"</span>: <span class="hljs-params">3</span>, <span class="hljs-string">"u"</span>: <span class="hljs-params">4</span> } <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">check</span><span class="hljs-params">(self, s, pre, l, r)</span>:</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">5</span>): <span class="hljs-keyword">if</span> s[l] <span class="hljs-keyword">in</span> self.i_mapper <span class="hljs-keyword">and</span> i == self.i_mapper[s[l]]: cnt = <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: cnt = <span class="hljs-params">0</span> <span class="hljs-keyword">if</span> (pre[r][i] - pre[l][i] + cnt) % <span class="hljs-params">2</span> != <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findTheLongestSubstring</span><span class="hljs-params">(self, s: str)</span> -> int:</span> n = len(s) pre = [[<span class="hljs-params">0</span>] * <span class="hljs-params">5</span> <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n)] <span class="hljs-title"># pre</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-params">5</span>): <span class="hljs-keyword">if</span> s[i] <span class="hljs-keyword">in</span> self.i_mapper <span class="hljs-keyword">and</span> self.i_mapper[s[i]] == j: pre[i][j] = pre[i - <span class="hljs-params">1</span>][j] + <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: pre[i][j] = pre[i - <span class="hljs-params">1</span>][j] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - <span class="hljs-params">1</span>, <span class="hljs-params">-1</span>, <span class="hljs-params">-1</span>): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n - i): <span class="hljs-keyword">if</span> self.check(s, pre, j, i + j): <span class="hljs-keyword">return</span> i + <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> <span class="hljs-params">0</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">int</span> <span class="hljs-title">findTheLongestSubstring</span><span class="hljs-params">(String s)</span> </span>{ <span class="hljs-keyword">int</span> len = s.length(); <span class="hljs-keyword">if</span> (len == <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span>[][] preSum = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[len][<span class="hljs-params">5</span>]; <span class="hljs-keyword">int</span> start = getIndex(s.charAt(<span class="hljs-params">0</span>)); <span class="hljs-keyword">if</span> (start != -<span class="hljs-params">1</span>) preSum[<span class="hljs-params">0</span>][start]++; <span class="hljs-title">// preSum</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">1</span>; i < len; i++) { <span class="hljs-keyword">int</span> idx = getIndex(s.charAt(i)); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-params">0</span>; j < <span class="hljs-params">5</span>; j++) { <span class="hljs-keyword">if</span> (idx == j) preSum[i][j] = preSum[i - <span class="hljs-params">1</span>][j] + <span class="hljs-params">1</span>; <span class="hljs-keyword">else</span> preSum[i][j] = preSum[i - <span class="hljs-params">1</span>][j]; } } <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = len - <span class="hljs-params">1</span>; i >= <span class="hljs-params">0</span>; i--) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-params">0</span>; j < len - i; j++) { <span class="hljs-keyword">if</span> (checkValid(preSum, s, j, i + j)) <span class="hljs-keyword">return</span> i + <span class="hljs-params">1</span>; } } <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; } <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">checkValid</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[][] preSum, String s, <span class="hljs-keyword">int</span> left, <span class="hljs-keyword">int</span> right)</span> </span>{ <span class="hljs-keyword">int</span> idx = getIndex(s.charAt(left)); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>; i < <span class="hljs-params">5</span>; i++) <span class="hljs-keyword">if</span> (((preSum[right][i] - preSum[left][i] + (idx == i ? <span class="hljs-params">1</span> : <span class="hljs-params">0</span>)) & <span class="hljs-params">1</span>) == <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; } <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getIndex</span><span class="hljs-params">(<span class="hljs-keyword">char</span> ch)</span> </span>{ <span class="hljs-keyword">if</span> (ch == <span class="hljs-string">'a'</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (ch == <span class="hljs-string">'e'</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">1</span>; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (ch == <span class="hljs-string">'i'</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">2</span>; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (ch == <span class="hljs-string">'o'</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">3</span>; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (ch == <span class="hljs-string">'u'</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">4</span>; <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> -<span class="hljs-params">1</span>; } } ``` ``` **復雜度分析** - 時間復雜度:O(n2)O(n^2)O(n2)。 - 空間復雜度:O(n)O(n)O(n) ## 前綴和 + 狀態壓縮 ### 思路 前面的前綴和思路,我們通過空間(prefix)換取時間的方式降低了時間復雜度。但是時間復雜度仍然是平方,我們是否可以繼續優化呢? 實際上由于我們只關心奇偶性,并不關心每一個元音字母具體出現的次數。因此我們可以使用`是奇數,是偶數`兩個狀態來表示,由于只有兩個狀態,我們考慮使用位運算。 我們使用 5 位的二進制來表示以 i 結尾的字符串中包含各個元音的奇偶性,其中 0 表示偶數,1 表示奇數,并且最低位表示 a,然后依次是 e,i,o,u。比如 `10110` 則表示的是包含偶數個 a 和 o,奇數個 e,i,u,我們用變量 `cur` 來表示。 為什么用 0 表示偶數?1 表示奇數? 回答這個問題,你需要繼續往下看。 其實這個解法還用到了一個性質,這個性質是小學數學知識: - 如果兩個數字奇偶性相同,那么其相減一定是偶數。 - 如果兩個數字奇偶性不同,那么其相減一定是奇數。 看到這里,我們再來看上面拋出的問題`為什么用 0 表示偶數?1 表示奇數?`。因為這里我們打算用異或運算,而異或的性質是: 如果對兩個二進制做異或,會對其每一位進行位運算,如果相同則位 0,否則位 1。這和上面的性質非常相似。上面說`奇偶性相同則位偶數,否則為奇數`。因此很自然地`用 0 表示偶數?1 表示奇數`會更加方便。 ### 代碼 代碼支持:Python3 Python3 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">def</span> <span class="hljs-title">findTheLongestSubstring</span><span class="hljs-params">(self, s: str)</span> -> int:</span> mapper = { <span class="hljs-string">"a"</span>: <span class="hljs-params">1</span>, <span class="hljs-string">"e"</span>: <span class="hljs-params">2</span>, <span class="hljs-string">"i"</span>: <span class="hljs-params">4</span>, <span class="hljs-string">"o"</span>: <span class="hljs-params">8</span>, <span class="hljs-string">"u"</span>: <span class="hljs-params">16</span> } seen = {<span class="hljs-params">0</span>: <span class="hljs-params">-1</span>} res = cur = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(s)): <span class="hljs-keyword">if</span> s[i] <span class="hljs-keyword">in</span> mapper: cur ^= mapper.get(s[i]) <span class="hljs-title"># 全部奇偶性都相同,相減一定都是偶數</span> <span class="hljs-keyword">if</span> cur <span class="hljs-keyword">in</span> seen: res = max(res, i - seen.get(cur)) <span class="hljs-keyword">else</span>: seen[cur] = i <span class="hljs-keyword">return</span> res ``` ``` **復雜度分析** - 時間復雜度:O(n)O(n)O(n)。 - 空間復雜度:O(n)O(n)O(n) ## 關鍵點解析 - 前綴和 - 狀態壓縮 ## 相關題目 - [掌握前綴表達式真的可以為所欲為!](https://lucifer.ren/blog/2020/01/09/1310.xor-queries-of-a-subarray/)
                  <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>

                              哎呀哎呀视频在线观看