Archive for the ‘C/C++’ category

字符串切割问题求解

June 30th, 2015

我在做Leetecode的一道题时,遇到了一道切割字符串求解回文字符串的题目,题目大意如下:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

这个时候我们需要使用DFS算法,进行深搜,但是这个里我们需要注意的一个问题是,每个字符只能用一次,而且不能使用拼接的方式,需要直接从string s中截取子字符串,所以我们使用s.substr(start,count)的方式。这个不同于之前的combinationSum的题目,需要有一个中间target保存。我们只需要传入下面几个参数即可,使用step来标示当前指向s的开头index,i为结束index。

void DFS(string &s,vector<vector<string>> &result,vector<string> &path,int step){
		if(step>=s.size()){
			result.push_back(path);
			return;
		}
		for(auto i = step;i<s.size();i++){
			if(is_palindrome(s,step,i)){
				path.push_back(s.substr(step,i-step+1));
				DFS(s,result,path,i+1);
				path.pop_back();
			}
		}
	}

	bool is_palindrome(string &s,int start,int end){
		while(start < end){
			if(s[start]!=s[end])
				return false;
			start++;
			end--;
		}
		return true;
	}
};

一个长度为n 的字符串,有n-1 个地方可以砍断,每个地方可断可不断,因此复杂度为O(2^(n-1))

 

https://leetcode.com/problems/palindrome-partitioning/

信号处理函数所踩过的坑

June 16th, 2015

Update 2015-6-24

最近在看APUE的信号章节,在这里我总结下进程信号处理中应该注意的一些坑。Unix中有很多的信号是可以被进程接管,然后跳到信号处理函数中。

1. 有两个信号是无法被接管或者被忽略的SIGKILL与SIGSTOP

2. SIGHUP 是要出现在远程ssh一台主机时,连接意外断开时,系统会向所有与这个终端相关的控制进程发送SIGHUP。

3. 在liunx中SIGIO与SIGPOLL相同,默认是终止这个进程。

4. SIGTERM可以由进程编写者定义,当收到这个信号那么,进程可以自行做退出操作的扫尾工作,然后退出程序。

5. signal与sigaction功能相似,但是signal在不同平台上实现不同,应该使用sigaction进程信号的接管。

6. 交互式进程后台运行时,shell会将后台进程设置为对于中断和退出信号的处理方式设置为忽略SIG_IGN。也就是说当向进程发送SIGINT时,捕捉这种类型的代码:

void sig_int(int), sig_quit(int);
if (signal(SIGINT, SIG_IGN) != SIG_IGN)
    signal(SIGINT, sig_int);
if (signal(SIGQUIT, SIG_IGN) != SIG_IGN)
    signal(SIGQUIT, sig_quit);

7. 当父进程fork()一个子进程,子进程将会继承父进程的信号处理函数,这种方式在早期fork()一个子进程后会把这个子进程信号处理函数复位到默认值,我们不必在代码中这么做:

int sig_int(); /* my signal handling function */
...
signal(SIGINT, sig_int); /* establish handler */
...
sig_int()
{
    signal(SIGINT, sig_int); /* reestablish handler for next time */
... /* process the signal ... */
}

8. 信号会发生在任何时刻,我们不能设置flag来使得进程进行忙等。下面这种代码在大多数情况下是正确的,但是如果信号发生在while()与pause()之间,会直接导致进程陷入睡眠,无法醒来。

int sig_int(); /* my signal handling function */
int sig_int_flag; /* set nonzero when signal occurs */
main()
{
     signal(SIGINT, sig_int); /* establish handler */
...
     while (sig_int_flag == 0)
            pause(); /* go to sleep, waiting for signal */
...
}
sig_int()
{
    signal(SIGINT, sig_int); /* reestablish handler for next time */
    sig_int_flag = 1; /* set flag for main loop to examine */
}

9. 被中断的syscall(通常是慢速系统调用:read,write,open()(如果open不返回,就意味着进程会被永久的阻塞) etc.)必须显式的处理出错返回,在linux中被中断的syscall,会重启这个syscall,但是在当次的调用中,会将errno设置为EINTR,所以我们要对这个EINTR进行处理。如下面的代码:

again:
if ((n = read(fd, buf, BUFFSIZE)) < 0) {
    if (errno == EINTR)
        goto again; /* just an interrupted system call */
    /* handle other errors */
}

10. 信号处理函数的可重入性。如果在信号处理函数中调用,会对进程主体的程序执行流造成破坏,产生Sigment fault。在内核中的实现,我发现为了实现进程处理函数在用户态执行,会将内核态的堆栈数据复制到用户空间的堆栈保存,返回用户空间,执行完sys_sigreturn() 再次陷入到内核,将正常程序的用户态堆栈硬件上下文拷贝到内核堆栈,并将之前备份在用户空间的堆栈还原到内核空间,完成这次中断处理函数。

不可重入性:(a) they are known to use static data structures, (b) they call malloc or free, or (c) they are part of the standard I/O library. Most implementations of the standard I/O library use global data structures in a nonreentrant way.

所以按照定义,为了保证函数是可重入的,需要做到一下几点:

  • 不在函数内部使用静态或者全局数据
  • 不返回静态或者全局数据,所有的数据都由函数调用者提供
  • 使用本地数据,或者通过制作全局数据的本地拷贝来保护全局数据
  •  如果必须访问全局数据,使用互斥锁来保护
  • 不调用不可重入函数

getpwnam()函数是非可重入函数,他在中断处理函数中使用的话,就会修改原来应用程序的数据,导致程序出错

#include "apue.h"
#include <pwd.h>
static void
my_alarm(int signo)
{
       struct passwd *rootptr;
       printf("in signal handler\n");
       if ((rootptr = getpwnam("root")) == NULL)
           err_sys("getpwnam(root) error");
        alarm(1);
}
int main(void)
{
       struct passwd *ptr;
       signal(SIGALRM, my_alarm);
       alarm(1);
       for ( ; ; ) {
           if ((ptr = getpwnam("sar")) == NULL)
               err_sys("getpwnam error");
           if (strcmp(ptr->pw_name, "sar") != 0)
               printf("return value corrupted!, pw_name = %s\n",ptr->pw_name);
       }
}

这段代码中的rootptr其实最后都是指向ptr,这就是造成不可重入的关键!我们使用getpwnam_r()函数便可以正常工作。

void sig_handler(int signo)
{
   struct passwd root_ptr;
   struct passwd *result;
   int s;
   char *buf;
   size_t bufsize;

   bufsize = sysconf(_SC_GETPW_R_SIZE_MAX);
   if(bufsize==-1)
      bufsize = 16384;

   buf = malloc(bufsize);
   if(buf==NULL){
      perror("malloc");
      exit(EXIT_FAILURE);
   }

   printf("in sig_handler\n");
   s = getpwnam_r("root",&root_ptr,buf,bufsize,&result);
   if(result == NULL){
      if(s==0)
          printf("Not found\n");
      else{
          // errno = s;
          perror("getpwnam_r");
      }
      exit(EXIT_FAILURE);
   }
   printf("pw_name = %s\n", root_ptr.pw_name);
   alarm(1);
}

11. SIGCHLD这个信号非常特殊,这个信号很多时候与系统的信号实现相关。在linux平台上 SIGCHLD与SIGCLD等同,这里查看C/S模型下Server 中fork()的健壮性文章,我们需要在父进程信号处理函数中调用pid = wait(&stat);实现对于子进程退出的等待。

void sig_zchild(int signo)
{
      pid_t pid;
      int stat;

      while ((pid = waitpid(-1, &stat, WNOHANG)) > 0)
           printf("child %d terminated\n", pid);
      return;
}

12. kill() 函数负责将信号发送给进程或者进程组,raise()是进程向自己发送信号。一个程序全局只能有一个alarm()函数,如果多次调用,那么alarm()登记的值被新值代替。pause()使得调用进程挂起直至捕捉到一个信号,只有执行了一个信号处理函数返回后,pause()才返回。

#include <signal.h>
#include <unistd.h>
static void
sig_alrm(int signo)
{
/* nothing to do, just return to wake up the pause */
}
unsigned int
sleep1(unsigned int seconds)
{
      if (signal(SIGALRM, sig_alrm) == SIG_ERR)
               return(seconds);
      alarm(seconds); /* start the timer */
      pause(); /* next caught signal wakes us up */
      return(alarm(0)); /* turn off timer, return unslept time */
}

这个函数看似正确,但是有一个竞争条件,如果alarm()后调用被阻塞,然后超时,pause()没有捕捉到信号,那么调用到pause()将永久挂起,这里我们要使用到longjmp() 与 setjmp() 可以使得信号处理函数返回到主函数中指定位置,在longjmp第二个参数设置返回值,在setjmp()中检查这个返回值。可以做到跨函数跳跃,类似于函数内部的goto。

所以使用alarm() pause() 慢速系统调用三者很有可能产生竞争,Linux中syscall是被中断后自启动的。

13. 使用sigprocmask() 可以用来屏蔽,或者取消屏蔽某个信号,但是如果在sigprocmask()之后调用sleep() 函数,程序进入睡眠,这个期间产生的某个屏蔽信号,他会被投递到这个进程,进行处理! APUE 10-11

14. 使用sigaction(int signum, const struct sigaction *act,struct sigaction *oldact)对于信号进行处理,struct sigaction下的成员变量sa_flags可以定义各种中断的动作,包括被中断的系统调用是否会重启(SA_INTERUPT)还有信号处理函数只执行一次后复位等(SA_RESETHAND)默认sigaction()函数不再重启被中断的系统调用。

 15. 使用int sigsuspend(const sigset_t *mask)函数可以挂起当前进程,但是当进程收到mask以外的信号并从中断处理函数返回,那么进程从这个函数返回!mask中的信号,进程会屏蔽掉[4]。

16. sleep() 函数与alarm()函数混用,实现需要依赖于具体实现。

17. SIGSTOP、SIGCONT不允许被接管,如果我们需要在SIGSTOP后自定义一些操作,那么我们可以自定义一个信号和信号处理函数。只要跳转到信号处理函数,那么就可以阻止进程访问错误内存地址,进而可以进行一些处理。

 

 

参考:

[1] http://www.cnblogs.com/mickole/p/3187770.html

[2] http://www.man7.org/linux/man-pages/man3/getpwnam.3.html

[3] http://blog.csdn.net/feiyinzilgd/article/details/5811157

[4] http://blog.sina.com.cn/s/blog_6af9566301013xp4.html

Combination Sum 思路

June 1st, 2015

最新刷leetcode的题目,发现了Combination Sum题目,这个题目分为I、II、III。难度层层递进,题目就是遍历vector容器,选择出符合target number的sum组合,这个题目的思路可以参考DFS通用解法。我们使用那个DFS模板,首先要构造dfs函数。

一般情况下,我们需要五个参数:结果,原始数据集,中间结果,当前指向的数据,满足target number的值:

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target)

然后我们根据candidates中的数据集,深搜这个数据集的各种可能性,将达成target的path中间结果加入result,按照通用模版

void dfs(type &input, type &path, type &result, int cur or gap) {
              if (数据非法) return 0; // 终止条件
              if (cur == input.size()) { // 收敛条件
                  // if (gap == 0) {
                        将path 放入result
              }
              if (可以剪枝) return;
              for(...) { // 执行所有可能的扩展动作
                     执行动作,修改path
                     dfs(input, step + 1 or gap--, result);
                     恢复path
              }
}

第一步:收敛也就是target==0
第二步:使用for(),并在循环中剪枝 if(target-candidates[current]<0) return;
第三步:如果通过第二部,也就意味着这个current合格,可以将这个加入到path中,然后继续深度遍历。dfs(result,candidates,path,current,target-candidates[current]);这里的问题是candidates的数据是可重复的,可以多次使用。如果只使用一次的话,也就意味着我们需要sort(),然后需要将上个满足条件的值跳过,也就是II中的nums[i]==nums[i-1]比较Combination Sum II

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target){
		if(!path.empty()&&target==0){
			result.push_back(path);
			return;
		}
		if(current<candidates.size()){
			int tmp = -1;//start from 0 and 1
			for(;current<candidates.size();current++){
				if(candidates[current]==tmp)
					continue;
				if(target-candidates[current]<0)
					return;

				tmp = candidates[current];
				path.push_back(candidates[current]);
				dfs(result,candidates,path,current+1,target-candidates[current]);
				path.pop_back();
			}
		}
	}

 

 

题目:

 

https://leetcode.com/problems/combination-sum/

https://leetcode.com/problems/combination-sum-ii/

https://leetcode.com/problems/combination-sum-iii/

DFS通用解法

May 8th, 2015

最近在刷一些算法题,发现DFS在单链表,二叉树,图,集合的解题比较多,具有一定的通用规律,现在讲通用方法记录下。拿二叉树举例,比如我们需要从根走到叶子节点才能得到一个解,这种类型非常适合是用DFS,再以二维数组举例,我们可以将二维数组当成一个图,进行搜索,在搜索的同事满足一定的匹配等。

一般情况下Wide-FS只要求有一个解,而且需要将整个中间状态存储到内存中,而DFS只存储一条路径,非常时候解决一些问题。

在DFS中我们需要一个收敛条件,也就是合法解。这时我们就需要把这个中间状态保存到最后的结果中。为了加快深搜,我们可以剪枝,常用方式使用状态数组表示,提前return,可以大大加快递归速度。

通用dfs模板:

/**
* dfs 模板.
* @param[in] input 输入数据指针
* @param[out] path 当前路径,也是中间结果,可以是一维数组
* @param[out] result 存放最终结果,二维数组
* @param[inout] cur or gap 标记当前位置或距离目标的距离,或者可以
* 是start end等标记
* @return 路径长度,如果是求路径本身,则不需要返回长度
* 可以返回bool等,依照题目要求来实现。
*/
void dfs(type &input, type &path, type &result, int cur or gap) {
              if (数据非法) return 0; // 终止条件
              if (cur == input.size()) { // 收敛条件
                  // if (gap == 0) {
                        将path 放入result
              }
              if (可以剪枝) return;
              for(...) { // 执行所有可能的扩展动作
                     执行动作,修改path
                     dfs(input, step + 1 or gap--, result);
                     恢复path
              }
}

这里我举一个例子:列举所有set可能的子集合,比如S=[1,2,3],那么结果是[[3],[2],[1],[1,2,3],[1,3],[2,3],[1,2],[]]
解决这个问题,需要首先按照上面的这种模板构建,首先是这个dfs的input 也就是这个S,中间路径path与S类型相同。结果应该是一个二维数组,也就是vector< vector > result,最后我们需要一个step作为收敛条件。

void dfs(const vector<int> &S, vector<int> &path, vector<vector<int> > &result,int step) {
     if (step == S.size()) {//到达S.size()收敛
           result.push_back(path);
           return;
     }
     //这里没有剪枝
     // 不选S[step]
     subsets(S, path, step + 1, result);
     // 选S[step]
     path.push_back(S[step]);
     subsets(S, path, step + 1, result);
     path.pop_back();
}
 void dfs(vector<int>& nums,vector<int> &path,vector<vector<int>> &result,
                     vector<int>::iterator start){
 
     result.push_back(path);
 
     for(auto i = start;i<nums.end();i++)
     {
          path.push_back(*i);
          dfs(nums,path,result,i+1);
          path.pop_back(); 
     }
 }

深度搜索比较难以理解,层层递归会让我迷失,不过进行断点认真跟踪是可行的。最后跟踪断点结果是:

[]
3
2
2,3
1,
1,3
1,2
1,2,3

还有很多场景,比如二维数组寻路,都会用到上下左右的移动,还要使用flag来标示,具体查看
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/word-search/

priority_queue与heap的使用

April 20th, 2015

1.priority_queue

priority_queue是一个优先队列,下面是他的声明,我们平时可以直接使用下面的方式声明一个优先队列。

priority_queue<int> pq

优先队列内部是一个heap的实现,也就是说默认push到priority_queue中的数据,当我们pop出来的时候,默认是优先级最高的,(数字大的优先级高,数字小的优先级低),这个数据结构默认使用vector作为容器,cmp函数默认使用less作为比较函数。

下面的是一个完整的priority_queue的声明

std::priority_queue
template <class T, class Container = vector<T>,
class Compare = less < typename Container::value_type> > class priority_queue;

 

priority_queue<Type, Container, Functional>
其中Type 为数据类型, Container 为保存数据的容器,Functional 为元素比较方式。Container 必须是用数组实现的容器,比如 vector, deque 但不能用 list。STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果把后面俩个参数缺省的话,优先队列就是大顶堆,队头元素最大。

我们使用的时候和平常queue的方式没有什么太大的却别,最大的区别在于这个cmp应该如何自定义。我们知道cmp是一个函数指针,所以我们可以有两种方式重载cmp函数。

 

struct cmp
{
    bool operator () (int &a, int &b)
    {
        return a > b ;              // 从小到大排序,值 小的 优先级别高
    }
}; 

priority_queue<int,vector<int>,cmp> q;

 

方式1:

struct Time {
    int h;
    int m;
    int s;
};

class CompareTime {
    public:
    bool operator()(Time& t1, Time& t2) // Returns true if t1 is earlier than t2
    {
       if (t1.h < t2.h) return true;
       if (t1.h == t2.h && t1.m < t2.m) return true;
       if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
       return false;
    }
}

这里我们必须保证重载的()函数返回值是bool,上面的重载函数核心就是当t1<t2时候,返回tree,所以得到的也就是从大到小的排列,也是这个数据结构默认的,如果我们想重新实现这个数据结构,改为从小到大排列,那么可以使用下面的方式

方式2:

class CompareTime {
public:
    bool operator()(Time& t1, Time& t2) // t2 has highest prio than t1 if t2 is earlier than t1
    {
       if (t1.h > t2.h) return true;
       if (t2.h == t1.h && t2.m < t1.m) return true;
       if (t2.h == t1.h && t2.m == t1.m && t2.s < t1.s) return true;
       return false;
    }
};

保证第一个大于第二个返回true即可。
上面我们看到在一个class类里面重载()函数,我们也可以在要使用的类里面,使用struct{}方式。

class Solution {
public:
.....
private:
struct cmp {
        bool operator()(ListNode* node1, ListNode* node2) {
            return node1->val > node2->val;
        }
    };
};

在C/C++中,我们可以等同class与struct相似。

2.heap

heap 主要分为push_heappop_heapsort_heapreverse四个函数,我们使用这四个函数使得vector中数据按照heap来排列。

make_heap的两种形式:

template <class RandomAccessIterator>
  void make_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
  void make_heap (RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp );

同样有一个comp函数可以指定以排列顺序,所以priority_queue是基于heap的方式来实现的。

示例代码:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class priority_queue
{
    private:
        vector<int> data;
    public:
        void push( int t ){
            data.push_back(t);
            push_heap( data.begin(), data.end());
        }
        void pop(){
            pop_heap( data.begin(), data.end() );
            data.pop_back();
        }
        int top() { return data.front(); }
        int size() { return data.size(); }
        bool empty() { return data.empty(); }
}; 

int main()
{
    priority_queue test;
    test.push( 3 );
    test.push( 5 );
    test.push( 2 );
    test.push( 4 );

    while( !test.empty() ){
        cout << test.top() << endl;
        test.pop(); }
    return 0;
}

 

参考:

[1] http://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html

[2] http://www.cplusplus.com/reference/queue/priority_queue/

[3] http://stackoverflow.com/questions/23529815/how-to-use-stdmake-heap

[4] http://www.cppblog.com/mzty/archive/2005/12/15/1770.html