Jepson's Blog

语法糖(syntactic sugar)，也译为糖衣语法，是由英国计算机科学家彼得·约翰·兰达（Peter J. Landin）发明的一个术语，指计算机语言中添加的某种语法，这种语法对语言的功能并没有影响，但是更方便程序员使用。通常来说使用语法糖能够增加程序的可读性，从而减少程序代码出错的机会。

语法糖是指编程语言中可以更容易的表达一个操作的语法，它可以使程序员更加容易去使用这门语言：操作可以变得更加清晰、方便，或者更加符合程序员的编程习惯。

具体来说，语法糖是指语言中的一个构件，当去掉该构件后并不影响语言的功能和表达能力。

例如，C语言中的标记a[i]就是*(a+i)的语法糖。

已通过

• 上来先聊了一会儿，问了读研几，啥时候毕业之类的。还问了实习安排，能实习多久之类的。

• 简单自我介绍

• 稍微讲了一下项目

  • 接着项目问的什么是抽象语法树?
  • 抽象语法树的作用，为什么要用抽象语法树？

• 提问（问的问题都好难）

  • 语法tang了解过吗？（我连哪个tang都不知道。。）
  • java编译后的产物，字节码之类的知道多少。（不知道。。表示对java不是很了解）
  • c++里的多态，虚函数怎么实现的（看我不懂java，想了一会儿问的c++的问题，感觉这是全场唯一一个能正常回答出来的问题）
  • 动态代理？（不知道。。）
  • systemcall了解吗，为什么会有系统调用？（答了一些内核态和用户态相关的东西）
  • 具体的系统调用有哪些，具体是怎么执行的？（盲猜了一个c++里面的sleep函数，具体咋执行的乱答了继承阻塞之类的。。）
  • 文件描述符（不是很了解，乱答了一些文件的唯一标识，记录文件状态之类的）
  • 一个文件可以有两个文件标识符吗？（不知道）
  • CDN了解吗？（不了解）
  • 解释了一通CDN，问CDN存在的意义或者作用是啥？（一开始理解成用户可以把数据保存在CDN上可以把连接共享给别人，结果理解错了，面试官又解释了一下一般是服务商把资源放在CDN上供用户访问，问这样做有什么作用。想了一会儿答了本来要访问服务器的请求转到CDN上了，可以用来缓解服务器压力之类和分流之类的，然后感觉和云边端服务器有点像有聊了一大堆云边端的东西，比如提高访问性能啊之类的）
  • 如果CDN上的一个资源不见了，用户访问会怎么办？（不知道。。乱聊了一些设计一个表记录资源是否存在，没有资源了就告诉用户无法访问）
  • 还是上一个问题，有没有别的办法？（不知道。。又乱聊了一些CDN如果发现资源不存在就向服务器请求重新发送资源，好像聊对了，面试官说这叫CDN回源）
  • 然后就问了回源还有啥别的作用？（不知道。。）
  • 除了http还了解过其他不常见的协议吗？（不知道，表示只了解过ftp，ssh之类常见的协议）
  • QUIC协议了解过吗？（惊了，才看的，答了一下是谷歌做的UDP的升级版，http3.0之后使用的协议，利用udp不需要建立连接解决了tcp握手比较慢的问题，在udp基础上增加重传和拥塞控制等功能保证了可靠性。因为了解的不深说的都很肤浅，面试官反应还行。）
  • 对kotlin有了解吗？（没接触过。。）
  • 对安卓开发有了解吗，做过项目吗？（有一点了解，大学做过几个app）
  • 讲一下做的安卓项目。（讲了个模拟请假的app，听到我说后来全校都在用面试官笑了。）

• 算法题

  给一个正整数组nums和一个数字N，每次都从数组头部或者尾部取出一个数字从N中减掉，问最少需要多少使N变为0，如果不能变为0则输出-1。

  • 想了一会儿先给了个暴力解。

    最后的结果一定是从数组前面取出一段加上从数组后面取出一段，这两段的和是N。所以最简单的做法是先计算前缀和以及后缀和，然后n^2暴力，对于每一个前缀和找有没有一个合适的后缀和使二者的和为N，如果有则用二者的长度更新ans。

  • 面试官表示这个方案应该可以解决，但是能不能优化？

    想了个优化方案复杂度优化到了O(nlogn)。之前的方案复杂度主要在对于每一个前缀和都要枚举遍历每一个后缀和，而因为都是正整数，所以后缀和是具有单调性的，所以可以用二分的方式找有没有这个前缀和匹配的后缀和。

  • 面试官表示可以，但感觉我的解法跟他想的不一样，又说了一下这个题相当于有两个指针啥的，一个指向前一段，一个指向后一段

    面试官说道这里突然悟道他的的意思了。。这题可以反过来想，假设整个数组的和为M，这题其实就相当于从数组里找一段使其和为M-N，然后就没了。。

  • 面试官说那写出来吧。然后看面试官的表情确定这就是他想要的方法。

    我就写了个最复杂的方法。枚举子数组的头尾，然后对数组求和看是否等于M-N，连前缀和都没写，复杂度O(n^3)。。

  • 问哪里可以优化？

    第三层for循环可以用前缀和替换，优化到O(n^2)。然后就结束了。。

    但是这个方法明明没有我刚刚说的那个二分的复杂度低呀。。。

• 顺便问一下英语怎么样啊？敢说吗？（我笑了，表示还行吧，无障碍交流做不到，听懂应该差不多。。感觉要gg）

• 容器支持迭代器，容器适配器不支持迭代器。

• map中的基本元素就是对组pair。

• pair是用一个结构体实现的，结构体主要的两个成员变量first和second，分别存储两个数据。

• map中的pair第一个元素为key(键值)，起索引作用，就相当于数组下标，第二个元素为value(实值)。map所有元素会根据键值大小自动排序

leetcode上买卖股票问题一共有六道题，六道题十分相似，只要掌握一个算法稍作修改就可以都AC掉，现做一个总结。

买卖股票的最佳时机

只能买卖一次

1
2
3
4
5
6
7
8
9
10

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int buy = -0x3f3f3f3f;
    int sell = 0;
    for(int i=0;i<n;i++){
        buy = max(buy, 0-prices[i]);
        sell = max(sell, prices[i]+buy);
    }
    return sell;
}

买卖股票的最佳时机 II

可以买卖多次

1
2
3
4
5
6
7
8
9
10

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int buy = -0x3f3f3f3f;
    int sell = 0;
    for(int i=0;i<n;i++){
        buy = max(buy, sell-prices[i]);
        sell = max(sell, prices[i]+buy);
    }
    return sell;
}

买卖股票的最佳时机 III

只能买卖两次

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

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int buy = -0x3f3f3f3f;
    int sell = 0;
    int buy2 = -0x3f3f3f3f;
    int sell2 = 0;
    for(int i=0;i<n;i++){
        buy = max(buy, 0-prices[i]);
        sell = max(sell, prices[i]+buy);
        buy2 = max(buy2, sell-prices[i]);
        sell2 = max(sell2, prices[i]+buy2);
    }
    return sell2;
}

买卖股票的最佳时机 IV

只能买卖K次

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

int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    int buy[k+1], sell[k+1];
    for(int i=0;i<=k;i++){
        buy[i] = -0x3f3f3f3f;
        sell[i] = 0;
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<=k;j++){
            buy[j] = max(buy[j], sell[j-1]-prices[i]);
            sell[j] = max(sell[j], prices[i]+buy[j]);
        }
    }
    return sell[k];
}

最佳买卖股票时机含冷冻期

有一天冷冻期，卖了之后隔一个天才能再买

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

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int buy = -0x3f3f3f3f;
    int sell = 0;
    int sell2 = 0;
    for(int i=0;i<n;i++){
        buy = max(buy, sell2-prices[i]);

        sell2 = sell;
        sell = max(sell, prices[i]+buy);
    }
    return sell;
}

买卖股票的最佳时机含手续费

每次买卖需要交手续费fee（同一次买卖只交一次）

1
2
3
4
5
6
7
8
9
10

int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    int buy = -0x3f3f3f3f;
    int sell = 0;
    for(int i=0;i<n;i++){
        buy = max(buy, sell-prices[i]-fee);
        sell = max(sell, prices[i]+buy);
    }
    return sell;
}

页表

• 页表是将逻辑地址转换为物理地址。

• 页表内存储的是页号和块号的映射。

• 逻辑地址整除页长得到的商就是页号，余数就是页面偏移量。

• 通过页表将页号转换为块号，在用块号和页面偏移量即可得到数据在内存中的物理地址。

• 当请求的页面不在内存中时（页表中还有状态位等信息表示页面是否在内存中），发生缺页中断将需要的页面调入内存，如果内存没有多余的空间则使用页面置换算法替换掉内存中的某个页。

快表

• 快表是一种比内存快很多的高速缓存存储器

• 快表存储的是一些常用的的页号，相当于页表的cache，如果快表命中了则不需要再访问页表。

• 快表中的页一定在内存中，页表中的页不一定在内存中。

• 快表命中了只需要访问一次内存，没命中则需要访问两次内存（访问页表一次加访问数据一次）。