tryhard
BAN USER@Chrisz
That's brilliant!!!
I never thought of intervals.....
Anyway, I improved your algorithm a little bit, and I've got O(n):
public class _6018738030641152 {
public static void main(String[] args) {
int[] a = {4, 3, 6, 8, 0, 3, 2, 3};
// 6 7 0 1 2 3 4 5 = 6
// 7 0 1 2 3 4 5 6 = 5
// 4 5 6 7 0 1 2 3 = 6
// a = new int[]{0, 1, 2, 3};
// a = new int[]{1, 0, 0};
System.out.println(amazingNumber(a));
// System.out.println(bruteForce(a));
}
private static int bruteForce(int[] a) {
int res = 0;
int max = 0;
for (int i = 0; i < a.length; i++) {
int count = 0;
for (int j = 0; j < a.length; j++) {
int p = j + i;
if (j - a[p % a.length] >= 0) count++;
}
if (count > max) {
max = count;
res = i;
}
}
return res;
}
public static int amazingNumber(int[] a) {
int len = a.length;
LinkedList<Interval> intervals = new LinkedList<>();
// find all the intervals that if the array starts at any index in the interval, there will
// be at least 1 element is amazing number
for (int i = 0; i < len; i++) {
if (a[i] >= len) continue;
int start = (i+1) % len;
int end = (len + (i - a[i])) % len;
System.out.println(i + ": " + start + " - " + end);
intervals.add(new Interval(start, end));
}
// now our problem has just become: "find the year that has the maximum number of people
// alive"
int[] count = new int[len];
for (Interval i : intervals) {
count[i.start]++;
if (i.end+1 < count.length) count[i.end+1]--;
}
int max = 0;
int counter = 0;
int idx = 0;
for (int i = 0; i < count.length; i++) {
counter += count[i];
if (counter > max) {
max = counter;
idx = i;
}
}
return idx;
}
static class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
}
public static int tvOn(int[][] intervals) {
if (intervals.length == 0) return 0;
if (intervals.length == 1) return intervals[0][1] - intervals[0][0];
Arrays.sort(intervals, 0, intervals.length, new Comparator<int[]>() {
public int compare(int[] left, int[] right) {
return left[0] - right[0];
}
});
int[] last = intervals[0];
int res = intervals[0][1] - intervals[0][0];
for (int i = 1; i < intervals.length; i++) {
int[] cur = intervals[i];
if (cur[0] <= last[1]) {
if (cur[1] > last[1]) {
res += cur[1] - last[1];
last = new int[]{last[0], cur[1]};
} else {
continue;
}
} else {
res += cur[1] - cur[0];
last = cur;
}
}
return res;
}
anyone can solve this less than O(N^2)?
@OP: could you?
This is my brute force O(N^2):
private static int bruteForce(int[] a) {
int res = 0;
int max = 0;
for (int i = 0; i < a.length; i++) {
int count = 0;
for (int j = 0; j < a.length; j++) {
int p = j + i;
if (j - a[p % a.length] >= 0) count++;
}
if (count > max) {
max = count;
res = i;
}
}
return res;
}
private static String reformat(String s, int k) {
int len = s.length();
StringBuilder res = new StringBuilder();
int count = 0;
for (int i = len - 1; i >= 0; i--) {
char c = s.charAt(i);
if (c != '-') {
if (count == k) {
res.append("-");
count = 0;
i++;
} else {
res.append(c);
count++;
}
}
}
return res.reverse().toString();
}
A typical dp problem
- tryhard February 11, 2017