mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
95 lines
3.3 KiB
HTML
95 lines
3.3 KiB
HTML
<p>You are given an array <code>nums</code> of <code>n</code> integers, and a 2D integer array <code>queries</code> of size <code>q</code>, where <code>queries[i] = [l<sub>i</sub>, r<sub>i</sub>]</code>.</p>
|
|
|
|
<p>For each query, you must find the <strong>maximum XOR score</strong> of any <span data-keyword="subarray">subarray</span> of <code>nums[l<sub>i</sub>..r<sub>i</sub>]</code>.</p>
|
|
|
|
<p>The <strong>XOR score</strong> of an array <code>a</code> is found by repeatedly applying the following operations on <code>a</code> so that only one element remains, that is the <strong>score</strong>:</p>
|
|
|
|
<ul>
|
|
<li>Simultaneously replace <code>a[i]</code> with <code>a[i] XOR a[i + 1]</code> for all indices <code>i</code> except the last one.</li>
|
|
<li>Remove the last element of <code>a</code>.</li>
|
|
</ul>
|
|
|
|
<p>Return an array <code>answer</code> of size <code>q</code> where <code>answer[i]</code> is the answer to query <code>i</code>.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[12,60,60]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>In the first query, <code>nums[0..2]</code> has 6 subarrays <code>[2]</code>, <code>[8]</code>, <code>[4]</code>, <code>[2, 8]</code>, <code>[8, 4]</code>, and <code>[2, 8, 4]</code> each with a respective XOR score of 2, 8, 4, 10, 12, and 6. The answer for the query is 12, the largest of all XOR scores.</p>
|
|
|
|
<p>In the second query, the subarray of <code>nums[1..4]</code> with the largest XOR score is <code>nums[1..4]</code> with a score of 60.</p>
|
|
|
|
<p>In the third query, the subarray of <code>nums[0..5]</code> with the largest XOR score is <code>nums[1..4]</code> with a score of 60.</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[7,14,11,14,5]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<table height="70" width="472">
|
|
<thead>
|
|
<tr>
|
|
<th>Index</th>
|
|
<th>nums[l<sub>i</sub>..r<sub>i</sub>]</th>
|
|
<th>Maximum XOR Score Subarray</th>
|
|
<th>Maximum Subarray XOR Score</th>
|
|
</tr>
|
|
</thead>
|
|
<tbody>
|
|
<tr>
|
|
<td>0</td>
|
|
<td>[0, 7, 3, 2]</td>
|
|
<td>[7]</td>
|
|
<td>7</td>
|
|
</tr>
|
|
<tr>
|
|
<td>1</td>
|
|
<td>[7, 3, 2, 8, 5]</td>
|
|
<td>[7, 3, 2, 8]</td>
|
|
<td>14</td>
|
|
</tr>
|
|
<tr>
|
|
<td>2</td>
|
|
<td>[3, 2, 8]</td>
|
|
<td>[3, 2, 8]</td>
|
|
<td>11</td>
|
|
</tr>
|
|
<tr>
|
|
<td>3</td>
|
|
<td>[3, 2, 8, 5, 1]</td>
|
|
<td>[2, 8, 5, 1]</td>
|
|
<td>14</td>
|
|
</tr>
|
|
<tr>
|
|
<td>4</td>
|
|
<td>[5, 1]</td>
|
|
<td>[5]</td>
|
|
<td>5</td>
|
|
</tr>
|
|
</tbody>
|
|
</table>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= n == nums.length <= 2000</code></li>
|
|
<li><code>0 <= nums[i] <= 2<sup>31</sup> - 1</code></li>
|
|
<li><code>1 <= q == queries.length <= 10<sup>5</sup></code></li>
|
|
<li><code>queries[i].length == 2 </code></li>
|
|
<li><code>queries[i] = [l<sub>i</sub>, r<sub>i</sub>]</code></li>
|
|
<li><code>0 <= l<sub>i</sub> <= r<sub>i</sub> <= n - 1</code></li>
|
|
</ul>
|