算法1
题目：一些数字 1-n，n的范围很小（1~52），先找到1，把1去掉，随后 找下一个除4余2的， 除4余3的， 除4余0的，除4余1的，直到最后一个
解法（自己）
暴力解法，感觉我自己写的这个太暴力了，哈哈~
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
| public class Solution2 {
public static void main(String[] args) {
int circle[] = {2,4,1,3};
int i = shrinkCircle(circle);
System.out.println(i);
}
public static int shrinkCircle (int[] circle) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < circle.length; i++) {
list.add(circle[i]);
}
int len = circle.length;
int j = 0;
int res = 0;
while (true) {
if (list.size() > 1) {
int l = list.size();
if (j == list.size() ) j = 0;
for (int i = j; i < list.size(); i++) {
if (list.get(i) == 1) {
list.remove(i);
j = i;
break;
}
}
if (l==list.size()){
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == 1) {
list.remove(i);
j = i;
break;
}
}
}
} else {
res = list.get(0);
break;
}
if (list.size() > 1) {
int l = list.size();
if (j == list.size() ) j = 0;
for (int i = j; i < list.size(); i++) {
if (list.get(i) % 4 == 2) {
list.remove(i);
j = i;
break;
}
}
if (l==list.size()){
for (int i = 0; i < list.size(); i++) {
if (list.get(i) % 4 == 2) {
list.remove(i);
j = i;
break;
}
}
}
} else {
res = list.get(0);
break;
}
if (list.size() > 1) {
if (j == list.size()) j = 0;
int l = list.size();
for (int i = j; i < list.size(); i++) {
if (list.get(i) % 4 == 3) {
list.remove(i);
j = i;
break;
}
}
if (l==list.size()){
for (int i = 0; i < list.size(); i++) {
if (list.get(i) % 4 == 3) {
list.remove(i);
j = i;
break;
}
}
}
} else {
res = list.get(0);
break;
}
if (list.size() > 1) {
int l = list.size();
if (j == list.size() ) j = 0;
for (int i = j; i < list.size(); i++) {
if (list.get(i) % 4 == 0) {
list.remove(i);
j = i;
break;
}
}
if (l==list.size()){
for (int i = 0; i < list.size(); i++) {
if (list.get(i) % 4 == 0) {
list.remove(i);
j = i;
break;
}
}
}
} else {
res = list.get(0);
break;
}
if (list.size()> 1) {
int l = list.size();
if (j == list.size() ) j = 0;
for (int i = j; i < list.size(); i++) {
if (list.get(i) % 4 == 1) {
list.remove(i);
j = i;
break;
}
}
if (l==list.size()){
for (int i = 0; i < list.size(); i++) {
if (list.get(i) % 4 == 1) {
list.remove(i);
j = i;
break;
}
}
}
} else {
res = list.get(0);
break;
}
}
return res;
}
}
|
参考大佬的：
解法二
对暴力解法进行优化，先对数组中的数进行%4运算，用数组info存储。再使用数组valied进行判断数组中的数是否被访问过。如果选择，以后就不要选择了。
代码1为：
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
| public class Solution2 {
public static void main(String[] args) {
int circle[] = {2,4,1,3};
int i = shrinkCircle(circle);
System.out.println(i);
}
public static int shrinkCircle (int[] circle) {
int len = circle.length;
int info[] = new int[len];
boolean valied[] = new boolean[len];
for (int i = 0;i<len;i++){
info[i] = circle[i]%4;
}
int index = 0;
while (circle[index]!=1){
index++;
}
valied[index] = true;
int num = 1;
int c = 2;
while (num!=len-1){
if (!valied[index] && info[index]==c){
num++;
c = c==3?0:c+1;
valied[index] = true;
}
index = index==len-1?0:index+1;
}
for(int i = 0;i<len;i++){
if (!valied[i]){
return circle[i];
}
}
return -1;
}
}
|
解法三
代码2为：
手动实现环形链表，将不满足的数据加到链表的后面
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
| public class Solution2 {
public static void main(String[] args) {
int circle[] = {9,8,7,6,5,4,3,2,1};
int i = shrinkCircle(circle);
System.out.println(i);
}
public static int shrinkCircle (int[] circle) {
LinkedList<Integer> list = new LinkedList<>();
int len = circle.length;
int index = 0;
for (int i = 0;i<len;i++){
list.add(circle[i]);
}
for (int i = 0;i<len;i++){
if (circle[i]==1){
index = i;
break;
}
}
list.remove(index);
int p = 2;
while (list.size()>1){
int t = list.removeFirst();
if (t%4==p){
p = p==3?0:p+1;
continue;
}
list.addLast(t);
}
return list.get(0);
}
}
|
算法2
题目：
在一个三维直角坐标系中，有一只蚂蚁从原点 (0, 0, 0) 开始，向目标点 (l, m, n) 前进，蚂蚁的前进规则如下：
1、l, m, n >= 0，且 l + m + n > 0；
2、蚂蚁每次只能沿X/Y/Z轴的方向前进一个单位，比如，当前蚂蚁在点(x0, y0, z0)，下一步只能前进到下面三个点中的任意一个：(x0 + 1, y0, z0)，或(x0, y0 + 1, z0)，或(x0, y0, z0 + 1)。
返回所有可以从原点 (0, 0, 0) 到目标点 (l, m, n) 的可行路径数量。
- @param x int整型 目标点的X坐标 * @param y int整型 目标点的Y坐标 * @param z int整型 目标点的Z坐标 * @return long长整型 */
解法一
通过数学的方法
高中数学题，我们可以认为，有三个商品abc，每一个又有多个，问你有多少种组合方式。相当于
1、在所有的 a+b+c 中，先选出a个位置 放a，个数为C(a+b+c, a) [不太会打上下的格式，就是排列组合中的 C，不是A]
2、在剩下的b+c个中，选出b个放b
3、c的话剩余的位置，只有1种
答案就是 第一步结果 * 第二部结果 * 1
注意说返回的long，应该很大，我再计算过程中用的Big Integer。
代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution {
public static void main(String[] args) {
System.out.println(countPaths(1,1,1));
Scanner in = new Scanner(System.in);
}
public static long countPaths (int x, int y, int z) {
int sum = x+y+z;
BigInteger b1 = process(sum,x);
BigInteger b2 = process(sum-x,y);
return b1.multiply(b2).longValue();
}
public static BigInteger process(int sum,int a){
BigInteger top = BigInteger.valueOf(1);
BigInteger down = BigInteger.valueOf(1);
for (int i = 0;i<a;i++){
top=top.multiply(BigInteger.valueOf(sum--));
}
for (int i = 1;i<=a;i++){
down = down.multiply(BigInteger.valueOf(i));
}
return top.divide(down);
}
}
|
算法3
最长递增子序列