[数据结构与算法]ARTS挑战第十九周

Algorithm

【大根堆+小根堆】295. 数据流的中位数

实现的思路是使用两个优先级队列，一个是大根堆，一个是小根堆。要求满足以下条件：

• 大根堆所有的元素小于等于 小根堆所有元素，即大根堆堆顶元素小于小根堆堆顶元素
• 如果大根堆元素和小根堆元素个数相等，则插入时，优先插入大根堆；否则插入小根堆。

如果所有元素满足以上两个条件，那么中位数(findMedian函数逻辑）就是：如果大根堆元素多，就大根堆堆顶，否则就是两个堆顶元素取平均值。

为了保证以上两个条件，在插入元素（addNum函数逻辑）时，需要进行以下操作：

• 首先根据大根堆和小根堆元素判断应该插入大根堆还是小根堆，这样满足条件2
• 插入大根堆，则需要先插入小根堆，再将小根堆堆顶元素插入大根堆；反之，亦然，这样才能保证条件1成立

【hash+双链表】146. LRU 缓存机制

完全使用c++自带的list和unordered_map 实现，虽然代码更加简洁，但是效率比自己实现的双链表要低。

【动态规划】1262. 可被三整除的最大和

dp[i][0]表示前i个数中，被三整除的元素最大和

? dp[i][1]表示前i个数中，被三除后余数为1的元素最大和

? dp[i][2]表示前i个数中，被三除后余数为2的元素最大和

? 选择：是否将第i个元素放入

? base case: dp[0][0] =0, dp[0][1] = dp[0][2] = -inf;

? 状态转移：

r = nums[i-1]%3;
switch(r){
case 0:   
dp[i][0] = dp[i-1][0]+nums[i-1]; 
dp[i][1] = dp[i-1][1]+nums[i-1];
dp[i][2] = dp[i-1][2]+nums[i-1];
break;
case 1: 
dp[i][0] = max(dp[i-1][0],dp[i-1][2]+nums[i-1]);
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+nums[i-1]);
dp[i][2] = max(dp[i-1][2],dp[i-1][1] + nums[i-1]);
break;
case 2:
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+nums[i-1]);
dp[i][1] = max(dp[i-1][1],dp[i-1][2]+nums[i-1]);
dp[i][2] = max(dp[i-1][2],dp[i-1][0]+nums[i-1]);

}

【动态规划】983. 最低票价

dp[i]表示前i天所需要的最少钱，注意i是指实际天，而不是days下表

? base case: dp[0]=0;

? 状态转移：如果第i天不在旅行计划中，则dp[i] = dp[i-1];

? 否则：dp[i] = min(dp[i-1]+cost[0], dp[i-7]+cost[1],dp[i-30]+cost[2]);

? 括号中的三个选项分别表示使用当天买的票，使用上次买的7天的票，使用上次买的30天的票

? 这里为什么是dp[i-7]+cost[1]呢，

? 举个例子，假设i=8好了，那么要用上次买的七天的票，得是i=2,…,6天这几天买的对吧

? 如果i=2那天有行程，则最早那天买的，则总共花的最少的钱是dp[1]+costs[1].

? 假设i=2那天没有行程，假设i=3那天有，则总共花费的是dp[2]+costs[1];

? 由于此时dp[2] = dp[1]，因此还是等价的。

? 另外，如果i<7，则直接将dp[i-7]取零就好。对30的情况依此类推

【栈】20. 有效的括号

• 左括号入栈，右括号和栈顶元素比，如果不匹配则返回false，
• 最后栈不为空也返回false
• 长度为奇数也返回false

【回文字符串】336. 回文对

naive想法：

两层for 循环遍历所有 words[i]+words[j] 和 words[j]+words[i]的情况，复杂度O(N^2)

判断words[i]+words[j]是否是回文串，复杂度O(L)

总的时间复杂度 O(L*N^2)约等于 25000000*300 复杂度太高，肯定会超时

其实s1+s2满足条件的一共就三类情况：

\1. len(s1) = len(s2), 则s2是s1的翻转

\2. len(s1) > len(s2), 则s2是s1的前缀t1的翻转，s1后缀t2必须是回文

\3. len(s1) < len(s2), 则s1是s2的后缀t2的翻转，s2的前缀t1必须是回文的

?

因此，只需要遍历每一个字符串的所有前缀和后缀，判断是否满足条件2和条件3，

使用一个hash表存储所有单词的翻转，来实现O(1)时间查找相应的字符串的下标

总的时间复杂度O(L^2*N)，90000*5000

【动态规划】91. 解码方法 类似于跳台阶问题

dp[i]表示前i个字符所能达到的最大解码数

选择：当前字符i可以单独解码或者与上一个一起解码

转移：如果当前字符i只能自己解码，则dp[i] = dp[i-1]

如果当前字符只能和前面一个一起解码，则dp[i] = dp[i-2]

否则加起来：dp[i] = dp[i-1]+dp[i-2];

base case: dp[0] = 1, dp[1]=s[0]==‘0’?0:1;

【动态规划】5. 最长回文子串

思路大概就是从小的回文串不断扩展，从长度为2的子串开始，到长度为n的子串进行暴力枚举

假设dp[i][j]表示子串s[i] … s[j] 是否为回文串

如果s[i] == s[j] ,则 dp[i][j]=dp[i+1][j-1](长度为2时为true) ，否则 false,

记录下来dp[i][j]为true时的最大长度j-i+1以及对应的起始下标i

【贪心算法】45. 跳跃游戏 II

? 贪心算法，从下标为0开始，不断往后面跳。这里并不是每次尽可能跳最远，而是跳往下一跳能到达最远的那点。

? 例如[2,3,1,1,4], 一开始可以跳往下标为3和1这两个位置，但是3下一跳能跳的更远，因此从2这个位置应该跳一步到3

? 同理，3这个位置能到达1，1，4这三个位置，当前能跳往的位置已经达到终点了，因此再跳一次就好。

? 在代码实现上

? |–维护当前能跳往的最远值，作为边界bound，初始为0，方便处理边界情况

? |–维护当前所在的位置cur，cur从0开始

? |–维护next_bound表示下一步能跳往的最远位置

? |–在bound内从前往后进行搜索，根据下一步能到大的最远距离来更新bound

? |–到达bound时，表示至少需要跳一步了，至于跳到bound前的哪一格不用管,只需要知道跳完后的边界在哪

? |–到达终点target结束

【动态规划】42. 接雨水

直观解法，对于每一个位置i，它所能承载的水量是 min(左边最高的柱子高度,右边最高的柱子高度)-当前柱子高度

? 那么如何得到min(左边最高的柱子高度,右边最高的柱子高度)是该题的主要优化点

? 一种思路是直接对于每个位置都搜一遍，复杂度较高

? 第二种思路是使用动态规划，将每个位置的最左边高度和最右边高度算出来存到数组里面

? 第三种思路是双指针，这个比较巧妙，暂时还没完全掌握

1190. 反转每对括号间的子串

string f(string s, int& cur)

cur是全局游标

递归触发条件：s[i] = ‘(’, res+= f(s,cur);

递归终结条件：s[i]=’)’, return reverse(res);

对于非括号字符，加入当前字符串到结果集;

Review

无锁编程基础

• 无锁编程的概念：是利用处理器的一些特殊的原子指令来避免传统并行设计中对锁的使用。

• 使用互斥锁带来的问题：

  • 死锁(dead lock)：两个以上线程互相等待
  • 锁护送(lock convoy)：多个同优先级的线程反复竞争同一个锁，抢占锁失败后强制上下文切换，引起性能下降
  • 优先级反转(priority inversion)：低优先级线程拥有锁时被中优先级的线程抢占，而高优先级的线程因为申请不到锁被阻塞

面试官灵魂4连问：乐观锁与悲观锁的概念、实现方式、场景、优缺点？

• 乐观锁与悲观锁的区别：
  • 乐观锁就是对共享数据不上互斥锁，只是在执行更新的时候判断一下在此期间别人是否修改了数据：如果别人修改了数据则放弃操作，否则执行操作。
  • 悲观锁则是对共享数据上互斥锁，完成后才会释放锁，上锁期间其他人不能修改数据
• 乐观锁与悲观锁的优缺点与适用场景：
  • 功能限制：与悲观锁相比，乐观锁适用的场景受到了更多的限制。例如CAS只能保证单个变量操作的原子性，涉及多个变量则无能为力
  • 竞争激烈程度：竞争不激烈，乐观锁性能更好，因为加锁解锁需要消耗资源。如果竞争激烈，则由于不断更新失败，浪费大量的CPU

Tips

• 如何查看全连接队列大小：ss -lnt Recv-Q表示 全连接队列大小 Send-Q表示全连接最大队列长度
• 全连接队列满了怎么办：
  1. 丢弃新来的ack，等待客户端重发，因为收到重发的ack时队列可能正好空出来了
  2. 发送rst报文表示连接建立失败
  3. 增大全连接队列大小

3. 文件名包含特殊字符，可能无法正常删除。这时直接删除inode，能够起到删除文件的作用；

Share

• 295. 数据流的中位数
• 快速排序法的递归和迭代两种实现
• 归并排序递归与迭代实现c++