C++博客-技术笔记——Beyond Programming

程序员面试题精选100题－栈的push、pop序列

David Fang — Wed, 01 Sep 2010 03:30:00 GMT

昨天看程序员面试精选100题，看到一个栈的push，pop序列问题。
题目：输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
一开始还真不知道怎么下手，看了分析才知道大概方法。然后再看参考代码,感觉还是有些复杂。自己想了个稍微简单的方法,pop队列还可能是push队列的子集：

1 #include <iostream>
2 #include <stack>
3
4 using namespace std;
5 /*!
6 \brief This algorithm demostrates how to judge whether or not a given seqence is
7 possibly a popup sequence providing the pushing sequence.
8 */
9
10 bool IsPopSequence(int* ppush, int pushm, int* ppop, int popm)
11 {
12     int i = 0, j = 0;
13     stack<int> help_stack;
14     while(j < popm)
15     {
16         if (!help_stack.empty() && help_stack.top() == ppop[j])
17         {
18             help_stack.pop();
19             j++;
20         }
21         else if (i < pushm)
22         {
23             help_stack.push(ppush[i++]);
24         }
25         else
26             break;
27     }
28
29     return j >= popm;
30 }
31
32 int main(int argc, char *argv, char *env[])
33 {
34     //int pushseq[] = {1, 2, 3, 4, 5};
35     //int pushseqlen = sizeof(pushseq)/sizeof(pushseq[0]);
36     ////int popseq[] = {4, 5, 3, 2, 1};
37     //int popseq[] = {4, 3, 5, 1, 2};
38     //int popseqlen = sizeof(popseq)/sizeof(popseq[0]);
39
40     int pushseq[] = {1, 2, 3, 4, 5, 6};
41     int popseq[] = {4, 3, 5, 2, 1};
42     int pushseqlen = sizeof(pushseq)/sizeof(pushseq[0]);
43     int popseqlen = sizeof(popseq)/sizeof(popseq[0]);
44
45     cout<<boolalpha<<IsPopSequence(pushseq, pushseqlen, popseq, popseqlen)<<"\n";
46
47     return 0;
48 }

David Fang 2010-09-01 11:30 发表评论

链表排序之冒泡、插入、选择

David Fang — Fri, 20 Aug 2010 06:24:00 GMT

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 #include 2 #include ... 阅读全文

David Fang 2010-08-20 14:24 发表评论

GNU C/C＋＋简易编译支持脚本

David Fang — Sun, 20 Jun 2010 03:50:00 GMT

看了Unix原理和应用，也是为了平时写些小程序，小例子方便，特别制作了一个易用的辅助脚本，脚本文件compile.sh如下：

#!/bin/sh
#comc.sh: script that helps programming in C/C++
#author:Don

sources=`ls -t *.c *.cpp *.cxx *.h 2>/dev/null`
lastsource=`ls -t *.c *.cpp *.cxx *.h 2>/dev/null | head -n 1`

command=$0
executable="${PWD##*/}"

case $command in
    *r) ./"${executable}" dev/tty >/dev/tty 2>&1 ;;
    *vc) vim $lastsource ;;
    *vac) vim $sources ;;
    *c) gcc -g -O0 -o $executable $sources && echo "gcc compiled successfully";;
    *cxx) g++ -g -O0 -o $executable $sources && echo "g++ compiled successfully";;
esac

放在任何目录下都可以：
然后添加连接到/usr/bin

ln /path/to/compile.sh  /usr/bin/r
ln /path/to/compile.sh  /usr/bin/vc
ln /path/to/compile.sh  /usr/bin/vac
ln /path/to/compile.sh  /usr/bin/c
ln /path/to/compile.sh  /usr/bin/cxx

这样写小程序时就能用下面的步骤了:
1.创建程序目录并切换到目录下

mkdir example && cd $_

2.创建源码文件

vim main.cpp

3.编辑代码，保存
4.编译，如果是cpp代码则运行cxx，如果是c代码则运行c，生成的二进制可执行文件名称是程序坐在目录名称。
5.要重新编辑最后一个源文件则运行vc命令，要重新编辑所有源文件则运行vac命令。
6.编译成功后，要运行时运行r命令。

上面是我参考Unix原理于应用上的一个例子写出来的，最近在搞一些算法方面的题目，用这个脚本做些算法题和简单的测试程序还是比较实用的，当然如果要开发大型的软件，特别是要依赖标准库以外的东西，还是要靠Makefile.

David Fang 2010-06-20 11:50 发表评论

Lua小程序:十六进制字符串和二进制数据间的转换

David Fang — Tue, 30 Mar 2010 14:20:00 GMT

摘要: 最近玩了一下Lua，写了一个小程序，用于实践十六进制字符串和二进制数据之间的转换。
主要是因为最近有这方面的需要（在搞一些 RSA加密的东西）。阅读全文

David Fang 2010-03-30 22:20 发表评论

关于管道——子进程调用命令行并返回执行结果的问题

David Fang — Fri, 05 Mar 2010 11:22:00 GMT

摘要: 一般情况下，用system或CreateProcess创建一个进程来执行一个命令行，并不关心它执行过程中的具体信息，有时甚至不在乎它何时结束，而在今天所碰到的问题中，却恰恰需要关注这两点。阅读全文

David Fang 2010-03-05 19:22 发表评论

在内存中解压-实用gzip解压类封装

David Fang — Fri, 05 Mar 2010 09:51:00 GMT

摘要: zlib的使用一般是以文件作为输入输出，而本类在zlib库基础上进行了一层封装，以便在内存中解压gzip数据，阅读全文

David Fang 2010-03-05 17:51 发表评论

使用Boost.Asio写的多线程TCP转发代理服务器

David Fang — Fri, 05 Mar 2010 07:37:00 GMT

摘要: 应用场景是这样的：客户端和服务器在不同的网段内，它们之间不能直接通过TCP连接，但是有一台机器（暂时称为转发器）有双网卡，两块网卡分别在客户端和服务器端的网段内，这样转发器就能分别和客户端即服务器建立连接，并来回传输数据。设计思路是这样的：当客户端连接到转发器后，转发器马上建立一条到服务器之间的连接，与服务器端的连接建立后，就同时异步地从客户端和服务器端接收数据到两个缓冲区中，一旦... 阅读全文

David Fang 2010-03-05 15:37 发表评论

VI/VIM使用小技巧

David Fang — Fri, 05 Mar 2010 07:31:00 GMT

1.打开文件时自动回到上次关闭时的位置

注意单引号和双引号
2.在普通模式下输入Enter键时也能换行（不用切换到插入模式然后换行然后又切回普通模式这么麻烦的）

:nmap i

或

:nmap i

或

:nmap ylpr

David Fang 2010-03-05 15:31 发表评论

CPP博客开通

David Fang — Fri, 05 Mar 2010 07:17:00 GMT

摘要: 刚刚开通了CPP博客阅读全文

David Fang 2010-03-05 15:17 发表评论