博文

leetcode笔记(word break)

  Given a   non-empty   string   s   and a dictionary   wordDict   containing a list of   non-empty   words, determine if   s   can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1: Input:  s = “leetcode”, wordDict = [“leet”, “code”]  Output:  true  Explanation:  Return true because  "leetcode"  can be segmented as  "leet code" . Example 2: Input:  s = “applepenapple”, wordDict = [“apple”, “pen”]  Output:  true  Explanation:  Return true because  " applepenapple "  can be segmented as  " apple pen apple " . Note that you are allowed to reuse a dictionary word. Example 3: Input:  s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]  Output:  false 胡乱的想法 动态规划,假设到输入字符串到  0  到  [j]  区间是可以被字典中的词组成的,那么如果  [j]+1  到  [i] (i > j)  区间到子字符串存在于字典中,那么  0  

HashMap比较数字时用equals而不是==

  今天在leetcode上看到一个很有趣的discuss,一个人用map.get(a) == map.get(b)来比较hashmap中的Integer的值但是却报错。 Integer默认情况下,在-128到127区间内是有缓存的,用==来比较相等是可以返回真的。但是一旦超出这个范围,它就变成了一个引用类型,需要用equals方法来比较。 如果应用场景中计数基本不会超过127,但是代码中用了==的方式,那么不知道哪天就会产生一个不明所以的bug,细思恐极…

HashMap思考题

  1. 为什么HashMap的一个拉链长度大于8后就会转成红黑树? HashMap中存储的元素所存在的集合(桶,bucket)是一个 单链表 ,或者是一颗 红黑树 。当总bucket数(MIN_TREEIFY_CAPACITY)超过64时,长度超过8(TREEIFY_THRESHOLD)的单链表就会被转化程一颗红黑树。 这样做的目的是为了减少query某个元素时的时间复杂度。在单链表中,查询元素具有线性时间复杂度;而在红黑树中,查找某个元素只需要对数时间复杂度。 长度太长的单链表不利于高效查找元素。 ​ 2. 为什么用红黑树,不用AVL树? 红黑树是一种 弱平衡二叉树 ,它确保没有任何一条路径会大于其他路径长度的二倍。AVL树对于高度的限制比红黑树更加严格,其所有节点的左右子树高度差不超过1。 所以: 查询数据时,AVL树比红黑树更快(因为AVL树高度更低)。 添加或删除数据时,红黑树比AVL树更快(因为AVL树更严格,所以对节点的旋转操作更频繁)。 HashMap选择红黑树是一种对查询效率和增删效率的折衷。 ​ 3. 为什么生成哈希值要对hashcode进行高低位异或处理? static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 这是生成哈希值的代码。 为啥要把hashcode高16位和低16位做异或操作呢? 原来就是为了减少哈希冲突。 在将某一个Key加入HashMap时,如何确定这个Key该放到那个bucket中呢?正常来讲,应该是先计算这个Key的哈希值,然后对HashMap的容量进行模运算来确定这个Key放到第几个bucket里。比如向一个容量位16个bucket的HashMap加入一个哈希值为17的Key,那么就应该把这个Key放到第17 % 16 = 1个bucket。 实际上HashMap在处理这个操作时并不是做模运算,而是让哈希值和(HashMap容量 - 1)作与运算。 比如HashMap容量为16,16 - 1 = 15的二进制表示是1111。 也就是hashcode的高位都没用了,都被与没了。 只要后4位相同的Hashc