算法竞赛Java数据结构与算法类详解

// 定义
String str = "Hello World!";

char[] charArray = { 'A', 'B', 'C' };
String strFromChar = new String(charArray);

// 遍历
for (int i = 0; i < str.length(); i++)
    System.out.print(str.charAt(i));
System.out.println();

for (char c: str.toCharArray())  // toCharArray将String转为字符数组
    System.out.print(c);
System.out.println();

// 常用方法
str.charAt(0);  // H，返回第0个字符
str.compareTo("G");  // 1，比较字符串，如果大于返回1，小于返回-1，否则返回0
str.equals("Hello World!");  // true，Java中比较两个字符串值是否相等必须用equals
str.startsWith("He");  // true，判断是否以"He"开头
str.endsWith("d!");  // true，判断是否以"d!"结尾
str.indexOf('o');  // 4，返回'o'第一次出现的位置，若不存在返回-1
str.indexOf('o', 5);  // 7，返回'o'从下标5开始第一次出现的位置，若不存在返回-1
str.lastIndexOf('o');  // 7，返回'o'最后出现的位置，若不存在返回-1
str.lastIndexOf('o', 6);  // 4，返回'o'在下标6之前的字符串中最后出现的位置，若不存在返回-1
str.replace('o', 'x');  // Hellx Wxrld!，将'o'替换成'x'
str.split(" ");  // [Hello, World!]，以" "进行分割，返回分割后的数组，支持正则表达式
str.substring(6, 9);  // Wor，返回[6, 9)的字串，如果不指定第二个下标默认为末尾
str.toLowerCase();  // hello world!，将所有字母转为小写后返回
str.toUpperCase();  // HELLO WORLD!，将所有字母转为大写后返回

// 定义
StringBuilder strBuilder = new StringBuilder(str);

// 遍历
for (int i = 0; i < strBuilder.length(); i++)
    System.out.print(strBuilder.charAt(i));
System.out.println();

// 常用方法
strBuilder.append("A");  // 在末尾追加字符串/字符/数字
strBuilder.reverse();  // 翻转字符串
strBuilder.delete(0, 1);  // 删除[0, 1)中的字符串
strBuilder.insert(6, "A");  // 在下标6的位置插入字符串/字符/数字
strBuilder.replace(0, 7, "Hello");  // 将[0, 7)中的字符串替换为"Hello"
strBuilder.toString();  // 转换回String

// 定义
int[] arr = { 2, 4, 3, 1, 5 };
int[][] arr2d = {{ 1, 2 }, { 3, 4 }};
Integer[] arrInteger = { 2, 4, 3, 1, 5 };

// 遍历
for (int i = 0; i < arr.length; i++)
    System.out.print(arr[i] + " ");
System.out.println();

for (int x: arr)
    System.out.print(x + " ");
System.out.println();

// 常用方法
Arrays.sort(arr);  // 从小到大排序
Arrays.sort(arrInteger, (x, y) -> y - x);  // 从大到小排序，必须用Integer对象
Arrays.binarySearch(arr, 3);  // 返回2，对排好序的数组二分查找
Arrays.equals(arr, arr);  // 返回true，判断两个数组是否相等
Arrays.fill(arr, 0);  // 用0填充数组所有元素
Arrays.toString(arr);  // 返回[0, 0, 0, 0, 0]，将数组的第一维转换成字符串形式
Arrays.deepToString(arr2d);  // 返回[[1, 2], [3, 4]]，递归转换数组的每一维，可用于二维及以上的数组

// 定义
ArrayList<Integer> v = new ArrayList<>();  // <>中只能为引用数据类型
ArrayList<Integer> v = new ArrayList<>(Arrays.asList(1, 2, 3));  // 初始化时赋值，当前为[1, 2, 3]
List<Integer> v = Arrays.stream(new int[] { 1, 2, 3 }).boxed().collect(Collectors.toList());  // int[]转List，注意只能为List，不能用ArrayList

// 遍历
for (int i = 0; i < v.size(); i++)  // 传统for循环
    System.out.printf("%d ", v.get(i));
System.out.println();

for (int x: v)  // forEach循环，推荐这种写法
    System.out.printf("%d ", x);
System.out.println();

for (Iterator<Integer> it = v.iterator(); it.hasNext();)  // 迭代器
    System.out.printf("%d ", it.next());
System.out.println();

for (ListIterator<Integer> it = v.listIterator(); it.hasNext();)  // 列表迭代器
    System.out.printf("%d ", it.next());
System.out.println();

v.stream().forEach(x -> System.out.printf("%d ", x));  // Java8的Stream API和Lambda表达式
System.out.println();

// 常用方法
v.add(4);  // 在尾部添加4，当前为[1, 2, 3, 4]
v.add(1, 5);  // 在下标1处添加5，当前为[1, 5, 2, 3, 4]
v.remove(4);  // 删除下标4处的元素，当前为[1, 5, 2, 3]
v.set(0, 4);  // 将下标0处的元素置为4，当前为[4, 5, 2, 3]
v.subList(0, 2);  // 返回[4, 5]，截取[0, 2)的子列表
v.indexOf(5);  // 返回1，获取元素5第一次出现的下标，若不存在返回-1
v.isEmpty();  // 返回false，判断是否为空
v.contains(2);  // 返回true，判断是否含有元素2
v.sort(Comparator.naturalOrder());  // 从小到大排序，当前为[2, 3, 4, 5]
v.sort(Comparator.reverseOrder());  // 从大到小排序，当前为[5, 4, 3, 2]
v.addAll(Arrays.asList(1, 2));  // 添加另一个Collection对象，当前为[5, 4, 3, 2, 1, 2]
Collections.addAll(v, 7, 8, 9);  // 添加任意数量的元素，当前为[5, 4, 3, 2, 1, 2, 7, 8, 9]
Collections.reverse(v);  // 翻转List，当前为[9, 8, 7, 2, 1, 2, 3, 4, 5]
ArrayList<Integer> t = (ArrayList<Integer>)v.clone();  // 复制一份，和原ArrayList不是同一份

// List转换为数组
Integer[] a = new Integer[v.size()];  // 必须为包装类
v.toArray(a);

Integer[] b = v.toArray(new Integer[0]);  // 效果同上

int[] c = v.stream().mapToInt(Integer::valueOf).toArray();  // 必须为基本类型，mapToInt()将Stream<Integer>转换成IntStream

// 定义
LinkedList<Integer> v = new LinkedList<>(Arrays.asList(1, 2, 3));

// 常用方法
v.addLast(4);  // 在尾部添加4，当前为[1, 2, 3, 4]
v.addFirst(5);  // 在首部添加5，当前为[5, 1, 2, 3, 4]
v.removeLast();  // 删除并返回尾部元素，当前为[5, 1, 2, 3]
v.removeFirst();  // 删除并返回首部元素，当前为[1, 2, 3]
v.getFirst();  // 返回首部元素1
v.getLast();  // 返回尾部元素3

// 定义
HashSet<Integer> st = new HashSet<>();
HashSet<Integer> st = new HashSet<>(Arrays.asList(1, 2, 3));

// 遍历
for (int x: st)  // forEach循环，推荐这种写法
    System.out.printf("%d ", x);
System.out.println();

for (Iterator<Integer> it = st.iterator(); it.hasNext();)  // 迭代器
    System.out.printf("%d ", it.next());
System.out.println();

st.stream().forEach(x -> System.out.printf("%d ", x));  // Java8的Stream API和Lambda表达式
System.out.println();

// 常用方法
st.add(4);  // 添加元素，当前为{1, 2, 3, 4}
st.remove(3);  // 删除元素，当前为{1, 2, 4}
st.contains(3);  // 返回false，判断是否存在3
st.size();  // 返回3，获取集合的元素数量
st.isEmpty();  // 返回false，判断是否为空
st.clear();  // 清空元素

// 定义
TreeSet<Integer> st = new TreeSet<>();
TreeSet<Integer> st = new TreeSet<>(Arrays.asList(3, 2, 1, 2));

// 常用方法
st.ceiling(3);  // 返回3，查找大于等于3的最小的数，不存在则返回null
st.floor(3);  // 返回3，查找小于等于3的最大的数，不存在则返回null
...其余同HashSet

// 定义
HashMap<String, Integer> mp = new HashMap<>();
HashMap<String, Integer> mp = new HashMap<String, Integer>() {{  // 可能会导致一些未预期的副作用，因为它实际上创建了一个匿名子类
    put("ABC", 1);
    put("DEF", 2);
}};

// 遍历
for (String k: mp.keySet())  // 遍历key
    System.out.println(k);

for (int v: mp.values())  // 遍历value
    System.out.println(v);

for (Map.Entry<String, Integer> e: mp.entrySet())  // 遍历key-value，推荐这种写法
    System.out.println(e.getKey() + " " + e.getValue());

for (Iterator it = mp.entrySet().iterator(); it.hasNext();) {  // 迭代器
    Map.Entry e = (Map.Entry)it.next();
    System.out.println(e.getKey() + " " + e.getValue());
}

// 常用方法
mp.put("YYJ", 666);  // 添加键值对，如果键已经存在，就替换原来的值，当前为{ABC=2, DEF=1, YYJ=666}
mp.get("YYJ");  // 返回666，获取某个key对应的value，如果key不存在返回null
mp.remove("YYJ");  // 删除指定的key及其对应的value，如果key不存在返回null，当前为{ABC=2, DEF=1}
mp.containsKey("YYJ");  // 返回false，判断是否包含指定的key
mp.containsValue(1);  // 返回true，判断是否包含指定的value
mp.size();  // 返回2，获取键值对的数量
mp.clear();  // 清空键值对
mp.isEmpty();  // 返回true，判断是否为空

// 定义
TreeMap<String, Integer> mp = new TreeMap<>();
TreeMap<String, Integer> mp = new TreeMap<String, Integer>() {{  // 可能会导致一些未预期的副作用，因为它实际上创建了一个匿名子类
    put("DEF", 1);
    put("ABC", 2);
}};

// 常用方法
Map.Entry<String, Integer> ceiling = mp.ceilingEntry("AAA");  // 查找键大于等于"AAA"的最小的键值对，不存在则返回null
System.out.println(ceiling.getKey() + ": " + ceiling.getValue());  // ABC: 2
Map.Entry<String, Integer> floor = mp.floorEntry("DEG");  // 查找键小于等于"DEG"的最大的键值对，不存在则返回null
System.out.println(floor.getKey() + ": " + floor.getValue());  // DEF: 1
mp.ceilingKey("A");  // 返回ABC，查找键大于等于"A"的最小的键，不存在则返回null
mp.floorKey("A");  // 返回null，查找键小于等于"A"的最大的键，不存在则返回null
...其余同HashMap

Deque<String> stk = new ArrayDeque<>();

for (String s: "This is stack".split(" "))
    stk.push(s);

while (!stk.isEmpty())
    System.out.print(stk.pop() + " ");  // stack is This

Queue<Integer> Q = new LinkedList<>();

for (int i = 0; i < 5; i++)
    Q.offer(i);

System.out.println(Q);  // [0, 1, 2, 3, 4]

while (Q.peek() != null)
    System.out.print(Q.remove() + " ");  // 0 1 2 3 4

PriorityQueue<Integer> Q = new PriorityQueue<>();  // 默认是升序

for (int i = 5; i > 0; i--)
    Q.offer(i);

while (Q.peek() != null)
    System.out.print(Q.remove() + " ");  // 1 2 3 4 5
System.out.println();

List<Integer> nums = Arrays.asList(2, 5, 1, 3, 7);
PriorityQueue<Integer> RQ = new PriorityQueue<>(Collections.reverseOrder());  // 逆序
RQ.addAll(nums);

while (RQ.peek() != null)
    System.out.print(RQ.remove() + " ");  // 7 5 3 2 1
System.out.println();

package com.yyj;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> numsList = new ArrayList<>(Arrays.asList(1, 2, 3, 3));
        Set<Integer> numsSet = new HashSet<>(Arrays.asList(1, 2, 3, 3));

        display(numsList.iterator());  // 1 2 3 3
        display(numsSet.iterator());  // 1 2 3
        display(numsList);  // 1 2 3 3
        display(numsSet);  // 1 2 3
    }

    public static void display(Iterator<Integer> it) {
        while (it.hasNext())
            System.out.print(it.next() + " ");
        System.out.println();
    }

    public static void display(Collection<Integer> nums) {
        for (Integer x: nums)
            System.out.print(x + " ");
        System.out.println();
    }
}

import java.util.Arrays;

class Data implements Comparable<Data> {  // 实现Comparable<T>接口
    int x;
    String s;

    Data(int x, String s) {
        this.x = x;
        this.s = s;
    }

    @Override
    public int compareTo(Data t) {  // 重写compareTo(T obj)方法
        return t.x - x;  // 若t.x比当前对象的x小则返回-1，表示根据x从大到小排序
    }

    @Override
    public String toString() {
        return String.format("[%d, %s]", x, s);
    }
}

public class SortObjectArrays {
    public static void main(String[] args) {
        Data[] datas = { new Data(4, "Hello"), new Data(1, "Java"), new Data(6, "C++") };
        Arrays.sort(datas);
        Arrays.stream(datas).forEach(System.out::println);

        /*
         * [6, C++]
         * [4, Hello]
         * [1, Java]
         */
    }
}