面向对象软件设计的S.O.L.I.D原则

具体示例请看原文:S.O.L.I.D: The First 5 Principles of Object Oriented Design

S.O.L.I.D 代表着:
S – Single-responsiblity principle 单一责任原则

一个类应有且仅有一个理由去变更,即一个类只应用于一个工作。

O – Open-closed principle 开闭原则

对象或实体只应该开放扩展,而不该开放修改。

我的理解是应该避免越俎代庖的事情发生,不应该在调用某类实体的地方去关心某个对象该方法的具体实现。例如有两个Shape类的继承类Circle及Square,在对各自计算面积的时候,具体计算面积的方法不是调用者需要关心的,否则每增加一种继承类都要去修改调用方法。

L – Liskov substitution principle 李斯柯夫替代原则

令q(x)是关于类型T的对象x的可证明属性。那么对于T的子类型S的对象y,q(y)也应该是可证明的。

这个是官话,简单来说就是每个子类都应该可替代他们的父类,所谓“子承父业”。

I – Interface segregation principle 接口分离原则

永远不应该强迫用户实现它不使用的接口,或不应该强迫用户依赖于他们不使用的方法。
比如不应该让一个二维平面的类去实现一个计算体积的方法。

D – Dependency Inversion Principle 依赖倒置原则

实体必须依赖于抽象,而不是具象。高级别的模块不能依赖于低级别模块,而是需要依赖于某种抽象。

比如一个Gateway类需要通过某种网络IO接收数据,它应该依赖于一种IO接口的抽象而不是具体的某种IO(比如UDP IO),否则当你想换一种IO做同样的事情时你就会很头疼。

654. Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

  1. The root is the maximum number in the array.
  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
  3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

 

 

C++ Template: Handle mutual (circular) dependencies

Sometimes we have two classes that need to call each other’s somewhat function, for example

but as you can see A depends on B’s type to initialize and vise versa. If we declare the types as above we’ll not get a chance to create any instance.

There are at least two ways to resolve the issue.

I.Template template

A quick introduction about template template can be found here.

Declare either of {A, B} with template of template which accepts the other’s template argument.

II.Type traits

The other resolution is create a type trait struct which acts like a bridge that links the type of each other.

 

Some of the best answers to LeetCode questions

Here I gathered some of (what I thought are) best answers to LeetCode questions:

  • https://leetcode.com/problems/wiggle-subsequence/discuss/84887/C++-0ms-O(N)-dynamic-programming-solution
    • an O(n) solution
  • https://leetcode.com/problems/trapping-rain-water/description/
    • an O(n) solution of a similar (but harder) question, found in the book <算法竞赛入门经典(第二版) pp249例8-18
    • basic idea is to find a maximal height which can reserve the water for each position i, if the max height equals to the unit then no rain can be collected at i
    • (vice versa, from right to left)

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)的遍历操作了。