Sunday, January 24, 2016

G面经prepare: Jump Game Return to Original Place - neverlandly - 博客园

G面经prepare: Jump Game Return to Original Place - neverlandly - 博客园
`第二题 算法 给你一个arr 返回 T 或者 F arr的每个数代表从这个点开始跳几部，返回T的情况：`
`从这个arr中任意一个数开始跳，可以在每个元素都跳到且只跳到一次的情况下返回到开始跳的元素 `
`比如[1,1,1,1,1,1] => T [0,1,1,1,1,1]=> F [7, 5, 2, 3] => F [2,2,3,1] => T. From 1poi`

scan array once, get the index that can be reached by each array element for one step. check if every index can be reached by using HashSet
``` 5     public boolean check(int[] arr) {
6         HashSet<Integer> set = new HashSet<Integer>();
7         for (int i=0; i<arr.length; i++) {
8             set.add((i + arr[i]) % arr.length);
9         }
10         if (set.size() == arr.length) return true;
11         else return false;
12     }
17     public static void main(String[] args) {
18         // TODO Auto-generated method stub
19         Solution sol = new Solution();
20         boolean res = sol.check(new int[]{1,1,1,1,1,1,1});
21         if (res) System.out.println("True");
22         else System.out.println("False");
23     }```