But I cant find why ??
Anybody to help me??
Code: Select all
removed after AC
Moderator: Board moderators
Code: Select all
removed after AC
Code: Select all
removed after AC
Code: Select all
3
xyPzwIM
abcABdefgCDEF
xyPzwIM
Use queue::front() to access the head element of the queue.I tried to use a STL queue of the pointers of the objects of my self-defined class 'node' . But when popping , the compiler threw an error that the pop function is returning a void type pointer which cannot be casted to my object's pointer.
Code: Select all
template<typename T>
T pop(queue<T> &q) { T x = q.front(); q.pop(); return x; }
Code: Select all
delete
Code: Select all
#include <iostream>
#include <string>
//11234.cpp
using namespace std;
int t;
string q[990000];
string ans;
int idx;
int head;
void push(string s){
q[idx++] = s;
}
string pop(){
string s = q[head];
head++;
return s;
}
bool isEmpty(){
if (head >= idx)
return true;
else
return false;
}
int numOfOps(string s){
int cnt = 0;
int len = s.length();
for (int i=len -1; i>=0; i--){
if (s[i] < 95) {//operator
cnt ++;
continue;
}
else
break;
}
return cnt;
}
int main(){
string s;
int len;
int skip;
cin >> t;
for (int i=0; i<t; i++){
cin >> s;
idx = 0;
head = 0;
push(s);
ans = "";
while (!isEmpty()){
s = pop();
len = s.length();
if (s[len-1] < 95){
ans = s[len-1] + ans;
skip = numOfOps(s);
if (skip > 1){
string right = s.substr(len-2*skip, 2*skip-1);
string left = s.substr(0, len-2*skip);
push(left);
push(right);
}
else{
push(s.substr(0, len-1));
}
}
else{
for (int j=0; j<len; j++)
ans = s[j] + ans;
}
} //end while
cout << ans << endl;
} //end for
}
You are copying string all the time, your algorithm is slow because of that.jjtse wrote:Does anyone know more ways to optimize this code? I already optimized my queue usage. I'm suspecting I can do my string concatenations faster, but I don't know how to do it. Any ideas how I can get this faster?
Code: Select all
//import java.io.File;
//import java.io.FileInputStream;
//import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
class Main {
private static Stack<Character> stack = new Stack<Character>();
public static void main(String[] args) /*throws FileNotFoundException*/ {
//final long startTime = System.currentTimeMillis();
// System.setIn(new FileInputStream(new File("test.txt")));
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
StringBuilder output = new StringBuilder();
while (sc.hasNextLine()) {
String line = sc.nextLine();
for (char c : line.toCharArray()) {
stack.push(c);
}
Node tree = buildTree();
output.append(tree.queueExpression() + "\n");
stack.clear();
}
output.deleteCharAt(output.length() - 1);
System.out.println(output.toString());
//System.out.println(System.currentTimeMillis() - startTime);
}
public static Node buildTree() {
Character c = stack.pop();
Node leftSubtree, rightSubtree;
if (Character.isUpperCase(c)) {
leftSubtree = buildTree();
rightSubtree = buildTree();
} else {
return new Node(c);
}
return new Node(c, leftSubtree, rightSubtree);
}
}
class Node {
Character value;
Node leftChild;
Node rightChild;
Node(Character value) {
this(value, null, null);
}
Node(Character value, Node leftChild, Node rightChild) {
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
public String queueExpression() {
Queue<Node> frontier = new LinkedList<Node>();
Stack<Character> visited = new Stack<Character>();
frontier.add(this);
while (!frontier.isEmpty()) {
Node current = frontier.remove();
visited.push(current.value);
if (current.rightChild != null) {
frontier.add(current.rightChild);
}
if (current.leftChild != null) {
frontier.add(current.leftChild);
}
}
StringBuilder sb = new StringBuilder();
while (!visited.isEmpty()) {
sb.append(visited.pop());
}
return sb.toString();
}
// @Override
// public String toString() {
// String str = "[value:" + value + ", left:" + leftChild.value
// + ", right:" + rightChild.value + "]";
// return str;
// }
}
Code: Select all
1
abDcdEBefFghGCA
Code: Select all
hgfedcbaGFEDCBA
Code: Select all
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<stack>
using namespace std;
char str[10010],in[10010];
struct node
{
char ch;
node* lchild;
node* rchild;
};
node* build(int n, char *in, char *str, node* u)
{
if (n<=0) return NULL;
int i=0;
while(*(in+i)!=*str) i++;
u=(node*) malloc (sizeof(node));
u->ch=*str;
u->lchild=build(i,in,str-n+i,u->lchild);
u->rchild=build(n-i-1,in+i+1,str-1,u->rchild);
return u;
}
void bfs(node* u)
{
node* tree[20010];
int front=0,rear=1,n=0;
char cx[10010];
tree[0]=u;
while(front<rear)
{
node* temp=tree[front++];
cx[n++]=temp->ch;
if (temp->lchild!=NULL) tree[rear++]=temp->lchild;
if (temp->rchild!=NULL) tree[rear++]=temp->rchild;
}
for (int i=n-1; i>=0; i--)
cout<<cx[i];
cout<<endl;
return;
}
int main ()
{
int t,len,i;
cin>>t;
while(t--)
{
memset(str,0,sizeof(str));
cin>>str;
stack<string> s;
len=strlen(str);
for (i=0; i<len; i++)
{
if (str[i]<='Z')
{
string t1,t2,temp;
t1=s.top();
s.pop();
t2=s.top();
s.pop();
temp+=t1+str[i]+t2;
s.push(temp);
}
else
{
string temp;
temp+=str[i];
s.push(temp);
}
}
string temp;
temp=s.top();
while(!s.empty())
{
s.pop();
}
int j=0;
memset(in,0,sizeof(in));
for (i=temp.length()-1; i>=0; i--)
in[j++]=temp[i];
in[j]='\0';
node* root=build(j,in,str+j-1,root);
bfs(root);
}
return 0;
}