怎么理解Two's complement

在Java里整数的表示就用的是Two's complement

转换方法：一个整数n, 想要得到-n的二进制表示，则可将n的二进制写出来，然后挨个翻转，完成后加1即可。比如 8 -> 00001000 -> 11110111 -> 11111000 -> -8

如此来算，则
00000001 ->1, 00000010 -> 2, ... , 01111111 -> 127
11111111 -> -1, 11111110 -> -2, ... , 10000001 -> -127, 10000000 -> -128

也可以这么想，n和-n加起来就是00000000 (往更高一位进一个1，100000000)

好处：加减都可以换成加法了。12-60 = 12 + (-60)

数学上怎么理解:
-n就是0 - n，然后0我们可以想像成100000000, 11111111-n就是把n 挨个翻转，但是11111111还比“0“多减了个1，所以我们要把结果加1. （就是减法上借位的思想）。

01-18-2019

刷题:
Leetcode 819，
很简单，需要补充的：String methods, Collections (Map, Set), Map.Entry methods. Regex

Core Java Chapter 2 finished

1-14-2019

Finished Core Java Chapter 1

01-10-2019

Udemy Web Developer Bootcamp Section4 finished.
form, input, label etc.

01-09-2019

农历生日

路上看microservices

看Core Java I 11th edition
Read about 11 buzzwords (Chapter 1.2)
Chapter 1
1.2 11 buzzwords

1. Simple
2. Object-Oriented
3. Distributed
4. Robust
5. Secure
6. Arcitecture-Neutral (JVM, Java runtime system)
7. Portable (size of primitive dat types are specified, for example int is always 32bit.)
8. Interpreted (jshell in Java 9 for rapid and exploratory programming)
9. High-Performance (just-in-time compilers)
10. Multithreaded (use more processors in parallel)
11. Dynamic

1.3 Java applets and the Internet

    applets: Java programs that work on web pages (need a supporting browser)

But actually Flash became popular.

Nowadays usually can use HTML and Javascript

打表学习从2019.1.10开始

用小本本记下来每天做了什么，学到了什么。

读1997年写雷军的文章有感

里面有一些雷军的讲话很有道理，值得学习。
摘录几条在下面自己经常看看。

1. 计算机搞懂精髓以后，所有的东西都很简单。计算机不是一门理论性很强的学科，强调的是实践。

2. 雷军的工作任务是按半小时来定的，当时雷军有一个笔记本记着每半小时干了什么。“如果浪费了半小时时间，我就觉得很惭愧。后来我看到很多人不珍惜时间的时候，我就觉得这样的人真没出息。时间是自己的，你到一个公司打工的时候，偷懒，老板没有看见，就觉得自己又蒙了一下，玩猫和老鼠的游戏，真是没有必要。公司所付的那么一点钱，就买下了你一个月的青春？学会的东西首先是自己的，其次才是公司的。没有多少人真正计算过自己一个小时值多少钱。”

3. 最让雷军佩服的程序员是现在中文之星的核心程序员陈波。“他写程序全是在上班时间，他每天按时上班按时下班，从不加班，但上班时间他时间利用率很高，连水都不喝，女朋友的电话都是中午去接。像这样的人就是为写程序而生的，就像李昌镐是为下棋而生的一样。”

4. 雷军承认自己写程序不如陈波。“我有杂念，而真正第一流的程序员是没有杂念的。我曾经72小时不睡觉连续写程序，但这有什么了不起呢？别人也可以三天三夜在麻将桌上不下来，难的是早上8点钟开始打牌，打到12点，下午1点再开始打，打到下午5点，这样一直坚持一年。”

5. 写了这么多年程序，雷军感触最深的有两点：第一，程序不仅仅是核心程序员的，同时也应该是用户和同事参与完成的，所以，功劳应该属于大家，不能把光环套在一个人头上；第二，程序员要有方便别人，麻烦自己的精神。因为，程序员花两天改进的一个小模块，就有可能会省却了用户数以百万计的麻烦。雷军最烦听到有程序员对他讲，程序改起来太麻烦，这个小错误凑合算了的话。“程序员发现自己的程序中有一个小小bug没有改，就应该睡不着觉。”

6. 在雷军看来，公司里面一个人干一个半人的工作最理想。“一个人干一个人工作的公司是不行的，在这么激烈的竞争中，无法降低成本；一个人干两个人的工作，人员没有任何冗余，任何一个人走，都会对公司结构造成致命的损失，组织不能够安全运行。”

另外从文章里看到，雷军是一个很能表达的人，不光是说，而且文章也写的好。所以可以看出，交流，表达能力是非常非常重要的。

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

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
/** */

Iterator

Iterator, an interface in java.util for iterating sequence of objects.

public interface Iterator {
    boolean hasNext();
    Object next();
    void remove();                          // The remove() method is optional.
  }

An Iterator is like a bookmark.
 Just as you can have many bookmarks in a book, you can have many Iterators iterating over the same data structure, each one independent of the others.

One Iterator can advance without disturbing other Iterators that are iterating over the same data structure.
The first time next() is called on a newly constructed Iterator, it returns the first item in the sequence. Each subsequent time next() is called, it returns the next item in the sequence.
 After the Iterator has returned every item in the sequence, every subsequent call to next() throws an exception and halts with an error message. (I find this annoying; I would prefer an interface in which next() returns null. The Java library designers disagree.)

To help you avoid triggering an exception, hasNext() returns true if the Iterator has more items to return, or false if it has already returned every item in the sequence. It is usually considered good practice to check hasNext() before calling next(). (In the next lecture we'll learn how to catch exceptions; that will give us an alternative way to prevent our program from crashing when next() throws an exception.)

 There is usually no way to reset an Iterator back to the beginning of the sequence. Instead, you construct a new Iterator.

Most data structures that support Iterators "implement" another interface in
java.util called "Iterable".

public interface Iterable {
    Iterator iterator();
  }

怎么用，一般来说，如果想遍历一个数据结构DS，就call DS.iteratre(); 这个method会constructs and returns DSIterator whose fields are initialized so it is ready to return the first item in DS.

例子:

/* list/SListIterator.java */

package list;
import java.util.*;

public class SListIterator implements Iterator {
  SListNode n;

  public SListIterator(SList l) {
    n = l.head;
  }

  public boolean hasNext() {
    return n != null;
  }

  public Object next() {
    if (n == null) {
      /* We'll learn about throwing exceptions in the next lecture. */
      throw new NoSuchElementException();                       // In java.util
    }
    Object i = n.item;
    n = n.next;
    return i;
  }

  public void remove() {
    /* Doing it the lazy way.  Remove this, motherf! */
    throw new UnsupportedOperationException("Nice try, bozo."); // In java.lang
  }
}

/* list/SList.java */

package list;
import java.util.*;

public class SList implements Iterable {
  SListNode head;
  int size;

  public Iterator iterator() {
    return new SListIterator(this);
  }

  [other methods here]
}

Ruby on Rails

Tools:
 Rake - Create/migrate database, clear web session data.
 WEBrick - Web server for hosting Rails web applications.
 SQLite - A simple database system.
 Rack Middleware - Standardized interface for interaction between web server and web application.

rails new hello_www
cd hello_www
rails server (start a web server)

Under hello_www (Rails root):
app: models, views, and controllers code
bin: helper scripts (bundle, rails, rake)
config: App, database and route configuration
db: database schema and migrations
Gemfile: specify the required gems
lib:
log: application logging directory
pulic: webroot of the application
test: Tests - Agile development

Popular web application frameworks

- Ruby on Rails (Ruby)
- Play (Java and Scala)
- ASP.NET MVC (Microsoft)
- Django (Python)
- Sinatra (Ruby) (very light-weight)
- Symfony (PHP)
- Sails.js (Node.js, JavaScript)

Content management systems (CMSs):
WordPress, Drupal, Joomla!

The MVC Design pattern
Model-View-Controller model
 - Decouples data (model) and presentation (view)
 - A controller handles requests, and coordinates between the model and the view
 - More robust applications, easier to maintain

MVC control flow:
 1. User interface (view) awaits user input
 2. User provides input, e.g., clicks a button
 3. Controller handles the input event -> some action (handler or callback) understandable by the model
 4. Controller notifies the model, possibly changing the model's state
 5. Controller notifies the view (if it needs to be updated). Back to step 1.

PriorityQueue

Operations:
add O(logn), find largest O(1), remove largest O(log(n))

Application:
scheduling long streams of actions to occur at various future times.
useful for sorting.

Common implementation is Heap.

Heap:
max-heap is a binary tree that:
Both labels in both children of each node are less than node's label

So node at the top has largest label.

Longest Increasing Subsequence

Leetcode 300
Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

O(n^2):
Naive solution is use array T[] to track the LIS for each element in the original array. We have to track all the elements because the LIS can only increase for previous element which are smaller than current element.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        // naive solution, keep another array to store the LIS so far. O(n^2)
        if (nums==null || nums.length == 0) return 0;
        int[] lens = new int[nums.length];
        int maxsofar = 1;
        for (int i = 0; i < nums.length; i++) {
            lens[i] = 1;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if ((lens[j]+1) > lens[i]) {
                        lens[i] = lens[j] + 1;
                    }
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (lens[i] > maxsofar) maxsofar = lens[i];
        }
        return maxsofar;
    }
}