异或的本质是无进位相加，符合交换律、结合律。0^N = N,N^N=0
public static void swap (int[] arr, int i, int j) {
// arr[0] = arr[0] ^ arr[0]不行;必须保证 i,j不是同一个内存地址的变量
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
} // arr中，只有一种数，出现奇数次
public static void printOddTimesNum1(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
System.out.println(eor);
}
//因为异或运算符合交换律，偶数次的全部与自己异或后为0，唯一那个奇数次的则被保留了下来a&(-a) == a&(~a+1)
//取反操作将最右侧的1右边全部变成1，因为最右侧1右边原来全部是0。然后加1，就可将这个最右侧的1（取反后变成0）变回1。将其与原先值相与，因为取反操作，导致结果的其余二进制bit全为0，只有原数最右侧的1的bit为1。
// a 1 0 1 1 0 0
// ~a 0 1 0 0 1 1
// ~a+1 0 1 0 1 0 0
&
// a 1 0 1 1 0 0
// ans 0 0 0 1 0 0 // arr中，有两种数，出现奇数次
public static void printOddTimesNum2(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
//所有数跟初始值为的变量eor异或，结果是出现奇数次的a^b，因为出现偶数次的数异或结果为0
// a 和 b是两种数
// eor != 0
// eor最右侧的1，提取出来
// eor : 00110010110111000
// rightOne :00000000000001000
int rightOne = eor & (-eor); // 提取出最右的1
int onlyOne = 0; // eor'
for (int i = 0 ; i < arr.length;i++) {
// arr[1] = 111100011110000
// rightOne= 000000000010000
if ((arr[i] & rightOne) != 0) {//eor最右侧为1的位置假设为x，因为eor的x位为1，则a、b在x位一定值不相同，则可划将a、b划分为两类，一类是x位为1的数，另一类是x位为0的数。arr[i]与rightone异或，结果不为0则说明该数的x位为1
onlyOne ^= arr[i];//将x位为1的数全部异或，因为出现奇数次的数只有a、b两种，则onlyOne最终结果为a或者是b。
}
}
System.out.println(onlyOne + " " + (eor ^ onlyOne));//将a^b^(a或者b)则可得到另一个数
} public static int onlyKTimes(int[] arr, int k, int m) {
int t = new int[32];
//t[0] 0位置的1出现几个
//t[i] i位置的1出现几个
//统计所有数字每个二进制位的1的个数总和
for(int num:arr){
for(int i=0;i <=31;i++){
t[i]+=(num >> i ) & 1;
}
}
int ans = 0;
//其他数字都是出现M次，那么当所求数在某个bit上为1时，这个bit的1的个数一定不是K的倍数。
for(int i=0;i<32;i++){
if(t[i] % m!=0){//
ans | = (1<<i);
}
}
return ans;
} public static int onlyKTimes(int[] arr, int k, int m) {
int t = new int[32];
//t[0] 0位置的1出现几个
//t[i] i位置的1出现几个
//统计所有数字每个二进制位的1的个数总和
for(int num:arr){
for(int i=0;i <=31;i++){
t[i]+=(num >> i ) & 1;
}
}
int ans = 0;
//其他数字都是出现M次，那么当所求数在某个bit上为1时，所有数的这个bit的1的总数一定不是K的倍数。
for(int i=0;i<32;i++){
if(t[i] % m == 0){//
continue;//答案的这个位为0，跳过
}
if(t[i] % m == k) //这个数的这个位为0（k<M）
{
ans |= (1<<i);
}else{//这个数并非出现k次
return -1;
}
}
//if判断是为了防止0出现次数不是k次，又因为0无法影响t[i]的值，导致上面for循环一直continue
if(ans == 0){
int count = 0;
for(int num : arr){
if(num == 0){
count++;
}
}
if(count != k){
return -1;
}
}
return ans;
}注意删除头部。
public static Node removeValue(Node head, int num) {
// head来到第一个不需要删的位置
while (head != null) {
if (head.value != num) {
break;
}
head = head.next;
}
// 1 ) head == null //链表被删光
// 2 ) head != null
Node pre = head;//开始删除中间节点
Node cur = head.next;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}public class Code04_RingArray {
public static class MyQueue {
private int[] arr;
private int pushi;// end
private int polli;// begin
private int size;
private final int limit;
public MyQueue(int limit) {
arr = new int[limit];
pushi = 0;
polli = 0;
size = 0;
this.limit = limit;
}
public void push(int value) {
if (size == limit) {
throw new RuntimeException("队列满了，不能再加了");
}
size++;
arr[pushi] = value;
pushi = nextIndex(pushi);
}
public int pop() {
if (size == 0) {
throw new RuntimeException("队列空了，不能再拿了");
}
size--;
int ans = arr[polli];
polli = nextIndex(polli);
return ans;
}
public boolean isEmpty() {
return size == 0;
}
// 如果现在的下标是i，返回下一个位置
private int nextIndex(int i) {
return i < limit - 1 ? i + 1 : 0;
}
}
}（1）pop、push、getMin操作的时间复杂度都是O(1)。 （2）设计的栈类型可以使用现成的栈结构。
思路：利用两个栈，每次push元素都与栈顶元素比较，并把最小值push到另一个栈中，getMin结果则为栈顶元素。
import java.util.Stack;
public class Code05_GetMinStack {
public static class MyStack1 {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack1() {
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}
public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum <= this.getmin()) {
this.stackMin.push(newNum);
}
this.stackData.push(newNum);
}
public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
int value = this.stackData.pop();
if (value == this.getmin()) {
this.stackMin.pop();
}
return value;
}
public int getmin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}
}思路：push一次进入push栈，然后倒入pop栈；pop一次，先倒入pop栈，再pop。
pop栈倒入的前提条件：①push栈的内容需一次性全部倒入。②pop栈导入时为空。
public static class TwoStacksQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;
public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
// push栈向pop栈倒入数据
private void pushToPop() {
if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
}
public void add(int pushInt) {
stackPush.push(pushInt);
pushToPop();
}
public int poll() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.pop();
}
public int peek() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.peek();
}
}思路：push时往queue队列offer即可，取出时往help队列offer queue的元素，保留最后一个，再将其poll，交换队列引用。peek同理，不过需要保留它，所以要向help（即将变成queue）offer回去。
public static class TwoQueueStack<T> {
public Queue<T> queue;
public Queue<T> help;
public TwoQueueStack() {
queue = new LinkedList<>();
help = new LinkedList<>();
}
public void push(T value) {
queue.offer(value);
}
public T poll() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public T peek() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
help.offer(ans);
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public boolean isEmpty() {
return queue.isEmpty();
}
}求数组中所有数左侧所有比它小的数的和。
求数组中所有数左侧所有比它小的数的和。public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
//在归并排序的过程中，左组某个数小于右组时，因为左、右组有序，可以知道右组中大于这个数的数的个数，因为要求最小和，则用大于这个数的个数*这个数的值可以得出右组中的大于这个数的数对于该值的和，这是总和的组成部分。对于左组中的每个数，都是如此。一次左右组的merge后，就可以得出右组中所有数在左组中的所有比它小的数的和。
//当左右组混合变得有序后，继续下一次划分，上一次的左右组已经变成新的左组，与更大范围的右组进行merge时，因为左组变得更大，就可以得知2倍范围的右组中所有数在2倍范围的左组中的所有比它小的数的和。
//最后一次的merge，是求出右半侧的右组中的所有数对于左半侧的左组中所有比它小的数的和。通俗地说，对于右组的每个数而言，就是把每个左组中比它小的数加起来，然后再把所有的这些和加起来。
public static int process(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
// l < r
int mid = l + ((r - l) >> 1);
return
process(arr, l, mid)
+
process(arr, mid + 1, r)
+
merge(arr, l, mid, r);
}
public static int merge(int[] arr, int L, int m, int r) {
int[] help = new int[r - L + 1];
int i = 0;
int p1 = L;
int p2 = m + 1;
int res = 0;
while (p1 <= m && p2 <= r) {
res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return res;
}定义：左侧比右侧大的某一对数字为逆序对
// arr[L..R]既要排好序，也要求逆序对数量返回
// 所有merge时，产生的逆序对数量，累加，返回
// 左 排序 merge并产生逆序对数量
// 右 排序 merge并产生逆序对数量
public static int process(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
// l < r
int mid = l + ((r - l) >> 1);
return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}
public static int merge(int[] arr, int L, int m, int r) {
int[] help = new int[r - L + 1];
int i = help.length - 1;
int p1 = m;
int p2 = r;
int res = 0;
while (p1 >= L && p2 > m) {//从后往前
res += arr[p1] > arr[p2] ? (p2 - m) : 0;
help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
}
while (p1 >= L) {
help[i--] = arr[p1--];
}
while (p2 > m) {
help[i--] = arr[p2--];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return res;
} public static int process(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
// l < r
int mid = l + ((r - l) >> 1);
return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}
public static int merge(int[] arr, int L, int m, int r) {
// [L....M] [M+1....R]
int ans = 0;
// 目前囊括进来的数，是从[M+1, windowR)
int windowR = m + 1;
for (int i = L; i <= m; i++) {
while (windowR <= r && arr[i] > (arr[windowR] << 1)) {
windowR++;
}
ans += windowR - m - 1;
}
int[] help = new int[r - L + 1];
int i = 0;
int p1 = L;
int p2 = m + 1;
while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return ans;
}