8000 1，update README · sswssx/javaalgorithm@738d353 · GitHub
[go: up one dir, main page]
Skip to content

Commit 738d353

Browse files
author
shengshijun
committed
1，update README
2，修改BitUtil部分方法 3，完成求唯一元素的函数。
1 parent fc11602 commit 738d353

File tree

4 files changed

+99
-8
lines changed

4 files changed

+99
-8
lines changed

‎README.md

Lines changed: 18 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,8 @@ javaalgorithm
1111

1212
2， toArray方法返回的是Object[]类型，原因是Java不能够通过泛型创建数组，我是通过toVector来实现这个需求的
1313

14+
3， JDK集合类库中所有的迭代器next方法实际上会向下移动一位，而我的集合迭代器中则是在hasNext的时候向下移动一位。
15+
1416
#数据结构
1517

1618
##链表
@@ -49,7 +51,7 @@ javaalgorithm
4951

5052
###AVL树
5153

52-
###红黑树(待完成)
54+
###红黑树
5355

5456
###B树
5557

@@ -61,8 +63,21 @@ javaalgorithm
6163

6264
##其他
6365

64-
###：跳跃表（SkipList）
66+
###跳跃表（SkipList）
67+
68+
###BitSet
69+
70+
###StringBuilder
71+
72+
#算法
73+
74+
##排序算法
75+
76+
###快速排序，也是默认的排序方法
77+
78+
###计数排序
79+
80+
###基数排序
6581

66-
###：BitSet
6782

6883

‎src/main/java/ssj/algorithm/math/BitUtil.java

Lines changed: 9 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -10,20 +10,25 @@ public class BitUtil {
1010
private BitUtil() {
1111
}
1212

13+
/**
14+
* 比较一个位置的位是不是1
15+
*
16+
* @param value 要判断的值
17+
* @param index 从右开始计数
18+
* @return
19+
*/
1320
public static boolean testBit(long value, int index) {
1421
Preconditions.checkArgument(index >= 0 && index < Long.SIZE);
1522
return (value & (1L << index)) != 0;
1623
}
1724

1825
public static int firstBitOne(long value) {
19-
int first_one_index = -1;
2026
for (int i = 0; i < Integer.SIZE; i++) {
2127
if (BitUtil.testBit(value, i)) {
22-
first_one_index = i;
23-
break;
28+
return i;
2429
}
2530
}
26-
return first_one_index;
31+
return -1;
2732
}
2833

2934
public static long moveBit(long value, int from, int to) {

‎src/main/java/ssj/algorithm/math/MathUtil.java

Lines changed: 64 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
import ssj.algorithm.lang.Tuple2;
66

77
import java.math.BigInteger;
8+
import java.util.Arrays;
89
import java.util.Random;
910

1011
/**
@@ -177,7 +178,8 @@ private static int countNumberOneCore(String number) {
177178
* 同理：右边也是一样的：A1A2...Ax....Ay-1Ay...An < A1A2...Ax+1....Ay-1AxAy...An。
178179
* 综合三个等式得到：A1A2....Ax+1...Ay-1AyAx...An < A1A2...Ax+1....Ay-1AxAy...An。也就是AyAx < AxAy，这样
179180
* 显然和定义的比较规则相反，所以原假设不成立，证明了通过这样的排序规则得到的序列是最小的序列。
180-
* {{code shsi}}
181+
* {{code shsi}}
182+
*
181183
* @param arr
182184
* @return
183185
*/
@@ -335,4 +337,65 @@ public static double maxSubList(double[] arr) {
335337
}
336338
return max_value;
337339
}
340+
341+
/**
342+
* 来自《剑指offer》的一个题目，一个int数组中有一个唯一的元素，
343+
* 其他的元素都有两个，求出唯一的元素。
344+
*
345+
* @param arr
346+
* @return 唯一元素
347+
*/
348+
public static int uniqueInt(int[] arr) {
349+
Preconditions.checkNotNull(arr);
350+
Preconditions.checkArgument(arr.length >= 1);
351+
int result = 0;
352+
for (int i : arr) {
353+
result ^= i;
354+
}
355+
if (!checkUnique(arr, result)) {
356+
throw new IllegalArgumentException("do not have unique element :" + Arrays.toString(arr));
357+
}
358+
return result;
359+
}
360+
361+
362+
public static Tuple2<Integer, Integer> uniqueTwoInt(int[] arr) {
363+
Preconditions.checkNotNull(arr);
364+
Preconditions.checkArgument(arr.length >= 2);
365+
int result_partition = 0;
366+
for (int i : arr) {
367+
result_partition ^= i;
368+
}
369+
370+
int last_one = BitUtil.firstBitOne(result_partition);
371+
if (last_one == -1) {
372+
throw new IllegalArgumentException("do not have two unique element :" + Arrays.toString(arr));
373+
}
374+
375+
int result1 = 0, result2 = 0;
376+
for (int i : arr) {
377+
if (BitUtil.testBit(i, last_one)) {
378+
result1 ^= i;
379+
} else {
380+
result2 ^= i;
381+
}
382+
}
383+
384+
if (!(checkUnique(arr, result1) && checkUnique(arr, result2))) {
385+
throw new IllegalArgumentException("do not have two unique element :" + Arrays.toString(arr));
386+
}
387+
388+
return new Tuple2<>(result1, result2);
389+
}
390+
391+
private static boolean checkUnique(int[] arr, int ele) {
392+
Preconditions.checkNotNull(arr);
393+
int count = 0;
394+
for (int i : arr) {
395+
if (i == ele) {
396+
count++;
397+
}
398+
}
399+
return count == 1;
400+
}
338401
}

‎src/test/java/ssj/algorithm/math/MathUtilTest.java

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -77,4 +77,12 @@ public void testStrToInt() {
7777

7878
}
7979
}
80+
81+
82+
@Test
83+
public void testUniqueInt() {
84+
assertEquals(1, MathUtil.uniqueInt(new int[]{1, 2, 3, 4, 5, 2, 3, 4, 5}));
85+
assertEquals(2, MathUtil.uniqueInt(new int[]{100, 100, 3, 4, 5, 2, 3, 4, 5}));
86+
assertEquals(new Tuple2<>(2, 100), MathUtil.uniqueTwoInt(new int[]{100, 3, 4, 5, 2, 3, 4, 5}));
87+
}
8088
}

0 commit comments

Comments
 (0)
0