資料結構
網路
關係資料庫管理系統
作業系統
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次檢視
