java 刷题基础知识

写在前面

lintcode 与 leetcode 刷题的好处：只关心功能的实现，不用处理相应的输入和输出。

对于大多数程序员而言这个功能非常好，处理输入和输出有时候也需要消耗一定的时间，尤其遇到golang这种特例的时候。

刷题需要掌握的基本知识点如下：

• java 数组、list及初始化
• java 对象的引用和指针
• treeNode
• java int最大值最小值表示法
• lintcode 图论问题举例

java 数组及list，初始化

这些虽然简单，但是一般总会各种语言的初始化、定义混淆掉。这里做一个简单的记录：

int a[] = {6,4,4,2,1};
//or
int b[] = new int[10];

链表：

 ArrayList<Integer> fibList = new ArrayList<Integer>();
 fibList.add(0);
 fibList.add(1);

java对象的引用和指针

在java语言中是没有指针这个概念的。看下面这行代码：

Person p = new Person();

这行代码中实际产生了两个东西：一个是p变量，一个是Person对象。
两个变量都是保存在jvm中的heap中。
假如有以下代码：

Person p2 = p;

上面把p变量的值赋给p2变量，也就是将p变量保存的地址赋给p2变量，这样p2变量和p变量将指向堆内存中同一个Person对象。
所以在java中所有涉及对象的传递都是引用的传递。
数组也是一种特殊的引用，链表也是。

treeNode 及题目中定义好的数据结构

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

上面是lintcode和leetcode常用的TreeNode数据结构，专用于二叉树操作。

此外题目中使用的链表和栈一般会给出定义。

java int最大值和最小值

有的时候偶尔会用到int类型的最大值和最小值。具体的数值很难记下来，java提供了它们的调用方法：

 System.out.println(Integer.MAX_VALUE);
 System.out.println(Integer.MIN_VALUE);

打印的结果如下：

2147483647
-2147483648

lintcode 图论问题举例

在严蔚敏的《数据结构与算法》一书中，说明了图有四种表示结构，其中主要两种是邻接矩阵和邻接链表。
在lintcode和leetcode图论问题的输入没有那么复杂，一般是一个二维数组。

如下图：

[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]

同时一般会附上一些话说明这个数据的含义。