数组中元素和问题
给定n个数字序列，各个数字都不相同，给定K值。
1. 从序列中找到所有的数对，其和为K
2. 从序列中找出三个数，其和为K，找出所有的情况
3. 从序列中找出任意个数，其和为k。
| 1 | 3 | 5 | 7 | 8 | 9 |
| f | | | | | b |
| 1 | 3 | 5 | 7 | 8 | 9 |
| | f | | | | b |
| 1 | 3 | 5 | 7 | 8 | 9 |
| | f | | | b | |
f和b分别是从最左和最右遍历的指针，当*f+*b < 11时，则f指向的数字
不可能和其他的数字相加为11，因为剩余的数字都小于*b。同理当
*f+*b>11时，*b不可能和其他的数字相加为11，因为其他的数字都大于
*f。当*f+*b=11时，同时移动f,b，并且保存结果。
2. 从序列中找出三个数，其和为K，找出所有的情况
3. 从序列中找出任意个数，其和为k。
问题一
首先将数组排序，假如K=11， 排好序的结果如下：| 1 | 3 | 5 | 7 | 8 | 9 |
| f | | | | | b |
| 1 | 3 | 5 | 7 | 8 | 9 |
| | f | | | | b |
| 1 | 3 | 5 | 7 | 8 | 9 |
| | f | | | b | |
f和b分别是从最左和最右遍历的指针，当*f+*b < 11时，则f指向的数字
不可能和其他的数字相加为11，因为剩余的数字都小于*b。同理当
*f+*b>11时，*b不可能和其他的数字相加为11，因为其他的数字都大于
*f。当*f+*b=11时，同时移动f,b，并且保存结果。
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
vector< vector<int> > sum2( const std::vector<int> &A,int start,int end,int K ) {
vector< vector<int> > ret;
for(int i = start,j = end; i < j ; ) {
int sum = A[i] + A[j];
if( sum > K ) {
j--;
} else if( sum < K ) {
i++;
} else {
vector<int> tmp;
tmp.push_back(A[i]);
tmp.push_back(A[j]);
ret.push_back(tmp);
j--,i++;
}
}
return ret;
}
问题二、
从左到右遍历数组，假定先取一个最小的当前元素，然后在该元素后面取两个数字，使其和为K-a[i],这样就可以列举到所有的情况
vector< vector<int> > sum3( const std::vector<int> &A,int len,int K ) {
vector< vector<int> > ret;
for( int i = 0; i < len; i++ ) {
vector<vector<int> > tmp = sum2( A,i+1,len - 1,K - A[i] );
for(unsigned int j = 0; j < tmp.size(); j++){
vector<int> cur;
cur.push_back(A[i]);
cur.push_back(tmp[j][0]);
cur.push_back(tmp[j][1]);
ret.push_back(cur);
}
}
return ret;
}
问题三、
假定取当前元素作为最小元素，则在后面取任意个数字的和为K-a[i],如果不取当前数字，则在后面取任意个数字的和为K，递归的出口是：当
当前位置超过数组，或者当前位置的元素大于k。如果当前元素等于k，
则将当前元素作为结果加，并且返回。
void resolve( const std::vector<int> &vi,int pos,int K,std::vector< std::vector<int> > &result ) {
if( pos >= vi.size() || vi[pos] > K )
return ;
if( vi[pos] == K ) {
std::vector<int> temp;
temp.push_back( vi[pos] );
result.push_back( temp );
}
std::vector< std::vector<int> > t1;
resolve( vi,pos+1,K-vi[pos],t1 );
resolve( vi,K,result );
for( int i = 0; i < t1.size(); i++ ) {
t1[i].push_back( vi[pos] );
result.push_back( t1[i] );
}
}
测试
void printSum(vector< vector<int> > v )
{
for(unsigned int i = 0; i < v.size(); i++){
for(unsigned int j = 0; j < v[i].size(); j++)
cout<<"\t"<<v[i][j];
cout<<endl;
}
}
int main()
{
int A[] = { 1,3,5,6,7,8,9,10,-2 };
std::vector<int> vi( A,A + sizeof(A)/sizeof(int) );
std::sort( vi.begin(),vi.end() );
std::cout << "print 2 sum" << std::endl;
printSum( sum2(vi,vi.size() - 1,10));
std::cout << "print 2 sum" << std::endl;
printSum( sum2(vi,2,10));
std::cout << "print 3 sum" << std::endl;
printSum(sum3(vi,vi.size(),10));
cout<<endl<<endl;
vector<vector<int> > res;
resolve( vi,res );
std::cout << "print K sum" << std::endl;
printSum(res);
getchar();
return 0;
}
正则表达式匹配
问题描述
'.'用来匹配任意字符，'*'用来匹配0个或者以上的前置字符，给出字符
串以及含有.*的模式串，返回其是否匹配。
一些例子:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa","a*") ? true
isMatch("aa",".*") ? true
isMatch("ab",".*") ? true
isMatch("aab","c*a*b") ? true
串以及含有.*的模式串，返回其是否匹配。
一些例子:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa","a*") ? true
isMatch("aa",".*") ? true
isMatch("ab",".*") ? true
isMatch("aab","c*a*b") ? true
算法描述以及代码
正则表达式的匹配问题是比较难写的递归问题。
首先是递归结束的条件，当字符串和模式串都结束了，表明匹配结束，显
然应该返回true，但是我们还要考虑当模式串没有结束，但是模式串匹配
0个字符的情况，总结起来如下：
if( src[sstart] == '\0' && (pattern[pstart] == '\0' ||
(pattern[pstart + 1] == '*' && pattern[pstart + 2] == '\0')) )
return true;
对于其他情况，当字符串或者模式串结束了一个，则返回false。
然后考虑*匹配0个，匹配一个或者以上字符的情况。如果不是*，则只用
考虑匹配当前字符。
首先是递归结束的条件，当字符串和模式串都结束了，表明匹配结束，显
然应该返回true，但是我们还要考虑当模式串没有结束，但是模式串匹配
0个字符的情况，总结起来如下：
if( src[sstart] == '\0' && (pattern[pstart] == '\0' ||
(pattern[pstart + 1] == '*' && pattern[pstart + 2] == '\0')) )
return true;
对于其他情况，当字符串或者模式串结束了一个，则返回false。
然后考虑*匹配0个，匹配一个或者以上字符的情况。如果不是*，则只用
考虑匹配当前字符。
#include <assert.h>
#include <iostream>
bool isMatch(const char *src,int sstart,const char *pattern,int pstart) {
if( src[sstart] == '\0' && (pattern[pstart] == '\0' ||
(pattern[pstart + 1] == '*' && pattern[pstart + 2] == '\0')) )
return true;
if(pattern[pstart] == '\0' || src[sstart] == '\0' )
return false;
if(pattern[pstart + 1] == '*'){
if(isMatch(src,sstart,pattern,pstart + 2))
return true;
if (pattern[pstart] == '.' || src[sstart] == pattern[pstart])
return isMatch(src,sstart + 1,pstart);
return false;
} else {
if(pattern[pstart] == '.' || src[sstart] == pattern[pstart])
return isMatch(src,pstart + 1);
return false;
}
return false;
}
测试
//we donot support the pattern start with '*' character
bool isMatch(const char *src,const char *pattern) {
return isMatch(src,0);
}
int main()
{
assert(isMatch( "aa","a") == false);
assert(isMatch( "aa","aa") == true );
assert(isMatch("aaa","aa") == false);
assert(isMatch("aa","a*") == true);
assert(isMatch("aa",".*") == true);
assert(isMatch("ab",".*") == true);
assert(isMatch("aab","c*a*b") == true);
getchar();
return 0;
}
BFS最短路径问题
问题描述
给定一个棋盘的边界，然后有一个棋子，棋子按照“日”字形的走法，
求解棋子从某一处走到另一处的最少步数。
比如棋子当前位置为(1,2)，则按照日子形的走法，在x方法加1，y方法
加2，则位置为 (2,4),也可能在x方向加2，y方向加1，则为(3,3)....
如果给定当前位置为（0,0),要走到（30，30）处，则最少需要多少步。
这个问题是一个典型的BFS求最短路径问题。（代码为Visual studio）
求解棋子从某一处走到另一处的最少步数。
比如棋子当前位置为(1,2)，则按照日子形的走法，在x方法加1，y方法
加2，则位置为 (2,4),也可能在x方向加2，y方向加1，则为(3,3)....
如果给定当前位置为（0,0),要走到（30，30）处，则最少需要多少步。
这个问题是一个典型的BFS求最短路径问题。（代码为Visual studio）
#include "StdAfx.h"
#include <iostream>
#include <unordered_map>
#include <queue>
#include "my_algorithm.h"
const int step_type = 8;
int move_type[step_type][2] = {
{1,2},{1,-2},{-1,{2,1},-1},{-2,-1}
};
struct Position{
int x_,y_;
Position( int x,int y ) : x_(x),y_(y) { }
};
bool operator==( const Position &lhs,const Position &rhs ) {
return lhs.x_ == rhs.x_ && lhs.y_ == rhs.y_;
}
class PositionHasher {
public:
PositionHasher( const int row,const int column ) :
row_(row),column_(column) { }
unsigned int operator( ) ( const Position &p ) const {
return p.x_ * row_ + p.y_;
}
private:
const int row_,column_;
};
bool isValid( const Position &dest,const Position &tl,const Position &br ) {
return dest.x_ >= tl.x_ && dest.x_ <= br.x_ &&
dest.y_ >= tl.y_ && dest.y_ <= br.y_;
}
int BFSShortestPath( std::unordered_map<Position,int,PositionHasher> &ca,const Position start,const Position end,const Position tl,const Position br ) {
typedef std::pair<Position,int> STPostion;
std::queue<STPostion> Q;
Q.push( STPostion(start,0) );
while( !Q.empty() ) {
STPostion cur = Q.front();
Q.pop();
if( cur.first == end ) return cur.second;
if( ca.find(cur.first) == ca.end() ) {
ca.insert( cur );
for( int i = 0; i < step_type; i++ ) {
int steps = cur.second;
Position cp = cur.first,n(cp.x_+move_type[i][0],cp.y_+move_type[i][1]);
if( isValid( n,tl,br) ) Q.push( STPostion(n,steps+1) );
}
}
}
return -1; //can not reach
}
void testingBFSShortestPath() {
Position tl(0,br(30,30),start(0,exit(7,8);
std::unordered_map<Position,PositionHasher> cache(100,PositionHasher(31,31) );
std::cout << BFSShortestPath( cache,start,exit,br ) << std::endl;
}