public class Solution {
public static class Line implements Comparable<Line> {
public int index;
public int height;
public boolean isStart;
@Override
public int compareTo(Line arg0) {
if (index != arg0.index)
return index - arg0.index;
return (arg0.isStart?arg0.height:-arg0.height)-(isStart?height:-height);
}
}
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<int[]>();
if (buildings == null || buildings.length == 0)
return result;
Line[] l = new Line[buildings.length * 2];
for (int i = 0; i < buildings.length; i++) {
l[i * 2] = new Line();
l[i * 2].index = buildings[i][0];
l[i * 2].height = buildings[i][2];
l[i * 2].isStart = true;
l[i * 2 + 1] = new Line();
l[i * 2 + 1].index = buildings[i][1];
l[i * 2 + 1].height = buildings[i][2];
l[i * 2 + 1].isStart = false;
}
Arrays.sort(l);
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
int height = 0;
for (Line line : l) {
if (line.isStart)
pq.add(line.height);
else
pq.remove(line.height);
int newH = pq.peek() == null ? 0 : pq.peek();
if (newH != height) {
height = newH;
int[] re = new int[2];
re[0] = line.index;
re[1] = height;
result.add(re);
}
}
return result;
}
}
Category Archives: Coding
Palindrome Linked List
public class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null||head.next==null)return true;
ListNode newhead=head;
int len=0;
while(newhead!=null){
newhead=newhead.next;
len++;
}
int i=0;
while(i<len/2){
ListNode temp=head.next;
head.next=newhead;
newhead=head;
head=temp;
i++;
}
if(len%2==1)head=head.next;
while(head!=null){
if(head.val!=newhead.val)return false;
head=head.next;
newhead=newhead.next;
}
return true;
}
}
Largest Number
public class Solution {
public String largestNumber(int[] nums){
Integer[]in=new Integer[nums.length];
for (int i = 0; i < nums.length; i++) {
in[i]=nums[i];
}
Arrays.sort(in,new Compare());
StringBuilder sb = new StringBuilder();
for (int i = nums.length - 1; i >= 0; i--) {
sb.append(in[i]);
}
if(sb.charAt(0) == '0'){
return "0";
}
return sb.toString();
}
public class Compare implements Comparator<Integer> {
public int compare(Integer arg0, Integer arg1) {
String s1 = arg0.toString();
String s2 = arg1.toString() + arg1.toString();
while (s1.length() < s2.length()) {
s1 += s1;
}
while (s2.length() < s1.length()) {
s2 += s2;
}
return s1.compareTo(s2);
}
}
}
Rectangle Area
public class Solution {
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int total=(C-A)*(D-B)+(G-E)*(H-F);
return total-getIntersect(A,C,E,G)*getIntersect(B,D,F,H);
}
public int getIntersect(int x1,int x2, int x3, int x4){
if(x2<x3||x1>x4)return 0;
return Math.abs(Math.max(x1,x3)-Math.min(x2,x4));
}
}
Summary Ranges
public class Solution {
public List<String> summaryRanges(int[] nums) {
int i=0;
List<String> result=new ArrayList<String>();
while(i<nums.length){
int start =nums[i];
int end=nums[i];
while(i<nums.length-1&&nums[i]+1==nums[i+1]){
end++;
i++;
}
if(start==end){
result.add(start+"");
}else{
result.add(start+"->"+end);
}
i++;
}
return result;
}
}
Remove Duplicates from Sorted List II
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
int c;
ListNode newhead=head;
ListNode last=head;
boolean needMoveHead=true;
while(head!=null&&head.next!=null){
c=0;
while(head.next!=null&&head.val==head.next.val){
c++;
head=head.next;
}
if(c>=1){
// need to cut it
if(needMoveHead){
// it's the first element, move the new head
newhead=head.next;
}
// cut it
last.next=head.next;
}else{
// doesn't need to cut it. No need to move new head now
needMoveHead=false;
last=head;
}
head=head.next;
}
return newhead;
}
}
Pocket Mine 5 hidden achievement
Let’s Do This – 20 pts (Hidden)
Shuffle 3 mythical cards in one shuffle
Dream Run – 20 pts (Hidden)
Shuffle 3 5-stars cards in one shuffle
Treasure Hunter – 15 pts (Hidden)
Get 3 treasure-related powerups in one shuffle
Gold Digger – 15 pts (Hidden)
Get 3 gold-related powerups in one shuffle
Is This Real Life!? (Hidden)
Shuffle 3 mythical 5-stars cards in one shuffle
Leetcode: Add Binary
public class Solution {
public String addBinary(String a, String b) {
StringBuilder sb=new StringBuilder();
int i=a.length()-1,j=b.length()-1;
boolean carry=false;
while(i>=0||j>=0){
if((i<0||a.charAt(i)=='0')&&(j<0||b.charAt(j)=='0')){
if(carry)sb.insert(0,'1');
else sb.insert(0,'0');
carry=false;
}else if(i>=0&&j>=0&&a.charAt(i)=='1'&&b.charAt(j)=='1'){
if(carry)sb.insert(0,'1');
else sb.insert(0,'0');
carry=true;
}else{
if(carry)sb.insert(0,'0');
else sb.insert(0,'1');
}
i--;j--;
}
if(carry)
sb.insert(0,'1');
return sb.toString();
}
}
Leetcode: Minimum Window Substring
public class Solution {
public String minWindow(String S, String T) {
HashMap<Character,Integer>needToFind=new HashMap<Character,Integer>();
for(char c:T.toCharArray()){
if(needToFind.containsKey(c)){
needToFind.put(c,needToFind.get(c)+1);
}else{
needToFind.put(c,1);
}
}
int found=0;
int min=Integer.MAX_VALUE;
int rstart=0,rend=0;
HashMap<Character,Integer>foundMap=new HashMap<Character,Integer>();
int begin=0;
for(int end=0;end<S.length();end++){
char c=S.charAt(end);
if(!needToFind.containsKey(c))continue;
if(foundMap.containsKey(c)){
foundMap.put(c,foundMap.get(c)+1);
}else{
foundMap.put(c,1);
}
if(foundMap.get(c)<=needToFind.get(c))
found++;
if(found==T.length()){
c=S.charAt(begin);
while(!needToFind.containsKey(c)||
foundMap.get(c)>needToFind.get(c)){
if(needToFind.containsKey(c)){
foundMap.put(c,foundMap.get(c)-1);
}
begin++;
c=S.charAt(begin);
}
if(min>end-begin){
min=end-begin;
rstart=begin;
rend=end;
}
}
}
if(found==T.length())return S.substring(rstart,rend+1);
return "";
}
}
Leetcode: remove duplicates from sorted array II
public class Solution {
public int removeDuplicates(int[] A) {
if (A.length == 0) return 0;
int len = 1;
int dup = 1;
for(int i = 1; i < A.length; i++) {
if(A[i] != A[len - 1]) {
A[len++] = A[i];
dup=1;
// dup less than the max allow here, 1 mean no dup allow
} else if (dup<2) {
A[len++] = A[i];
dup ++;
}
}
return len;
}
}