Java 程序在经过 K 次循环移位后将给定数组分成两半,然后使用按位或运算查找数组总和

javaobject oriented programmingprogramming更新于 2024/3/9 1:48:17

数组是一组单一的非原始类似数据类型(值或变量),将元素存储在具有固定数量值的内存中。在创建具有某些元素的数组后,此数据集的长度将固定。这里的非原始意味着,这些数据类型可用于调用方法来执行字符可以为空的特定操作。这里的按位和意味着,具有恰好 2 位设置的某些数字的总和。按位或表示每个整数都存在于子数组中。它是数组中存在的相邻非空元素序列。在数组的排序操作中,有一个半元的概念。在这种方法中,如果有可能对数组进行除法,则整个概念将返回真值。

在本文中,我们将学习如何在执行 K 次循环移位方法后将特定数组分成两半,然后使用按位或运算找到数组的总和。

通过执行 K 次循环移位对整数进行二进制表示

数据结构中的循环移位是什么?

在数据结构中,元素的按位旋转称为循环移位,它不会保存特定数字的符号位。对于循环移位,有两种类型的移位方法

  • 常规左移 - 这是一个乘以 2(mod 2^N)的过程。这里,N 是整数类型的特定位

  • 循环左移 - 这是位数的乘法方法。其中乘法可以通过方法 2(mod (2^N - 1)) 完成。

现在,我们假设列表中有两个正整数。通过执行循环方法,我们必须通过二进制表示交换这两个元素的位置。

  • 左循环移位

    • 最后一位将移动到第一个位置。

    • 将所有其他位移到下一个位置。

  • 右循环移位:

    • 将第一位移到最后一位。

    • 将剩余位移到前一位。

数据结构中的 K 循环移位是什么?

假设一个长度为 N 的数组 A[]。这里 N 是偶数。如果 Q 是这里的查询,K 是正数的表示。如果我们对该数组应用循环移位,则这些特定元素的总和将通过对半数组进行按位或运算来执行。

输入:A[] = {12, 23, 4, 21, 22, 76}, Q = 1, K = 2
输出:117

循环移位算法:-

  • 步骤 1 − 为该数组构建一个线段树。

  • 步骤 2 − 分配一个输入变量,i= K%(N/2)。

  • 步骤 3 − 然后,使用该构建树获取按位或的值。

  • 步骤 4 − 第一个元素将是 (N/2)-i-1 个元素。

  • 步骤5 − 使用 [(N/2)-i 和 N-i-1] 计算按位或范围。

  • 步骤 6 − 将两个结果相加,得到第 i 个数字查询的答案。

使用循环链表执行循环移位的语法:-

struct Node {
int data;
struct Node * next;
};

/* 节点初始化 */
struct node *last;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
struct node *four = NULL;
struct node *five = NULL;
struct node *six = NULL;

/* 使用 malloc 函数分配内存 */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
four = malloc(sizeof(struct node));
five = malloc(sizeof(struct node));
six = malloc(sizeof(struct node));

/* 在列表中分配一些数据值 */
one->data = 1;
two->data = 2;
three->data = 3;
four->data = 4;
five->data = 5;
six->data = 6;

/* 用指针连接节点 */
one->next = two;
two->next = three;
three->next = four;
four->next = five;
five->next = six;
six->next = one;

/* 在最后一个位置保存第六个节点的地址 */
last = six;

在此语法中,我们有六个节点,数据项分别为 1、2、3、4、5、6。其中,第一个节点存储二的地址,二存储三的地址,依此类推。对于最后一个,它将是一个指向节点一的 NULL。这里的时间复杂度为 O(N + Q*log(N)),辅助空间为 O(4*MAX)。

方法

  • 方法 1 - 使用 Java 查找数组中两个相等一半的按位或。

  • 方法 2 - 使用 Java 对给定数组中所有对的按位或求和的有效解决方案

使用 Java 查找数组中两个相等一半的按位或

在此 Java 构建代码中,我们将计算按位或对的总和。这里 I 是 OR 按位运算符。时间复杂度为 O(n)。

示例 1

import java.util.*;

public class KCTPRDD{
   static int MAX = 102001;
   static int []seg = new int[4 * MAX];
   static void build(int node, int l,int r, int a[]){
      if (l == r)
         seg[node] = a[l];

      else{
         int mid = (l + r) / 2;

         build(2 * node, l, mid, a);
         build(2 * node + 1, mid + 1, r, a);

         seg[node] = (seg[2 * node] |
            seg[2 * node + 1]);
      }
   }

   static int query(int node, int l, int r, int start, int end, int a[]) {
      
      if (l > end || r < start)
         return 0;

      if (start <= l && r <= end)
         return seg[node];

      int mid = (l + r) / 2;
      return ((query(2 * node, l, mid, start, end, a)) | (query(2 * node + 1, mid + 1, r, start, end, a)));
   }

   static void orsum(int a[], int n, int q, int k[]){
      
      build(1, 0, n - 1, a);

      for(int j = 0; j < q; j++) {
      int i = k[j] % (n / 2);
         int sec = query(1, 0, n - 1,  n / 2 - i, n - i - 1, a);
         int first = (query(1, 0, n - 1, 0,  n / 2 - 1 - i, a) | query(1, 0, n - 1,  n - i, n - 1, a));
         int temp = sec + first;
         System.out.print(temp + " ");
      }
   }
   public static void main(String[] args) {
      int a[] = { 7, 16, 10, 2001, 1997, 2022, 24, 11 };
      int n = a.length;
      int q = 2;
      int k[] = { 4, 2 };
      orsum(a, n, q, k);
   }
}

输出

4062 2078

对给定数组中的所有对进行按位或求和的有效解决方案:

在此 Java 代码中,我们将使用 K%(N/2) 方法将每个元素移位到该特定数组。然后遍历它以计算每个查询的两个半部分的或。

示例 2

import java.io.*;

public class KCIRLLTP {
	static int pairORSum(int arr[], int n){
		int ans = 0; 
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++)
				ans += arr[i] | arr[j];

		return ans;
	}
	public static void main(String args[]) {
		int arr[] = { 16, 07, 10, 2001, 1997 };
		int n = arr.length;
		System.out.println(pairORSum(arr, n));
	}
}

输出

14107

结论

在今天的文章中,我们学习了如何通过 K 次循环移位将给定数组分成两半,然后使用按位或运算求出数组的总和。


相关文章


有用资源