Java 程序在经过 K 次循环移位后将给定数组分成两半,然后使用按位或运算查找数组总和
数组是一组单一的非原始类似数据类型(值或变量),将元素存储在具有固定数量值的内存中。在创建具有某些元素的数组后,此数据集的长度将固定。这里的非原始意味着,这些数据类型可用于调用方法来执行字符可以为空的特定操作。这里的按位和意味着,具有恰好 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 次循环移位将给定数组分成两半,然后使用按位或运算求出数组的总和。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

