数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Java程序，用于在对给定数组进行K次循环移位后将其分成两半，并使用按位或运算符查找数组和
数组是一组存储在内存中具有固定数量值的相同非基本数据类型（值或变量）的元素。在使用某些元素创建数组后，此数据集的长度将固定。这里非基本是指这些数据类型可以用来调用方法以执行特定操作，其字符可以为空。这里按位和是指某些数字的和，这些数字正好设置了2位。按位或表示每个整数都存在于子数组中。它是数组中存在的相邻非空元素序列。在数组的排序操作中，存在一半的概念。在这种方法中，整个概念如果能够对数组进行划分，则返回真值。
在本文中，我们将学习如何在执行K次循环移位方法后，将特定数组分成两半，并使用按位或运算符查找数组的和。
通过执行K次循环移位，整数的二进制表示形式
什么是数据结构中的循环移位？
在数据结构中，元素的按位旋转称为循环移位，它不保存特定数字的符号位。对于循环移位，存在两种类型的移位方法
常规左移 - 它是通过2（mod 2^N）完成的乘法过程。这里，N是整数类型的特定位数
循环左移 - 它是位数的乘法方法。其中乘法可以通过方法2（mod（2^N - 1））完成。
现在，假设列表中存在两个正整数。通过执行循环方法，我们必须通过二进制表示来交换这两个元素的位置。
左循环移位
最终位将移动到第一个位置。
将所有其他位移至下一个位置。
右循环移位
将第一位移到最后。
将其余位移至前一位。
什么是数据结构中的K次循环移位？
假设一个长度为N的数组A[]。这里N是偶数。如果Q是这里的查询，而K是正数的表示。如果我们对该数组应用循环移位，则这些特定元素的总和将通过数组的两半进行按位或运算。
Input: A[] = {12, 23, 4, 21, 22, 76}, Q = 1, K = 2
Output: 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;
};
/* Node Initialization */
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;
/* Allocate the memory using malloc function */
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));
/* Assign some data values in the list */
one->data = 1;
two->data = 2;
three->data = 3;
four->data = 4;
five->data = 5;
six->data = 6;
/* Connect the nodes with pointers */
one->next = two;
two->next = three;
three->next = four;
four->next = five;
five->next = six;
six->next = one;
/* Save address of sixth node in last position */
last = six;
在此语法中，我们有六个节点，其数据项分别为1、2、3、4、5、6。在此，第一个节点存储第二个节点的地址，第二个节点存储第三个节点的地址，依此类推。对于最后一个，它将是NULL，它指向节点一。这里的时复杂度为O(N + Q*log(N))，辅助空间为O(4*MAX)。
方法
方法1 - 使用Java查找数组两个相等一半的按位或。
方法2 - 使用Java对给定数组中所有对的按位或之和进行有效的解决方案
使用Java查找数组两个相等一半的按位或
在此Java构建代码中，我们将计算按位或对的总和。这里I是或按位运算符。时复杂度为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次循环移位后，将给定数组分成两半，并使用按位或运算符查找数组的和。
161次查看
