FilesExpand file tree

 master

/

Solution62.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

48 lines (40 loc) · 974 Bytes

 master

/

Solution62.java

Copy path

Top

File metadata and controls

• Code
• Blame

48 lines (40 loc) · 974 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

package com.usher.algorithm.offer;

import java.util.ArrayList;

import java.util.List;

/**

* @Author: Usher

* @Description:

* 约瑟夫环

* f(n,m)={0,n=1},{[f(n-1,m)+m]%n,n>1}

*/

public class Solution62 {

/* public int LastRemaining_Solution(int n, int m) {

if (n < 1|| m < 1)

return -1;

if (n ==1 )

return 0;

return (LastRemaining_Solution(n-1,m) + m) % n;

}*/

/**

* 模拟循环链表

* @param n

* @param m

* @return

*/

public int LastRemaining_Solution(int n, int m) {

if (n < 1|| m < 1)

return -1;

if (n ==1 )

return 0;

List<Integer> list = new ArrayList<>();

for (int i = 0;i < n;i++)

list.add(i);

int index = -1;

while (list.size() > 1){

index = (index + m) %list.size();

list.remove(index);

index--;

}

return list.get(0);

}

}