KK's blog

public int[][] kClosest(int[][] points, int K) {
	PriorityQueue<Point> maxHeap = new PriorityQueue<Point>(K,
			new Comparator<Point>() {
				@Override
				public int compare(Point o1, Point o2) {
					return distance(o2, o1); // descending
				}
			}
	);
	
	for(int i = 0; i < points.length; i++) {
		Point p = new Point(points[i][0], points[i][1]);
		if(maxHeap.size() < K)
			maxHeap.offer(p);
		else if(distance(p, maxHeap.peek()) < 0) {
			maxHeap.poll();
			maxHeap.offer(p);
		}
	}
	int[][] res = new int[K][2];
	int j = 0;
	while(!maxHeap.isEmpty()) {
		Point p = maxHeap.poll();
		res[j][0] = p.x;
		res[j][1] = p.y;
		j++;
	}
	return res;
}

int distance(Point o1, Point o2) {
	return (o1.x * o1.x + o1.y * o1.y) - (o2.x * o2.x + o2.y * o2.y);
}

class Point {
	 int x;
	 int y;
	 Point() { x = 0; y = 0; }
	 Point(int a, int b) { x = a; y = b; }
}

public void spiral2(int[][] a){
	int rowTop = 0, rowBottom = a.length-1, colLeft = 0, colRight = a[0].length-1;
	
	while(rowTop<=rowBottom && colLeft<=colRight){
		//topRow
		for(int i=colLeft;i<=colRight;i++)
			System.out.print(a[rowTop][i]+" ");
		rowTop++;
		//rightCol
		for(int i=rowTop;i<=rowBottom;i++)
			System.out.print(a[i][colRight]+" ");
		colRight--;
		if(rowTop<=rowBottom){
			for(int i=colRight;i>=colLeft;i--)
				System.out.print(a[rowBottom][i]+" ");
			rowBottom--;
		}
		if(colLeft<=colRight){
			for(int i=rowBottom;i>=rowTop;i--)
				System.out.print(a[i][colLeft]+" ");
			colLeft++;
		}
	}
}

public void spiral3(int[][] a){
	int rowTop = 0, colLeft = 0;
	
	while(rowTop<=a.length-rowTop-1 && colLeft<=a[0].length-colLeft-1){
		//topRow
		for(int i=colLeft;i<=a[0].length-colLeft-1;i++)
			System.out.print(a[rowTop][i]+" ");
		rowTop++;
		//rightCol
		for(int i=rowTop;i<=a.length-rowTop;i++)
			System.out.print(a[i][a[0].length-colLeft-1]+" ");
		//colRight--;
		if(rowTop<=a.length-rowTop){
			for(int i=a[0].length-colLeft-2;i>=colLeft;i--)
				System.out.print(a[a.length-rowTop][i]+" ");
		}
		if(colLeft<=a[0].length-colLeft-2){
			for(int i=a.length-rowTop-1;i>=rowTop;i--)
				System.out.print(a[i][colLeft]+" ");
			colLeft++;
		}
	}
}

public void spiral4(int[][] a){
	int num = Math.min(a.length, a[0].length);
	for(int st=0;st<(num+1)/2;st++){
		//complete edge(top)
		for(int i=st;i<a[0].length-st;i++)
			System.out.print(a[st][i]+" ");
		//complete edge-top (right)
		for(int i=st+1;i<a.length-st;i++)
			System.out.print(a[i][a[0].length-1-st]+" ");
		if(a[0].length-2-st>st)
			for(int i=a[0].length-2-st;i>=st;i--)
				System.out.print(a[a.length-st-1][i]+" ");
		if(a.length-2-st>st+1)
			for(int i=a.length-2-st;i>=st+1;i--)
				System.out.print(a[i][st]+" ");
	}
}

public int maxProfit(int[] prices) {
	if(prices.length==0)
		return 0;
	int min = prices[0];
	int curProfit = 0;
	for(int i=1;i<prices.length;i++){
		int todayProfit = prices[i]-min;
		if(todayProfit>curProfit)
			curProfit = todayProfit;
		if(min>prices[i])
			min = prices[i];
	}
	return curProfit;
}

public List<Interval> merge(List<Interval> intervals) {
	Collections.sort(intervals, new Comparator<Interval>(){
		public int compare(Interval v1, Interval v2){
			return v1.start - v2.start;
		}
	});
	intervals.add(new Interval(Integer.MAX_VALUE, Integer.MAX_VALUE));
	List<Interval> re = new ArrayList<Interval>();
	Interval newInterval = null;
	for(int i=1;i<intervals.size();i++){
		if(newInterval==null)
			newInterval = intervals.get(i-1);
		if(canMerge(newInterval,intervals.get(i))){
			newInterval = mergeIntervals(newInterval,intervals.get(i));
		}
		else{
			re.add(newInterval);
			newInterval = null;
		}
	}
	return re;
}


//假设in与in2按start排序，所以只有两情况：
/*
 * In  -------
 * In2   ---
 * In2   -------- 
 */
public boolean canMerge(Interval in, Interval in2){
	if(in2.start == Integer.MAX_VALUE)
		return false;
	return in.end>=in2.start;
}

public Interval mergeIntervals(Interval in, Interval in2){
	return new Interval(in.start, Math.max(in.end, in2.end));
}

int[] directX = new int[]{1, 1,-1,-1,2,2,-2,-2};
int[] directY = new int[]{2,-2,2,-2,1,-1,1,-1};

public int shortestPath(boolean[][] grid, Point source, Point destination) {
	if(grid == null || grid.length == 0 || grid[0].length == 0)
		return -1;
	
	Queue<Point> q = new LinkedList<>();
	Map<Point, Integer> map = new HashMap<>();
	map.put(source, 0); // remember
	boolean[][] visited = new boolean[grid.length][grid[0].length];
	q.offer(source);
	visited[source.x][source.y] = true; // use hashSet is wrong.
	while(!q.isEmpty()) {
		Point p = q.poll();
		if(p.x == destination.x && p.y == destination.y)
			return map.get(p);
		for(Point neighbor : getNeighbors(p)) {
			if(!isValid(grid, neighbor) || visited[neighbor.x][neighbor.y])
				continue;
			q.offer(neighbor);
			visited[neighbor.x][neighbor.y] = true;
			map.put(neighbor, map.get(p) + 1);
		}
	}
	
	return -1;
}

List<Point> getNeighbors(Point point) {
	List<Point> result = new ArrayList<>();
	for(int i = 0; i < 8; i++) {
		result.add(new Point(point.x + directX[i], point.y + directY[i]));
	}
	return result;
}

boolean isValid(boolean[][] grid, Point point) {
	if(point.x >= 0 && point.x < grid.length && point.y >= 0 && point.y < grid[0].length 
			&& !grid[point.x][point.y])
		return true;
	else return false;
}