This repository was archived by the owner on Jul 3, 2020. It is now read-only.
forked from dc-mak/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathArrays.java
More file actions
114 lines (95 loc) · 2.29 KB
/
Arrays.java
File metadata and controls
114 lines (95 loc) · 2.29 KB
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
public class Arrays {
public static void sum1(int[] a, int[] b) {
assert (a.length == b.length);
for (int i = 0; i < a.length; i++)
for (int j = 0; j < a.length; j++)
b[i] += j == i ? 0 : a[i];
}
public static void sum2(int[] a, int[] b) {
assert (a.length == b.length);
int total = 0;
for (int i = 0; i < a.length; i++)
for (int j = 0; j < a.length; j++)
total += b[i];
total /= (a.length-1);
for (int i = 0; i < a.length; i++)
a[i] = total - b[i];
}
public static void heapify(int[] a) {
int heapsize = a.length;
for (int i = a.length / 2; i >= 0; i--) {
int j = i;
while (true) {
final int left = 2*j + 1;
final int right = left + 1;
int max = 0;
if (left <= heapsize && a[left] > a[right])
max = left;
else
max = j;
if (right <= heapsize && a[right] > a[max])
max = right;
if (max == j)
break;
// else
int tmp = a[j];
a[j] = a[max];
a[max] = tmp;
j = max;
}
}
}
public static int stream(int[] a, long k) {
assert (k >= 0);
long len = a.length;
k %= 2*len;
if (k < len)
return a[(int) k];
else // k >= len
return 1 - a[(int) (2*len-1 - k)];
}
public static boolean isSubseq(int[] a, int[] b) {
if (a.length > b.length)
return false;
int current = 0;
for (int i = 0; i < b.length ; i++)
if (b[i] == a[current])
current++;
return current >= a.length;
}
public static boolean isConsecSubseq(int[] a, int[] b) {
if (a.length > b.length)
return false;
boolean match = false;
for (int i = 0; i < b.length - a.length; i++) {
match = true;
for (int j = 0; j < a.length; j++)
if (b[j+i] != a[j]) {
match = false;
break;
}
if (match)
return true;
}
return false;
}
// Princeton Knuth-Morris-Pratt Algorithm: youtu.be/iZ93Unvxwtw
public static boolean KMP(int[] a, int[] b) {
if (a.length > b.length)
return false;
final int RADIX = 10;
final int[][] dfa = new int[RADIX][a.length];
// assume all values are single digits
dfa[a[0]][0] = 1;
for (int x = 0, j = 1; j < a.length; j++) {
for (int c = 0; c < RADIX; c++)
dfa[c][j] = dfa[c][x];
dfa[a[j]][j] = j+1;
x = dfa[a[j]][x];
}
int i, j;
for (j = 0, i = 0; i < b.length && j < a.length; i++)
j = dfa[b[i]][j];
return j == a.length;
}
}