Amazon

Leetcode 146 LRU Cache

Leetcode 403 Frog Jump

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