线段树是一种适合进行区间运算的数据结构,一般为完全二叉树形状。树上的每个节点,都有着自己维护的数据区间,节点中保存了自己所维护的区间中的有用的数据,相邻区间可进行区间加法的逻辑运算。树叶是点信息,包含了原始数据,只负责维护自己,其他节点负责维护自己的子树,根节点维护整个区间。这种分区间而维护计算的方法实际上是分治思想。使用完全二叉树维护可以使查询/更新达到
O(lgN) 的复杂度。
因为室友睡了,不能打字影响,所以明天再更新
线段树是一种适合进行区间运算的数据结构,一般为完全二叉树形状。树上的每个节点,都有着自己维护的数据区间,节点中保存了自己所维护的区间中的有用的数据,相邻区间可进行区间加法的逻辑运算。树叶是点信息,包含了原始数据,只负责维护自己,其他节点负责维护自己的子树,根节点维护整个区间。这种分区间而维护计算的方法实际上是分治思想。使用完全二叉树维护可以使查询/更新达到
O(lgN) 的复杂度。
因为室友睡了,不能打字影响,所以明天再更新
最近牵扯了太多利益相关问题,这种问题往往很烦人。
然而我又不得不扯进去,实在是,坑爹哇!
其实想一想,大概有两个原因:
1.实力不够,如果已经强到可以无视某些东西的地步,就不需要牵扯这些事情了
2.心性有缺,内心不平静,才会让这些事情一直纠结在心上。
总的来说就是这样,哎。
昨天晚上写了一个OJ上的八皇后问题,然后居然TLE了。。。。(本人弱鸡)。。。然后就躺在床上想怎么优化,想着想着就睡着了,做了一个令人感到忧伤的梦,然后醒了,然后就想到了怎么优化了。。。。当然我很菜。。。用的还是简单回溯的算法,其实就是DFS,皇后多了还是很耗时的,所以,各位皇帝麻烦您们专一一点好吧。
好吧,先说回溯法吧,回溯法和DFS差不多,其思想就是:“我就是要一条路走到黑,走到黑了然后感觉不对,就赶紧返回上一层,看看有没有其他的路,如果没有走到黑,反而走到白了,那就恭喜我,我成功搞出一条通天大道,那么,我。。我。。我我我还是要返回上一层。。。。看看有没有其他的路。。。“讲道理一条路就中了,但可恶的出题人太贪心,总喜欢让我们把所有的路都找到,这不是坑爹呢吗。。。。
大致的框架可以写为:
void func(int step){
1判断路是不是死路,如果是就返回;
2如果判断是不是已经走出一条通天大道了,如果已经是了,那就在这里搞一些操纵,然后。。。还是要返回上一层。。。
for chioce in allOption{
标记一下这个chioce被选过了(某些情况下需要)
func(step+1);//走下一步
}
}
注意,一定不要把1嵌入2里面,如果这样做的话,会DFS出所有选择的全排列,然后再判断是否可行,这样就没有剪枝的效果了。
好吧我知道本人讲的很渣渣,很坑爹,应该没有人能看懂。。。。嗯。。。如果能画图就好了。。。。但是我很懒。。不想画完图用手机拍照然后再传到电脑上然后在传到博客上。。。。。。。
题目:
检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
解法(代码里面的注释应该很清楚):
#include <iostream> using namespace std; void queen(int step); int n;//有多少个皇后 int count;//记录成功的方案 int book[14];//标记 int a[14];//a[1]表示第一行的皇后在第几列,a[2]表示第二行的。。。。。 int main(){ cin>>n; queen(n); cout<<count; return 0; } void queen(int step){ int LastLine=n-step;//上一步摆下来的皇后,因为摆放皇后时候已经用了book数组进行标记约束,所以不需要判断行列 for(int i=1;i<LastLine;i++){//判断是否在同同一斜线上 if(a[LastLine]-a[i]==LastLine-i||a[LastLine]-a[i]==i-LastLine){ return; } } /*for(int i=1;i<=n-step;i++){//这里是原来的判断是否在同一条斜线上的算法,但是算法复杂度很高,分析原因发现 for(int j=i+1;j<=n-step;j++){//这个算法是,对于每一行,都有对比其他的行,重复了很多 if(a[j]-a[i]==j-i||a[j]-a[i]==i-j){//仔细思考发现,只需要判断新加入的皇后符不符合要求就行,所以 return;//换成了上面的算法,复杂度是o(N) } } }*/ if(step==0){//拜访了最后一个皇后,已经得出了一种解法 count++; if(count<=3){ for(int i=1;i<=n;i++){ cout<<a[i]<<' '; } cout<<endl; } }else{ //进行本次放置,然后递归下一次 for(int i=1;i<=n;i++){//每次摆放这一行的皇后的时候,都有N列可以摆,意思就是有N个岔路口。 //我们选一个深入,等这个返回之后,再选下一个进行深入,所以是一个for循环 if(!book[i]){//如果第i列还没有黄后占场子 book[i]=1;//标记一下我要占上 a[n+1-step]=i;//摆放皇后 queen(step-1);//深入下一个路口 book[i]=0;//返回了,就要开始走下一个差路口(下一列),所以这一列的标记取消掉 } } } }
运行查询指令的时候,无法查询到信息,是不会进入回调函数的,可以利用这个点判断数据库里面是否有查询的记录。
技术细节稍后更新
—————————-2018.9.8更新————————————
首先回调函数一般是指,自己定义一个函数的功能,然后把函数作为参数传入另一个函数里面,在另一个函数里面会执行我们自己定义的函数,这个我们定义的函数叫回调函数。回调函数的参数需要符合另一个函数的要求,才能被传入、调用。而这另一个函数一般是我们无法直接更改内容的一个黑盒,但是我们可以通过自己定义的回调函数来操控程序。
c/c++的sqlite库中执行SQL命令的函数sqlite3_exec原型如下:
sqlite3_exec(sqlite3* pdb, const char *sql, sqlite_callback func, void *data, char **errmsg);
sqlite3* pdb是指向已经打开的数据库的指针;
const char * sql是需要执行的sql语句,注意在c++中如果是string的话需要传参的时候用c_str()更改一下类型;
sqlite_callback func是一个回调函数,如果不需要回调,可以传实参为NULL,使用select语句时,每产生一条记录都会调用一次回调函数;
void *data将会作为参数传入回调函数,作为回调函数的第一个参数,利用这点可以向回调函数中动态传入数据;
char errmsg保存执行命令时发生的错误,注意errmsg是char类型的,但是错误语句应该是char类型的,那么我们传入实参的时候就一个调用&取一个char类型的变量,这样就好了,sqlite3_exec执行完毕之后错误会保存在这个变量指向的字符串里面;
回调函数:
typedef int(*sqlite3_callback)(void*,int,char**,char**);
void*是exec里面的第四个参数,int是记录的列数,第一个char是一个二维数组,记录查到的值,第二个char保存键名
当使用sqlite3_exe执行select语句时,如果没有查询到记录,是不会报错的,那么怎么知道没有查到记录呢?
如果查到了相关记录,会调用回调函数,查询到的记录条数是0的话,就不会调用,可以利用sqlite3_exec的第四个void *参数,向回调函数里面传入一个变量,在回调函数中改变这个变量的值,在exec执行完毕之后判断变量的值是否被改变,这样就可以知道是否查询到了值。这样可以避免某些错误。
例如我在某个程序中写的代码:
static int callback_sqlite(void * data,int argc,char **argv,char **azColName){ int i=0; #ifdef _DEBUG_ printf("进入回调函数\n"); #endif string keys[]={"word","phonetic","pos","acceptation","orig","trans"}; for(i=0;i<argc;i++){ #ifdef _DEBUG_ printf("内存地址:%p\n",argv); printf("数据库查询中:%s\n",argv[i]); #endif (*(map<string,string>*)data).insert(pair<string,string>(keys[i],argv[i]?string(argv[i]):string("NULL"))); } #ifdef _DEBUG_ printf("退出回调函数\n"); #endif (*(map<string,string>*)data)["isExistWord"]="true"; return 0; } Interpretation inquire_core(sqlite3 * db,string word){ Interpretation tempTransDataObj; char *ErrorInfo=0; int rc; map<string,string> WordData; WordData.insert(pair<string,string>("isExistWord","false")); string sql_cmd="select word,ps,pos,acceptation,orig,trans from words where word=\'"; sql_cmd=sql_cmd+word+"\';"; rc=sqlite3_exec(db,sql_cmd.c_str(),callback_sqlite,(void *)&WordData,&ErrorInfo); if(rc!=SQLITE_OK){ cout<<"SQL ERROR:"<<ErrorInfo<<endl; sqlite3_free(ErrorInfo); exit(0); }else{ #ifdef _DEBUG_ cout<<"查询数据库成功"<<endl; #endif } sqlite3_close(db); map<string,string>::iterator it; it=WordData.find(string("isExistWord")); if(it->second!="true"){ return tempTransDataObj; } …… …… …… }
占坑,待填
今天中午开始坐车,下午五点左右才到学校,注册完,进寝室收拾东西。
没有开始感觉的那么坑了,学校也看起来也不是那么黑暗了,在家就是闲了,才容易多想,一来到学校,感觉还可以,事情很多,又开始忙起来了。看到迎新的场面,想起来去年的自己,想起当时心里无比抗拒的感觉。
一年已经过了,时间不多了。