31三
归类于程序人生
2 条评论
题目原型来自HDUOJ的1372 Knight Moves
很简单的一个搜索题
就是告诉你棋盘上的两个点，然后让你算出Knight，也就是国际象棋的马，最少多少步能够从一个点到另一个点。
算法很简单，深搜即可，这个不是本文讨论的问题。这里我是把原来通过函数递归调用的深搜改为用栈自行模拟
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<stdio.h>
#include<stack>
using namespace std;
#define INF 99999
int map[8][8];
int dir[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
struct node{
int x,y,t;
};
stack<node>zerob;
int main()
{
char str1[3],str2[3];
node head,p;
while(scanf("%s %s",str1,str2)==2)
{
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
map[i][j]=INF;
}
}
while(!zerob.empty()){
zerob.pop();
}
head.x=str1[0]-'a';
head.y=str1[1]-'1';
head.t=0;
int ans=-1;
zerob.push(head);
while(!zerob.empty()){
head=zerob.top();
zerob.pop();
if(head.x==str2[0]-'a'&&head.y==str2[1]-'1')
{
if(ans>head.t||ans==-1)
ans=head.t;
continue;
}
for(int i=0;i<8;i++)
{
p=head;
p.x+=dir[i][0];
p.y+=dir[i][1];
if(!(p.x>=0 && p.x<8 && p.y>=0 && p.y<8))
continue;
p.t++;
if(map[p.x][p.y]<=p.t)
continue;
map[p.x][p.y]=p.t;
zerob.push(p);
}
}
printf("To get from %s to %s takes %d knight moves.\n",str1,str2,ans);
}
} |
后记：
其实当你理解了深搜和广搜后，你会发现，你写出来的深搜和广搜的代码可以看上去是差不多的。为什么那么说呢，因为，无论那种搜索，都是通过对一个线性表进行处理，只不过是先处理头部还是尾部的问题罢了。处理头部优先的时候，就是广度优先了，因为，头部的都是兄弟节点；而尾部的则是深度优先，因为放入尾部的都是刚刚生产出来的节点——也就是所谓一条路走到死。
同理可以联想到启发式搜索。启发式搜索就是先以你自定义的优先级处理，然后再以广度为优先级处理。
所以，归根结底，所谓的搜索，就是一种定义了优先级的枚举。当然，这个只是我个人的理解，欢迎各位大牛拍转。
196 views dfs, 搜索, 数据结构, 栈, 深搜, 算法
03二
归类于程序人生
参与评论
c＋＋很久没用了。。。好生疏阿。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
| #include <iostream>
using namespace std;
typedef int ElemType;
const int MaxNum=100;
class List {
public :
ElemType list[MaxNum+1];
int size;
void Clear(){
this->size=0;
}
int GetSize(){
return this->size;
}
bool isEmpty(){
if(this->size)
return false;
else
return true;
}
ElemType GetElem(int pos)
{
if(0<=pos && pos<size)
return this->list[pos];
else {
exit(1);
}
}
bool find(ElemType& it)
{
int i;
for(i=0;i<size;i++)
{
if(it==this->list[i])
return true;
}
return false;
}
bool update(int pos,const ElemType& it){
int i;
for(i=0;i<size;i++)
{
if(it==this->list[i]){
this->list[i]=it;
return true;
}
}
return false;
}
bool InsertRear(const ElemType& it){
if(size>=MaxNum)
return false;
this->list[size]=it;
size++;
return true;
}
bool InsertFront(const ElemType& it){
int i;
if(size>=MaxNum)
return false;
for(i=size;i>0;i--){
this->list[i]=this->list[i-1];
}
this->list[0]=it;
size++;
return true;
}
bool Insert(int pos,const ElemType& it){
int i;
if(size>=MaxNum)
return false;
for(i=size;i>pos;i--){
this->list[i]=this->list[i-1];
}
this->list[pos]=it;
size++;
return true;
}
ElemType DeletFront(){
int i;
if(size==0)
exit(1);
ElemType temp=this->list[0];
for(i=0;i<size-1;i++)
{
this->list[i]=this->list[i+1];
}
return temp;
}
ElemType Delet(int pos){
int i;
if(size<=pos)
exit(1);
ElemType temp=this->list[pos];
for(i=pos;i<size-1;i++)
{
this->list[i]=this->list[i+1];
}
return temp;
}
};
int main(int argc, char *argv[]) {
List a;
a.InsertFront(1);
a.InsertRear(2);
cout<<a.GetSize()<<endl;
cout<<a.GetElem(0)<<endl;
a.Insert(0,3);
int b=1;
cout<<a.find(b)<<endl;
cout<<a.Delet(1)<<endl;
return 0;
} |
123 views code, cpp, data structure, 数据结构, 编程
24一
归类于程序人生
2 条评论
今天开始学习学习哈夫曼树，于是就去找点题目做做，毕竟学数据结构这种东西还是让oj来验证你的想法最方便了。
google了一下，pku的3252貌似是个软柿子，捏之～
看了一些关于哈夫曼的介绍，大致有个想法了，打出来，wa。。。看来想错了。
于是再看资料，发现需要动态寻找最小的两个节点的，于是就写了一个比较暴力的，参考网上的资料。
6365627 zerob13 3253 Accepted 236K 250MS C++ 628B 2010-01-24 15:08:06
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<stdio.h>
#include<string.h>
#include<stdlib.h>
int lef[20001];
int n;
int cmp(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}
int main (int argc, char * const argv[]) {
int i,j,k,l;
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++)
{
scanf("%d",&lef[i]);
}
qsort(lef,n,sizeof(int),cmp);
long long int sum=0;
for(i=1;i<n;i++)
{
lef[i]+=lef[i-1];
sum+=lef[i];
k=lef[i];
for(j=i+1;j<n;j++)
{
if(k>lef[j])
{
lef[j-1]=lef[j];
}else {
break;
}
}
lef[j-1]=k;
}
printf("%lld\n",sum);
}
return 0;
} |
但是很不爽阿，感觉这种代码不是我的风格，于是打算用stl重新写一遍，于是我就开始用stl折腾了。。。
之后就出了一个效率好多了的stl版本。。。
6365653 zerob13 3253 Accepted 348K 32MS C++ 819B 2010-01-24 15:18:24
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include<stdio.h>
#include<string.h>
#include<queue>
#include<stdlib.h>
using namespace std;
int lef;
int n;
int cmp(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}
struct node{
int a;
friend bool operator< (node n1, node n2)
{
return n1.a > n2.a;
}
};
priority_queue<node>zerob;
int main (int argc, char * const argv[]) {
int i,j,k,l;
node kk;
while(scanf("%d",&n)!=EOF){
while(!zerob.empty()){
zerob.pop();
}
for(i=0;i<n;i++)
{
scanf("%d",&lef);
kk.a=lef;
zerob.push(kk);
}
long long int sum=0;
while(zerob.size()>1)
{
node a=zerob.top();
zerob.pop();
node b=zerob.top();
zerob.pop();
sum+=a.a+b.a;
kk.a=a.a+b.a;
zerob.push(kk);
}
printf("%lld\n",sum);
}
return 0;
} |
268 views acm, code, pku3252, 哈夫曼, 数据结构, 树, 算法, 编程
23一
归类于程序人生
参与评论
下学期的数据结构期末作业貌似要做这个，估计就是循环链表的模拟解法吧。。。
所以就凭着记忆写了一个比较简单的cpp版本。
大牛一笑哂之～
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include<cstdlib>
#include<iostream>
using namespace std;
struct node{
int data;
int index;
node *next,*pre;
}*root,*tail;
void del(node* a)
{
node *p;
p=a->pre;
p->next=a->next;
a->next->pre=p;
cout<<a->index<<endl;
free(a);
return ;
}
void add(int aas,int ind)
{
node *aa=new node;
aa->data=aas;
aa->index=ind;
aa->pre=tail;
tail->next=aa;
aa->next=root;
tail=aa;
root->pre=tail;
}
int main()
{
int i;
int a;
int n,m;
m=4;n=6;
cin>>m>>n;
for(i=0;i<n;i++)
{
cin>>a;
if(i){
add(a,i+1);
}else{
root=new node;
tail=root;
root->data=a;
root->index=i+1;
root->next=tail;
root->pre=tail;
tail->next=root;
tail->pre=root;
}
}
node *tt;
tt=root;
while(n){
int kk=0;
while(1)
{
kk++;
if(kk==m)
{
m=tt->data;
del(tt);
tt=tt->next;
break;
}else {
tt=tt->next;
}
}
n--;
}
} |
123 views cpp, 循环, 数据结构, 算法, 约瑟夫环, 编程, 链表
08十一
归类于程序人生
9 条评论
对于字符串的高效处理一般都是用字典树——Trie，或者ac自动机的。但是字典树对于大量数据的空间的开销相当大，特别我们的字典中不仅仅是26个字母组成的字符串时空间的损耗就会巨大无比。。。
三叉搜索树就是一种比较好的解决方法，我第一次看到的时候时在最近的《程序员》杂志上的一篇文章——《用三叉搜索树实现高效率的“自动完成”》，是一个.net大牛写的～于是我便对这个产生了兴趣，在折腾几天后，终于用java也写了一个很挫的三叉搜索树（见用三叉搜索树实现高效字符查找）。
其实所谓的三叉树就是舍去了Trie的多余的指针，而是把一个个树套在一起，每个节点压缩成三个方向。如果匹配的话就走中间方向的指针，如果不匹配，那么就走左或者右指针。选左选右则是这个数据结构优化的一个好地方，我用了字母顺序，文章作者说这个是最挫的方法。。。窘一个。。。好方法我还没有想到，因为不会写自平衡的树。。。杯具一个。。。
这里有一个例子，假如我们存入”AB”,”ABBA”.”ABCD”.”BCD”,这几个单词，那么三叉树就会出现如下的储存方式。。。
红线表示匹配的箭头～黄色的表示单词结尾
641 views java, Ternary Search Tree, 三叉树, 字符串处理, 搜索树, 数据结构
08十一
归类于程序人生
参与评论
学着书上的写了一个优先队列，用堆实现。笔记一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| package com.zerob13.PriorityQueue;
/**
*
* @author yanglingfeng
*/
public class PriorityQueue {
private static final int def_size=10;
private Comparable[] array;
private int count;
/**
* 初始化函数
*/
public PriorityQueue(){
array=new Comparable[def_size];
count=0;
}
/**
* 清理函数
*/
public void clear(){
for(int i=0;i<count;i++)
array[i]=null;
count=0;
}
/**
* 添加一个元素
* @param val
*/
public void add(Comparable val){
if(count==array.length)expand();
int curr=count++;
while(curr>0){
int parent=(curr-1)/2;
if(val.compareTo(array[parent])>0)
break;
array[curr]=array[parent];
curr=parent;
}
array[curr]=val;
}
/**
* 移除顶端元素
* @return 最小元素
*/
public Comparable remove(){
if(count==0)
return null;
Comparable min=array[0];
Comparable last=array[--count];
array[count]=null;
int child,curr=0;
while((child=2*curr+1)<count){
if(child+1<count&&array[child+1].compareTo(array[child])<0)
child++;
if(last.compareTo(array[child])<=0)
break;
array[curr]=array[child];
curr=child;
}
array[curr]=last;
return min;
}
/**
* 判断是否为空队列
* @return boolean
*/
public boolean isEmpty(){
return count==0;
}
/**
* 返回大小
* @return int
*/
public int size(){
return count;
}
/**
* 返回最小值
* @return minval
*/
public Comparable getMin(){
if(count==0)
return null;
return array[0];
}
private void expand(){
Comparable[] newArray=new Comparable[2*array.length];
for(int i=0;i<array.length;i++)
newArray[i]=array[i];
array=newArray;
}
@Override
public String toString(){
String buf="";
int i=0;
int j=1;
int k=0;
while(i<count){
if(k<j){
buf+=array[i++]+" ";
k++;
}else{
buf+=array[i++]+" ";
k=0;
j*=2;
}
}
return buf;
}
} |
169 views java, PriorityQueue, 优先队列, 堆, 数据结构, 编程
06十一
归类于程序人生
2 条评论
hdu的1251
上代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
| import java.util.*;
/**
*
* @author yanglingfeng
*/
class TernaryTree {
private class Node {
char m_char;
Node left, right, middle;
boolean end;
int co;
public Node(char ch, boolean e) {
m_char = ch;
end = e;
co=0;
}
public Node(char ch, boolean e, Node leftc, Node rightc, Node middlec) {
m_char = ch;
end = e;
left = leftc;
right = rightc;
middle = middlec;
}
}
private Node root;
private int count;
/**
* 初始化三叉树
*/
public TernaryTree() {
clear();
}
/**
* 清除三叉树
*/
public final void clear() {
root = null;
count = 0;
}
/**
* 插入一个字符串
* @param s
*/
public void insert(String s) {
root = insert(root, s, 0);
}
/**
* 返回三叉树大小
* @return
*/
public int size() {
return count;
}
/**
* 返回是否能够找到字符串s
* @param s
* @return boolean
*/
public boolean contains(String s) {
return search(root, s, 0) != null;
}
public int count(String s) {
Node a= search(root, s, 0);
if(a!=null){
return a.co;
}else
return 0;
}
private Node search(Node ref, String s, int pos) {
if (ref == null) {
return null;
} else {
int cmp = s.charAt(pos) - ref.m_char;
if (cmp < 0) {
return search(ref.left, s, pos);
} else if (cmp > 0) {
return search(ref.right, s, pos);
} else {
if (1 + pos == s.length()) {
return ref;
}
return search(ref.middle, s, pos + 1);
}
}
}
private Node insert(Node ref, String s, int i) {
if (ref == null) {
count++;
ref = new Node(s.charAt(i), false);
}
int cmp = s.charAt(i) - ref.m_char;
if (cmp < 0) {
ref.left = insert(ref.left, s, i);
} else if (cmp > 0) {
ref.right = insert(ref.right, s, i);
} else {
if (i + 1 == s.length()) {
ref.end = true;
} else {
ref.middle = insert(ref.middle, s, i + 1);
}
ref.co++;
}
return ref;
}
}
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
TernaryTree dic=new TernaryTree();
Scanner inp=new Scanner(System.in);
String a=new String();
int mo=0;
while(inp.hasNextLine()){
a=inp.nextLine();
if(a.equals("")){
mo=1;
continue;
}
if(mo==0)
{
dic.insert(a);
}else
{
System.out.println(dic.count(a));
}
}
}
} |
341 views 1251, acm, hdu, java, oj, 三叉树, 数据结构
