2024.02.04_学习日记

Posted on Edited on In Views:

天气：小雪
学习地点：家
学习时长：8h

学习内容

  1. mysql视图、存储过程、存储函数、触发器
    alt text
  2. 大数据题目
    alt text
    alt text
    怎么找到top100，先分成局部几部分数据，然后用哈希表记录每一部分的词频，然后用堆结构把词频排序，然后用一个新的堆结构放入各个小部分的堆顶并排序，然后弹出堆顶，就是全局最大值，并且看该堆顶之前是哪个堆的顶，然后把这个子堆的堆顶元素弹出放入新堆顶，然后循环弹出一百个数就是top100。
    alt text
    解决办法：
    哈希函数分流：看1GB内存的哈希表能放多少数据，然后就能知道分多少小文件了，一个数通过哈希函数最后取模就知道放到哪个小文件里去，最后用哈希表对每个小文件进行词频统计，然后汇总就是答案。
    位图方法：用两个位来判断一个数字出现的次数，如果是00，就没出现，01，出现一次，10，出现两次，11，出现很多次。2的32次方个数占用2的32次方*2/8个字节。
    找中位数的办法：
    alt text
    腾讯面试题：怎么把一堆10G内存的没有排序过的数字通过任意内存比如1M内存然后生成一个排序过的文件？
    第一种方法通过分段统计思想，计算1M能记录多少int数字，然后相除就可以知道分成多少个区间，然后对所有数字以及出现的次数处在第一个区间的放进小根堆，按照数值排序，然后根据词频放进生成的文件即可。
    第二种方法是通过大根堆，大根堆放的数据量也是根据内存大小定，大根堆放数字以及词频，如果大根堆放满了，那就比较接下来的值和堆顶的大小，如果大，就跳过，如果小，堆顶弹出并且把这个值放进堆当中，遍历完以后让Y=3，第二次遍历，只把Y>3的数放进大根堆里来。
    比较两个值的大小：
    alt text
    alt text
    怎么判断一个数是不是2或者4的幂？(lc342)
    判断2的幂可以用x&(x-1) == 0来判断。
    判断4的幂可以先判断是不是2的幂，然后用x&(32位010101010101)来判断，如果!=0，就是4的幂。二进制用0b的前缀表示。
    alt text
    +：两个数异或^就是不进位相加，两个数&然后<<1就是进位信息，然后重复这样，直到两个数&为0了，此时异或的值就是最后的答案。
    -：a加上b的相反数，相反数就是b取反+1
    ：乘法二进制也跟十进制的乘法一样，ab等于如果b末尾是1，那就res+a，然后a左移一位，b右移一位，如果末尾是0，跳过res+a部分，然后重复，直到b=0弹出，返回res。
    /：除法就是看被除数左移多少位能被除数减掉，从31位开始往下数，如果到第三位，被除数大于除数，那么res = 1左移3位，然后相减之后继续从第二位开始左移相减，如果左移后被除数大于除数，那么res+1左移2位，最后知道左移数为0跳出循环，返回res。
    alt text
    alt text