Title
https://www.lintcode.com/problem/346
Given an array, please calculate the XOR of the maximum value or the minimum value of all subintervals. The specific steps are: First, for a subrange, find the maximum and minimum values of the range, and then XOR these two numbers, you can get a value. Second, find all the subranges of this array, XOR the resulting values, and you'll get the correct solution. 1 <= n <= 1e6 1 <= a[i] <= 1e6 Sample Example 1: Input: [1, 2, 3] Output: 0 illustrate: This array has 6 subranges: [1], [2], [3], [1, 2], [2, 3], [1, 2, 3] The corresponding XOR sums are: 0, 0, 0, 3, 1, 2 The final answer is: 0 Example 2: Input: [1, 3, 2] Output: 1 illustrate: This array has 6 subranges: [1], [3], [2], [1, 3], [3, 2], [1, 3, 2] The corresponding XOR sums are: 0, 0, 0, 2, 1, 2 The final answer is: 1
Prerequisite knowledge
Monotone stack, or operation
Answer
public class Solution {<!-- -->
/**
* @param nums: a list of integers
* @return: The xorsum of maximun value xor minimun value of all subintervals
*/
public int xorSum(int[] nums) {<!-- -->
//monotone stack
int n = nums.length;
int[] lmin = new int[n], lmax = new int[n], rmin = new int[n], rmax = new int[n];
Stack<Integer> stacklmin = new Stack<>(), stacklmax = new Stack<>(),
stackrmin = new Stack<>(), stackrmax = new Stack<>();
for (int i = 0; i <n ; i + + ) {<!-- -->
while (!stacklmin.isEmpty() & amp; & amp; nums[i] > nums[stacklmin.peek()])
stacklmin.pop();
lmin[i]= (stacklmin.isEmpty())?i:i-stacklmin.peek()-1;
stacklmin.add(i);
while (!stacklmax.isEmpty() & amp; & amp; nums[i]< nums[stacklmax.peek()])
stacklmax.pop();
lmax[i] = (stacklmax.isEmpty())?i: i-stacklmax.peek()-1;
stacklmax.add(i);
int ri = n-i-1;
while (!stackrmin.isEmpty() & amp; & amp; nums[ri] >= nums[stackrmin.peek()])
stackrmin.pop();
rmin[ri] = (stackrmin.isEmpty())? n-ri-1: stackrmin.peek()-ri-1;
stackrmin.add(ri);
while (!stackrmax.isEmpty() & amp; & amp; nums[ri] <= nums[stackrmax.peek()])
stackrmax.pop();
rmax[ri] = (stackrmax.isEmpty())? n-ri-1: stackrmax.peek()-ri-1;
stackrmax.add(ri);
}
int ans =0;
for (int i = 0; i < n; i + + ) {<!-- -->
int cnt = lmin[i] + rmin[i] + 2;
cnt + = (lmin[i]%2)*(rmin[i]%2);
cnt + = lmax[i] + rmax[i] + 2;
cnt + =(lmax[i]%2)*(rmax[i]%2);
ans^=(cnt%2)*nums[i];
}
return ans;
}
}
Local test code
public class LC966 {<!-- -->
public static double getClosestDistance(double[] x, double[] y) {<!-- -->
//Note: This problem cannot be solved with violence. You can use the divide and conquer strategy.
int n = x.length;
List<Info> points = new ArrayList<>();
for (int i = 0; i < n; i + + ) {<!-- -->
points.add(new Info(x[i], y[i]));
}
Collections.sort(points, (a, b) -> {<!-- -->
if (a.x == b.x) return 0;
if (a.x > b.x) return 1;
return -1;
});
return nearestPair(points, 0, n - 1);
}
// Calculate the distance between the nearest point pairs in the two-dimensional plane point set
// The x coordinate interval is [p[l],p[r]]
//Input: search interval
// Output: distance of the nearest point pair
public static double nearestPair(List<Info> ps, int l, int r) {<!-- -->
//Process the smallest subproblem
int n = r - l + 1;
if (n <= 3) {<!-- -->
return f(ps, l, r);
}
//Handle general problems and divide sub-intervals
int mid = (l + r) / 2;
Info mp = ps.get(mid);
double d1 = nearestPair(ps, l, mid);
double d2 = nearestPair(ps, mid + 1, r);
//Merge the problem and separate out a sub-interval with a width of 2d
double d = Math.min(d1, d2);
List<Info> strip = new ArrayList<>();
for (int i = l; i <= r; i + + ) {<!-- -->
Info cur = ps.get(i);
if (Math.abs(cur.x - mp.x) < d)
strip.add(cur);
}
Collections.sort(strip, (a, b) -> {<!-- -->
if (a.y == b.y) return 0;
if (a.y > b.y) return 1;
return -1;
});
return f2(strip, d);
}
public static double f(List<Info> ps, int l, int r) {<!-- -->
int n = r - l + 1;
double min = Double.MAX_VALUE;
for (int i = 0; i < n; i + + ) {<!-- -->
for (int j = i + 1; j < n; j + + ) {<!-- -->
double cur = dis(ps.get(l + i), ps.get(l + j));
if (cur < min) min = cur;
}
}
return min;
}
public static double f2(List<Info> strip, double d) {<!-- -->
int n = strip.size();
double min = d;
for (int i = 0; i < n; i + + ) {<!-- -->
Info a = strip.get(i);
for (int j = i + 1; j < n; j + + ) {<!-- -->
Info b = strip.get(j);
if (b.y - a.y >= d) break;
min = Math.min(min, dis(a, b));
}
}
return min;
}
public static double dis(Info a, Info b) {<!-- -->
return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
static class Info {<!-- -->
double x;
double y;
public Info(double x, double y) {<!-- -->
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {<!-- -->
double[] x = {<!-- -->1.0, 2.0, 3.0, 4.0, 5.0},
y = {<!-- -->2.0, 3.0, 1.0, 2.0, 2.0},
x1 = {<!-- -->1.0, 2.0, 3.0, 4.0, 5.0},
y1 = {<!-- -->2.0, 3.0, 1.0, 2.0, 7.0};
System.out.println(getClosestDistance(x, y)); // 1.00
// System.out.println("Answer:" + new Solution().getClosestDistance(x, y)); // 1.00
System.out.println(getClosestDistance(x1, y1)); // 1.41
// System.out.println("Answer:" + new Solution().getClosestDistance(x1, y1)); // 1.41
}
}