combination
CS BS架构的区别
CS架构客户端是本地运行的一个程序，服务器端有数据库服务器端，还有衣蛾socket服务器端，通过socket与客户端进行通信
BS架构是请求响应模式，因此需要刷新页面，ajax风行后一定程度缓解。
BS架构优点：
1.客户端无需安装
2.BS架构放在互联网，交互性强
3.无须升级客户端，只需升级服务器
缺点：
1.跨浏览器方面不好
2.速度和安全性需要花费巨大设计成本
3.请求响应模式，需要刷新页面
最近get了递归转非递归之后，有点上瘾，几乎所有看到就想转非递归了。
找到规律其实就不难了，记录递归函数参数，然后还有一个type变量表示处于哪个位置
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
class Solution {
public:
struct info
{
int selectk ,k, selectn, n;
int type;
};
bool select[10000];
vector<vector<int> > ans;
vector<int> curvec;
vector<vector<int> > combine_select(int n, int k) {
ans.clear();
memset(select,0,sizeof(select));
dfs(0,k,0,n);
return ans;
}
void dfs(int selectk, int k, int selectn, int n)
{
if(selectn==n)
{
if(selectk==k)
{
vector<int> oneans;
for(int i=0;i<n;i++)
if(select[i])
oneans.push_back(i+1);
ans.push_back(oneans);
}
}
else
{
select[selectn]=0;
dfs(selectk,k,selectn+1,n);
select[selectn]=1;
dfs(selectk+1,k,selectn+1,n);
}
}
vector<vector<int> > combine_vector(int n, int k) {
ans.clear();
curvec.clear();
//memset(select,0,sizeof(select));
dfs_vector(0,k,0,n);
return ans;
}
vector<vector<int> > combination_iterative(int n, int k)
{
ans.clear();
curvec.clear();
stack<info> S;
S.push({0,k,0,n,0});
while(!S.empty())
{
info& cur=S.top();
if(cur.selectk>cur.k)
{
S.pop();
}
else if(cur.selectn==cur.n)
{
if(cur.selectk==cur.k)
ans.push_back(curvec);
S.pop();
}
else
{
if(cur.type==0)
cur.type++,S.push({cur.selectk,cur.k,cur.selectn+1,cur.n,0});
else if(cur.type==1)
cur.type++,curvec.push_back(cur.selectn+1),S.push({cur.selectk+1,cur.k,cur.selectn+1,cur.n,0});
else
curvec.pop_back(),S.pop();
}
}
return ans;
}
void dfs_vector(int selectk, int k, int selectn, int n)
{
if(selectk>k) return;
if(selectn==n)
{
if(selectk==k)
{
ans.push_back(curvec);
/*
vector<int> oneans;
for(int i=0;i<n;i++)
if(select[i])
oneans.push_back(i+1);
ans.push_back(oneans);*/
}
}
else
{
//select[selectn]=0;
dfs_vector(selectk,k,selectn+1,n);
curvec.push_back(selectn+1);
//select[selectn]=1;
dfs_vector(selectk+1,k,selectn+1,n);
curvec.pop_back();
}
}
} F;
int main()
{
int n=4,k=2;
vector<vector<int> > ans=F.combination_iterative(n,k);
for(int i=0;i<F.ans.size();i++)
{
for(int j=0;j<F.ans[i].size();j++)
cout<<F.ans[i][j]<<" ";
cout<<endl;
}
return 0;
}