1 Star 41 Fork 18

小墨/力扣题库(完整版)

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
count-the-number-of-substrings-with-dominant-ones.html 2.64 KB
一键复制 编辑 原始数据 按行查看 历史
zhangbk1 提交于 2024-08-06 08:46 +08:00 . update
<p>You are given a binary string <code>s</code>.</p>
<p>Return the number of <span data-keyword="substring-nonempty">substrings</span> with <strong>dominant</strong> ones.</p>
<p>A string has <strong>dominant</strong> ones if the number of ones in the string is <strong>greater than or equal to</strong> the <strong>square</strong> of the number of zeros in the string.</p>
<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;00011&quot;</span></p>
<p><strong>Output:</strong> <span class="example-io">5</span></p>
<p><strong>Explanation:</strong></p>
<p>The substrings with dominant ones are shown in the table below.</p>
</div>
<table>
<thead>
<tr>
<th>i</th>
<th>j</th>
<th>s[i..j]</th>
<th>Number of Zeros</th>
<th>Number of Ones</th>
</tr>
</thead>
<tbody>
<tr>
<td>3</td>
<td>3</td>
<td>1</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>4</td>
<td>4</td>
<td>1</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>2</td>
<td>3</td>
<td>01</td>
<td>1</td>
<td>1</td>
</tr>
<tr>
<td>3</td>
<td>4</td>
<td>11</td>
<td>0</td>
<td>2</td>
</tr>
<tr>
<td>2</td>
<td>4</td>
<td>011</td>
<td>1</td>
<td>2</td>
</tr>
</tbody>
</table>
<p><strong class="example">Example 2:</strong></p>
<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;101101&quot;</span></p>
<p><strong>Output:</strong> <span class="example-io">16</span></p>
<p><strong>Explanation:</strong></p>
<p>The substrings with <strong>non-dominant</strong> ones are shown in the table below.</p>
<p>Since there are 21 substrings total and 5 of them have non-dominant ones, it follows that there are 16 substrings with dominant ones.</p>
</div>
<table>
<thead>
<tr>
<th>i</th>
<th>j</th>
<th>s[i..j]</th>
<th>Number of Zeros</th>
<th>Number of Ones</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>1</td>
<td>0</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>4</td>
<td>4</td>
<td>0</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>4</td>
<td>0110</td>
<td>2</td>
<td>2</td>
</tr>
<tr>
<td>0</td>
<td>4</td>
<td>10110</td>
<td>2</td>
<td>3</td>
</tr>
<tr>
<td>1</td>
<td>5</td>
<td>01101</td>
<td>2</td>
<td>3</td>
</tr>
</tbody>
</table>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 &lt;= s.length &lt;= 4 * 10<sup>4</sup></code></li>
<li><code>s</code> consists only of characters <code>&#39;0&#39;</code> and <code>&#39;1&#39;</code>.</li>
</ul>
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/coder-xiaomo/leetcode-problemset.git
git@gitee.com:coder-xiaomo/leetcode-problemset.git
coder-xiaomo
leetcode-problemset
力扣题库(完整版)
master

搜索帮助