2017.05.03

mhcoderwl · mhcoderwl · commit 27a32ea26cf1 · 2017-05-03T09:23:58.000+08:00
diff --git a/10.1.cpp b/10.1.cpp
@@ -0,0 +1,102 @@
+//给一个字符串,分割使得分割后的所有子串都为回文//
+#include<iostream>
+#include<string>
+#include<algorithm>
+#include<vector>
+using namespace std;
+//深搜
+class Solution{
+public:
+	vector<vector<string>> partition(string s){
+		vector<vector<string>> result;
+		vector<string> cur;
+		dfs(s,result,cur,0,1);
+		return result;
+	}
+	void dfs(string& s,vector<vector<string>>& result,vector<string>& cur,int prev,int start){
+		auto isPalindrome=[](const string& s){
+			auto begin=s.begin();
+			auto end=std::prev(s.end());
+			while(begin<=end){
+				if(*begin!=*end)
+					return false;
+				begin++;
+				end--;
+			}
+			return true;
+		};	
+		if(start==s.size()){
+			if(isPalindrome(s.substr(prev,start-prev))){
+				cur.push_back(s.substr(prev,start-prev));
+				result.push_back(cur);
+				cur.pop_back();
+			}
+		return;
+		}
+		dfs(s,result,cur,prev,start+1);
+		if(isPalindrome(s.substr(prev,start-prev))){
+			cur.push_back(s.substr(prev,start-prev));
+			dfs(s,result,cur,start,start+1);
+			cur.pop_back();
+		}
+	}
+};
+//DP
+class Solution1{
+public:
+	vector<vector<string>> partition(string s){
+		const int n=s.size();
+		bool p[n][n];
+		fill_n(&p[0][0],n*n,0);
+		for(int i=n-1;i>=0;i--)
+			for(int j=i;j<n;j++)
+				p[i][j]=s[i]==s[j]&&(j-i<2||p[i+1][j-1]);
+		vector<vector<string>> result[n];
+		for(int i=n-1;i>=0;i--)
+			for(int j=i;j<n;j++)
+				 if(p[i][j]){
+					 if(j<n-1){
+					 	for(auto str:result[j+1]){
+					 	str.insert(str.begin(),s.substr(i,j-i+1));
+						result[i].push_back(str);
+						}
+					 }else{
+						result[i].push_back(vector<string>{s.substr(i,j-i+1)});
+					}
+				 }
+		return result[0];
+	}
+};
+
+					 
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+int main(){
+	Solution s;
+	string str="aab";
+	auto result=s.partition(str);
+	for(auto i:result){
+		for(auto j:i)
+			cout<<j<<' ';
+		cout<<endl;
+	}
+};
+
+
+
+
+	
diff --git a/10.2.cpp b/10.2.cpp
@@ -0,0 +1,19 @@
+//从一个m*n的数组左上角走到右下角有多少种走法//
+#include<iostream>
+#include<vector>
+#include<algorithm>
+#include<stack>
+using namespace std;
+//深搜
+class Solution1{
+	int uniquePaths(int m,int n){
+		if(m<0||n<0)return 0;
+		if(m==1||n==1)return 1;
+		return uniquePaths(m-1,n)+uniquePaths(m,n-1);
+	}
+};
+
+//深搜,加备忘录可以加速
+class Solution2{
+	int uniquePaths(int m,int n){
+
diff --git a/9.1.cpp b/9.1.cpp
@@ -0,0 +1,80 @@
+//给两个单词和一个字典,找到最短变换距离.每次只能变一个字母,必须按照字典中的路径走
+#include<iostream>
+#include<queue>
+#include<algorithm>
+#include<unordered_set>
+using namespace std;
+struct state_t{
+	string word;
+	int level;
+	state_t(){word="";level=0;}
+	state_t(const string& word,int level){
+		this->word=word;
+		this->level=level;
+	}
+	bool operator==(const state_t &other)const{
+		return this->word==other.word;
+	}
+};
+
+namespace std{
+template<> struct hash<state_t>{
+	public:
+		size_t operator()(const state_t& s)const {
+			return str_hash(s.word);
+		}
+	private:
+		hash<string>str_hash;
+	};
+}
+
+
+class Solution{
+public:
+	int ladderLength(const string& start,const string& end,const unordered_set<string>&dict){
+		queue<state_t> q;
+		unordered_set<state_t> visited;//用于判重
+		auto state_is_valid=[&](const state_t& s){
+			return dict.find(s.word)!=dict.end()||s.word==end;
+		};
+		auto state_is_target=[&](const state_t &s){return s.word==end;};
+		auto state_extend=[&](const state_t& s){
+			unordered_set<state_t> result;
+			for(int i=0;i<s.word.size();i++){
+				state_t new_state(s.word,s.level+1);
+				for(char c='a';c<='z';c++){
+					if(c==new_state.word[i])continue;
+					swap(c,new_state.word[i]);
+					if(state_is_valid(new_state)&&visited.find(new_state)==visited.end())
+						result.insert(new_state);
+					swap(c,new_state.word[i]);
+				}
+			}
+			return result;
+		};
+		state_t start_state(start,0);
+		q.push(start_state);
+		visited.insert(start_state);
+		while(!q.empty()){
+			const auto state=q.front();
+			q.pop();
+			if(state_is_target(state))
+				return state.level+1;
+			const auto& next_states=state_extend(state);
+			for(const auto& new_state:next_states){
+				q.push(new_state);
+				visited.insert(new_state);
+			}
+			return 0;
+		}
+	}
+};
+int main(){
+}
+
+
+
+
+
+		
+
diff --git a/9.2.cpp b/9.2.cpp
@@ -0,0 +1,10 @@
+#include<iostream>
+#include<vector>
+#include<unordered_set>
+#include<unordered_map>
+#include<algorithm>
+using namespace std;
+struct state_t{
+
+int main(){
+}
diff --git a/9.3.cpp b/9.3.cpp
@@ -0,0 +1,74 @@
+//一个2维数组只有"X"和'O',如果'O'区域被x包围则需要被改成'+'
+//思路:用广搜,起点为边上元素向内部搜索
+#include<iostream>
+#include<vector>
+#include<algorithm>
+#include<queue>
+using namespace std;
+class Solution{
+public:
+	void solve(vector<vector<char>> &board){
+		if(board.empty())return;
+		int m=board.size();
+		int n=board[0].size();
+		for(int i=0;i<n;i++){
+			bfs(board,0,i);
+			bfs(board,m-1,i);
+		}
+		for(int i=1;i<m-1;i++){
+			bfs(board,i,0);
+			bfs(board,i,n-1);
+		}
+		for(int i=0;i<m;i++){
+			for(int j=0;j<n;j++){
+				if(board[i][j]=='O')
+					board[i][j]=='X';
+				else if(board[i][j]=='+')
+					board[i][j]=='O';
+			}
+		}
+	}
+
+	void bfs(vector<vector<char>> &board,int i,int j){
+	typedef pair<int,int> state_t;
+	queue<state_t>q;
+	const int m=board.size();
+	const int n=board[0].size();
+	auto state_is_valid=[&](const state_t& s){
+		const int x=s.first;
+		const int y=s.second;
+		if(0<=x<=m-1&&0<=y<=n-1&&board[x][y]=='O')
+			return true;
+		else return false;
+	};
+	auto state_extend=[&](const state_t& s){
+		vector<state_t> new_state_ts={state_t(s.first-1,s.second),
+						state_t(s.first,s.second-1),
+						state_t(s.first+1,s.second),
+						state_t(s.first,s.second+1)};
+		vector<state_t>result;
+		for(int i=0;i<new_state_ts.size();i++)
+			if(state_is_valid(new_state_ts[i])){
+				board[new_state_ts[i].first][new_state_ts[i].second]=='+';
+				result.push_back(new_state_ts[i]);
+			}
+		return result;
+	};
+	state_t start(i,j);
+	if(state_is_valid(start)){
+		board[i][j]=='+';
+		q.push(start);
+	}
+	while(!q.empty()){
+		const auto p=q.front();
+		q.pop();
+	for(auto next_state_t:state_extend(p))
+		q.push(next_state_t);
+	}
+	}
+
+
+	
+
+};
+int main(){}
diff --git a/baidu5.cpp b/baidu5.cpp
@@ -0,0 +1,26 @@
+#include<iostream>
+#include<vector>
+#include<algorithm>
+#include<memory.h>
+using namespace std;
+int all_array(int n,int k){
+	vector<vector<int>> count(n,vector<int>(n+1,0));
+	for(int i=1;i<n+1;i++)
+	count[0][i]=1;
+	for(int i=1;i<k+1;i++){
+		for(int j=i+1;j<n+1;j++){
+			count[i][j]=(count[i][j-1]*(i+1)+count[i-1][j-1]*(j-i))%2017;
+		}
+	}
+	return count[k][n];
+}
+int main(){
+	int n;
+	cin>>n;
+	int k;
+	cin>>k;
+	cout<<all_array(n,k);
+}
+
+		
+
