• 2020-01-21

    算法题分类及解题思路

    Views: 8250 | No Comments

    * 暴力破解(brute force)

    暴力破解, 就是穷举. 穷举的方式一般用递归, O(n^2). 优化的思路是减少递归步骤:

    1. 更加严格的静态递归条件
    2. 增加 close_list, 动态地判断是否需要进行递归, close_list 根据执行情况动态变化

    另外的一种优化方向是消除递归. 因为递归是可以通过递归栈 open_list 来消除的. 可以对栈进行动态排序, 优先进行最可能成功的下一个步骤(A*). 这种排序优化, 导致可以使用不同的数据结构来存储递归栈: stack, queue, priority_queue.

    有序性, 有序子集: 有一种非常常用的优化思路是利用输入条件的局部有序性(存在有序的子集), 不再穷举这些有序的子集. 在处理这些有序子集时, 采用 O(n) 或者 O(K) 算法, 最差也能采用二分法 O(logN), 而且其它元素与这些有序子集结合时, 也不再需要穷举.

    A* 算法: open_list 根据沉没成本G和未来成本(H)之和来决定下一个处理步骤, 达成即最优.

    * 动态规划(dynamic programming)

    动态规划与暴力破解类似, 都是分而治之的思路, 但又不相同. 动态规划的下一个处理步骤是唯一的, 而且 open_list 初始可以确定, 后续单调递减. 下一个步骤的处理除了依赖自身的静态条件, 还依赖之前的处理结果集, 并维护这个结果集. 有点像消除了递归之后的暴力破解, 但暴力破解的 open_list 不是初始固定的.

    * 直观解法(coding)

    这类问题的解法非常直观, 一般没有算法上的优化空间, 也不需要技巧, 纯粹是为了训练编程能力. 考察做题者对变量的状态判断是否完备充分, 判断路径是否最简, if 分支是否可以合并等等. 所以, 就是考察边界条件的判断, 还有逻辑条件精减, 要求有非常强的逻辑思维能力.

    一般这类题就是链表翻转, 有序链表合并, 删除重复元素, 数组遍历(螺旋向内, 螺旋向外, 蛇形, 等等), partition 等.

    要点是: 边界判断, 分支合并, 简化重合边界的处理, 增加虚拟节点进行辅助.

    Posted by ideawu at 2020-01-21 09:38:57
  • 2020-01-21

    蛇形遍历数组

    Views: 10567 | No Comments

    蛇形遍历数组, 我的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.

    但是, 其实这个问题本质就是从一点出发, 不断地 walk, 一次只 walk 一步, 需要保留方向状态. 如果一次 walk 完斜线, 则不用方向状态, 因为可以根据 walk 的起点来判断.

    Continue reading »

    Posted by ideawu at 01:43:19
  • 2020-01-15

    在有序的KV引擎之上建造结构化数据库引擎

    Views: 27161 | 2 Comments

    KV 数据结构极大地简化了存储引擎的接口和实现. 基本的 KV 接口一般就是 Get(), Set(), 实现上代码也很简单, 极简的实现可以直接利用编码语言提供的 map(哈希, 红黑树)来提供内存数据结构, 而且硬盘上直接 dump 内存数据即可(类似 Redis 的策略).

    不过, KV 存储引擎自己省事了, 但使用者不喜欢, 因为大部分的业务并不是 KV 所能表达的, 业务需要丰富的数据结构, 表格(table), 列表(list), map 等各种容器. 另外还需要排序功能, 业务依赖排序.

    Continue reading »

    Posted by ideawu at 2020-01-15 19:30:00
  • 2020-01-15

    分而治之算法(divide and conquer)

    Views: 9401 | No Comments

    分而治之算法(divide and conquer)是计算机算法领域最常用最有效的算法之一, 体现到编程上就是树(数据结构), 递归函数. 一般的代码模板是这样的:

    func recursive(N){
    	if(!N){return;}
    	a, b = split(N); // divide 
    	proc(a);         // conquer a
    	recursive(b);      // process b
    }
    

    对于寻路, 分段处理最终达成目标这种模式的问题, 一般的代码模板是:

    func recursive(N){
    	if(!N){return;}
    	a, b = split(N); // divide 
    	r = proc(a);     // conquer a
    	if(r){recursive(r + b);}  // conquer remain + b
    	recursive(b);      // process b
    }
    

    多了一步:

    if(r){recursive(r + b);}
    

    因为前一段的剩余, 要和后一段组成新的问题, 然后被处理.

    Posted by ideawu at 16:36:14 Tags:
  • 2020-01-13

    关于分布式的一些记录

    Views: 9820 | No Comments

    多副本一致性的理论基础: W + R > N

    写时要同时写 W 个节点, 读时要同时读 R 个节点. 确保读的时候能获知集群的 commitIndex.
    可以只读写 Leader, 因为 Leader 维护了 commitIndex.
    如果要读 Follower, 则 Follower 要向 Leader 查询 commitIndex, 或者向 R 个节点查询获取最新的 commitIndex.

    分布式事务也是类似, 协调者相当于 Leader, 参与者相当于 Follower.
    如果 Follower 有未提交事务, 收到读或写请求时, 需要向协调者查询事务状态.

    Posted by ideawu at 2020-01-13 19:03:37
  • 2019-04-21

    NSMutableArray 空数组相等, 导致 NSOutlineView 无法正确展开

    Views: 27335 | 2 Comments

    对于 Objective-C, 两个 NSMutableArray isEqual 返回 YES, 无论它们是否相同的范型类型. 这个特性导致 NSOutlineView 在展开两个空的节点(对应着不同的空数组实例)时, 出现混乱. 当你点击展开 A 时, 它却展开 B. 这个可能是 NSOutlineView 内部使用 isEqual 来判断 item 是否相等, 而不是用 "==".

    即使数组不是空的, 只要它们包含相同的内容, 都会出现这个 bug. 原因就是, 不应该用 isEqual 来判断, 而应该用 == 来判断指针是否相等.

    Posted by ideawu at 2019-04-21 15:19:22
|<<<101112131415161718>>>| 14/138 Pages, 825 Results.