首页
社区
课程
招聘
[求助]一个Acm题
发表于: 2010-8-10 15:01 7267

[求助]一个Acm题

2010-8-10 15:01
7267
UVA 的122---ZOJ的1167,
连接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=167
题目要求是给出一序列字符串,然后构建成树,按水平遍历输出
我的思路是:因为题目给定节点数不出 超过256个,所以申请一个300*300的数组 ,其中行代表深度,列代表在这一层的偏移,如(0,0)表示根,(1,0)表示的是根的左子树;
因为给出的路径表示是L和 R组 成的串,可以按 l=0,R=1,这样求出偏移
我的代码如下(从网上找了好多测试实例都没有错 ,可以提交有错希望各位帮忙解答一下那里出错的,先 谢谢)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int Row=300;
const int Col=300;
string mytree[Row][Col];
int ndepth=0;
const string nNoNode="";
bool isComplete=false;

void mMapIntoTree(const string);
int GetTreePath(const string &);
void  coutPutTree();
bool  checkTree();
void clearMyMem();

int main()
{
        ifstream cin("122.txt");
        string str;
        while(1){
                clearMyMem();
                while(cin>>str){
                        if(str.compare("()")==0) break;
                        if(!isComplete){
                                continue;
                        }
                        string s=str.substr(1,str.length()-2);
                        mMapIntoTree(s);
                }
                coutPutTree();
                if(cin.eof()) break;
               
        }
}
void mMapIntoTree(const string str)
{
        if(str=="") return;
        int x=str.find(',',0);
        string numstr=str.substr(0,x);
        if(numstr==""){
                isComplete=false;
                return;
        }
        string pathstr=str.substr(x+1);
        int len=pathstr.length();
        if(len>256){
                isComplete=false;
                return;
        }
        int col=GetTreePath(pathstr);
        if(mytree[len][col]!=nNoNode){
                isComplete=false;
                return;
        }
        mytree[len][col]=numstr;
}

int GetTreePath(const string & str)
{
        int num=0,x=0;
        int len=str.length();
        if(len>ndepth) ndepth=len;//get the max depth of tree;
        for(int i=0;i<len;i++){
                if(str.at(i)=='L')  x=0;
                if(str.at(i)=='R')  x=1;
                num+=x*(1<<(len-i-1));
        }
        return num;
}
bool checkTree()
{
        if(!isComplete) return false;
        for(int j=ndepth+1;j>0;j--){
                for(int i=0;i<Col;i++){
                        if(mytree[j][i]!=nNoNode){
                                if(mytree[j-1][i/2]==nNoNode) return false;
                        }
                }
        }
        return true;
}
void coutPutTree()
{
        if(!checkTree()){
                cout<<"not complete\n";
                return;
        }
        cout<<mytree[0][0];
        for(int x=1;x<ndepth+1;x++){
                for(int y=0;y<Col;y++){
                        if(mytree[x][y]!=nNoNode){
                                cout<<" "<<mytree[x][y];
                        }
                }
        }
        cout<<endl;
}
void clearMyMem()
{
        for(int i=0;i<Row;i++){
                for(int j=0;j<Col;j++){
                        mytree[i][j]=nNoNode;
                }
        }
        ndepth=0;
        isComplete=true;
}

[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)

收藏
免费 0
支持
分享
最新回复 (15)
雪    币: 6075
活跃值: (2236)
能力值: (RANK:1060 )
在线值:
发帖
回帖
粉丝
2
作业应该自己做
import re
def solve(input):
    #
    # build complete binary tree
    #
    tree = [None]*256
    def put(node, index, path):
        if not path:
            tree[index] = node
        elif path[0] == 'L':
            put(node, 2*index+1, path[1:])
        elif path[0] == 'R':
            put(node, 2*index+2, path[1:])
    input = [x.split(',') for x in re.findall('\((.*?)\)', input)]
    for node, path in input:
        put(node, 0, path)
    #
    # check completeness -- all nodes except the root have parent
    #
    complete = True
    for i in range(1, len(tree)):
        if tree[i] is not None:
            if tree[(i-1)/2] is None:
                complete = False
                break
    if complete:
        print [x for x in tree if x is not None]
    else:
        print 'not complete'
solve('(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR)')
solve('(3,L) (4,R)')
2010-8-10 16:15
0
雪    币: 70
活跃值: (74)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
3
发现看FORGOT的代码,是种享受,赞啊
2010-8-10 17:03
0
雪    币: 1708
活跃值: (586)
能力值: ( LV15,RANK:670 )
在线值:
发帖
回帖
粉丝
4
[QUOTE=forgot;845603]作业应该自己做

import re
def solve(input):
    #
    # build complete binary tree
    #
    tree = [None]*256
    def put(node, index, path):
        if not...[/QUOTE]
能问下这是什么语言?
2010-8-10 17:47
0
雪    币: 206
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
不是作业,我是自己练习的,我只是 好奇为何我的思路不能AC
2010-8-10 18:53
0
雪    币: 206
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
那位大侠,可以看一下我哪里 错 了吗?实在是 找不到原因
2010-8-10 19:05
0
雪    币: 1126
活跃值: (156)
能力值: ( LV9,RANK:210 )
在线值:
发帖
回帖
粉丝
7
为啥要这么复杂啊。
O=0    =                      0
L=1     =                 1 * 1
R=2     =                 2 * 1
LL=3,   =         1 * 2 + 1 * 1
LR=4    =         1 * 2 + 2 * 1
RL=5    =         2 * 2 + 1 * 1
RR=6    =         2 * 2 + 2 * 1
LLL=7   = 1 * 4 + 1 * 2 + 1 * 1
LLR=8   = 1 * 4 + 1 * 2 + 2 * 1
LRL=9   = 1 * 4 + 2 * 2 + 1 * 1
LRR=10  = 1 * 4 + 2 * 2 + 2 * 1
RLL=11  = 2 * 4 + 1 * 2 + 1 * 1
RLR=12  = 2 * 4 + 1 * 2 + 2 * 1
RRL=13  = 2 * 4 + 2 * 2 + 1 * 1
RRR=14  = 2 * 4 + 2 * 2 + 2 * 1

看明白了原理没?好像fg的也是这个意思,看不懂。
2010-8-10 20:20
0
雪    币: 325
活跃值: (97)
能力值: ( LV13,RANK:530 )
在线值:
发帖
回帖
粉丝
8
Regex + heap...

膜拜楼上。

some node in the tree is NOT given a value or a node is given a value more than once, then the string ``not complete'' should be printed.

我眼拙,望赐教,没看出来哪里检测more than once的
2010-8-10 22:32
0
雪    币: 6075
活跃值: (2236)
能力值: (RANK:1060 )
在线值:
发帖
回帖
粉丝
9
没注意看,改一下吧
import re
def solve(input):
    complete = [True]
    #
    # build complete binary tree
    #
    tree = [None]*256
    def put(node, index, path):
        if not path:
            if tree[index] is None:
                tree[index] = node
            else:
                complete[0] = False
        elif path[0] == 'L':
            put(node, 2*index+1, path[1:])
        elif path[0] == 'R':
            put(node, 2*index+2, path[1:])
    for node, path in input:
        put(node, 0, path)
    #
    # check completeness -- all nodes except the root have parent
    #
    
    for i in range(1, len(tree)):
        if tree[i] is not None:
            if tree[(i-1)/2] is None:
                complete[0] = False
                break
    if complete[0]:
        print [x for x in tree if x is not None]
    else:
        print 'not complete'
def solve_all():
    s = """    
    (11,LL) (7,LLL) (8,R)
    (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
    (3,L) (4,R) ()
    (11,LL) (7,LLL) (8,R) (8,LL)
    (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()    
    """
    t = []
    for x in re.findall('\((.*?)\)', s):
        if not x:
            solve(t)
            t = []
        else:
            t.append(x.split(','))
solve_all()
    
2010-8-10 22:52
0
雪    币: 325
活跃值: (97)
能力值: ( LV13,RANK:530 )
在线值:
发帖
回帖
粉丝
10
open System.Text.RegularExpressions //use alternative if use ocaml
open System //use alternative if use ocaml
let hd = List.head //ignore this if use SML
let tl = List.tail //ignore this if use SML
let ofstr (str:string)=
    let heap = Array.create(256) -1
    let heapWrite index n = if heap.[index] <> -1 then 
        failwith "incomplete" else heap.[index] <- n
    let conv (num,path:string)=
        Int32.Parse(num),path.ToCharArray()|>List.ofArray
    let heapL n = n * 2 + 1
    let heapR n = n * 2 + 2
    let rec cInsert num path counter =
        match path with
            | [] -> heapWrite counter num
            | head::tail when head = 'L' -> cInsert num tail (heapL counter)
            | head::tail when head = 'R' -> cInsert num tail (heapR counter)
            | _ -> failwith "unknown"
    str.Split(' ')|>Array.map(fun x->Regex.Match(x,@"\((\d*),(\w*)\)"))|>
    Array.map(fun x->(x.Groups.[1].Value,x.Groups.[2].Value)) |> 
    Array.map conv |> Array.iter(fun (n,p) -> cInsert n p 0)
    heap
let isComplete (heap:int [])=
    let rec isCompleteRec n = 
        if n=1 then true else
        let nP=(n-(2-n%2)) / 2
        if heap.[nP] = -1 && heap.[n] <> -1 then false
        else isCompleteRec (n - 1)
    isCompleteRec (heap.Length-1)
let printHeap heap=
    heap |> Array.filter(fun x->x <> -1)

let heap = ofstr "(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR)" 
heap |> isComplete |> printfn "heap is completed?%b"
heap |> printHeap |> printfn "data : %A"


我模仿写了一个。
2010-8-10 23:55
0
雪    币: 206
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
11
多谢楼 上,我找到出错的原因了,是按lR转换的时候,如果给出256个R的时候出溢出了
2010-8-11 10:43
0
雪    币: 206
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
12
类似于你的思想,要是给出
RRRRRRRR*****RRR共256个,就不太好表示了,我错在这个地方了
不细心了
2010-8-11 10:45
0
雪    币: 1126
活跃值: (156)
能力值: ( LV9,RANK:210 )
在线值:
发帖
回帖
粉丝
13
嗯,有道理,严格说,输入100W个R也行,因为只说256个节点,没说是树的层数。用堆也只能用字符串存储比较大小了。
2010-8-11 20:20
0
雪    币: 159
活跃值: (339)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
14
想问问zoj1167对应poj的哪题?
2010-8-12 11:43
0
雪    币: 6075
活跃值: (2236)
能力值: (RANK:1060 )
在线值:
发帖
回帖
粉丝
15
邪恶,三进宫
class Node:
    def __init__(self, left=None, right=None, value=None):
        self.left = left
        self.right = right
        self.value = value

def build_child(node, value, path):
    branch, path = path[:1], path[1:]
    if branch == 'L':
        if node.left is None:
            node.left = Node()
        return build_child(node.left, value, path)
    elif branch == 'R':
        if node.right is None:
            node.right = Node()
        return build_child(node.right, value, path)
    else:
        if node.value is None:
            node.value = value
            return True
        else:
            return False

def build_tree(input):
    tree = Node()
    for value, path in input:
        if not build_child(tree, value, path):
            return
    return tree

def is_complete(node):
    if node is None:
        return True
    elif node.value is not None and is_complete(node.left) and is_complete(node.right):
        return True
    else:
        return False

def breadth_first_search(node):
    q = [node]
    path = []
    while q:
        node = q.pop(0)
        if node is None or node in path:
            continue
        path.append(node.value)
        q.append(node.left)
        q.append(node.right)
    return path

def solve(input):
    tree = build_tree(input)
    if tree and is_complete(tree):
        print breadth_first_search(tree)
    else:
        print 'not complete'

def test():
    import re
    s = """    
    (11,LL) (7,LLL) (8,R)
    (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
    (3,L) (4,R) ()
    (11,LL) (7,LLL) (8,R) (8,LL)
    (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()    
    """
    t = []
    for x in re.findall('\((.*?)\)', s):
        if not x:
            solve(t)
            t = []
        else:
            t.append(x.split(','))
            
if __name__ == '__main__':            
    test()
2010-8-12 12:14
0
雪    币: 206
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
16
膜拜楼上,不到山顶不罢休呀
2010-8-12 16:45
0
游客
登录 | 注册 方可回帖
返回
//