leetcode代码练习——Java的数据结构（具体使用）

注：Java中所有的泛型必须是引用类型 如<Integer>而不是<int>
java提供的数学方法：
求最大值Math.max(10,15)，最小值Math.min(10,15)
看取值范围：

int范围:-2^31-2^31-1   
double范围:-2^63-2^63-1
long范围:-2^63-2^63-1
1
2
3

-231 <= Node.val <= 231 - 1 要想有个比取值范围内都大的数double maxx=Double.MAX_VALUE
Integer.MAX_VALUE,Double.MAX_VALUE,Float.MAX_VALUE,Long.MAX_VALUE,Byte.MAX_VALUE

打印：for (Integer number : innerList) {
System.out.print(number + " ");
}
&& 符号有所谓的“短路原则”，当 A && B 出现时，如果A经判断是假，那么B表达式将不会获得执行或被判断的机会。直接结果就为假。
|| 前真后面就不去判断了，|前真后也会去判断

数组定义需要开空间，可以这样根据题目给出的大小开空间：

int s1=text1.length(),s2=text2.length();
int[][] dp=new int[s1+1][s2+1];//用定义的变量开空间
1
2

1.Map基本操作

Map<String, Integer> map这是声明Map对象指明键值对类型为String,
Map<String, Integer> map = new HashMap<>();创建一个实例并赋值给map

 Map<String, List<String>> map = new HashMap<String, List<String>>();//value为一个String的列表
1

定义：Map<Integer,Integer> map= new HashMap<>();
添加：map.put(‘aa’,‘aaa’)
访问： map.get(‘aa’) 方法来获取 key 对应的 value:
删除：map.remove(‘aa’)
计算大小：map.size()
迭代：map.keySet()、map.values()
map.containsKey(‘aa’) 方法检查 hashMap 中是否存在指定的 key 对应的映射关系。存在返回 true，否则返回 false。

Map<Integer,Integer> map= new HashMap<>();
 	// 输出 key 和 value
        for (Integer i : map.keySet()) {
            System.out.println("key: " + i + " value: " + map.get(i));
        }
   // 返回所有 value 值
        for(String value: map.values()) {
          // 输出每一个value
          System.out.print(value + ", ");
        }      
1
2
3
4
5
6
7
8
9
10

1.1.map的value值转List

ArrayList<List<String>>(map.values());
1

HashSet（需要找是否已经包含了的时候用）

里面的元素无序，由于无序所以元素依旧是不能重复的，而且只能用for-each循环或迭代器

HashSet<String> set = new HashSet<String>();//定义
set.add("Tom");//添加
set.size();
set.isEmpty();
set.clear();//清除集合set中所有元素
boolean flag = set.contains("Tom");//将contains()判断结果赋给flag
boolean flag = set.remove("Tom");//将set集合中“Tom”元素除去并将是否成功的布尔值赋给flag

for (String name : set) {
	System.out.println(name);
}

Iterator<String> iterator = set.iterator();//创建Iterator<>对象
while(iterator.hasNext()) {
	System.out.println(iterator.next());
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.List操作

定义：

List<String> list = new ArrayList<String>();
List<List<Integer>> ret = new ArrayList<List<Integer>>();
1
2

List<String> list = new ArrayList<String>();
//添加元素.
list.add("Tom");
list.add("Jam");
list.add("Alix");

//获取元素.
String str = list.get(0);

//删除元素.
list.remove(1);
list.remove("Alix");

//遍历元素.
for (String s: list) {
    System.out.println(s);
}
 //判断某一个元素是否在list中
list.contains(name)
 //根据索引改变list中某一个值.
list.set(0, "Tom");
//返回元素值等于2的索引.
System.out.println(list.indexOf(2));
 //利用subList()截取， 然后给num.
 num = list.subList(1, 4);
 //判断是否为空
 arrayList.isEmpty()
  //转化成iterator对象.
Iterator it = arrayList.iterator();
 while(it.hasNext) {
     Object obj = it.next();
     System.out.println(obj);
 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

list转为String

String str = "";
str = list.toString();
1
2

list转为数组

String[] str = list.toArray();
for (String s: str) {
    System.out.println(str);
}
1
2
3
4

list排序功能

Arrays.sort(arr);//将字母排序
1

2.1 list和数组的区别

数组：
固定长度的容器，可以在其中存储同一类型的数据。数组在Java中是一个对象，可以通过索引访问其中的元素。
定义一个数组：

数据类型[] 数组名 = new 数据类型[数组长度];
int[] a = new int[5];
String str = new String[5];  str[0]='aa'; str[1]='bb';

数组定义时赋值
int[] ary1 = {1,2,3};//一维数组
int next[][]={{0,1},{1,0},{0,-1},{-1,0}};//二维数组
1
2
3
4
5
6
7

list：
List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。
（1）LinkedList实现了List接口，允许null元素。LinkedList底层采用了双向链表来存储数据，每个节点都存储着上一个节点和下一个节点的地址以及本节点的数据。
此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

（2）ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList底层采用动态数组的存储方式，遍历效率非常高，ArrayList是线程不安全的。
size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

ArrayList和LindedList的区别：

1. ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2. 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3. 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

总结：
1、如果涉及到堆栈、队列等操作，应该考虑使用List，对于需要快速插入、删除的元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。
2、如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。
3、要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。
4、尽量返回接口而非实际的类型，如返回**List而非ArrayList，**这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

Java数组，List互相转换

（1）数组转换成 List 集合:
Arrays.asList(strArray) 方式,将数组转换List后，不能对List增删，只能查改，否则抛异常。

import java.util.Arrays;

// 转换数组对象
Long[] arr = new Long[]{10L, 20L, 30L};
List<Long> list1 = Arrays.asList(arr);

// 转换数组常量
List<String> list2 = Arrays.asList("123", "456", "789");

1
2
3
4
5
6
7
8
9

要想能修改可以这种：

private void testArrayCastToListEfficient(){
		String[] strArray = new String[2];
		ArrayList< String> arrayList = new ArrayList<String>(strArray.length);//创建一个ArrayList
		Collections.addAll(arrayList, strArray);//把值赋过去
		arrayList.add("1");
		System.out.println(arrayList);
	}

1
2
3
4
5
6
7
8

（2）List 集合转数组
.toArray

// 方式1（推荐）
Long[] array = list.toArray(new Long[0]);//10L, 20L, 30L

// 方式2
String[] array = (String[]) list.toArray();

1
2
3
4
5
6

2.2栈和队列

队列的实现—利用Queue接口
堆栈的实现—利用Deque接口
使用ArrayDeque类实例化队列和栈
队列：

Queue<String> queue = new LinkedList<String> ();//队列定义
   queue.offer("x");//增加
   queue.offer("u");
   queue.offer("e");
   while(!queue.isEmpty()){//判断是否为空
       System.out.print(queue.poll()+" ");//移除
   }
1
2
3
4
5
6
7

堆栈：

Deque<String> stack= new LinkedList<String>();//堆栈
    stack.push("x");
    stack.push("u");
    stack.push("e");
    while(!stack.isEmpty()){
        System.out.print(stack.pop());
    }

1
2
3
4
5
6
7
8

使用ArrayDeque类实例化队列和栈：

该类是Deque接口的大小可变数组的实现。数组双端队列没有容量限制；它们可根据需要增加以支持使用。它们不是线程安全的；在没有外部同步时，它们不支持多个线程的并发访问。禁止 null 元素。此类很可能在用作堆栈时快于 Stack，在用作队列时快于 LinkedList。
操作 队列方法
插入 offer(e)
移除 poll()
检查 peek()
操作 堆栈方法
插入 push(e)
移除 pop()
检查 peek()

new一个ArrayDeque对象 既能当堆栈又能当队列。

ArrayDeque<String> stack = new ArrayDeque<String> ();
   stack.push("x");
   stack.push("u");
   stack.push("e");
   while(!stack.isEmpty()){
       System.out.print(stack.pop());
   }

1
2
3
4
5
6
7
8

3.String,char转换

String需要转char 列表

“apple”->[‘a’,‘p’,‘p’,‘l’,‘e’]

char[] arr = str.toCharArray();//将String中的字母转成char放列表里
Arrays.sort(arr);//将字母排序
1
2

char列表转String

String key = new String(arr);
1

charAt()方法

java中，charAt()方法用于返回指定索引处的字符。
因为String不能s[i]这样访问字符，所以只能s.charAt(i)

String s = "helloworld";
char what =s.charAt(5);//o
1
2