FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

linear search optimization (#188) · alimogh/Java@2d9f263 · GitHub

/ Java Public
forked from examplehub/Java

Commit 2d9f263

Browse files
realDuYuanChao
authored
linear search optimization (examplehub#188)
* linear search optimization * update bubble sort
1 parent 29c8dbb commit 2d9f263

5 files changed

Lines changed: 139 additions & 4 deletions

File tree

‎src/main/java/com/examplehub/leetcode/easy/PathSumII.java‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package com.examplehub.leetcode.easy;
2+
3+
import com.examplehub.leetcode.TreeNode;
4+
import com.sun.source.tree.Tree;
5+
6+
import java.util.ArrayList;
7+
import java.util.List;
8+
9+
/**
10+
* https://leetcode.com/problems/path-sum-ii/
11+
*/
12+
public class PathSumII {
13+
private static List<List<Integer>> result = new ArrayList<>();
14+
private static List<Integer> path = new ArrayList<>();
15+
public static List<List<Integer>> doSolution1(TreeNode root, int targetNum) {
16+
deepFirstSearch(root, targetNum);
17+
return result;
18+
}
19+
20+
private static void deepFirstSearch(TreeNode root, int targetNum) {
21+
if (root == null) {
22+
return;
23+
}
24+
path.add(root.val);
25+
targetNum -= root.val;
26+
if (root.left == null && root.right == null && targetNum == 0) {
27+
result.add(new ArrayList<>(path));
28+
}
29+
deepFirstSearch(root.left, targetNum);
30+
deepFirstSearch(root.right, targetNum);
31+
path.remove(path.size() - 1);
32+
}
33+
}

‎src/main/java/com/examplehub/searches/LinearSearchOptimization.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package com.examplehub.searches;
2+
3+
public class LinearSearchOptimization implements Search {
4+
5+
/**
6+
* Linear search algorithm.
7+
*
8+
* @param numbers the numbers to be searched.
9+
* @param key the key value t o be searched.
10+
* @return index of {@code key} value if found, otherwise -1.
11+
*/
12+
@Override
13+
public int search(int[] numbers, int key) {
14+
if (numbers.length == 0) {
15+
return -1;
16+
}
17+
if (key == numbers[0]) {
18+
return 0;
19+
}
20+
numbers[0] = key;
21+
int index = numbers.length - 1;
22+
while (key != numbers[index]) {
23+
index--;
24+
}
25+
return index == 0 ? -1 : index;
26+
}
27+
28+
/**
29+
* Generic linear search algorithm.
30+
*
31+
* @param array the array to be searched.
32+
* @param key the key object to be searched.
33+
* @param <T> the class of the objects in the array.
34+
* @return index of {@code key} if found, otherwise -1.
35+
*/
36+
@Override
37+
public <T extends Comparable<T>> int search(T[] array, T key) {
38+
if (array.length == 0) {
39+
return -1;
40+
}
41+
if (key.compareTo(array[0]) == 0) {
42+
return 0;
43+
}
44+
array[0] = key;
45+
int index = array.length - 1;
46+
while (key.compareTo(array[index]) != 0) {
47+
index--;
48+
}
49+
return index == 0 ? -1 : index;
50+
}
51+
}

‎src/main/java/com/examplehub/sorts/BubbleSort.java‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -10,9 +10,9 @@ public class BubbleSort implements Sort {
1010
* @param numbers the numbers to be sorted.
1111
*/
1212
public void sort(int[] numbers) {
13-
for (int i = 0; i < numbers.length - 1; ++i) {
13+
for (int i = 1; i < numbers.length; ++i) {
1414
boolean swapped = false;
15-
for (int j = 0; j < numbers.length - 1 - i; ++j) {
15+
for (int j = 0; j < numbers.length - i; ++j) {
1616
if (numbers[j] > numbers[j + 1]) {
1717
SortUtils.swap(numbers, j, j + 1);
1818
swapped = true;
@@ -31,9 +31,9 @@ public void sort(int[] numbers) {
3131
* @param <T> the class of the objects in the array.
3232
*/
3333
public <T extends Comparable<T>> void sort(T[] array) {
34-
for (int i = 0; i < array.length - 1; ++i) {
34+
for (int i = 1; i < array.length; ++i) {
3535
boolean swapped = false;
36-
for (int j = 0; j < array.length - 1 - i; ++j) {
36+
for (int j = 0; j < array.length - i; ++j) {
3737
if (array[j].compareTo(array[j + 1]) > 0) {
3838
SortUtils.swap(array, j, j + 1);
3939
swapped = true;

‎src/test/java/com/examplehub/leetcode/easy/PathSumIITest.java‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package com.examplehub.leetcode.easy;
2+
3+
import com.examplehub.leetcode.TreeNode;
4+
import com.examplehub.leetcode.utils.BinaryTreeUtils;
5+
import org.junit.jupiter.api.Test;
6+
7+
class PathSumIITest {
8+
@Test
9+
void testSolution1() {
10+
TreeNode root = BinaryTreeUtils.createTree(new int[]{5, 4, 8, 11, 0, 13, 4, 7, 2, 0, 0, 5, 1}, 0);
11+
//TODO
12+
}
13+
}

‎src/test/java/com/examplehub/searches/LinearSearchOptimizationTest.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.examplehub.searches;
2+
3+
import org.junit.jupiter.api.BeforeEach;
4+
import org.junit.jupiter.api.Test;
5+
6+
import java.util.stream.IntStream;
7+
8+
import static org.junit.jupiter.api.Assertions.assertEquals;
9+
10+
class LinearSearchOptimizationTest {
11+
12+
private Search search;
13+
14+
@BeforeEach
15+
void setup() {
16+
search = new LinearSearchOptimization();
17+
}
18+
19+
@Test
20+
void testLinearSearch() {
21+
int[] ints = IntStream.range(0, 10).toArray();
22+
for (int i = 0; i < ints.length; ++i) {
23+
assertEquals(i, search.search(ints, i));
24+
}
25+
26+
assertEquals(-1, search.search(ints, 10));
27+
assertEquals(-1, search.search(ints, 100));
28+
assertEquals(-1, search.search(ints, -1));
29+
30+
String[] strings = {"abc", "123", "ABC", "ExampleHub", "Java"};
31+
for (int i = 0; i < strings.length; ++i) {
32+
assertEquals(i, search.search(strings, strings[i]));
33+
}
34+
assertEquals(-1, search.search(strings, "Windows"));
35+
assertEquals(-1, search.search(strings, "321"));
36+
assertEquals(-1, search.search(strings, ""));
37+
}
38+
}

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL