jasmine8gu
BAN USERpublic class Solution {
Pair point = new Pair(5, 5);
int dist(Pair p1, Pair p2) {
return (int)Math.sqrt(Math.pow((p2.x - p1.x), 2) + Math.pow((p2.y - p1.y), 2));
}
class Obj {
int dist;
int index;
Obj(int d, int i) {
dist = d;
index = i;
}
}
int departion(LinkedList<Obj> dilist, int l, int h) {
Obj pivot = dilist.get(l);
while (l < h) {
while (l < h && dilist.get(h).dist >= pivot.dist) {
h--;
}
dilist.set(l, dilist.get(h));
while (l < h && dilist.get(l).dist <= pivot.dist) {
l++;
}
dilist.set(h, dilist.get(l));
}
dilist.set(l, pivot);
return l;
}
void qsort(LinkedList<Obj> dilist, int l, int h) {
if (l < h) {
int m = departion(dilist, l, h);
qsort(dilist, l, m - 1);
qsort(dilist, m + 1, h);
}
}
void sort(LinkedList<Obj> dilist) {
qsort(dilist, 0, dilist.size() - 1);
}
LinkedList<Pair> find(LinkedList<Pair> list, int k) {
LinkedList<Obj> dilist = new LinkedList<Obj>();
for (int i = 0; i < list.size(); i++) {
int d = dist(point, list.get(i));
Obj o = new Obj(d, i);
dilist.add(o);
}
sort(dilist);
LinkedList<Pair> ret = new LinkedList<Pair>();
for (int i = 0; i < k; i++) {
ret.add(list.get(dilist.get(i).index));
}
return ret;
}
}
public class Solution {
LinkedList<TreeNode> queue = null;
LinkedList<Integer> list = null;
int maxDepth = 0;
void levelOrder(TreeNode root) {
queue.add(root);
list.add(root.val);
int depth = 0;
while (!queue.isEmpty()) {
for (int i = 0; i < Math.pow(2, depth); i++) {
TreeNode p = queue.removeFirst();
if (p == null) {
queue.add(null);
list.add(0);
queue.add(null);
list.add(0);
}
else {
queue.add(p.left);
if (p.left == null) {
list.add(0);
}
else {
list.add(p.left.val);
}
queue.add(p.right);
if (p.right == null) {
list.add(0);
}
else {
list.add(p.right.val);
}
}
}
depth++;
if (depth == maxDepth) {
break;
}
}
}
void drawBT(TreeNode root) {
queue = new LinkedList<TreeNode>();
list = new LinkedList<Integer>();
getDepth();
levelOrder(root);
for (int i = 0; i < maxDepth + 1; i++) {
int dis = (int)Math.pow(2, maxDepth - i);
StringBuilder sdis = new StringBuilder();
for (int k = 0; k < dis; k++) {
sdis.append(" ");
}
for (int j = 0; j < Math.pow(2, i); j++) {
if (j == 0) {
System.out.print(sdis.toString());
}
else {
System.out.print(sdis.toString());
System.out.print(sdis.toString());
}
System.out.print(list.removeFirst());
}
System.out.println("");
}
}
}
public class Solution {
int[] ages = null;
int[] cnt = null;
void count(int l , int h) {
if (l <= h) {
if (ages[l] == ages[h]) {
cnt[ages[l]] += h - l + 1;
}
else {
int m = (l + h) / 2;
count(l, m);
count(m + 1, h);
}
}
}
void countAges(int[] array) {
ages = array;
cnt = new int[ages[ages.length - 1] + 1];
int l = 0;
int h = ages.length - 1;
count(l, h);
for (int i = 0; i < cnt.length; i++) {
System.out.println(i + " " + cnt[i]);
}
}
}
void levelOrder(TreeNode root) {
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.addLast(root);
queue.addLast(null);
while (!queue.isEmpty()) {
TreeNode p = null;
while ((p = queue.removeFirst()) != null) {
System.out.print(p.val + " ");
if (p.left != null) {
queue.addLast(p.left);
}
if (p.right != null) {
queue.addLast(p.right);
}
}
if (!queue.isEmpty()) {
queue.addLast(null);
System.out.println("");
}
}
}
String find(String str, Set<Character> set) {
int idx2 = 0;
String minStr = null;
StringBuilder subStr = new StringBuilder();
Set<Character> subSet = new HashSet<Character>();
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
while (idx2 < str.length()) {
while (idx2 < str.length() && !subSet.containsAll(set)) {
char nc = str.charAt(idx2);
subStr.append(nc);
subSet.add(nc);
if (map.containsKey(nc)) {
map.put(nc, map.get(nc) + 1);
}
else {
map.put(nc, 1);
}
idx2++;
}
if (idx2 == str.length() && !subSet.containsAll(set)) {
break;
}
if (subStr.length() == set.size()) {
return subStr.toString();
}
if (minStr == null || subStr.length() < minStr.length()) {
minStr = subStr.toString();
}
while (true) {
char prefix = subStr.charAt(0);
subStr.deleteCharAt(0);
map.put(prefix, map.get(prefix) - 1);
if (map.get(prefix) == 0) {
subSet.remove(prefix);
break;
}
else {
if (subStr.length() < minStr.length()) {
minStr = subStr.toString();
}
}
}
}
return minStr;
}
ArrayList<Range> merge(ArrayList<Range> list, Range range) {
sort(list);
int idx = 0;
while (idx < list.size() && range.begin > list.get(idx).end) {
idx++;
}
if (range.begin > list.get(idx).begin) {
range.begin = list.get(idx).begin;
}
int idx1 = idx;
while (idx1 < list.size() && range.end >= list.get(idx1).begin) {
idx1++;
}
if (range.end < list.get(idx1 - 1).end) {
range.end = list.get(idx1 - 1).end;
}
for (int i = idx; i < idx1; i++) {
list.set(i, null);
}
list.set(idx, range);
return list;
}
ListNode reverse(ListNode head) {
ListNode p = head;
if (p.next != null) {
head = reverse(p.next);
p.next.next = p;
p.next = null;
}
return head;
}
void reverse(ListNode head) {
ListNode p = head;
while (p.next != null) {
while (p.next.next != null) {
p = p.next;
}
p.next.next = p;
p.next = null;
p = head;
}
}
int steps(int m, int n) {
if (m < 1 || n < 1) {
return Integer.MAX_VALUE - 1;
}
if (m == 1 && n == 1) {
return 0;
}
int cnt1 = 1 + steps(m - n, n);
int cnt2 = 1 + steps(m, n - m);
if (cnt1 <= cnt2) {
return cnt1;
}
else {
return cnt2;
}
}
Vector<String> stairs(int n) {
HashMap<Integer, Vector<String>> table = new HashMap<Integer, Vector<String>>();
Vector<String> ret = new Vector<String>();
if (n <= 0) {
return ret;
}
if (n == 1) {
String line = "1";
ret.add(line);
table.put(1, ret);
return ret;
}
if (n == 2) {
String line1 = "11";
ret.add(line1);
String line2 = "2";
ret.add(line2);
table.put(2, ret);
return ret;
}
Vector<String> subRet1 = table.get(n - 1);
if (subRet1 == null) {
subRet1 = stairs(n - 1);
}
for (int i = 0; i < subRet1.size(); i++) {
ret.add("1" + subRet1.get(i));
}
Vector<String> subRet2 = table.get(n - 2);
if (subRet2 == null) {
subRet2 = stairs(n - 2);
}
for (int i = 0; i < subRet2.size(); i++) {
ret.add("2" + subRet2.get(i));
}
return ret;
}
- jasmine8gu March 28, 2015