시퀀스 요소, 정규 표현 식 일치, BFS 최 단 경로 문제

배열 의 요소 와 문제
n 개의 숫자 서열 을 지정 합 니 다. 각 숫자 가 다 르 고 K 값 을 지정 합 니 다.
       1. 시퀀스 에서 모든 쌍 을 찾 습 니 다. 그 합 은 K 입 니 다.
       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 가 가리 키 는 숫자 입 니 다.       나머지 숫자 는 * b 보다 작 기 때문에 다른 숫자 와 11 을 더 할 수 없습니다.이치 에 맞다       *f + * b > 11 시, * b 는 다른 숫자 와 11 을 더 할 수 없습니다. 다른 숫자 가 모두 크 기 때 문 입 니 다.       *f。* f + * b = 11 시 f, b 를 동시에 이동 하고 결 과 를 저장 합 니 다.

#include 
#include 
#include 
#include 
#include 
using namespace std;
vector< vector > sum2( const std::vector &A, int start, 
                                             int end, int K ) {
	vector< vector > 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 tmp;
			tmp.push_back(A[i]);
			tmp.push_back(A[j]);
			ret.push_back(tmp);
			j--, i++;
		}
	}
	return ret;		
}

문제
      왼쪽 에서 오른쪽으로 배열 을 옮 겨 다 니 며 가장 작은 현재 요 소 를 먼저 가 져 온 다음 에 이 요소 뒤에       면 에서 두 개의 숫자 를 취하 여 합 쳐 K - a [i] 로 하면 모든 상황 을 열거 할 수 있다.

vector< vector > sum3( const std::vector &A, int len, int K ) {
	vector< vector > ret;
	for( int i = 0; i < len; i++ ) {
		vector > tmp = sum2( A, i+1, 
				                 len - 1, K - A[i] );
		for(unsigned int j = 0; j < tmp.size(); j++){
			vector cur;
			cur.push_back(A[i]);
			cur.push_back(tmp[j][0]);
			cur.push_back(tmp[j][1]);
			ret.push_back(cur);
		}
	}
	return ret;
}

문제 3.
      현재 요 소 를 최소 요소 로 가정 하면 뒤에서 임의의 숫자 와 K - a [i] 를 가 져 옵 니 다.        현재 숫자 를 가 져 오지 않 으 면 뒤에서 임의의 숫자 와 K 를 가 져 옵 니 다. 재 귀적 인 출구 는 다음 과 같 습 니 다.       현재 위치 가 배열 을 초과 하거나 현재 위치의 요 소 는 k 보다 큽 니 다.현재 원소 가 k 와 같다 면,       현재 요 소 를 결과 로 추가 하고 되 돌려 줍 니 다.

void resolve( const std::vector &vi, int pos , int K, 
     std::vector< std::vector > &result ) {
	if( pos >= vi.size() || vi[pos] > K )
	    return ;
    if( vi[pos] == K ) {
        std::vector temp;
        temp.push_back( vi[pos] );
        result.push_back( temp );
    }
    
    std::vector< std::vector > t1;
    resolve( vi, pos+1, K-vi[pos], t1 );
    resolve( vi, pos+1, 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 >  v )
{
	for(unsigned int i = 0; i < v.size(); i++){
		for(unsigned int j = 0; j < v[i].size(); j++)
			cout< vi( A, A + sizeof(A)/sizeof(int) );
    std::sort( vi.begin(), vi.end() );
    std::cout << "print 2 sum" << std::endl;
	printSum( sum2(vi, 0, vi.size() - 1, 10));
    std::cout << "print 2 sum" << std::endl;
	printSum( sum2(vi, 2, vi.size() - 1, 10));

    std::cout << "print 3 sum" << std::endl;
	printSum(sum3(vi, vi.size(), 10));
	cout< > res;
    resolve( vi, 0, 10, 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
알고리즘 설명 및 코드
       정규 표현 식 의 일치 문 제 는 쓰기 어 려 운 귀속 문제 입 니 다.         우선 재 귀적 으로 끝 나 는 조건 입 니 다. 문자열 과 패턴 문자열 이 모두 끝 났 을 때 일치 하 는 끝 을 표시 합 니 다.       true 로 돌아 가 야 합 니 다. 그러나 패턴 문자열 이 끝나 지 않 았 을 때 패턴 문자열 이 일치 하 는 것 을 고려 해 야 합 니 다.       0 글자 의 상황 을 요약 하면 다음 과 같다.       if( src[sstart] == '\0' && (pattern[pstart] == '\0' ||                         (pattern[pstart + 1] == '*' && pattern[pstart + 2] == '\0')) )return true;        다른 경우 문자열 이나 패턴 문자열 이 끝나 면 false 로 돌아 갑 니 다.       그리고 * 0 개 이상 일치 하 는 문 자 를 고려 합 니 다.하면, 만약, 만약...       현재 문자 와 일치 하 는 것 을 고려 합 니 다.
   

#include 
#include 
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, pattern, pstart);
		return false;
	} else {
		if(pattern[pstart] == '.' || src[sstart] == pattern[pstart])
			return isMatch(src, sstart + 1, pattern, 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, pattern,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;
}

질문
문제 설명
       바둑판 의 경 계 를 정 한 다음 에 바둑 알 이 하나 있 는데 바둑 알 은 '일' 자형 에 따라 걷는다.       바둑 알 이 어 딘 가 에서 다른 곳 으로 가 는 최소 걸음 수 를 구하 다.       예 를 들 어 바둑 알 의 현재 위 치 는 (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 
#include 
#include 
#include "my_algorithm.h"
const int step_type = 8;
int move_type[step_type][2] = {
	{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
	{2, 1}, {2, -1}, {-2, 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 &ca, 
		const Position start, const Position end, const Position tl, const Position br ) {
			typedef std::pair STPostion;
			std::queue 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, 0), br(30, 30), start(0,0), exit(7,8);
	std::unordered_map cache(100, PositionHasher(31, 31) );
	std::cout << BFSShortestPath( cache, start, exit, tl, br ) << std::endl;
}