Java算法做题中用到的-数据结构（对应C++的STL）【java中各种集合的api方法】

一、数组List

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

ArrayList的方法

add
remove（参数是角标）【 cur.remove(cur.size()-1);】
get
indexOf() 返回指定元素下标
contains()
toArray()

LinkedList的方法

排序

方法一：数组排序Comparator cmp

// import java.util.*;

class Solution {

    static Comparator<Integer> cmp = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1,Integer o2) {
            String s1 = o1+""+o2;
            String s2 = o2+""+o1;
            return s1.compareTo(s2);
        }
    };

    public String printMinNumber(int[] nums) {
        String res = "";
        Integer[] list = new Integer[nums.length];
        int n = nums.length;
        for(int i = 0; i < n; i++){
            list[i] = nums[i];
        }
        Arrays.sort(list,cmp);
        for(int i = 0; i < n; i++){
            res += list[i]+"";
        }
        return res;

    }
}
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

方法二：List排序 Collections.sort(arrayMap);

去重 arrayMap = new ArrayList<>(new HashSet<>(arrayMap));

indexof的时间复杂度是 o(N)

二、优先队列 PriorityQueue

peek()//返回队首元素
poll()//返回队首元素，队首元素出队列
add()//添加元素
size()//返回队列元素个数
isEmpty()//判断队列是否为空，为空返回true,不空返回false
1
2
3
4
5

static Comparator<Integer> cmp = new Comparator<Integer>() {
      public int compare(Integer e1, Integer e2) {
        return e2 - e1;
      }
    };
public static void main(String[] args) {
        //不用比较器，默认升序排列
        Queue<Integer> q = new PriorityQueue<>();
        q.add(3);
        q.add(2);
        q.add(4);
        while(!q.isEmpty())
        {
            System.out.print(q.poll()+" ");
        }
        /**
         * 输出结果
         * 2 3 4 
         */
        //使用自定义比较器，降序排列
        Queue<Integer> qq = new PriorityQueue<>(cmp);
        qq.add(3);
        qq.add(2);
        qq.add(4);
        while(!qq.isEmpty())
        {
            System.out.print(qq.poll()+" ");
        }
        /**
         * 输出结果
         * 4 3 2 
         */
}
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

PriorityQueue<Integer> queue1 = 
		new PriorityQueue<Integer>();
queue1.add(10);
queue1.add(8);
System.out.println(queue1.poll()); // 8
PriorityQueue<Integer> queue2 = 
		new PriorityQueue<Integer>((o1,o2) -> o1 - o2);
queue2.add(10);
queue2.add(8);
System.out.println(queue2.poll()); // 8
PriorityQueue<Integer> queue3 = 
		new PriorityQueue<Integer>((o1,o2) -> o2 - o1);
queue3.add(10);
queue3.add(8);
System.out.println(queue3.poll()); // 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三、 String

1. cpp中的s[i] 在java中是 s.charAt(i);

四、超时问题

1. 使用print 和 println 别用 printf
2. 使用二分

五、类排序问题（数组用arrays list用collections）

1. 类自身实现 Comparable 实现comparaTo方法

package compare;

public class Goods implements Comparable{
    private String name;
    private double price;

    public Goods() {
    }
    
    public Goods(String name, double price) {
        this.name = name;
        this.price = price;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    @Override
    public String toString() {
        return "Goods{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }

    //重写compareTo方法，并指明排序的方式：先按价格从低到高排序，再按名称从高到低排序
    @Override
    public int compareTo(Object o) {
        //instanceof ，用来测试对象0是否为Goods类的实例
       if (o instanceof Goods){
           Goods goods = (Goods) o;
           if (this.price > goods.price){
               return 1;
           } else if (this.price < goods.price){
               return -1;
           }else {
               return -this.name.compareTo(goods.name);
           }
       }
       throw new RuntimeException("输入类型错误，无法比较");
    }
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

2. 定制排序 Comparator

String[] str = new String[]{"aa","kk","dd","cc"};
Arrays.sort(str, new Comparator<String>() {
    @Override
    //从大到小进行排序
    public int compare(String o1, String o2) {
        return -o1.compareTo(o2);
    }
});
System.out.println(Arrays.toString(str));//[kk, dd, cc, aa]
1
2
3
4
5
6
7
8
9

3. 简化Comparator

//Arrays.sort(range, 0, n, (o1, o2) -> o1.r - o2.r);
1

六、Deque

addFirst(): 向队头插入元素，如果元素为空，则发生NPE(空指针异常)
addLast(): 向队尾插入元素，如果为空，则发生NPE
offerFirst(): 向队头插入元素，如果插入成功返回true，否则返回false
offerLast(): 向队尾插入元素，如果插入成功返回true，否则返回false
removeFirst(): 返回并移除队头元素，如果该元素是null，则发生NoSuchElementException
removeLast(): 返回并移除队尾元素，如果该元素是null，则发生NoSuchElementException
pollFirst(): 返回并移除队头元素，如果队列无元素，则返回null
pollLast(): 返回并移除队尾元素，如果队列无元素，则返回null
getFirst(): 获取队头元素但不移除，如果队列无元素，则发生NoSuchElementException
getLast(): 获取队尾元素但不移除，如果队列无元素，则发生NoSuchElementException
peekFirst(): 获取队头元素但不移除，如果队列无元素，则返回null
peekLast(): 获取队尾元素但不移除，如果队列无元素，则返回null
pop(): 弹出栈中元素，也就是返回并移除队头元素，等价于removeFirst()，如果队列无元素，则发生NoSuchElementException
push(): 向栈中压入元素，也就是向队头增加元素，等价于addFirst()，如果元素为null，则发生NPE，如果栈空间受到限制，则发生IllegalStateException

七、输入输出

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter wt = new BufferedWriter(new OutputStreamWriter(System.out));
bf.readLine()
wt.write((i - n) + " ");
wt.flush();
wt.close();
bf.close();
1
2
3
4
5
6
7

八、Collections

文章

九、Queue

十、Set

十一、Stack