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;
}
}
Monthly Archives: July 2015
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;
}
}