用于算法题的常用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)];
    }

    // ...
}

 

 

发表回复

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