我的站点

一个系统软件工程师的随手涂鸦

Date: 十一月 3, 2016

由一道题理解DFS算法

GENERATE PARENTHESES这篇文章讲解了如何使用Depth First Search,即DFS算法生成所有有效的括号组合:

void generateParentheses(int n) {
    dfs("", n, n);
}
void dfs(String s, int left, int right) // build the set of solutions using DFS approach
{
    if(left == 0 && right == 0) // BASE CASE: there is no more parentheses to add? we have a solution!
        System.out.println(s);
    if(left > 0) // while we have left parentheses to add, just add them
        dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added
    if(right > left) // We are gonna add a right parentheses if we have more right parentheses than left ones
        dfs(s + ")", left, right - 1);
}

由此我也总结了一下DFS算法:
(1)DFS算法也是使用递归来解决问题;
(2)

if(left == 0 && right == 0) // BASE CASE: there is no more parentheses to add? we have a solution!
    System.out.println(s);

上述代码是递归的终止条件。
(3)

if(left > 0) // while we have left parentheses to add, just add them
    dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added
if(right > left) // We are gonna add a right parentheses if we have more right parentheses than left ones
    dfs(s + ")", left, right - 1);

每调用一次dfs()函数,会为字符串添加()

if(left > 0) // while we have left parentheses to add, just add them
    dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added

会递归地生成当前位置是(的所有情况。if(right > left)分支则会生成当前位置是)的所有情况。

strace命令介绍

straceLinux上的一个很好用的工具,它可以用来输出程序在运行过程中发生的系统调用以及收到的信号的相关信息,因此在调试和诊断问题时有很大的帮助,特别是在程序没有源码,或是在前期做一些粗略的分析时。strace命令格式如下:

strace [options] command [args]

举个例子:

# strace sleep 300
execve("/usr/bin/sleep", ["sleep", "300"], [/* 24 vars */]) = 0
brk(0)                                  = 0x22fa000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f70d1ef8000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
......
--- SIGTERM {si_signo=SIGTERM, si_code=SI_USER, si_pid=20243, si_uid=0} ---
......

从上面例子可以看出,对于系统调用,比如openaccessstrace都会输出详细的参数和返回值,如果发生了错误,也会输出细致的错误信息。而对于接收到的信号,除了输出信息外,还要注意信号信息的前后都加了“---”,以示与系统调用的区别。

以下是一些常用的选项:
(1)-o:把strace执行结果输出到指定文件里:

# strace -o out ls

(2)-t:打印时间:

# strace -t ls
10:30:07 execve("/usr/bin/ls", ["ls"], [/* 24 vars */]) = 0
10:30:07 brk(0)
......

(3)-e:只关注某一系统调用:

# strace -e open ls
open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
open("/lib64/libselinux.so.1", O_RDONLY|O_CLOEXEC) = 3
......

(4)-y:显示和文件描述符关联的文件路径:

# strace -y ls
......
fstat(3</etc/ld.so.cache>, {st_mode=S_IFREG|0644, st_size=32951, ...}) = 0
mmap(NULL, 32951, PROT_READ, MAP_PRIVATE, 3</etc/ld.so.cache>, 0) = 0x7fba3db13000
close(3</etc/ld.so.cache>)              = 0
......

(5)-f:追踪运行进程所生成的子进程。

参考资料:
strace(1) – Linux man page
A swiss army knife of debugging tools

Powered by WordPress & Theme by Anders Norén