← Back

ARTS 第9周 晋升述职

Algorithm

本周完成的算法题: Permutations II

题目要求:

1
2
3
4
5
6
7
8
9
10
11

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

这个问题通过使用Map来记录每个数字出现的个数，然后对出现数字通过回溯法可以解决。

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

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();

        Map<Integer, Integer> counter = new HashMap<>();
        for (int num : nums) {
            Integer c = counter.get(num);
            if (c == null) {
                counter.put(num, 1);
            }else {
                counter.put(num, c + 1);
            }
        }
        backtrack(nums, lists, new ArrayList<>(), counter);

        return lists;
    }

    private void backtrack(int[] nums, List<List<Integer>> lists, List<Integer> stack, Map<Integer, Integer> counter) {
        if (stack.size() == nums.length) {
            lists.add(new ArrayList<>(stack));
        } else {

            //注意这里遍历的是计数的Map 而不是原来的数组
            for (Integer i : counter.keySet()) {

                //只对计数大于0的数字做后续的操作
                if(counter.get(i) > 0){
                    counter.put(i, counter.get(i) - 1);
                    stack.add(i);
                    backtrack(nums,lists, stack, counter);
                    stack.remove(stack.size() - 1);
                    counter.put(i, counter.get(i) + 1);
                }
            }
        }
    }
}

Review

本周Review Bloom Filter : A Probabilistic Data Structure

本文主要分享的是Bloom Filter的特性和使用场景。

Bloom Filter的特点：

  • 能够在Constant space & time 回答类似“商品是否在集合内?”的 YES/NO问题。
  • 一定不存在(Definitely not in the set) 和 可能存在(Probably in the set)

Bloom Filter的使用场景：

  • 内容平台可以用来判断用户是否阅读过某个内容
  • 文件系统可以用来判断文件或者数据是否存在以便减少磁盘寻找时间
  • 恶意网址校验。

更多参考内容:

Tip

在HashMap循环时，如何增加、删除HashMap中的元素?

1
2
3
4
5
6
7
8
9

    Map<String, String> map = new HashMap<>(16);
    for (Map.Entry<String, String> entry : map.entrySet()) {

        // will throw java.util.ConcurrentModificationException
        map.remove(entry.getKey());

        // will throw java.util.ConcurrentModificationException
        map.put("new Key", "new Value");
    }

如果直接在循环体中删除或者增加元素会抛出java.util.ConcurrentModificationException异常。 HashMap遍历的顺序是不固定的，所以当你加入或者增加元素时可能会改变顺序(rehash)，这样的话有些元素可能会出现多次，有的可能就不出现了。程序应当保持一种一致的可预期的行为，因此在循环中增加或者删除是与允许的。

HashMap中定义了一个变量modCount，这个变量代表这个HashMap被修改(增加、删除、Rehash等)的次数。同时在HashMap定义的HashIterator中用一个变量expectedModCount记录了当前的modCount，在每次循环是会比较这两个值是否一样，如果不一样就抛出java.util.ConcurrentModificationException 异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }
}

所以对于HashMap的修改正确的方式是引入额外的空间。比如使用一个List来记录需要删除的key, 使用一个临时Map来记录需要增加的元素，在循环结束后统一处理。

Share

相信很多人程序员都会碰到晋升述职的场景，如何把自己做的事情、自己的能力最大化的展示出来是程序员普遍的一个短板。最近看到一篇关于晋升述职的文章感觉很不错，特地分享给大家。

通道答辩的7个小技巧 7 Tips to Grow Your Career