阅文集团笔试总结

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

func numDupDigitsAtMostN(N int) int {
    num = make([]int, 0)
    t := N
    i := 0
    for t > 0 {
        num = append(num, t%10)
        t /= 10
        i++
    }
    return N + 1 - dfs(i-1, 0, true)/*用来寻找不符合条件的数字*/
}

//空间换时间 dp[i][j]就表示 在j的情况下 第i位的值
//比如12XXX 和 21XXX 不具有重复数字的个数一定相等
//此时j = 6 (0000000110) i=3 (倒数索引为3) 
//当计算过12XXX时将其记忆化 下次直接调取结果
var dp =[][]int{make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
}
var num = make([]int, 0)
//假定i=5 t=0 这里的方法用来寻找 0~100000中 各个位都不重复的个数 即不符合条件的数
//t用来存储之前用过的数字 10位二进制数字 1000000111 就代表用过了0 1 2 9
func dfs(i /*数位*/ int, t /*记录前几位数字*/ int, limit /*是否是边界*/ bool) int {
    if i == -1 {
        return 1
    }
    if !limit && dp[i][t]!=0{ return dp[i][t]};
    res := 0
    //比如数字是54321 当第一位是5 第二位是4 那么此时就是边界值 第三位只能是0~3 
    //否则 可以为0~9
    u  := 9
    if limit {
        u = num[i]
    }
    for d := 0; d <= u; d++ {
        a := t / (1<<uint8(d)) & 1
        if a == 1 {
            //假定此时t = 10(0000001010) 那么当前位不能位 1 和 3
            continue
        }
        var tt int
        //当t是0 且当前位也是0 代表下一位是首位数字 此时下一位还可以用0 不做记录
        if !(t==0 && d == 0) {
            //以二进制记录下已经用过的值
            tt = t + (1<<uint8(d))
        }
        res += dfs(i-1, tt , d == num[i] && limit)
    }
    if !limit {
        //记忆化
        dp[i][t]=res
    }
    return res
}

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

final V putVal(K key, V value, boolean onlyIfAbsent) {
        // key 与 value 不允许为 null
        if (key == null || value == null) throw new NullPointerException();
        // 得到 hash 值
        int hash = spread(key.hashCode());
        // 用于记录相应链表的长度
        int binCount = 0;
        //这里是个死循环，直到putVal 之后 才会 break
        for (Node<K,V>[] tab = table;;) {
            //死循环，不停失败重试
            Node<K,V> f; int n, i, fh;
            // 如果数组"空"，进行数组初始化
            if (tab == null || (n = tab.length) == 0)
                // 初始化数组，后面会详细介绍
                tab = initTable();

                // 找该 hash 值对应的数组下标，得到第一个节点 f
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                //f表示链表的头节点 或者 红黑树的根节点
                // 如果数组该位置为空，
                //    用一次 CAS 操作将这个新值放入其中即可，这个 put 操作差不多就结束了，可以拉到最后面了
                //          如果 CAS 失败，那就是有并发操作，进到下一个循环就好了
                if (casTabAt(tab, i, null,
                        new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            // hash 居然可以等于 MOVED，这个需要到后面才能看明白，不过从名字上也能猜到，肯定是因为在扩容
            else if ((fh = f.hash) == MOVED)
                // 帮助数据迁移，这个等到看完数据迁移部分的介绍后，再理解这个就很简单了
                tab = helpTransfer(tab, f);

            else { // 到这里就是说，f 是该位置的头结点，而且不为空
                //如果槽位不为空，那么就 要 锁住这个 头节点，然后使用尾插法 插入元素
                V oldVal = null;
                // 获取数组该位置的头结点的监视器锁
                synchronized (f) {
                    //发生了哈希碰撞，锁住链表（或者红黑树根节点）头节点
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) { // 头结点的 hash 值大于 0，说明是链表
                            // 用于累加，记录链表的长度
                            binCount = 1;
                            // 遍历链表
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                // 如果发现了"相等"的 key，判断是否要进行值覆盖，然后也就可以 break 了
                                if (e.hash == hash &&
                                        ((ek = e.key) == key ||
                                                (ek != null && key.equals(ek)))) {
                                    //因为已经锁住了链表的头节点，只有一个线程，所以可以直接替换
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    //如果遍历链表途中找到 了 Node ，就替换，然后 break出来
                                    break;
                                }
                                // 到了链表的最末端，将这个新值放到链表的最后面
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                            value, null);
                                    //应为已经锁住了链表的头节点，只有一个线程，所以可以直接尾插，不用再 CAS抢夺尾部节点
                                    break;
                                }
                            }
                        }
                        // 红黑树
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            // 调用红黑树的插值方法插入新节点
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                    value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                // binCount != 0 说明上面在做链表操作
                if (binCount != 0) {
                    // 判断是否要将链表转换为红黑树，临界值和 HashMap 一样，也是 8
                    if (binCount >= TREEIFY_THRESHOLD  /* 链表长度>=8 ->转红黑树 */)
                        // 这个方法和 HashMap 中稍微有一点点不同，那就是它不是一定会进行红黑树转换，
                        // 如果当前数组的长度小于 64，那么会选择进行数组扩容，而不是转换为红黑树
                        //    具体源码我们就不看了，扩容部分后面说
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        //
        addCount(1L, binCount);
        return null;
    }

 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

  public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        // 计算哈希值
        int h = spread(key.hashCode());
        // 哈希表存在，长度大于 0，桶位置上有键值对
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (e = tabAt(tab, (n - 1) & h)) != null) {
            // 判断头结点是否就是我们需要的节点
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            // 如果头结点的 hash 小于 0，说明 正在扩容，或者该位置是红黑树
            else if (eh < 0)
                // 参考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k)
                return (p = e.find(h, key)) != null ? p.val : null;

            // 遍历链表
            while ((e = e.next) != null) {
                if (e.hash == h &&
                        ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

  public V get(Object key) {
        Segment<K,V> s; // manually integrate access methods to reduce overhead
        HashEntry<K,V>[] tab;
        // 1. hash 值
        int h = hash(key);
        // 快速 定位 segment
        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
        // 2. 根据 hash 找到对应的 segment
        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
                (tab = s.table) != null) {
            // 3. 找到segment 内部数组相应位置的链表，遍历
            for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                    (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
                 e != null; e = e.next) {
                K k;
                if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                    // 找到了，返回 value，找不到 返回 null
                    return e.value;
            }
        }
        return null;
    }

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

    public V put(K key, V value) {
        Segment<K,V> s;
        if (value == null)
            throw new NullPointerException();
        // 1. 计算 key 的 hash 值
        int hash = hash(key);
        // 2. 根据 hash 值找到 Segment 数组中的位置 j
        //    hash 是 32 位，无符号右移 segmentShift(28) 位，剩下低 4 位，
        //    然后和 segmentMask(15) 做一次与操作，也就是说 j 是 hash 值的最后 4 位，也就是槽的数组下标
        int j = (hash >>> segmentShift) & segmentMask;
        // 刚刚说了，初始化的时候初始化了 segment[0]，但是其他位置还是 null，
        // ensureSegment(j) 对 segment[j] 进行初始化
        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
                (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            s = ensureSegment(j);
        // 3. 插入新值到 槽 s 中
        return s.put(key, hash, value, false);
    }