K closest points

Find the K closest points to the origin in a 2D plane, given an array containing N points.

 Method1, use a priority queue. Because it takes constant time to retrieve the smallest one always.

/*
public class Point {
    public int x;
    public int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
*/
 
public List<Point> findKClosest(Point[] p, int k) {
    PriorityQueue<Point> pq = new PriorityQueue<>(10, new Comparator<Point>() {
        @Override
        public int compare(Point a, Point b) {
            return (b.x * b.x + b.y * b.y) - (a.x * a.x + a.y * a.y);
        }
    });
     
    for (int i = 0; i < p.length; i++) {
        if (i < k)
            pq.offer(p[i]);
        else {
            Point temp = pq.peek();
            if ((p[i].x * p[i].x + p[i].y * p[i].y) - (temp.x * temp.x + temp.y * temp.y) < 0) {
                pq.poll();
                pq.offer(p[i]);
            }
        }
    }
     
    List<Point> x = new ArrayList<>();
    while (!pq.isEmpty())
        x.add(pq.poll());
     
    return x;
}

Max points on a line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

public int maxPoints(Point[] points) {
    if(points == null || points.length == 0) return 0;
 
    HashMap<Double, Integer> result = new HashMap<Double, Integer>();
    int max=0;
 
    for(int i=0; i<points.length; i++){
        int duplicate = 1;//
        int vertical = 0;
        for(int j=i+1; j < points.length; j++){
            //handle duplicates and vertical
            if(points[i].x == points[j].x){
                if(points[i].y == points[j].y){
                    duplicate++;
                }else{
                    vertical++;
                }
            }else{
                double slope = points[j].y == points[i].y ? 0.0
            : (1.0 * (points[j].y - points[i].y))
      / (points[j].x - points[i].x);
 
                if(result.get(slope) != null){
                    result.put(slope, result.get(slope) + 1);
                }else{
                    result.put(slope, 1);
                }
            }
        }
 
        for(Integer count: result.values()){
            if(count+duplicate > max){
                max = count+duplicate;
            }
        }
 
        max = Math.max(vertical + duplicate, max);
        result.clear();
    }
 
 
    return max;
}

Scala - 1. Setup

Need:
1. JDK 1.8
2. Scala Build Tool (sbt), version 0.13x
3. IDE. Scala IDE for Eclipse or Intellij IDEA


1. JDK 1.8
Install JDK and set PATH of the bin direcotry

Check version: java -version

2. sbt
Install sbt.
Check version: sbt about
Compile and run: sbt
then run

3. Intellij IDEA
Install community edition.
Install Scala plugin.
go to Configure → Project defaults → Project structure and add the JDK
To use it, click Create New Project on the Welcome Screen, then select Scala, and finally SBT Project.

Sorting

Insertion Sort

Selection Sort

Merge Sort

Quick Sort

Bubble Sort

Selenium Learning Notes

Selenium IDE

Working and Handling multiple windows
storeTitle i
openWindow
selectWindow
selectWindow ${i}
close i
close

Selenium Webdriver

java learning part2

input and output

文本界面的输入输出
1. 使用Scanner类
java.util.Scanner
nextInt();
nextDouble();
next();
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
System.out.printf("%d\n", a);

2. use java.io
System.in.read()
System.out.print()

输入一行
BufferedReader in = new BufferedReader(new InputStreamReader( System.in ));
s = in.readLine();
ss = in.readLine();
n = Integer.parseInt( ss );
d = Double.parseDouble( ss );

图形界面的输入输出
文本框 TextField 输入
标签 Label 输出
按钮Button 执行命令
首先需要创建一个Frame

java learning part1

path: 命令所在路径 (javac, java etc.)
classpath: 所要引用的类所在的路径

set path=.;c:\jdk\bin...
set path: 查看当前path

javac -cp libxx.jar xxx.java
java -cp libxx.jar xxx
//临时设一下classpath, 用-cp

使用package时的编译
文件和路径一致
程序中使用package语句
使用import语句
javac -d classes src\edu\uiuc\tds\ui\*.java src\edu\uiuc\tds\util\*.java src\edu\uiuc\tds\*.java
java -cp classes edu.uiuc.tds.PackageTest

运行applet
javac xxx.java
appletViewer xxx.html
applet替代物: Flash, SilverLight, javascript, HTML5

javac 编译
java 运行
javaw 运行图形界面
appletViewer 运行applet程序
jar 打包工具
javadoc 生成文档
javap 查看类信息及反汇编

jar打包
javac A.java
jar cvfm A.jar A.man A.class (c create, v显示详情verbose, m表示生成清单文件, f表示指定文件名
java A.jar
A.man一般命名为MANIFEST.MF

javadoc -d 目录名 xxx.java
/** */