current position：Home>leetcode 1829. Maximum XOR for Each Query（python）
leetcode 1829. Maximum XOR for Each Query（python）
20220129 17:11:05 【Wang Daya】
This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .
describe
You are given a sorted array nums of n nonnegative integers and an integer maximumBit. You want to perform the following query n times:
Find a nonnegative integer k < 2^{maximumBit} such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length1] XOR k is maximized. k is the answer to the i^{th} query. Remove the last element from the current array nums. Return an array answer, where answer[i] is the answer to the i^{th} query.
Example 1:
Input: nums = [0,1,1,3], maximumBit = 2
Output: [0,3,2,3]
Explanation: The queries are answered as follows:
1st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
2nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.
3rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.
4th query: nums = [0], k = 3 since 0 XOR 3 = 3.
Copy code
Example 2:
Input: nums = [2,3,4,7], maximumBit = 3
Output: [5,2,6,5]
Explanation: The queries are answered as follows:
1st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
2nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.
3rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.
4th query: nums = [2], k = 5 since 2 XOR 5 = 7.
Copy code
Example 3:
Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]
Copy code
Note:
nums.length == n
1 <= n <= 10^5
1 <= maximumBit <= 20
0 <= nums[i] < 2^maximumBit
nums is sorted in ascending order.
Copy code
analysis
According to the meaning , Is to give a sorted length of n A list of integers nums , And gives an integer maximumBit, Let's take the following steps ：
 Before the 1 An element performs an operation , and [0, 2^ maximumBit1] An integer or operation between can ensure the maximum result , Add this integer to the result list
 Before the 2 An element performs an operation , and [0, 2^ maximumBit1] An integer or operation between can ensure the maximum result , Add this integer to the result list
 Before the 3 An element performs an operation , and [0, 2^ maximumBit1] An integer or operation between can ensure the maximum result , Add this integer to the result list
 ......
 front n An element performs an operation , and [0, 2^ maximumBit1] An integer or operation between can ensure the maximum result , Add this integer to the result list
Finally, return the result list .
The most direct way is to solve by violence , First solve all the elements before each position or the result , Then double loop to find the most suitable... For each position [0, 2^ maximumBit1] Integer results between . But the result timed out . Because in the title n and maximumBit It's big .
answer
class Solution(object):
def getMaximumXor(self, nums, maximumBit):
"""
:type nums: List[int]
:type maximumBit: int
:rtype: List[int]
"""
XORS = [nums[0]]
for i,num in enumerate(nums[1:]):
XORS.append(XORS[1] ^ num)
result = [0]*len(nums)
for i,num in enumerate(XORS):
tmp = num ^ 0
for bit in range(1, 2**maximumBit):
if num^bit > tmp:
tmp = num^bit
result[i] = bit
return result[::1]
Copy code
Running results
Time Limit Exceeded
Copy code
analysis
In fact, this is a question of investigation or operation , To solve a problem, you need to know two key knowledge points ：
 No matter how many [0, 2^maximumBit1] The numbers in this range are or calculated , The biggest result can only be 2^maximumBit 1
 If x ^ y == z, that x ^ z == y, meanwhile y ^ z == x
Combined with the meaning of the question, we can get :
 nums Each element in the satisfies 0 <= nums[i] < 2^maximumBit
 k The value must meet or the maximum result is (2^maximumBit1), therefore nums[0] ^ nums[1] ^ ... ^ nums[nums.length1] ^ k == (2^maximumBit1), that k == nums[0] ^ nums[1] ^ ... ^ nums[nums.length1] ^ (2^maximumBit1)
answer
class Solution(object):
def getMaximumXor(self, nums, maximumBit):
"""
:type nums: List[int]
:type maximumBit: int
:rtype: List[int]
"""
ALL = 0
for num in nums: ALL ^= num
maxresult = 2**maximumBit1
result = []
while nums:
result.append(ALL ^ maxresult)
ALL ^= nums.pop()
return result
Copy code
Running results
Runtime: 1113 ms, faster than 25.93% of Python online submissions for Maximum XOR for Each Query.
Memory Usage: 29.1 MB, less than 81.48% of Python online submissions for Maximum XOR for Each Query.
Copy code
Original link ：leetcode.com/problems/ma…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201291711028304.html
The sidebar is recommended
 [Python introduction project] use Python to generate QR code
 Compile D + +, and use d to call C from python
 Quickly build Django blog based on function calculation
 Python collects and monitors system data  psutil
 Finally, this Python import guide has been sorted out. Look!
 Quickly build Django blog based on function calculation
 Python interface test unittest usage details
 Implementation of toplevel design pattern in Python
 You can easily get started with Excel. Python data analysis package pandas (VII): breakdown
 Python simulation random coin toss (non optimized version)
guess what you like

Python tiktok 5000+ V, and found that everyone love this video.

Using linear systems in python with scipy.linalg

Using linear systems in python with scipy.linalg

Together with Python to do a license plate automatic recognition system, fun and practical!

You can easily get started with Excel. Python data analysis package pandas (XI): segment matching

Advanced practical case: Javascript confusion of Python anti crawling

Using linear systems in python with scipy.linalg

Fast power modulus Python implementation of large numbers

Quickly build Django blog based on function calculation

This paper clarifies the chaotic switching operation and elegant derivation of Python
Random recommended
 You can easily get started with Excel pandas (I): filtering function
 You can easily get started with Excel. Python data analysis package pandas (II): advanced filtering (I)
 You can easily get started with Excel. Python data analysis package pandas (2): advanced filtering (2)
 You can easily get started with Excel. Python data analysis package pandas (3): making score bar
 Test Development: self study Dubbo + Python experience summary and sharing
 You can easily get started with Excel. Python data analysis package pandas (V): duplicate value processing
 How does Python correctly call jar package encryption to get the encrypted value?
 Python 3 interview question: give an array. If there is 0 in the array, add a 0 after 0, and the overall array length remains the same
 Python simple Snake game (single player mode)
 Using linear systems in python with scipy.linalg
 Python executes functions and even code through strings! Come and understand the operation of such a top!
 Decoding the verification code of Taobao slider with Python + selenium, the road of information security
 [Python introduction project] use Python to generate QR code
 Vanessa basks in her photos and gets caught up in the golden python. There are highlights in the accompanying text. She can't forget Kobe after all
 [windows] Python installation pyteseract
 [introduction to Python project] create bar chart animation in Python
 Fundamentals of Python I
 Python series tutorials 116
 Python code reading (chapter 35): fully (deeply) expand nested lists
 Practical series 1 ️⃣ Wechat applet automatic testing practice (with Python source code)
 Python Basics: do you know how to use lists?
 Solution of no Python 3.9 installation was detected when uninstalling Python
 [Python homework] coupling network information dissemination
 [common links of Python & Python]
 Python application software development tool  tkinterdesigner v1.0 5.1 release!
 [Python development tool tkinterdiesigner]: example: develop stock monitoring alarm using Tkinter desinger
 [Python development tool Tkinter designer]: Lecture 2: introduction to Tkinter designer's example project
 [Python development tool Tkinter designer]: Lecture 1: introduction to the basic functions of Tkinter Designer
 [introduction to Python tutorial] use Python 3 to teach you how to extract any HTML main content
 Python socket implements UDP server and client
 Python socket implements TCP server and client
 leetcode 1261. Find Elements in a Contaminated Binary Tree（python）
 [algorithm learning] 1486 Array XOR operation (Java / C / C + + / Python / go / trust)
 leetcode 1974. Minimum Time to Type Word Using Special Typewriter（python）
 The mobile phone uses Python to operate picture files
 [learning notes] Python exception handling try except...
 Two methods of using pandas to read poorly structured excel. You're welcome to take them away
 Python sum (): the summation method of Python
 Practical experience sharing: use pyo3 to build your Python module
 Using Python to realize multitasking process