豌豆

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

2018/06/12

例题一 : 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}$$

由此写出代码：

class Solution {
public:
    int getMinPathSum(vector<vector<int>>& triangle, int r, int c){
        if(r == triangle.size() - 1) return triangle[r][c];

        int x = getMinPathSum(triangle, r+1, c);
        int y = getMinPathSum(triangle, r+1, c+1);

        x = x<y ? x: y;

        return triangle[r][c] + x;
    }

    int minimumTotal(vector<vector<int>>& triangle) {
        return getMinPathSum(triangle, 0,0);
    }
};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution {

public:

int getMinPathSum(vector<vector<int>>& triangle, int r, int c){

if(r == triangle.size() - 1) return triangle[r][c];

int x = getMinPathSum(triangle, r+1, c);

int y = getMinPathSum(triangle, r+1, c+1);

x = x<y ? x: y;

return triangle[r][c] + x;

}

int minimumTotal(vector<vector<int>>& triangle) {

return getMinPathSum(triangle, 0,0);

}

};

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

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

继续阅读

Coding algorithm, leetcode, 动态规划, 算法 4,676

在 Qt 中使用 TreeView

2018/05/11

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

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

TreeView {
    TableViewColumn {
        title: "Name"
        role: "fileName"
        width: 300
    }
    TableViewColumn {
        title: "Permissions"
        role: "filePermissions"
        width: 100
    }
    model: fileSystemModel
}

1

2

3

4

5

6

7

8

9

10

11

12

13

TreeView {

TableViewColumn {

title: "Name"

role: "fileName"

width: 300

}

TableViewColumn {

title: "Permissions"

role: "filePermissions"

width: 100

}

model: fileSystemModel

}

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

virtual int    columnCount(const QModelIndex &parent = QModelIndex()) const = 0;
virtual QVariant data(const QModelIndex &index, int role = Qt::DisplayRole) const = 0;
virtual QModelIndex    index(int row, int column, const QModelIndex &parent = QModelIndex()) const = 0;
virtual QModelIndex    parent(const QModelIndex &index) const = 0;
virtual int    rowCount(const QModelIndex &parent = QModelIndex()) const = 0;

1

2

3

4

5

virtual int columnCount(const QModelIndex &parent = QModelIndex()) const = 0;

virtual QVariant data(const QModelIndex &index, int role = Qt::DisplayRole) const = 0;

virtual QModelIndex index(int row, int column, const QModelIndex &parent = QModelIndex()) const = 0;

virtual QModelIndex parent(const QModelIndex &index) const = 0;

virtual int rowCount(const QModelIndex &parent = QModelIndex()) const = 0;

继续阅读

Coding qml, qt 9,662

CMake 为项目添加自定义事件

2018/04/26

为满足需求：

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

解决该问题有两种方案：

add_custom_command prebuild

vcxproj 可以自定义生成事件，如：

<ItemDefinitionGroup>  
  <PreBuildEvent>  
    <Command>copy $(ProjectDir)main.cpp $(ProjectDir)copyOfMain.cpp</Command>  
    <Message>Making a copy of main.cpp </Message>  
  </PreBuildEvent>  
  <PreLinkEvent>  
<Command>copy $(ProjectDir)$(Configuration)\main.obj $(ProjectDir)$(Configuration)\copyOfMain.obj</Command>  
    <Message>Making a copy of main.obj</Message>  
  </PreLinkEvent>  
  <PostBuildEvent>  
<Command>copy $(ProjectDir)$(Configuration)\$(TargetFileName) $(ProjectDir)$(Configuration)\copyOfMyproject.exe</Command>  
    <Message>Making a copy of myproject.exe</Message>  
  </PostBuildEvent>  
</ItemDefinitionGroup>

1

2

3

4

5

6

7

8

9

10

11

12

13

14

<Command>copy $(ProjectDir)main.cpp $(ProjectDir)copyOfMain.cpp</Command>

<Message>Making a copy of main.cpp </Message>

</PreBuildEvent>

<Command>copy $(ProjectDir)$(Configuration)\main.obj $(ProjectDir)$(Configuration)\copyOfMain.obj</Command>

<Message>Making a copy of main.obj</Message>

</PreLinkEvent>

<Command>copy $(ProjectDir)$(Configuration)\$(TargetFileName) $(ProjectDir)$(Configuration)\copyOfMyproject.exe</Command>

<Message>Making a copy of myproject.exe</Message>

</PostBuildEvent>

</ItemDefinitionGroup>

继续阅读

Note cmake 6,355

多线程编程中的一些原则

2018/03/19

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

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

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

互斥器 Mutex

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

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

只使用非递归地 mutex

继续阅读

Note c++, thread, 多线程 5,328

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

2018/03/13

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

1. using 声明

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

// ...
{
    using std::map
    map<int, std::string> the_map; //ok
}
map<int, std::string> the_map2;  //error

1

2

3

4

5

6

// ...

{

using std::map

map<int, std::string> the_map; //ok

}

map<int, std::string> the_map2; //error

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

class Base{
protected:
    int bn1;
    int bn2;
};

class Derived: private Base{
public:
    using Base::bn1;
};

class DerivedAgain: public Derived{
};

int main(){
    Derived d;
    DerivedAgain da; 
    d.bn1 = 1;
    d.bn2 = 2; //error, 'bn2' is a private member of 'Base'
    da.bn1 = 3;  //ok
    std::cout<<d.bn1<<std::endl;

    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Base{

protected:

int bn1;

int bn2;

};

class Derived: private Base{

public:

using Base::bn1;

};

class DerivedAgain: public Derived{

};

int main(){

Derived d;

DerivedAgain da;

d.bn1 = 1;

d.bn2 = 2; //error, 'bn2' is a private member of 'Base'

da.bn1 = 3; //ok

std::cout<<d.bn1<<std::endl;

return 0;

}

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

继续阅读

Coding c++, c++11 16,144

正则表达式

2018/02/18

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

符号

择一匹配、任意匹配

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

边界匹配

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

字符集

继续阅读

Note regex, 正则表达式 5,264

跨平台的命令行参数工具 — boost program_oprations

2018/02/16

1 例子

下例展示了 program_oprations 的基本用法：为程序定义了 3 个参数: help, host, port . 其中 host 与 port 分别定义了简写 h ,p 。host 是必填项， port 是有缺省值(80)的选填项，当 port 有输入时使用输入项，否则使用缺省值，当输入了错误的参数时会输出错误信息。

#include <iostream>
#include "boost/program_options.hpp"

using namespace boost;

int main(int argc, char* argv[])
{
    program_options::options_description desc("Allowed options");
    desc.add_options()
	("help", "help")
	("host,h", program_options::value<std::string>()->required(), "host name")
	("port,p", program_options::value<int>()->default_value(80), "port number");

    program_options::variables_map vm;

    try
    {
	auto ops = program_options::parse_command_line(argc, argv, desc);
	boost::program_options::store(ops, vm);
    }
    catch (boost::program_options::error& e)
    {
	std::cout << e.what() << std::endl;
	return 1;
    }

    if (vm.count("help"))
    {
	std::cout << desc << std::endl;    
    }

    if (!vm.count("host"))
    {
	std::cout << "param is need : " << desc << std::endl;
	return 1;
    }

    //do sth ...

    std::cout << "Host is : "
	<< vm["host"].as<std::string>()
	<< ", Port is : "
	<< vm["port"].as<int>()
	<< std::endl;

    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

#include <iostream>

#include "boost/program_options.hpp"

using namespace boost;

int main(int argc, char* argv[])

{

program_options::options_description desc("Allowed options");

desc.add_options()

("help", "help")

("host,h", program_options::value<std::string>()->required(), "host name")

("port,p", program_options::value<int>()->default_value(80), "port number");

program_options::variables_map vm;

try

{

auto ops = program_options::parse_command_line(argc, argv, desc);

boost::program_options::store(ops, vm);

}

catch (boost::program_options::error& e)

{

std::cout << e.what() << std::endl;

return 1;

}

if (vm.count("help"))

{

std::cout << desc << std::endl;

}

if (!vm.count("host"))

{

std::cout << "param is need : " << desc << std::endl;

return 1;

}

//do sth ...

std::cout << "Host is : "

<< vm["host"].as<std::string>()

<< ", Port is : "

<< vm["port"].as<int>()

<< std::endl;

return 0;

}

测试效果：

>testBoostProgramOptions.exe
param is need : Allowed options:
  --help                  help
  -h [ --host ] arg       host name
  -p [ --port ] arg (=80) port number

>testBoostProgramOptions.exe  -h 127.0.0.1
Host is : 127.0.0.1, Port is : 80

>testBoostProgramOptions.exe  -h 127.0.0.1 -p  8080
Host is : 127.0.0.1, Port is : 8080

>testBoostProgramOptions.exe  -h 127.0.0.1 -p  8080  -o er
unrecognised option '-o'

>testBoostProgramOptions.exe  -p  8080
param is need : Allowed options:
  --help                  help
  -h [ --host ] arg       host name
  -p [ --port ] arg (=80) port number

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

>testBoostProgramOptions.exe

param is need : Allowed options:

--help help

-h [ --host ] arg host name

-p [ --port ] arg (=80) port number

>testBoostProgramOptions.exe -h 127.0.0.1

Host is : 127.0.0.1, Port is : 80

>testBoostProgramOptions.exe -h 127.0.0.1 -p 8080

Host is : 127.0.0.1, Port is : 8080

>testBoostProgramOptions.exe -h 127.0.0.1 -p 8080 -o er

unrecognised option '-o'

>testBoostProgramOptions.exe -p 8080

param is need : Allowed options:

--help help

-h [ --host ] arg host name

-p [ --port ] arg (=80) port number

progma_options 库由三部分组成：

descrition , 描述组件，用于描述允许的参数及这些参数的值。
parser , 解析组件，用于解析输入的参数与值
storage , 存储组件，它将解析器的输出转换成字符串表示的健与 C++ 类型的值的 map, 并提供了访问这些值的接口。

对于上例来说， program_options 所做的事情，就是使用 options_description 描述了我们期望的参数，使用 parse_command_line 解析了输入参数并使用 store 将参数存储在 variables_map 中。当我们需要使用某个参数时直接从 variables_map 中获取。

继续阅读

Note boost, program_oprations 6,094

CMake 使用札记

2018/01/20

本篇记录在使用 CMake 中遇到的一些问题及解决办法

参考资料：

继续阅读

Note cmake 6,233

豌豆

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

例题一 : Triangle

解法一：

在 Qt 中使用 TreeView

CMake 为项目添加自定义事件

add_custom_command prebuild

多线程编程中的一些原则

互斥器 Mutex

只使用非递归地 mutex

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

1. using 声明

正则表达式

符号

择一匹配、任意匹配

边界匹配

字符集

跨平台的命令行参数工具 — boost program_oprations

1 例子

CMake 使用札记

页面

近期文章

归档

分类

链接

例题 一 : Triangle

解法一：

add_custom_command prebuild

互斥器 Mutex

只使用非递归地 mutex

1. using 声明

符号

择一匹配、任意匹配

边界匹配

字符集

1 例子

页面

近期文章

归档

分类

标签

链接

例题一 : Triangle