LeetCode 560. Subarray Sum Equals K

https://leetcode.com/problems/subarray-sum-equals-k/description/ O(N^2)的方法想必所有人都会,这里有个用到prefix sum的O(N)方法。 试想一下,如果当前检查到end位置且目前所有项的和为sum,如果有那么一个(start, end)子序列的和为k,那么肯定有一个(0, start-1)的序列它的和是sum – k.

 

LeetCode LIS系列 (Longest Increasing Path in a Matrix)

类似的东西还有: 674. Longest Continuous Increasing Subsequence https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/ 300. Longest Increasing Subsequence https://leetcode.com/problems/longest-increasing-subsequence/description/ longest path increasing by 1 https://www.geeksforgeeks.org/find-the-longest-path-in-a-matrix-with-given-constraints/   下面的代码是这个题的: 329. Longest Increasing Path in a Matrix https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/  主要思路就是瞎JB搜索,不过某一个位置的结果可以记录下来给后续的重复搜索使用。

 

LeetCode 200. Number of Islands

https://leetcode.com/problems/number-of-islands/description/ DFS of a map, O(N^2)

 

LeetCode 76. Minimum Window Substring

76. Minimum Window Substring 思路: 构造一个哈希表结构统计我们的需求,也就是字符串t中每个字符的数量,方便起见如果有需求则哈希表的对应值-1。另外存储一下当前解的起始位置START以及最优解的位置。 扫描字符串s,在位置s[i]时如果能够满足需求(即哈希表中没有负值),则从START开始清除无用的字符直至无法满足需求位置。比如需求是A:1, B:2,START开始的字符是DEFBAB,则清除DEF。清除完成后更新START值并跟当前已知的最优解比较,更新最优解。 啰嗦一句,似乎相当一部分substring类型的题目都能用hash table + two pointers的方式解决。

 

LeetCode 432. All O`one Data Structure

几万年没做LeetCode的题了,更新一下。 https://leetcode.com/problems/all-oone-data-structure/description/ 这道题的思路是用一个双向链表(list)来存储一个以value排序的数据结构,使用哈希表(unordered_map)来存储key到链表iterator的映射: 需要注意特殊处理value=1的Node的情况。 代码写得比较毛糙,但是确实是O(1)的复杂度,如果要优化的话map的插入可以用emplace()之类的。 注意:除了value=1的节点,其余节点的keys为空的时候要把该节点删除掉,否则getMaxKey()和getMinKey()就需要O(n)的遍历操作了。

     

RFC1928 SOCKS5协议 – 部分内容翻译

Reference: https://www.ietf.org/rfc/rfc1928.txt 只是部分章节的翻译 3. TCP客户端的连接流程 当某一基于TCP的客户端想要经由防火墙(取决于具体实现)与远端对象建立连接时,它必须首先开启与SOCKS服务器上对应端口的TCP连接。通常情况下SOCKS服务器监听的TCP端口号是1080. 若连接请求成功,客户端将进入授权模式协商阶段,随后使用所选的模式进行授权,继而开始连接。SOCKS服务器对请求进行评估,继而建立指定的连接或拒绝连接。 除非另有说明,下文数据报中提及的十进制数字均为对应字段的字节长度。当某个字节必须是一个具体数值时,以X’hh’来表示这一字段的具体值。当使用’Variable'(可变长)时,表示这一字段拥有可变长度的内容,具体长度通过一个关联的长度字段表示,或根据某钟具体的数据类型字段决定。 客户端连接至服务器并发送一个标识符/方法选择信息:

其中,字段VER设置为X’05’以表明此协议的版本。NMETHODS字段包含了METHODS字段中所填鉴权方法(method)的个数,以字节为长度单位——METHODS中的一个方法标识符占一个字节。 服务器从METHODS给定的方法中选择一种,回传一个方法选择消息:

如果选择的方法值为X’FF’,则表明服务器不接受客户端能提供的任一种鉴权方法,客户端必须在收到此消息后断开连接。 METHOD中可以定义的方法为: X’00’ 无需鉴权方法 X’01’ GSSAPI X’02’ 用户名/密码 X’03’ 至 X’7F’ IANA指定 X’80’ 至 X’FE’ 私有方法保留 X’FF’ 没有可接受的方法 随后,服务器与客户端进入协议特定的子协商(sub-negotiation)阶段。 协议特定的子协商过程在描述于不同备忘录中。 本协议新方法的开发人员必须向IANA申请一个新的METHOD号……(省略两段合规相关的话) 4. 请求(Requests) 一旦完成了协议特定的子协商过程,客户端便发送请求细节。如果方法的协商包括了完整性检查或保密相关的封装,那么这些请求必须以指定方式进行相同的封装。 SOCKS的请求,其格式如下:

其中: VER: 协议版本号:X’05’ CMD CONNECT X’01’ BIND X’02’ UDP ASSOCIATE X’03’ RSV 保留字段 ATYP 地址类型 IP V4
Continue reading RFC1928 SOCKS5协议 – 部分内容翻译

Basic Risks on Options 期权的基本风险类型

书里看到的,摘记一下。 Delta (Directional) Risk. Underlying的价格向某一侧移动的风险,主要做法是构造delta中性的position; Gamma (Curvature) Risk. Underlying价格发生大幅波动的风险,这种风险并非是delta那种方向性的。承受这种风险的position是Gamma为负数的那些期权,因为由定义可以推出来,+Gamma的那些期权,在价格发生波动时其价值反而会增加; Theta (Time Decay) Risk. 与Gamma风险是反向的一对,能通过Gamma获得价值的期权,他们的价值随着时间而逝去… Vega (Volatility) Risk. 我们给模型输入的那个volatility可能是错的,错误的输入将得到错误的模型(概率分布),产生错误的结果;或者,期权市场自身的变化导致的隐含波动率的改变; Rho (Interest-Rate) Risk. 期权有效期内利率的变化对其价值的影响。Rho>0说明利率上升能增加期权的价值,反之亦然。但通常而言,这个风险应当是在前面几种风险之后才考虑的;  

Volatility Spreads – Two General Guidance

Here I excerpt two useful sections in Chapter 12 of the book Option Volatility & Pricing. Choosing an Appropriate Strategy If implied volatility is low, such that options generally appear underpriced, look for spreads with a positive vega. If implied volatility is high, such that options generally appear overpriced, look for spreads with a negative
Continue reading Volatility Spreads – Two General Guidance