用于算法题的常用Java工具

Array & List

// 排序
int[] array = {3, 4, 1, 2, 5};
Arrays.sort(array);    // T = O(n * log2(n))
List<Integer> list = Arrays.asList(array);
Collections.sort(list);  // 使用ArrayList的话,T = O(n * log2(n))
list.sort(null);         // 上面的函数调用这个函数,其内部实现方法是先把列表转换为数组再排序
                         // 因为如果是链表,直接排序的时间复杂度为O((n ^ 2) * log2(n))。

// array和list转换
List<String> list = Arrays.asList(array);
String[] array = list.toArray(new String[0]);

// max & min
Map<String, Integer> map = ...;
// 找出具有最大value值的key
String max = Collections.max(
        map.entrySet(),
        Comparator.comparingInt(Map.Entry<String, Integer>::getValue)).getKey();
// 或者
max = Collections.max(
        map.entrySet(),
        Map.Entry.comparingByValue()).getKey();
// 这些其实没什么必要,面试时记不住就用循环解决

// string
String str = "aaa bbb ccc";
String[] parts = str.split(" ");      // {"aaa", "bbb", "ccc"}
String[] parts1 = str.split(" ", 2);  // {"aaa", "bbb ccc"}
String[] parts2 = str.split(" ", -1); // -1的意思是不要删除最后面的空字符

另外,Java的Collection由于只接受对象形式的元素(就是说不能用基本数据类型的元素),加上其维护代码的开销,性能往往比数组差。比如int[]比ArrayList<Integer>要快,尤其是在比拼算法所用时间的情况下尤为明显。

Stack

“Stack”是Java中关于栈的旧API。现在应该使用Deque。LIFO。

Deque<String> stack = new ArrayDeque<>();
stack.push("abc");
String s1 = stack.peek();
String s2 = stack.pop();

Queue

普通的队列,在Java中一般是以LinkedList的方式实现的。Queue常用于广度优先搜索算法。FIFO。

Queue<String> queue = new LinkedList<>();
queue.offer("abc");       // enqueue
String s = queue.poll();  // dequeue

Priority Queue

Priority Queue常被用来在不排序的情况下取最大的或最小的几个值。如果有n个数据元素,要取前k个(k<n)最小的元素,用排序法的话T=O(n * log2(n)),而用Priority Queue的话,则为T=O(n * log2(k)),这样就能快一些。方法是往queue里逐个放入数据元素,如果queue的长度大于k,则把一个元素移出(也就是最大的那个或最小的那个,取决于Priority Queue的设定方式。这样,剩下的就是k个最小的或最大的元素。

Priority Queue的时间复杂度:enqueue和dequeue操作为O(log2(k)),查看(peek)最前面的元素为O(1)。

PriorityQueue<Elem> queue = new PriorityQueue<>(Comparator.comparingInt(Elem::getValue)); 

for (Elem elem : list) {
    queue.offer(elem);
    if (queue.size() > k) {
        queue.poll();
    }
}

上面的代码中的queue.poll()会把Elem.getValue()返回值最小的元素移出。要想移出最大的,则改为Comparator.comparingInt(elem -> -elem.getValue())。

另一个应用的例子:合并k个有序列表。一般的算法为取各列表的第一个元素,找到最小的那个,加入新列表,然后把最小元素的下一个元素作为它原所属列表的第一个元素。不断重复,直到用完所有列表的元素。这样做的话,T=O(N * k),其中N为所有列表中的元素总数,k为列表个数。因为每次从k各元素中取最小值为O(k),而对所有元素都要进行一次这样的操作,故为O(N * k)。

可以用Priority Queue进行优化:把各列表的第一个元素加入queue;取出最前面的元素加入新列表,并把它的下一个元素加入queue。这样的话,每次enqueue和dequeue操作为O(log2(k)),对所有元素做这种操作,总体的时间复杂度T=O(N * log2(k)),比上述的O(N * k)要快。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }

    if (lists.length == 1) {
        return lists[0];
    }

    PriorityQueue queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));

    for (ListNode node : lists) {
        if (node == null) {
            continue;
        }

        queue.offer(node);
    }

    ListNode dummyHead = new ListNode(0);
    ListNode prev = dummyHead;

    while (!queue.isEmpty()) {
        ListNode node = queue.poll();

        prev.next = node;
        prev = node;

        if (node.next != null) {
            queue.offer(node.next);
            node.next = null;
        }
    }

    return dummyHead.next;
}

题外话:另一种十分简单的解法是Divide & Conquer:合并两个有序列表(按第一种思路)的时间复杂度是O(n),n是两个列表中的元素总和。可以把k个列表两两分组,并将其合并成一组更长的列表;然后继续两两分组合并,直到最后只剩一个列表为止。这看起来跟体育比赛分组类似,没什么特别的,但观察一下的话,一共有log2(k)轮的分组,每轮都要遍历所有N个元素,因此,时间复杂度也是O(N * log2(k))。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }

    if (lists.length == 1) {
        return lists[0];
    }

    int i = 0;
    List mergedList = new ArrayList<>();

    // 两两分组合并。merge2()的作用是普通的合并两个有序列表。
    while (i < lists.length) {
        ListNode node1 = lists[i];

        if (++i < lists.length) {
            mergedList.add(merge2(node1, lists[i++]));
        } else {
            mergedList.add(node1);
        }
    }

    return mergeKLists(mergedList.toArray(new ListNode[0]));
}

Map

HashMap经常用来提高程序的效率。写入(put)、查找(contains)和取值(get)都为O(1)。这里有一些简单写法:

// 计数:记录相同词语出现的次数
Map<String, Integer> map = new HashMap<>();

for (String s : list) {
    map.merge(s, 1, Integer::sum); // 如果没有,值设为1;否则,在原来的基础上加1
}

// map的值为一个列表。如果不存在,创建列表。
// key为字符串,value为储存字符串索引位置的列表
Map<String, List<Integer>> map = new HashMap<>();

for (int i = 0; i < list.size(); ++i) {
    map.computeIfAbsent(list.get(i), k -> new ArrayList<>()).add(i);
}

Bitwise & Bit Shift Operations

// Unary bitwise complement (~)
int n = ~5;  // ~0101 --> 1010

// Bitwise AND (&)
int m = 0b0001;
int result = n & m;   // 1010 -> 0000
// Bitwise inclusive OR (|)
result = n | m;   // 1011

// Bitwise exclusive OR (XOR) (^)
result = n ^ 0b1111;   // 1010 --> 0101

// Signed left shift (<<): shift once results integer x 2
result = 8 << 1;  // 16
result = -8 << 1; // -16

// Signed right shift (>>): shift to right and fill 0 on left, but keep leftmost bit.
// shift once results integer / 2
result = 8 >> 1;  // 4
result = -8 >> 1; // -4 

// Unsigned right shift (>>>): shift to right and fill 0 on left.
result = 8 >>> 1;  // 4
result = -8 >>> 1; // 2147483644

一些常用的用法:

// 乘或除2的n次方
int result = 3 << 4;  // 3 * (2 ^ 4)
result = 32 >> 3;     // 32 / (2 ^ 3)

// 判断奇偶
boolean isEven = (123 & 1) == 0;  // 注意由于优先级的原因,应使用括号

// 判断某位是否为1(比如每个位表示一种flag)
int mask = 0b0010;
boolean isSecondBitFromRightSet = (7 & mask) == mask;  // 7 = 0b0111, 7 & mask = 0b0010

// XOR:
// a XOR a = 0
// a XOR 0 = a
// a XOR b XOR c = a XOR (b XOR c)
// a XOR b XOR b = a

Trie

Trie又名“前缀树”,用于根据前缀查找词汇。典型的应用包括:自动完成、拼写检查、IP路由、解字谜等等。哈希表虽说查找的时间复杂度为O(1),但在查找相同前缀的词汇时就缺乏效率了。而且如果输入了大量的词汇的话,还有因哈希冲突而导致的效率下降。

如果输入的词汇数量为n,查找的前缀长度为m,那么查找的时间复杂度为O(m)。

这里是一个简单的实现:

public class Trie {
    public static class Node {
        private String word;
        private final Map<Character, Node> childrenMap = new HashMap<>();

        public Node() {
            // empty
        }

        public boolean hasChild(char c) {
            return childrenMap.containsKey(c);
        }

        public Node getChild(char c) {
            return childrenMap.get(c);
        }

        public Node addChild(char c) {
            return childrenMap.computeIfAbsent(c, k -> new Node());
        }

        public void setWord(String str) {
            this.word = str;
        }

        public String getWord() {
            return word;
        }
    }

    private final Node root = new Node();

    public Trie() {
        // empty
    }

    // 输入一个词汇
    public void insert(String word) {
        Node node = root;

        for (char c : word.toCharArray()) {
            node = node.addChild(c);
        }

        node.setWord(word);
    }

    // 查看是否有该词汇
    public boolean search(String word) {
        Node node = root;

        for (char c : word.toCharArray()) {
            node = node.getChild(c);

            if (node == null) {
                return false;
            }
        }

        return node.getWord() != null;
    }

    // 查看是否有以该前缀开始的词汇
    public boolean startsWith(String prefix) {
        Node node = root;

        for (char c : prefix.toCharArray()) {
            node = node.getChild(c);

            if (node == null) {
                return false;
            }
        }

        return true;
    }
}

如果词汇的组成字符是有限的(比如小写英文单词由26个字母组成),另一种实现方法是用一个数组代替Trie.Node中的HashMap。我个人不太喜欢这种方法。但是用Java语言的时候,讽刺的是这种方法往往能快一点点。

public static class Node {
    private static final int N = 26;    // 字符总数
    private Node[] links = new Node[N]; // 查找时用索引 int i = c - 'a';

    // 用flag代替上面的字符串能节省点空间。
    // 用字符串的目的是在需要得到词汇时不用从头遍历到目前结点,而是能直接拿到
    private boolean end = false;

    // ...

    private int getIndex(char c) {
        return c - 'a';
    }

    public boolean contains(char c) {
        return get(c) != null;
    }

    public Node get(char c) {
        return links[getIndex(c)];
    }

    // ...
}

 

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注