HackerRank: Snakes and Ladders

public class Solution {
    private static final int N = 100;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int total = sc.nextInt();
        while (total > 0) {
            total--;
            int[] store = new int[N + 1];
            int ladders = sc.nextInt();
            for (int i = 0; i < ladders; i++) {
                int from = sc.nextInt();
                store[from] = sc.nextInt() - from;
            }
            int snakes = sc.nextInt();
            for (int i = 0; i < snakes; i++) {
                int from = sc.nextInt();
                store[from] = sc.nextInt() - from;
            }
            QueueEntry entry = new QueueEntry(1, 0);
            Queue<QueueEntry> queue = new LinkedList<QueueEntry>();
            queue.add(entry);
            boolean[] visited = new boolean[N + 1];
            boolean hasRes = false;
            while (!queue.isEmpty()) {
                entry = queue.poll();
                if (entry.pos == N) {
                    System.out.println(entry.step);
                    hasRes = true;
                    break;
                }
                if (visited[entry.pos] == true) {
                    continue;
                }
                visited[entry.pos] = true;
                for (int i = 1; i <= 6 && entry.pos + i <= N; i++) {
                    int nextPos = entry.pos + i;
                    if (store[nextPos] != 0) {
                        QueueEntry nextEntry = new QueueEntry(nextPos + store[nextPos], entry.step + 1);
                        queue.offer(nextEntry);
                    } else {
                        QueueEntry nextEntry = new QueueEntry(nextPos, entry.step + 1);
                        queue.offer(nextEntry);
                    }
                }
            }
            if (hasRes == false) {
                System.out.println(-1);
            }
        }
    }
    static class QueueEntry {
        int pos;
        int step;
        public QueueEntry (int pos, int step) {
            this.pos = pos;
            this.step = step;
        }
    }
}

Hacker Rank: Even Tree

用递归解决。貌似很多人面试都被问到的题。
从树的root开始遍历，如果一个节点的某个子节点形成的子树是even tree，那么直接断开这两个点。遍历的过程中将每个节点的所有节点都加入queue用于下一层继续遍历。

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int nodes = sc.nextInt();
        int vertices = sc.nextInt();
        int res = 0;
        Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
        for (int i = 0; i < vertices; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            if (!map.containsKey(to)) {
                map.put(to, new HashSet<Integer>());
            }
            map.get(to).add(from);
            
        }
        Queue<Integer> toVisit = new LinkedList<Integer>();
        toVisit.add(1);
        System.out.println(getRes(toVisit, map));
    }
    private static int getRes(Queue<Integer> queue, Map<Integer, Set<Integer>> map) {
        int res = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (map.containsKey(node)) {
                Set<Integer> neighbors = new HashSet<Integer>(map.get(node));
                for (int neighbor : neighbors) {
                    int nodeCount = getNodeCount(neighbor, map);
                    //the subtree of neighbor is an even tree, remove the link between node and neighbor
                    if (nodeCount % 2 == 1) {
                        res++;
                        map.get(node).remove(neighbor);
                    }
                    queue.offer(neighbor);
                }
            }
        }
        return res;
    }
    //get the children of current node
    private static int getNodeCount(int node, Map<Integer, Set<Integer>> map) {
        int res = 0;
        if (map.containsKey(node)) {
            for (int neighbor : map.get(node)) {
                res += getNodeCount(neighbor, map);
            }
            res += map.get(node).size();
        }
        return res;
    }
}

HackerRank: Red John is Back

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int total = sc.nextInt();
    while (total > 0) {
        total--;
        int n = sc.nextInt();
        int[] store = new int[n+1];
        store[0] = 1;
        for (int i = 1; i <= n; i++) {
            store[i] += store[i-1];
            if (i - 4 >= 0) {
                store[i] += store[i-4];
            }
        }
        int res = 0;
        for(int number = 2; number<=store[n]; number++){
            if(isPrime(number)){
                res++; 
            }
        }
        System.out.println(res);
    }
}
    
private static boolean isPrime(int n) {
    //check if n is a multiple of 2
    if (n!= 2 && n%2==0) return false;
    //if not, then just check the odds
    for(int i=3;i*i<=n;i+=2) {
        if(n%i==0)
            return false;
    }
    return true;
}

HackerRank: Knapsack

每件物品可以放多次的背包问题，核心代码在第二个for循环。

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int total = sc.nextInt();
    for (int i = 0;i < total; i++) {
        int size = sc.nextInt();
        int target = sc.nextInt();
        int[] store = new int[target+1];
        for (int j = 0; j < size; j++) {
            int cur = sc.nextInt();
            for (int k = target; k >= 0; k--) {
                for (int times = 1; times * cur <= k; times++) {
                    store[k] = Math.max(store[k], store[k-cur*times] + cur*times);
                }
            }
        }
        System.out.println(store[target]);
    }
}