leetcode面试题62. 圆圈中最后剩下的数字

leetcode面试题62. 圆圈中最后剩下的数字

四月 11, 2020

leetcode面试题62. 圆圈中最后剩下的数字

约瑟夫环问题，这绝对是我最后一次了，肯定能会了。

给出一个好想的方法，不用模拟链表，直接用取模模拟过程

先看最开始的版本，在while里面又多了一层循环，最后会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int lastRemaining(int n, int m) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int i=1,index=0;
        while (list.size() != 1) {
            for(i = 0; i < m; i++) {
                if (index > list.size()-1) {
                    index = 1;
                    //i = index;
                }
                else index++;
            }
            index--;
            int o = list.remove(index);
            //System.out.println(index+" "+o);
        }
        return list.get(0);
    }

其实在当前的节点的时候，可以直接知道下一个要删除的节点是哪个。
index=(index+m-1)%当前列表的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   public int lastRemaining(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int i=1,index=0;
        while (n > 1) {
            index = (index + m - 1)%n;
            list.remove(index);
            n--;
        }
        return list.get(0);
    }
}

注意这里如果用linkedList存储也会超时，因为remove需要遍历，而不是像数组一样直接删除。
最后补上公式法的题解甜姨的题解
leetcode 67/100