HackerRank: Missing Number

简单题

public static void main(String[] args) {
        Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
        Scanner sc = new Scanner(System.in);
        int size1 = sc.nextInt();
        for (int i = 0; i < size1; i++) {
            int cur = sc.nextInt();
            map.put(cur, map.containsKey(cur) ? map.get(cur) + 1 : 1);
        }
        int size2 = sc.nextInt();
        for (int i = 0;i < size2; i++) {
            int cur = sc.nextInt();
            map.put(cur, map.containsKey(cur) ? map.get(cur) - 1 : -1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() != 0) {
                System.out.print(entry.getKey() + " ");
            }
        }
}

HackerRank: Bus Station

用prefix sum即可。有一个testcase超时了。

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        Set<Integer> preSum = new HashSet<Integer>();
        int pre = 0;
        int min = -1;
        for (int i = 0; i < size; i++) {
            int cur = sc.nextInt();
            min = min == -1 ? cur : Math.min(min, cur);
            pre += cur;
            preSum.add(pre);            
        }
        for (int i = min; i <= pre; i++) { // i is the size of bus
            if (pre % i != 0) {
                continue;
            }
            boolean success = true;
            for (int times = 1; times <= pre/i; times++) {
                if (!preSum.contains(times*i)) {
                    success = false; //to indicate this size of bus does not work;
                    break;
                }
            }
            if (success == true) {
                System.out.print(i + " ");
            }
        }
    }

HackerRank: Jim and the Skyscrapers

还是用ordered stack。非递增stack。

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        Stack<Integer> stack = new Stack<Integer>();
        long res = 0;
        for (int i = 0; i < size; i++) {
            int cur = sc.nextInt();
            if (!stack.isEmpty() && stack.peek() < cur) {
                int tmp = stack.pop();
                long dupCount = 1;
                while (!stack.isEmpty() && stack.peek() < cur) {
                    int top = stack.pop();
                    if (top == tmp) {
                        dupCount++;
                    } else {
                        //update possible routes
                        res += dupCount * (dupCount - 1);
                        tmp = top;
                        dupCount = 1;
                    }
                }
                res += dupCount * (dupCount - 1);
            }
            stack.push(cur);
        }
        while (!stack.isEmpty()) {
            int tmp = stack.pop();
            long dupCount = 1;
            while (!stack.isEmpty() && stack.peek() == tmp) {
                dupCount++;
                stack.pop();
            } 
            res += dupCount * (dupCount - 1);
        }
        System.out.println(res);
    }