Aim_Google
BAN USERpublic static int getPaths(int length, int width, HashSet<String> blocked) {
String bottomLeft = String.valueOf(width-1) + " 0";
String bottomRight = String.valueOf(width-1) + " " + String.valueOf(length-1);
if ((length == 0) || (width == 0) || (blocked.contains(bottomLeft)) || (blocked.contains(bottomRight))) return 0;
int[] dp = new int[width];
dp[0] = 1;
for (int i = 1; i < length; i++) {
int store = 0;
for (int j = 0; j < width; j++) {
int temp = dp[j];
dp[j] = dp[j] + ((j == width-1) ? 0 : dp[j+1]) + store;
String currLocation = String.valueOf(width-1-j) + " " + String.valueOf(i);
if (blocked.contains(currLocation)) dp[j] = 0;
store = temp;
}
}
return dp[0];
}
public class Pair {
int row;
int col;
Pair(int r, int c) {
row = r;
col = c;
}
}
public static Point[] func(Point[] points) {
if (points == null || points.length <= 1) return null;
Point[] answer = new Point[2];
int length = points.length;
Point firstPoint = points[0];
int j = 0;
for (int i = 1; i < length; i++) {
Point tempPoint = points[i];
if (tempPoint.x < firstPoint.x) {
firstPoint = tempPoint;
j = i;
}
}
answer[0] = firstPoint;
answer[1] = points[(j+1)%length];
for (int i = 0; i < length; i++) {
boolean flag = checkDirection(answer[0], points[i], answer[1]);
if (flag) {
answer[1] = points[i];
}
}
return answer;
}
private static boolean checkDirection(Point p1, Point p2, Point p3) {
int value = ((p3.y - p2.y)*(p2.x-p1.x)) - ((p2.y - p1.y)*(p3.x-p2.x));
if (value > 0) return true;
return false;
}
static class Point {
int x;
int y;
Point (int xx, int yy) {
x = xx;
y = yy;
}
}
To do it optimally for toggle(i, j), we update arr[i] (using 1 based index) to 1 and arr[j+1] to 1, so that to get isOn for any index, we just have to sum the values from 1st index to that index, if its cumulative sum is 1 (mod 2), then it is ON, otherwise OFF.
E.g. In array of size 10, if we have to toggle (2, 5), then make arr[2] = 1 and arr[6] = 1, then to get isOn(3), sum from arr[1] to arr[3] = 1, thus ON, to get isOn(8) = sum from arr[1] to arr[8] = 2 = 0(mod2), thus OFF
Now to store cumulative sum optimally, use BIT.
int[] arr = new int[n+1];
public static void toggle(int i, int j) {
i++;
j++;
set(i);
set(j+1);
}
public static boolean isOn(int i) {
i++;
int sum = 0;
int pos = i;
while (pos > 0) {
sum += arr[pos];
sum %= 2;
pos -= (pos & (-pos));
}
return (sum%2 == 1);
}
private static void set(int i) {
int pos = i;
while (pos <= n) {
arr[pos] += 1;
arr[pos] %= 2;
pos += (pos & (-pos));
}
}
What does each function do? Can you explain it more? I mean what are their arguments and what each of them returns?
- Aim_Google January 12, 2018This code will check if such a string can be formed, if no then it will return null, otherwise it will return a possible string.
private static String generateOne(String str) {
if (str == null || str.length() == 0) return null;
int length = str.length();
StringBuilder answer = new StringBuilder();
PriorityQueue<Pair> pq = new PriorityQueue<>();
char[] array = str.toCharArray();
Arrays.sort(array);
for (int i = 0; i < length; ) {
char ch = array[i];
int freq = 1;
i++;
while (i < length && (array[i] == ch)) {
freq++;
i++;
}
pq.add(new Pair(freq, ch));
}
char prevChar = ' ';
while (pq.isEmpty() == false) {
Pair p = pq.poll();
char ch = p.ch;
int freq = p.freq;
if (ch == prevChar) {
if (pq.size() == 0) {
return null;
} else {
Pair q = pq.poll();
char ch2 = q.ch;
int freq2 = q.freq;
answer.append(ch2);
freq2--;
if (freq2 != 0) {
pq.add(new Pair(freq2, ch2));
}
prevChar = ch2;
pq.add(p);
}
} else {
answer.append(ch);
freq--;
if (freq != 0) {
pq.add(new Pair(freq, ch));
}
prevChar = ch;
}
}
return answer.toString();
}
static class Pair implements Comparable<Pair>{
int freq;
char ch;
Pair (int f, char c) {
freq = f;
ch = c;
}
public int compareTo(Pair p) {
if (freq > p.freq) return -1;
if (freq < p.freq) return 1;
return 0;
}
}
static int lastIndex(int[] arr) {
if (arr == null || arr.length <= 1) return -1;
int len = arr.length;
for (int i = len-1; i >0; i--) {
if (arr[i] == arr[i-1]) return i;
}
return -1;
}
static ArrayList<ArrayList<Integer>> makeClusters(int[] arr) {
ArrayList<ArrayList<Integer>> answer = new ArrayList<>();
if (arr == null || arr.length == 0) return answer;
int length = arr.length;
int ptr = 1, start = arr[0];
ArrayList<Integer> temp = new ArrayList<>();
temp.add(start);
while (ptr < length) {
int speed = arr[ptr];
if (speed >= start) {
temp.add(speed);
} else {
answer.add(temp);
temp = new ArrayList<Integer>();
temp.add(speed);
start = speed;
}
ptr++;
}
answer.add(temp);
return answer;
}
int func(int[] arr, int k) {
int ans = Integer.MAX_VALUE;
Deque<Integer> q = new LinkedList<>();
int ptr = 0;
int length = arr.length;
while (ptr < length) {
int ele = arr[ptr];
if (q.isEmpty() == true) {
q.add(ptr);
ptr++;
} else {
if (ptr-q.getFirst() <= k) {
if (ele >= arr[q.getFirst()]) {
while (q.isEmpty() == false) {
q.remove();
}
q.add(ptr);
ptr++;
} else {
if (ele >= arr[q.getLast()]) {
q.removeLast();
} else {
q.add(ptr);
ptr++;
}
}
} else {
int x = arr[q.removeFirst()];
if (ele > arr[q.removeFirst()]) {
ans = Math.min(ans, Math.min(ele, x));
while (q.isEmpty() == false) {
q.remove();
}
q.add(ptr);
ptr++;
} else {
if (ele >= arr[q.getLast()]) {
q.removeLast();
} else {
q.add(ptr);
ptr++;
}
}
}
}
}
return ans;
}
public static boolean matcher(String pattern, String seq) {
if (pattern == null && seq == null) return true;
int lenPattern = pattern.length(), lenSeq = seq.length();
int ptr1 = 0, ptr2 = 0;
while (ptr1 < lenPattern && ptr2 < lenSeq) {
char ch1 = pattern.charAt(ptr1);
char ch2 = seq.charAt(ptr2);
if (ch1 >= '1' && ch1 <= '9') {
ptr1++;
int rep = ch1-'0';
ptr2 += rep;
} else {
if (ch1 == ch2) {
ptr1++; ptr2++;
} else {
return false;
}
}
}
if (ptr1 != lenPattern || ptr2 != lenSeq) return false;
return true;
}
static HashMap<Integer, Integer> bracketPair = new HashMap<>();
String decodeString(String str) {
if (str == null || str.length() <= 2) return str;
Stack<Integer> stack = new Stack<>();
int length = str.length();
for (int i = 0; i < length; i++) {
char ch = str.charAt(i);
if (ch == '[') {
stack.push(i);
} else if (ch == ']') {
int start = stack.pop();
bracketPair.put(start, i);
}
}
return helper(str, 0, length-1);
}
private String helper(String str, int sI, int eI) {
StringBuilder ret = new StringBuilder();
for (int i = sI; i <= eI; ) {
char ch = str.charAt(i);
if (ch >= '0' && ch <= '9') {
int num = 0;
while (ch != '[') {
int x = ch - '0';
num *= 10;
num += x;
i++;
ch = str.charAt(i);
}
int last = bracketPair.get(i);
String temp = helper(str, i+1, last-1);
int rep = num;
for (int j = 0; j < rep; j++) {
ret.append(temp);
}
i = last+1;
} else {
ret.append(ch);
i++;
}
}
return ret.toString();
}
- Aim_Google March 30, 2018