LeetCode

2、两数相加

链表结构与树的结构类似,但是链表只有节点值和下一节点两个属性,因此除了递归,也可以通过循环来遍历。

3、无重复字符的最长子串

滑动窗口

237、删除链表中的节点

从链表里删除一个节点node的最常见方法是修改之前节点的next指针,使其指向之后的节点。

因为,我们无法访问我们想要删除的节点之前的节点,我们始终不能修改该节点的next指针。相反,我们必须将想要删除的节点的值替换为它后面节点中的值,然后删除它之后的节点。

因为我们知道要删除的节点不是列表的末尾,所以我们可以保证这种方法是可行的。

461、汉明距离

一、处理二进制的问题一般用位操作,包括&(与)、|(或)、~(非)、^(异或)、<<(左移)、>>(右移)、>>>(无符号右移)。

Java中所有的二进制操作符都是操作数字的补码。

二、Integer.bitCount(int a)用于计算a的二进制中1的个数。

617、合并二叉树

二叉树的结构类似链表,每个节点有值和左右子树三个属性,如果添加一个只有值的节点,不把它作为其他节点的子树,则该节点并不在树上。

657、机器人能否返回原点

一、switch case语句

switch(expression){
    case value :
        //语句
        break;  //可选
    case value :
        //语句
        break;  //可选
    //你可以有任意数量的case语句
    default :  //可选
        //语句
}
  • switch 语句中的变量类型可以是: byte、short、int 或者 char。从 Java SE 7 开始,switch 支持字符串 String 类型了,同时 case 标签必须为字符串常量或字面量。
  • switch 语句可以拥有多个 case 语句。每个 case 后面跟一个要比较的值和冒号。
  • case 语句中的值的数据类型必须与变量的数据类型相同,而且只能是常量或者字面常量。
  • 当变量的值与 case 语句的值相等时,那么 case 语句之后的语句开始执行,直到 break 语句出现才会跳出 switch 语句。
  • 当遇到 break 语句时,switch 语句终止。程序跳转到 switch 语句后面的语句执行。case 语句不必须要包含 break 语句。如果没有 break 语句出现,程序会继续执行下一条 case 语句,直到出现 break 语句。
  • switch 语句可以包含一个 default 分支,该分支一般是 switch 语句的最后一个分支(可以在任何位置,但建议在最后一个)。default 在没有 case 语句的值和变量值相等的时候执行。default 分支不需要 break 语句。

switch case 执行时,一定会先进行匹配,匹配成功返回当前 case 的值,再根据是否有 break,判断是否继续输出,或是跳出判断。

709、转换成小写字母

一、String.toLowerCase()。

二、String.toCharArray()把String转换成char[]。

三、char[]转String

char[] a = {'a', 'b', 'c'};
String s = new String(a);  //s为"abc"

四、ASCII代码

65~90:'A'~'Z'
97~122:'a'~'z'
'a' - 'A' = 32

804、唯一摩尔斯密码词

一、Set:无序,集合中的元素不重复。

计算不同元素的数量可以使用Set
Set.add(E)用来往Set中添加元素,重复的不会被添加进去
Set.size()返回Set中所有元素的数量

832、翻转图像

一、创建栈

Stack stack = new Stack();
stack.pop();  //返回值为Object类型

Stack<Integer> stack = new Stack<>();  //泛型
stack.pop();  //返回值为Integer类型

二、int和Integer

1. int是基本数据类型,Integer是int的包装类,因此Integer可用于泛型,而int不行。
2. 互相转换

int i = 0;
Ingeter j;

j = new Integer(i);  //int转Integer,装箱
System.out.println(i == j);  //false

i = j.intValue();  //Integer转int,拆箱
//Java7以后,可以自动实现int和Integer的转换,即自动装箱和自动拆箱
int i = 0;
Integer j = i;  //int转Integer,自动调用装箱方法
i = j;  //Integer转int,自动调用拆箱方法

938、二叉搜索树的范围和

一、二叉搜索树:它或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树。

二、二叉树遍历:二叉树有前、中、后三种遍历方式,因为树本身是根据递归来定义的,所以采用递归的方法实现三种遍历,不仅代码简洁且容易理解,但其开销也比较大,而若采用非递归方法实现三种遍历,则要用来模拟实现(递归也是用栈实现的)。

1. 前序遍历通俗的说就是从二叉树的根结点出发,当第一次到达结点时就输出结点数据,按照先向左在向右的方向访问。(根节点-左孩子-右孩子)

从根结点出发,则第一次到达结点A,故输出A;
继续向左访问,第一次访问结点B,故输出B;
按照同样规则,输出D,输出H;
当到达叶子结点H,返回到D,此时已经是第二次到达D,故不在输出D,进而向D右子树访问,D右子树不为空,则访问至I,第一次到达I,则输出I;
I为叶子结点,则返回到D,D左右子树已经访问完毕,则返回到B,进而到B右子树,第一次到达E,故输出E;
向E左子树,故输出J;
按照同样的访问规则,继续输出C、F、G;

则上图所示二叉树的前序遍历输出为:
ABDHIEJCFG

2. 中序遍历就是从二叉树的根结点出发,当第二次到达结点时就输出结点数据,按照先向左在向右的方向访问。(左孩子-根节点-右孩子)

从根结点出发,则第一次到达结点A,不输出A,继续向左访问,第一次访问结点B,不输出B;继续到达D,H;
到达H,H左子树为空,则返回到H,此时第二次访问H,故输出H;
H右子树为空,则返回至D,此时第二次到达D,故输出D;
由D返回至B,第二次到达B,故输出B;
按照同样规则继续访问,输出J、E、A、F、C、G;

则上图所示二叉树的中序遍历输出为:
HDIBJEAFCG

3. 后序遍历就是从二叉树的根结点出发,当第三次到达结点时就输出结点数据,按照先向左在向右的方向访问。(左孩子-右孩子-根节点)

从根结点出发,则第一次到达结点A,不输出A,继续向左访问,第一次访问结点B,不输出B;继续到达D,H;
到达H,H左子树为空,则返回到H,此时第二次访问H,不输出H;
H右子树为空,则返回至H,此时第三次到达H,故输出H;
由H返回至D,第二次到达D,不输出D;
继续访问至I,I左右子树均为空,故第三次访问I时,输出I;
返回至D,此时第三次到达D,故输出D;
按照同样规则继续访问,输出J、E、B、F、G、C,A;

则上图所示二叉树的中序遍历输出为:
HIDJEBFGCA

三、栈:栈是一种“先进后出”的一种数据结构,有压栈出栈两种操作方式,只能操作栈顶元素。

四、递归:自己调用自己,需要递归出口(递归终止的条件)和递归表达式(规律)。

977、有序数组的平方

一、Arrays.sort(int[] a)用于对指定的int型数组按数字升序进行排序。

二、^为异或,平方只能用*号

1021、删除最外层的括号

一、String.length()获取字符串长度。

二、String.charAt(int index)获取字符串第index位的字符,返回值为char类型。

三、String.Substring(int beginIndex, int endIndex)返回字符串的子字符串,beginIndex为起始索引(包括), 索引从 0 开始,endIndex为结束索引(不包括)。

四、String.concat(String s)用于将指定的字符串参数连接到字符串上。

String s1 = null;
String s2 = "";
String s3 = "abc";

s1.concat(s3);  //会报空指针异常
s3.concat(s2);  //因为s2为空,不会new一个新的String对象,返回s3指向的对象
s2.concat(s3);  //concat创建一个新的String对象,不改变s2的指向
s1 = s2.concat(s3);  //s1变为“abc”,s2仍为“”

策略模式

书中以模拟鸭子的应用为例引出策略模式,方便理解。

模拟鸭子游戏:游戏中会出现各种鸭子,一边游泳戏水,一边呱呱叫。此系统设计了一个鸭子超类(Superclass),并让各种鸭子继承此超类。

abstract class Duck {
/**
* 所有的鸭子都会呱呱叫(Quack)也会游泳(Swim),
* 所以由超类负责处理这部分的实现代码。
*/
public void quack() {};
public void swim() {};
//每一种鸭子的外观都不同,所以display()方法是抽象的。
public abstract void display();
}
/**
* 每个鸭子子类型(subtype)负责实现自己的display()行为,
* 在屏幕上显示其外观。
*/
class MallardDuck extends Duck {
@Override
public void display() {
//外观是绿头
}
}
/**
* 许多其他类型的鸭子继承Duck类。
*/
class RedheadDuck extends Duck {
@Override
public void display() {
//外观是红头
}
}
继续阅读“策略模式”

Java多线程机制

一、线程的基本概念
1. 线程是一个程序内部的顺序控制流。
2. 线程和进程的区别
①每个进程都有独立的代码和数据空间(进程上下文),进程间的切换会有较大的开销。
②线程可以看成是轻量级的进程,同一类线程共享代码和数据空间,每个线程有独立的运行栈和程序计数器(PC),线程切换的开销小。
③多进程:在操作系统中能同时运行多个任务(程序)
④多线程:在同一应用程序中有多个顺序流同时执行
3. Java的线程是通过java.lang.Thread类来实现的。
4. VM启动时会有一个由主方法(public static void main() {})所定义的线程。
5. 可以通过创建Thread的实例来创建新的线程。
6. 每个线程都是通过某个特定Thread对象所对应的方法run()来完成其操作的,方法run()称为线程体。
7. 通过调用Thread类的start()方法来启动一个线程。

二、线程的创建和启动
1. 可以有两种方法创建新的线程
①第一种

1.定义线程类实现Runnable接口
2.Thread myThread = new Thread(target); //target为Runnable接口类型
3.Runnable中只有一个方法:
public void run();用以定义线程运行体。
4.使用Runnable接口可以为多个线程提供共享的数据。
5.在实现Runnable接口的类的run方法定义中可以使用Thread的静态方法:
public static Thread currentThread();获取当前线程的引用。

②第二种

1.可以定义一个Thread的子类并重写其run方法,如:
class MyThread extends Thread {
public void run() {
...
}
}
2.然后生成该类的对象:
MyThread myThread = new MyThread(...);san
继续阅读“Java多线程机制”

Java流

一、Java流式输入/输出原理

在Java程序中,对于数据流的输入/输出操作以“流”(stream)方式进行。
JDK提供了各种各样的“流”类,用以获取不同种类的数据。
程序中通过标准的方法输入或输出数据。

二、输入/输出流的分类
1. java.io包中定义了多个流类型(类或抽象类)来实现输入/输出功能,可以从不同的角度对其进行分类:
①按数据流的方向不同可以分为输入流和输出流。
②按处理数据单元不同可以分为字节流和字符流。
③按功能不同可以分为节点流和处理流。
2. JDK所提供的所有流类型位于包java.io内都分别继承自以下四种抽象流类型:

字节流字符流
输入流InputStreamReader
输出流OutputStreamWriter
继续阅读“Java流”

Java常用类

一、字符串相关类
1. String类
①java.lang.String类代表不可变的字符序列。
②“xxxxx”为该类的一个对象。
③String类的常见构造方法:

  • String(String original):创建一个String对象为original的拷贝。
  • String(char[] value):用一个字符数组创建一个String对象。
  • String(char[] value, int offset, int count):用一个字符数组从offset项开始的count个字符序列创建一个String对象。

2. StringBuffer类
①java.lang.StringBuffer类代表可变的字符序列。
②StringBuffer和String类似,但StringBuffer可以对其字符串进行改变。
③StringBuffer类的常见构造方法:

  • StringBuffer():创建一个不包含字符序列的“空”的StringBuffer对象。
  • StringBuffer(String str):创建一个StringBuffer对象,包含与String对象str相同的字符序列。

二、基本数据类型包装类
1. 包装类(如:Integer,Double等)封装了一个相应的基本数据类型数值,并为其提供了一系列操作。
2. 以java.lang.Integer类为例,构造方法:

  • Integer(int value)
  • Integer(String s)
继续阅读“Java常用类”

Java数组

一、数组概述
1. 数组可以看成是多个相同类型数据组合,对这些数据的统一管理。
2. 数组变量属引用类型,数组也可以看成是对象,数组中的每个元素相当于该对象的成员变量。
3. 数组中的元素可以是任何数据类型,包括基本类型和引用类型。

二、一维数组
1. 一维数组的声明

type[] var; 

* type var[ ];也可以,但Java中推荐type[ ] var;
* Java语言中声名数组时不能指定其长度(数组中元素的个数),如int a[5];是非法的。
2. 数组对象的创建
Java中使用关键字new创建数组对象,格式为:
数组名 = new 数组元素的类型[数组元素的个数];
* 例如:

public class Test {
public static void main(String[] args) {
int[] s;
s = new int[5];
}
}

* 注意:元素为引用数据类型的数组中的每一个元素都需要实例化。

继续阅读“Java数组”

Java异常处理

一、Java异常的概念
1. Java异常是Java提供的用于处理程序中错误的一种机制。
2. 所谓错误是指在程序运行的过程中发生的一些异常事件(如:除0溢出,数组下标越界,所要读取的文件不存在)。
3. 设计良好的程序应该在异常发生时提供处理这些错误的方法,使得程序不会因为异常的发生而阻断或产生不可预见的结果。
4. Java程序的执行过程中如出现异常事件,可以生成一个异常类对象,该异常对象封装了异常事件的信息并将被提交给Java运行时系统,这个过程称为抛出(throw)异常。
5. 当Java运行时系统接收到异常对象时,会寻找能处理这一异常的代码并把当前异常对象交给其处理,这一过程称为捕获(catch)异常。

二、Java异常的分类

Java中定义了很多异常类,这些类对应了各种各样可能出现的异常事件。
  • Error:称为错误,由Java虚拟机生成并抛出,包括动态链接失败、虚拟机错误等,程序对其不做处理。
  • Exception:所有异常类的父类,其子类对应了各种各样可能出现的异常事件,一般需要用户显式的声明或捕获。
  • Runtime Exception:一类特殊的异常,如被0除、数组下标超范围等,其产生比较频繁,处理麻烦,如果显式的声明或捕获将会对程序可读性和运行效率影响很大。因此由系统自动检测并将它们交给缺省的异常处理程序(用户可不必对其处理)。
继续阅读“Java异常处理”

Java容器

一、容器的概念
Java API所提供的一系列类的实例,用于在程序中存放对象。位于java.util包内。

二、容器框架图
Java 集合框架主要包括两种类型的容器,一种是集合(Collection),存储一个元素集合,另一种是图(Map),存储键/值对映射。Collection 接口又有 3 种子类型,List、Set 和 Queue,再下面是一些抽象类,最后是具体实现类,常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

继续阅读“Java容器”

Java面向对象

一、引用
1. Java语言中除基本类型之外的变量类型都称之为引用类型。
2. Java中的对象是通过引用对其操作的。
* A a = new A( ); 中,a是对象的引用,位于栈内存,指向位于堆内存的对象的实体,也就是
new A( )。

二、构造方法
1. 构造方法与类同名且没有返回值。
2. 当没有指定构造方法时,编译器为类自动添加形如 类名( ) { } 的构造方法。

三、方法的重载
1. 方法的重载是指一个类中可以定义有相同的名字,但参数不同的多个方法。调用时,会根据不同的参数表选择对应的方法。
2. 构造方法也可以重载。

四、类的继承
1. Java中使用extends关键字实现类的继承机制。
2. 通过继承,子类自动拥有了基类(superclass)的所有成员(成员变量和方法)。
3. Java只支持单继承,不允许多继承。
* 一个子类只能有一个基类,一个基类可以派生出多个子类。

继续阅读“Java面向对象”

Java特殊关键字

一、this
1. 在类的方法定义中使用的this关键字代表使用该方法的对象的引用。
2. 当必须指出当前使用方法的对象是谁时要使用this。
3. 有时使用this可以处理方法中成员变量和参数重名的情况。
4. this可以看作是一个变量,它的值是当前对象的引用。

二、super
1. 在Java类中使用super来引用基类的成分。

三、static
1. 在类中,用static声明的成员变量为静态成员变量,它为该类的公用变量,在第一次使用时被初始化,对于该类的所有对象来说,static成员变量只有一份。
2. 用static声明的方法为静态方法,在调用该方法时,不会将对象的引用传递给它,所以在static方法中不可访问非static的成员。
* 静态方法不再是针对于某个对象调用,所以不能访问非静态成员。
3. 可以通过对象引用或类名(不需要实例化)访问静态成员。

四、final
1. final的变量的值不能够被改变
final的成员变量
final的局部变量(形参)
2. final的方法不能被重写
3. final的类不能够被继承

五、abstract
1. 用abstract关键字来修饰一个类时,这个类叫做抽象类;用abstract关键字来修饰一个 方法时,这个方法叫做抽象方法。
2. 含有抽象方法的类必须被声明为抽象类,抽象类必须被继承,抽象方法必须被重写。
3. 抽象类不能被实例化。
4. 抽象方法只需声明,而不需实现。