POJ1068

问题描述###

一组括号 (((( ) ( ) ( ) ) ) )

有两种描述方法:

P方法:4 5 6 6 6 6 - 每一个)前,有几个(

W方法:1 1 1 4 5 6 - 每一个),向前数几个是跟它匹配的(

要求是根据P求W

参考:http://www.cnblogs.com/linucos/archive/2011/10/12/2208567.html


难点###

将原序列转化为W
P转化为原序列是很好想到的,但是后一个需要用stack的思路来解决~
百度后解决,我果然很2~


解题思路###

首先把P转化为原始的序列,然后把原始序列转化为W。
其中用BitSet来描述序列

  • 0: "("
  • 1: ")"

因为数字描述的是')',所以我们先把数组初始化成都是'('.对于第N个数p,如第一个数4,4表示这个')'前边的'('个数,如果再知道前边')'的个数,那么这个')'的下标就找到了. N就是前边')'的个数,所以stack[N+p]=')'.

怎么利用stack推倒出W呢?也很简单,遍历stack数组,当我们发现')'时候,就向前找,另w = 1,c = 0,遇到一个')'加1,同时c加1,说明中间遇到一对(),遇到一个'('减1,当w为0时候,就找到了匹配的'('. c就是个数.


代码实现###

`
package poj;
import java.util.BitSet;
import java.util.Scanner;
public class Poj1068 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String nS = sc.nextLine();
int n = Integer.valueOf(nS);
for(int i = 0 ; i < n ; i ++){
/* translate P to real value */
sc.nextLine();
BitSet value = new BitSet();
String dataS = sc.nextLine();
String[] dataSs = dataS.split(" ");
int oldP = 0;
int newP = 0;
int len = 0;
for(String data : dataSs){
newP = Integer.valueOf(data);
int addP = newP - oldP;
for(int j = len ; j < len + addP ; j ++){
value.set(j, false);
}
len += addP;
value.set(len, true);
len ++;
oldP = newP;

        }

// for(int j = 0 ; j < value.length() ; j ++){
// if(value.get(j))
// System.out.print(")");
// else
// System.out.print("(");
// }
// System.out.println();
/* translate real value to W */
// System.out.println(value);
StringBuffer sb = new StringBuffer();
for(int j = 0 ; j < value.length() ; j ++){
if(value.get(j)){
int c = 0;
int w = 1;
for(int k = j - 1 ; k >= 0 ; k --){
if(value.get(k)){
w ++;
c ++;
}
else{
w --;
}
if(w == 0)
break;
}
sb.append((c+1)+" ");
}
}
String r = sb.toString();
System.out.println(r.substring(0, r.length()-1));
// System.out.println();
}
sc.close();
}
}

`

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔...
    叶总韩阅读 5,161评论 0 41
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,742评论 18 399
  • 回溯算法 回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并...
    fredal阅读 13,715评论 0 89
  • 一、 1、请用Java写一个冒泡排序方法 【参考答案】 public static void Bubble(int...
    独云阅读 1,410评论 0 6
  • 没肉不行啊 白菜烧肉包菜一颗,肉一坨 黑椒牛柳/牛肉粒/牛排超市来一包 素食主义者 蚕豆5块 西红柿/青椒炒鸡蛋 ...
    shm007阅读 290评论 0 0