京东笔试第一题括号问题代码分享

AC代码，思路就是暴力递归加状态记忆，没想到更好的方法了。。。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.next();
            int result = process(s);
            System.out.println(result);
        }
    }

    private static int process(String s) {
        Map<String, Integer> map = new HashMap<>();
        return remove("()" + s, 1, map);
    }

    private static int remove(String s, int r, Map<String, Integer> map) {
        if (s.length() == 2) {
            return 1;
        }
        s = newString(s, r);
        if(map.get(s) != null) {
            return map.get(s);
        }
        int count = 0;
        for (int i = 1, len = s.length(); i < len; ++i) {
            if (s.charAt(i) == ')' && check(s, i)) {
                count += remove(s, i, map);
            }
        }
        map.put(s, count);
        return count;
    }

    private static String newString(String s, int r) {
        char[] ns = new char[s.length() - 2];
        int index = 0;
        for (int i = 1, len = s.length(); i < len; ++i) {
            if (i == r) {
                continue;
            }
            ns[index++] = s.charAt(i);
        }
        return new String(ns);
    }

    private static boolean check(String s, int r) {
        int k = 0;
        for (int i = 1, len = s.length(); i < len; ++i) {
            if (i == r) {
                continue;
            }
            if (s.charAt(i) == '(') {
                ++k;
            } else {
                --k;
                if (k < 0) {
                    return false;
                }
            }
        }
        return true;
    }

}

#京东#

全部评论

推荐最新楼层

本命年的Offer！

喀什大学 Java

两道题都把我坑到了 20%。。。

点赞回复分享

发布于 2017-09-08 21:08

相信大未来win

北京工业大学 Java

public class 京东_括号匹配方案 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); String str = in.nextLine().trim(); char[] chars = str.toCharArray(); ArrayList<Character> list = new ArrayList<>(); for(int i=0;i<chars.length;i++) list.add(chars[i]); //System.out.println(list.lastIndexOf('(')); int count = 1; while(!list.isEmpty()){ int index = list.lastIndexOf('('); count *= (list.size()-index-1); list.remove(list.size()-1); list.remove(index); } System.out.println(count); } }

点赞回复分享

发布于 2017-09-08 21:08

牛客雨林木风

东北石油大学 Java

package test; import java.util.Scanner; public class Main16 { public static int[] addFlag(char[] chs) { int[] left = new int[chs.length]; int[] list = new int[chs.length]; int leftFlag = 0; int listFlag = 0; int times = 1; for(int i=0;i<chs.length;i++) { if(chs[i] == '(') { left[leftFlag] = times; times++; leftFlag++; list[listFlag] = left[leftFlag-1]; listFlag++; }else if(chs[i] == ')') { list[listFlag] = left[leftFlag-1]; listFlag++; leftFlag--; } } return list; } public static int count(int[] list, int start, int end) { if(start >= end) { return 0; } int ans = 0; while(start < end) { if(list[start] == list[end]) { ans++; start++; end--; }else{ break; } } int temp = 1; for(int i=ans;i>=1;i--) { temp *= i; } ans = temp; /*******递归*******/ int copyend = end - 1; while((copyend > start) && (list[copyend] != list[start])) { copyend--; } ans += count(list, start, copyend); ans += count(list, copyend+1, end); return ans; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); String str = scan.nextLine(); char[] chs = str.toCharArray(); int[] list = addFlag(chs); int ans = count(list, 0, list.length-1); System.out.println(ans); } }

点赞回复分享

发布于 2017-09-08 21:06

牛客394347号

吉林大学 Java

大神过了多少，都不会做。。。。

点赞回复分享

发布于 2017-09-08 21:06