京东括号匹配那题,我觉得又是笔试结束后才找出问题所在,好惨

public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String line = scanner.nextLine();
		List<Character> list = new ArrayList<>();
		for(int i = 0; i < line.length(); i++)
			list.add(line.charAt(i));		
		int res = opeNum(list);
		
		System.out.println(res);
	}
	private static int opeNum(List<Character> list) {
		if(list.size() == 2) {
			return 1;
		}
		//思路:将左括号压入栈中。遇到一个右括号则弹出。如果没有栈中空了,则结束这次循环。
		// indexes中保存的是这个可以被抹掉的右括号的索引。
		Stack<Character> stack = new Stack<>();
		List<Integer> indexes = new ArrayList<>();
		for(int i = 1; i < list.size(); i++) {
			if(list.get(i) == '(') {
				stack.push(list.get(i));
			}
			else {
				if(!stack.isEmpty()) {
					indexes.add(i);
					stack.pop();
				} else {
					indexes.add(i);
					break;
				}
			}
		}
		//下面,运用回溯法,找到这个list中所有的操作序列。
		int sum = 0;
		list.remove(0);
		for(int i = 0; i < indexes.size(); i++) {
                        //因为前面删除了第一个元素'(',所以,这里的索引减1
			int tmp = indexes.get(i) - 1;
			Character ch = list.get(tmp);
			list.remove(tmp);
			sum += opeNum(list);
			list.add(tmp, ch);
		}
		list.add(0, '('); //惨,做题时写成了list.add('(');
		return sum;
	}        
经过测试,至少()()()()和(((())))的情况可以通过,不至于只有10%。。。#京东#
全部评论
我看到别人写的这样也全过了
点赞 回复 分享
发布于 2017-09-08 22:07
如果不匹配的话把计数清0.。。说明没有合适的弹出方式
点赞 回复 分享
发布于 2017-09-08 22:09
我和你想法差不多,只过了30%。
点赞 回复 分享
发布于 2017-09-08 22:10
我也差不多,过了40%
点赞 回复 分享
发布于 2017-09-08 22:47
考试结束再修改10分钟左右才成功····伤心
点赞 回复 分享
发布于 2017-09-08 23:18
test
点赞 回复 分享
发布于 2017-09-09 10:45
要加上记忆搜索,直接递归会爆栈的
点赞 回复 分享
发布于 2017-09-09 10:55
40% 和20% 有机会面试吗
点赞 回复 分享
发布于 2017-09-09 11:00

相关推荐

点赞 5 评论
分享
牛客网
牛客企业服务