算法学习:动态规划问题的一般解法

2018/06/12

例题 一 : Triangle

LeetCode 120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

分析:

设三角形共有 $N$ 行, $r$ 为三角形的行, $c$ 为三角形的列。从点 $P(r,c)$ 出发,每向下走一步有两个点$P_1(r+1,c), P_2(r+1, c+1)$ 可以选择 ,如果每次都选值小的点$min(P1, P2)$,则最后得到的点的值之和即是最优解。令 $M(r,c)$ 为从 $P(r,c)$ 开始到下面的列的各条路径中,最佳路径的数字之和。

解法一:

这是一个典型的递归问题。

$$M(r,c) = \begin{cases}  P(r,c), & \text{if r = N }\\  min(M(r+1,c), M(r+1,c+1)) + P(r,c),& \text{others}\\ \end{cases}$$

由此写出代码:

代码没有问题,在 “Run Code” 时可以得出正确的结果。但是 “Submit” 却会给出 “Time Limit Exceeded”,超时!

如果我们推算这个解法的时间复杂度的话,可以得到 $O(2^n)$ .这不超时就有鬼了。我们需要改进这个算法。

阅读全文…

在 Qt 中使用 TreeView

2018/05/11

提示:本文中的 Demo 已 push 到 github,可忽略本文直接到 我的github 中查看代码。

Qt 提供了 QuickControl TreeView 。但是比较奇葩的是该控件不能直接使用,而需要用户自己扩展实现。
官方给出了一个示例如下:

它声明了一个 TreeView控件,该控件有 2 列,分别为 Name 和 Permissions,还有一个名为 fileSystemModel 的 model 。对用户来说,这里的 model 是一个关键性的对象,它需要用户使用 C++ 实现 ,并注册到 qml 中供 TreeView 使用。按官方的说法, model 是一个 为 tree view 提供数据的属性,它包含了 tree view 将要展示的数据
用户的 model 必须继承于 QAbstractItemModel
该类是一个抽象类,在运行中,treeview 从该类中获取用户数据,再在UI上展示。该类有如下纯虚函数,必须在子类中实现:

阅读全文…

Coding , 644

CMake 为项目添加自定义事件

2018/04/26

为满足需求:

项目编译前需要预处理一些自定义命令,如生成代码文件,拷贝成果文件等。

解决该问题有两种方案:

add_custom_command prebuild

vcxproj 可以自定义生成事件,如:

阅读全文…

Note 657

多线程编程中的一些原则

2018/03/19

关于 C++ 多线程编程一的些基本知识可以参考本博客的《C++11/14 新特性(多线程)》 ,《Unix线程基础》。本章不是多线程编程教程,而是个人经验的一些总结。这些经验有一些可能是不正确的,希望在今后的编程中实践、改进。

线程同步的四项基本原则:

  1. 最低限度地共享对象。对象尽量不要暴露给别的线程,如果需要暴露,优先考虑 immutable对象。否则尽量使用同步措施来充分地保护它
  2. 尽量使用高级地并发编程构件,如 任务队列、生产者消费者模式等
  3. 只用非递归的互斥器和条件变量,慎用读写锁,尽量少用信号量
  4. 除了使用 atomic 整数外,不要自己编写 lock-free 代码,也不要用”内核级”同步原语

互斥器 Mutex

mutex 是最常用的同步原语,它保护一个临界区,任何时候最多只能有一个线程能够访问 mutex 保护的域。使用 mutex 主要是为了保护共享数据。一般原则有:

  • 使用 RAII手法封装 mutex 的创建、销毁、加锁、解锁操作,充分保证锁的有效期等于其作用域,而不会因为中途返回或异常而忘记解锁。这类似于 Java 的synchronized 或 C# 的 using 语句。
  • 使用非递归的 mutex
  • 尽量不要人为地调用 lock()unlock()函数,将这些操作交给栈上的 guard 对象,利用其构造与析构函数。
  • 不要跨线程地加解锁,避免在不同的函数中分别加锁\解锁,避免在不同的语句分支中加锁\解锁
  • 每当构造 guard 对象时,需要考虑栈上已有的锁,防止因加锁顺序不同而导致死锁
  • 避免跨进程的 mutex, 进程间通讯尽量使用 TCP sockets

只使用非递归地 mutex

阅读全文…

using 关键字在 C++ 中的几种用法

2018/03/13

对C++中 using关键字的几种用法的总结:

1. using 声明

using 声明 (using declaration) 是将命名空间中单个名字注入到当前作用域的机制,使得在当前作用域下访问另一个作用域下的成员时无需使用限定符 ::

using 声明将其它 namespace 的成员引入本命名空间的 当前作用域 (包括其嵌套作用域)  。一个 using 声明一次只引入一个命名空间成员,它使得无论程序中使用哪些名字,都非常准确。
利用 using 声明,可以改变派生类对父类成员的访问控制:

尽管 Derived 对 base 是私有继承,但通过 using 声明,我们还是可以在 Derived 中访问其成员,且后续的继承同样不受 private 限定的影响。

阅读全文…

正则表达式

2018/02/18

正则表达式为高级的文本模式匹配、抽取、与/或文本形式的的搜索与替换功能提供基础。简单地说,它可以匹配多个字符串。

符号

择一匹配、任意匹配

  • | 择一匹配,表示从多个模式中选择其中一个 ,如 at | home 既可以匹配 at, 也可以匹配 home
  • . 任意匹配,表示匹配除了换行符 \n 以外的任何一个字符

边界匹配

  • ^ $ 用于匹配行的开头和结尾
  • \b 用于匹配字符边界。\B 则与之相反。如 \bthe 匹配任何以 the 起始的单词,\Bthe 匹配任何不以 the 起始的单词

字符集

阅读全文…