首页　>　文章列表　>　使用C++实现将数组转换为回文数组时，最小化配对的异或值

使用C++实现将数组转换为回文数组时，最小化配对的异或值

数组转换回文化异或最小化配对
286 2023-09-03

在计算机科学领域中，高效地解决优化问题对于开发最佳算法和系统至关重要。其中一个问题是通过最小化数组中的成对XOR（异或）操作使其成为回文。这种情况具有重要意义，因为它提供了确定在数组中重新排序项目的最佳方法的机会，这可以导致较低的XOR值和回文的创建。本文介绍了两种利用C++编程语言解决这个问题的方法。

Syntax

To begin with, let's define the syntax of the function we will be using in the following code examples −

int minimizeXORToPalindrome(int arr[], int n);

算法

The algorithm we will be using aims to minimize the XOR of pairs in the array to transform it into a palindrome. Here are the general steps −

Sort the array in non-decreasing order.
初始化两个指针，left和right，分别指向数组的第一个和最后一个元素。
初始化一个变量，xorSum，用于存储一对数的异或和。
While left is less than or equal to right, do the following −
Calculate the XOR of the elements at left and right, and add it to xorSum.
向左移动一步向前，向右移动一步向后。
返回 xorSum。

方法一：反转和异或

第一种方法涉及将数组反转并异或相应的元素以最小化异或值。

Example

#include <algorithm>
#include <iostream>

int minimizeXORToPalindrome(int arr[], int n) {
   std::sort(arr, arr + n);  // Step 1: Sort the array
   int xorSum = 0;
   int left = 0, right = n - 1;
    
   while (left <= right) {
      xorSum += arr[left] ^ arr[right];  // Step 4: XOR the elements
      left++;
      right--;
   }
    
   return xorSum;  // Step 5: Return the XOR sum
}

int main() {
   int arr[] = {5, 3, 8, 6, 2};
   int n = sizeof(arr) / sizeof(arr[0]);
    
   int result = minimizeXORToPalindrome(arr, n);
   std::cout << "Minimized XOR value to make the array palindrome: " << result << std::endl;
    
   return 0;
}

输出

Minimized XOR value to make the array palindrome: 15

Explanation

的中文翻译为：

解释

minimizeXORToPalindrome函数以一个数组（arr）和它的大小（n）作为输入。

在函数内部，我们首先使用std::sort(arr, arr + n)按非递减顺序对数组进行排序。这是算法的第一步。

最初，让我们将变量xorSum设置为零，因为它的功能将在后面存储异或和。

Additionally, two new variables named left and right are defined such that they respectively point towards the first and last element in our input array.

Finally, as long as an input condition states that left should be lesser than or equal to right; it keeps executing iteratively using a while statement within its body block.

Inside the loop, we calculate the XOR of the elements at left and right using the ^ operator and add it to xorSum. This is step 4 of the algorithm.

We increment left by one and decrement right by one to move closer towards the center of the array.

一旦左边大于右边，while循环退出。

最后，我们返回xorSum，它代表了使数组成为回文的最小XOR值。

In the main function, we provide an example usage of the minimizeXORToPalindrome function −

我们创建一个数组arr，其值为{5, 3, 8, 6, 2}。
We calculate the size of the array (n) using the sizeof operator.
We call the minimizeXORToPalindrome function, passing the array and its size as arguments, and store the result in the result variable.
最后，我们打印最小化的XOR值，使数组成为回文。

方法二：高效配对

The second approach focuses on pairing the elements in an efficient way to minimize the XOR value.

Example

#include <algorithm>
#include <iostream>  // Include the <iostream> header for std::cout and std::endl
#include <ostream>   // Include the <ostream> header for std::endl

int minimizeXORToPalindrome(int arr[], int n) {
   std::sort(arr, arr + n);  // Step 1: Sort the array
   int xorSum = 0;
    
   for (int i = 0; i < n / 2; i++) {
      xorSum += arr[i] ^ arr[n - 1 - i];  // Step 4: XOR the elements
   }
    
   return xorSum;  // Step 5: Return the XOR sum
}

int main() {
   int arr[] = {5, 3, 8, 6, 2};
   int n = sizeof(arr) / sizeof(arr[0]);
    
   int result = minimizeXORToPalindrome(arr, n);
   std::cout << "Minimized XOR value to make the array palindrome: " << result << std::endl;
    
   return 0;
}

输出

Minimized XOR value to make the array palindrome: 15

Explanation

的中文翻译为：

解释

minimizeXORToPalindrome函数以一个数组（arr）和它的大小（n）作为输入。

在函数内部，我们首先使用std::sort(arr, arr + n)按非递减顺序对数组进行排序。这是算法的第一步。

我们首先设置xorSum变量，并将其赋值为零。值得注意的是，这个变量在存储所有XOR和对中起着关键作用。

Next up is utilizing a for loop that cycles through half of our total array size -from index 0 up until n/2-1.

Within this loop lies Step four where we proceed with calculating XOR values between arr[i] (ith element from start) and arr[n-1-i] (ith value starting from endpoint).

我们将这个XOR值添加到xorSum中。

一旦循环完成，我们就有效地将所有元素配对，以最小化XOR值。

最后，我们返回xorSum，它代表了使数组成为回文的最小XOR值。

我们呈现的代码展示了对minimizeXORToPalindrome功能的有效利用，类似于之前迭代中展示的先前示例。

我们的过程始于在主方法操作中创建一个数组，并结合大小计算，进一步通过minimizseXORTOPalindrome的调用来突显。

We conclude with feedback conveying most efficient negotiated XOR level necessary for converting original set elements into palindromically structured configurations