第一个大于等于某个正整数的 2 的幂
2018-07-13
在计算机中，2 的幂是神奇的数，很多运算可以用位操作来完成。 求第一个大于等于某个正整数的 2 的幂，例如 1023 则返回 1024，这个算法在 Java 中哈希表分配桶就有所运用。 …
数组中首个缺失的正整数 First Missing Positive
2018-06-08
找出数组中首个缺失的正整数： https://leetcode.com/problems/first-missing-positive/ Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your algorithm should run in O(n) time and uses constant extra space. 看起来很简单，首先想到排序的方法，时间复杂度为 $O(n\log(n))$。 …
在 Java 中使用 Map 计数的几种姿势
2018-06-02
一个老生常谈的问题：在 Java 中，如何使用 Map 给对象计数，例如统计字符串出现的次数？ 姿势一：containsKey() Map<String, Integer> map = new HashMap<>(); for (String word : words) { if (map.containsKey(word)) map.put(word, map.get(word) + 1); else map.put(word, 1); } 或者： int count = map.containsKey(word) ? map.get(word) : 0; map.put(word, count + 1); 这是最容易想到的方法，然而这种方法至少有两个问题： …