存档

算法学习:(单)链表问题

2018/06/17 330

一 链表倒置

链表倒置是链表的基本操作之一。

题目 一 Reverse Linked List

LeetCode 206 Reverse Linked List

Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?

题目提示可以用 迭代 或 递归 两种方法来解。

  • 迭代方法
    如图: 两个指针 head p 分别指向 表头,欲倒置的元素. 为了使下一个欲倒置的元素不会  掉, 还需要一个指针 tmp 来保护它

    1. p->next 指向 head
    2. head->next 指向 tmp
    3. head = p, p = tmp, tmp 保护下一个欲倒置的元素

    代码:

  • 递归方法
    思想和上面一样,只不过代码的写法不同:

    递归的方法代码简洁高效,在很多链表题目中都会用到它,所以特别重要。例如下一题

阅读全文…

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

2018/06/12 287

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

提示:本文中的 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上展示。该类有如下纯虚函数,必须在子类中实现:

阅读全文…

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

2018/03/13 295

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

1. using 声明

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

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

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

阅读全文…

C++11/14 新特性 (多线程)

2017/03/28 2,333

在 C++11 之前 ,C++ 标准并没有提供统一的并发编程标准,也没有提供语言级别的支持。这导致我们在编写可移植的多线程程序时很不方便,往往需要面向不同的平台进行不同的实现,或者引入一些第三方平台,如Boost,pthread_win32 等。 从C++11开始 ,对并发编程进行了语言级别的支持,使用使用C++进行并发编译方便了很多。这里介绍C++11并发编译的相关特性。

1 线程

1.1 线程的创建

std::thread 的构造函数如下:

我们只需要提供线程函数或函数对象,即可以创建线程,并可以同时指定线程函数的参数。

join函数将会阻塞线程,直到线程函数执行完毕,主线程才会接着执行。如果线程函数有返回值,返回值将被忽略。 在使用线程对象的过程中,我们需要注意线程对象的生命周期。如果线程对象先于线程函数结束,那么将会出现不可预料的错误。可以通过线程阻塞的方式来等待线程函数执行完(join),或让线程在后台执行。 如果不希望线程被阻塞,可以调用线程的 detach() 函数,将线程与线程对象分离。但需要注意的是,detach 之后的线程无法再使用join来进行阻塞了,即detach之后的线程,我们无法控制了。当我们不确定一个线程是否可以join时,可以先使用 thead::joinable() 来进行判断。

另外,我们还可以通过 std::bind, lambda 来创建线程(其实就是使用函数对象创建线程)。

线程不可以被复制,但是可以被移动:
阅读全文…

C++11/14 新特性(function/bind 可调用对象包装器与绑定器)

2017/02/28 1,946

1 可调用对象

在 C++ 中,可调用对象一般是指:

  • 一个函数指针
  • 一个重载 () 操作符的类对句(仿函数)
  • 一个可被转换为函数指针的类对象
  • 一个类成员函数指针

上例中的这些对象(func_ptr,foo,bar,mem_func_ptr,mem_obj_ptr) 均可称之为 “可调用对象”。相应的,其类型可被称作“可调用类型”。注意这里只有成员函数有成员函数指针而没有函数类型或函数引用类型,这是因为函数类型并不能直接用于定义对象,而函数引用或以看做一个 const 的函数指针。 可调用对象具有比较统一的调用形式,即使用括号操作(除成员函数指针),而定义的方法各不一样。这样我们在试图使用统一的方式保存,或传递一个可调用对象时,会十分烦琐。

2 std::function 可调用对象包装器

std::function 是一个类模板,它可以容纳除了类成员(函数)指针之外的所有可调用对象。通过指定它的模板参数,它可以用统一的方式处理函数、函数对象、函数指针,并允许保存和延迟调用它们。
阅读全文…