<repo_name>qq98982/algorithm<file_sep>/src/main/java/com/home/henry/MergeTwoSortedArrays.java
package com.home.henry;

public class MergeTwoSortedArrays {
    public int[] merge(int[] first, int[] second) {
        if (first.length < 1 && second.length < 1) {
            return null;
        }
        int m = first.length - 1;
        int n = second.length - 1;
        int[] res = new int[m + n + 2];
        for (int i = res.length - 1; i >= 0; i--) {
            if (n >= 0 && m >= 0) {
                if (first[m] > second[n]) {
                    res[i] = first[m--];
                } else {
                    res[i] = second[n--];
                }
            } else {
                if (m < 0) {
                    res[i] = second[n--];
                }
                if (n < 0) {
                    res[i] = first[m--];
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] a = new int[] { 1, 3, 5, 6, 9 };
        int[] b = new int[] { 2, 4, 7, 8 };
        MergeTwoSortedArrays m = new MergeTwoSortedArrays();
        int[] c = m.merge(a, b);
        for (int aC : c) {
            System.out.print(aC + " ");
        }
    }
}
<file_sep>/src/main/java/com/home/henry/ReverseLinkedList.java
package com.home.henry;

/**
 * Reverse a linked list
 */
public class ReverseLinkedList {

    ListNode reverse(ListNode current) {
        if (current == null) {
            return null;
        }
        ListNode prev = null;
        while (current != null) {
            ListNode temp = current.next;
            current.next = prev;
            prev = current;
            current = temp;
        }
        return prev;
    }
}
<file_sep>/src/main/java/com/home/henry/FindMaxCountArray.java
package com.home.henry;

import java.util.Arrays;

public class FindMaxCountArray {

    public static int findMax(int[] a, int size) {
        int i, j;
        int max = a[0];
        int count;
        int maxCount = 1;
        for (i = 0; i < size; i++) {
            count = 1;
            for (j = i + 1; j < size; j++) {
                if (a[i] == a[j]) {
                    count++;
                }
                if (count > maxCount) {
                    max = a[i];
                    maxCount = count;
                }
            }
        }
        return max;
    }

    public static int findMaxUseSort(int[] a, int size) {
        if (size > a.length) {
            return a[0];
        }
        Arrays.sort(a);
        int count = 1, maxCount = 1, max = a[0];
        for (int i = 1; i < size; i++) {
            if (a[i] == a[i - 1]) {
                count++;
            } else {
                count = 1;
            }
            if (count > maxCount) {
                maxCount = count;
                max = a[i];
            }
        }
        return max;
    }

}
<file_sep>/src/test/java/com/home/henry/OneAwayTest.java
package com.home.henry;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class OneAwayTest {

    @Test
    void isOneWay() {
        OneAway oneAway = new OneAway();
        Assertions.assertTrue(oneAway.isOneWay("pale", "ple"));
        Assertions.assertTrue(oneAway.isOneWay("", "p"));
        Assertions.assertTrue(oneAway.isOneWay("p", ""));
        Assertions.assertTrue(oneAway.isOneWay("pales", "pale"));
        Assertions.assertTrue(oneAway.isOneWay("pale", "bale"));
        Assertions.assertFalse(oneAway.isOneWay("pale", "bake"));
        Assertions.assertFalse(oneAway.isOneWay("teach", "teacher"));
    }
}<file_sep>/src/main/java/com/home/henry/OneAway.java
package com.home.henry;

/**
 * There are three types of edits that can be performed on strings: insert a character,
 * remove a character, or replace a character. Given two strings, write a function to check if they are
 * one edit (or zero edits) away.
 */
public class OneAway {
    boolean isOneWay(String source, String target) {
        if (null == source || null == target) {
            return false;
        }
        if (Math.abs(source.length() - target.length()) > 1) {
            return false;
        }
        int i = 0, j = 0;
        int count = 0;
        while (i < source.length() && j < target.length()) {
            if (source.charAt(i) != target.charAt(j)) {
                if (count > 0) {
                    return false;
                }
                count++;
                if (source.length() > target.length()) {
                    i++;
                }
                if (source.length() < target.length()) {
                    j++;
                }
            }
            i++;
            j++;
        }
        return true;
    }
}
<file_sep>/src/main/java/com/home/henry/BinaryTreeLevelOrder.java
package com.home.henry;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    public TreeNode left;
    public TreeNode right;
    public int value;

    TreeNode(int value) {
        this.value = value;
        this.left = this.right = null;
    }
}

/**
 * BinaryTree Lever Order
 */
public class BinaryTreeLevelOrder {
    public List<List<Integer>> leverOrder(TreeNode root) {
        List<List<Integer>> results = new ArrayList<>();
        if (null == root) {
            return results;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Integer> current = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode head = queue.poll();
                current.add(head.value);
                if (null != head.left) {
                    queue.offer(head.left);
                }
                if (null != head.right) {
                    queue.offer(head.right);
                }
            }
            results.add(current);
        }
        return results;
    }
}
<file_sep>/src/main/java/com/home/henry/PalindromeLinkedList.java
package com.home.henry;

/**
 * Given a singly linked list, determine if it is a palindrome.
 * O(n) time and O(1) space?
 */
class PalindromeLinkedList {
    private static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public boolean isPalindrome(ListNode head) {
        // count length
        int count = 0;

        // Do not change head!!!
        ListNode curr = head;
        while (curr != null) {
            curr = curr.next;
            count++;
        }
        if (count < 2) {
            return true;
        }
        curr = head;
        // reverse last half part, return end part head
        ListNode endHead = reverseEnd(curr, count);
        // iterate, check if it is equal
        return checkPalindrome(head, endHead);
    }

    // reverse half end part
    private ListNode reverseEnd(ListNode head, int count) {
        for (int i = 0; i < count / 2; i++) {
            if (head != null) {
                head = head.next;
            }
        }
        return reverse(head);
    }

    // reverse a LinkedList
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = prev;
            prev = head;
            head = tmp;
        }
        return prev;
    }

    private boolean checkPalindrome(ListNode head, ListNode endHead) {
        while (head != null && endHead != null) {
            if (head.val != endHead.val) {
                return false;
            }
            head = head.next;
            endHead = endHead.next;
        }
        return true;
    }
}<file_sep>/src/main/java/com/home/henry/ListNoderemoveDups.java
package com.home.henry;

import java.util.HashSet;
import java.util.Set;

/**
 * Write code to remove duplicates from an unsorted linked list.
 */
public class ListNoderemoveDups {

    ListNode deleteDups(ListNode n) {
        ListNode prev = null;
        Set<Integer> set = new HashSet<>();
        while (n != null) {
            if (set.contains(n.data)) {
                assert prev != null;
                prev.next = n.next;
            } else {
                set.add(n.data);
                prev = n;
            }
            n = n.next;
        }
        return prev;
    }
}
<file_sep>/src/test/java/com/home/henry/BinarySearchSortedArrayTest.java
package com.home.henry;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class BinarySearchSortedArrayTest {

    private static final int[] a = { 1, 3, 5, 7, 9, 11 };

    @Test
    void binarySearchTest() {
        Assertions.assertEquals(0, BinarySearchSortedArray.binarySearch(new int[] {1}, 1));
        Assertions.assertEquals(-1, BinarySearchSortedArray.binarySearch(new int[] {}, 0));
        Assertions.assertEquals(2, BinarySearchSortedArray.binarySearch(a, 5));
        Assertions.assertEquals(5, BinarySearchSortedArray.binarySearch(a, 11));
        Assertions.assertEquals(-1, BinarySearchSortedArray.binarySearch(a, 8));
    }

    @Test
    void binarySearchRecurive() {
        Assertions.assertEquals(0, BinarySearchSortedArray.binarySearchRecurive(new int[] {1,2}, 0,1,1));
        Assertions.assertEquals(-1, BinarySearchSortedArray.binarySearchRecurive(new int[] {}, 0,0,0));
        Assertions.assertEquals(2, BinarySearchSortedArray.binarySearchRecurive(a,0,a.length-1, 5));
        Assertions.assertEquals(5, BinarySearchSortedArray.binarySearchRecurive(a, 0,a.length-1, 11));
        Assertions.assertEquals(-1, BinarySearchSortedArray.binarySearchRecurive(a, 0,a.length-1, 8));
    }
}<file_sep>/src/test/java/com/home/henry/ListNodeIsLoopTest.java
package com.home.henry;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class ListNodeIsLoopTest {
    private ListNode n1;
    private ListNode n2;
    private ListNode n3;
    private ListNode n4;
    private ListNode n5;
    private ListNode n6;

    @BeforeEach
    void setUp() {
        n1 = new ListNode(1);
        n2 = new ListNode(2);
        n3 = new ListNode(3);
        n4 = new ListNode(4);
        n5 = new ListNode(5);
        n6 = new ListNode(6);
    }

    @Test
    void isLoopList() {
        n1.next = n2;
        Assertions.assertFalse(ListNodeIsLoop.isLoopList(n1));
        n2.next = n1;
        Assertions.assertTrue(ListNodeIsLoop.isLoopList(n1));
        n2.next = n3;
        Assertions.assertFalse(ListNodeIsLoop.isLoopList(n1));
        n3.next = n4;
        Assertions.assertFalse(ListNodeIsLoop.isLoopList(n1));
        n4.next = n5;
        Assertions.assertFalse(ListNodeIsLoop.isLoopList(n1));
        n5.next = n2;
        Assertions.assertTrue(ListNodeIsLoop.isLoopList(n1));
        n5.next = n6;
        n6.next = n2;
        Assertions.assertTrue(ListNodeIsLoop.isLoopList(n1));
    }
}<file_sep>/src/test/java/com/home/henry/ListNodeGetMiddleTest.java
package com.home.henry;

import static com.home.henry.ListNodeGetMiddle.getMiddle;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class ListNodeGetMiddleTest {
    private ListNode n1;
    private ListNode n2;
    private ListNode n3;
    private ListNode n4;
    private ListNode n5;
    private ListNode n6;

    @BeforeEach
    void init() {
        n1 = new ListNode(1);
        n2 = new ListNode(2);
        n3 = new ListNode(3);
        n4 = new ListNode(4);
        n5 = new ListNode(5);
        n6 = new ListNode(6);
    }

    @Test
    void getMiddleTest() {
        ListNode nt = getMiddle(n1);
        Assertions.assertEquals(1, nt.data);
        n1.next = n2;
        nt = getMiddle(n1);
        Assertions.assertEquals(2, nt.data);
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        nt = getMiddle(n1);
        Assertions.assertEquals(3, nt.data);
        n5.next = n6;
        nt = getMiddle(n1);
        Assertions.assertEquals(4, nt.data);
    }
}<file_sep>/src/main/java/com/home/henry/HashTable.java
package com.home.henry;

public class HashTable {

    private int size;
    private Node[] entries;

    private static class Node<K, V> {
        K k;
        V v;
        Node next;

        Node(K k, V v) {
            this.k = k;
            this.v = v;
            this.next = null;
        }
    }

    public HashTable(int size) {
        this.size = size;
        entries = new Node[size];
        for (int i = 0; i < entries.length; i++) {
            entries[i] = null;
        }
    }

    public HashTable() {
        this(1 << 3);
    }

    private int hash(Object obj) {
        return obj == null ? 0 : (obj.hashCode() % size);
    }

    public <K, V> void set(K k, V v) {
        Node<K, V> node = new Node<>(k, v);
        node.next = entries[hash(k)];
        entries[hash(k)] = node;
    }

    public <K> Object get(K k) {
        Node entry = entries[hash(k)];
        if (entry == null) {
            return null;
        } else {
            while (entry != null) {
                if (entry.k.equals(k)) {
                    return entry.v;
                }
                entry = entry.next;
            }
            return null;
        }
    }

    public static void main(String[] args) {
        HashTable h = new HashTable();
        for (int i = 0; i < 1000; i++) {
            h.set(i, Math.sqrt(i));
        }
        System.out.println(h.get(484).toString());
    }

}
<file_sep>/src/main/java/com/home/henry/ReverseWords.java
package com.home.henry;

/**
 * Reverse words order in a String
 */
public class ReverseWords {
    public String reverseWords(char[] c) {
        if (c == null || c.length == 0) {
            return null;
        }
        reverse(c, 0, c.length - 1);
        int l = -1;
        int r = -1;
        for (int i = 0; i < c.length; i++) {
            if (c[i] != ' ') {
                l = ((i == 0) || (c[i - 1] == ' ')) ? i : l;
                r = ((i == (c.length - 1)) || (c[i + 1] == ' ')) ? i : r;
            }
            if (l != -1 && r != -1) {
                reverse(c, l, r);
                l = -1;
                r = -1;
            }
        }
        return String.valueOf(c);
    }

    private static void reverse(char[] c, int l, int r) {
        char tmp;
        while (l < r) {
            tmp = c[l];
            c[l] = c[r];
            c[r] = tmp;
            l++;
            r--;
        }
    }
}
<file_sep>/src/main/java/com/home/henry/RemoveZero.java
package com.home.henry;

/**
 * 去掉String中连续出现k个0的sub string
 */
public class RemoveZero {

    private static String removeZeros(String in, int k) {
        char[] inArr = in.toCharArray();
        int count = 0;
        int start = -1;
        for (int i = 0; i < inArr.length; i++) {
            if (inArr[i] == '0') {
                count++;
                start = start == -1 ? i : start;
            } else {
                if (count == k) {
                    while (count-- != 0) {
                        inArr[start++] = 0;
                    }
                }
                count = 0;
                start = -1;
            }
        }
        if (count == k) {
            while (count-- != 0) {
                inArr[start++] = 0;
            }
        }
        return String.valueOf(inArr).replace("\u0000","");
    }

    public static void main(String[] args) {
        assert "ABab0".equals(removeZeros("AB0000ab0", 4));
        assert "ABab".equals(removeZeros("AB0000ab0000", 4));
        assert "ABab".equals(removeZeros("AB0000ab0000", 4));
        assert "AB00000ab00000".equals(removeZeros("AB00000ab00000", 4));
        assert "AB00000ab".equals(removeZeros("AB00000ab0000", 4));
    }
}<file_sep>/src/test/java/com/home/henry/StringRotationTest.java
package com.home.henry;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class StringRotationTest {

    @Test
    void isRotation() {
        StringRotation sr = new StringRotation();
        Assertions.assertTrue(sr.isRotation("w", "w"));
        Assertions.assertTrue(sr.isRotation("wa", "aw"));
        Assertions.assertTrue(sr.isRotation("waterbottle", "erbottlewat"));
        Assertions.assertFalse(sr.isRotation("", ""));
        Assertions.assertFalse(sr.isRotation("", null));
        Assertions.assertFalse(sr.isRotation("waterbottle", "erbottletwa"));
    }
}<file_sep>/src/test/java/com/home/henry/RotateMatrixTest.java
package com.home.henry;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class RotateMatrixTest {

    @Test
    void testRotateMatrix() {
        int[][] mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } };
        RotateMatrix rotateMatrix = new RotateMatrix();
        rotateMatrix.displayMatrix(mat);
        rotateMatrix.rotateMatrix(mat);
        rotateMatrix.displayMatrix(mat);
        Assertions.assertEquals(7, mat[2][2]);
        Assertions.assertEquals(9, mat[0][1]);
        Assertions.assertEquals(10, mat[1][1]);
        Assertions.assertEquals(8, mat[3][2]);
        rotateMatrix.rotateMatrix(mat);
        Assertions.assertEquals(6, mat[2][2]);
        Assertions.assertEquals(15, mat[0][1]);
        Assertions.assertEquals(11, mat[1][1]);
        Assertions.assertEquals(2, mat[3][2]);
        rotateMatrix.displayMatrix(mat);
    }
}<file_sep>/src/main/java/com/home/henry/QuickSortMiddlePivot.java
package com.home.henry;

public class QuickSortMiddlePivot {
    public static void qSort(int[] a, int head, int tail) {
        if (head >= tail || a == null || a.length <= 1) {
            return;
        }
        int i = head, j = tail, pivot = a[(head + tail) / 2];
        while (i <= j) {
            while (a[i] < pivot) {
                i++;
            }
            while (a[j] > pivot) {
                j--;
            }
            if (i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            } else if (i == j) {
                i++;
            }
        }
        qSort(a, head, j);
        qSort(a, i, tail);
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 1, 4, 8, 2, 55, 3, 6, 0, 11, 34, 90, 23, 54, 77, 9, 10 };
        qSort(arr, 0, arr.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int digit : arr) {
            sb.append(digit).append(" ");
        }
        System.out.println(sb.toString());
    }

}
<file_sep>/src/main/java/com/home/henry/SubSet.java
package com.home.henry;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Given a set of distinct integers, S, return all possible subsets.
 * Note: Elements in a subset must be in non-descending order.
 * The solution set must not contain duplicate subsets.
 * For example, If S = [1,2,3], a solution is:
 * [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
 */
public class SubSet {
    List<List<Integer>> getSublist(int[] nums) {
        // Init a list to receive results
        List<List<Integer>> results = new ArrayList<>();

        // Validate input
        if (null == nums || nums.length < 1) {
            return results;
        }

        // Sort nums
        Arrays.sort(nums);
        // Use recursion to get results
        List<Integer> subset = new ArrayList<>();
        recursion(subset, nums, 0, results);
        return results;
    }

    // Recursion part
    private void recursion(List<Integer> subset, int[] nums, int startIndex,
                           List<List<Integer>> results) {
        // Deep copy
        results.add(new ArrayList<>(subset));

        // for loop
        for (int j = startIndex; j < nums.length; j++) {
            // In for loop 1. add current point 2. exec recursion 3. restore current point
            subset.add(nums[j]);
            recursion(subset, nums, j + 1, results);
            subset.remove(subset.size() - 1);
        }
    }
}
<file_sep>/src/main/java/com/home/henry/BinarySearchSortedArray.java
package com.home.henry;

/**
 * 	Binary Search a sorted array
 */
public class BinarySearchSortedArray {

    public static int binarySearch(int[] a, int value) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] == value) {
                return mid;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    // Recursive	Way
    public static int binarySearchRecurive(int[] a, int low, int high, int value) {
        if (low > high || high > a.length - 1) {
            return -1;
        }
        int mid = low + (high - low) / 2;
        if (a[mid] == value) {
            return mid;
        }
        if (a[mid] < value) {
            return binarySearchRecurive(a, mid + 1, high, value);
        } else {
            return binarySearchRecurive(a, low, mid - 1, value);
        }
    }
}
<file_sep>/src/main/java/com/home/henry/CloneGraph.java
package com.home.henry;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * 给一个graph node, 每个node有list of neighbors. 复制整个graph, return new head node.
 * BFS solution
 * Use HashMap to mark cloned nodes.
 * 先能复制多少Node复制多少. 然后把neighbor 加上
 * Use `map<oldNode, newNode>` to mark visited
 */
class GraphNode {
    int value;
    List<GraphNode> neighbours;

    GraphNode(int value) {
        this.value = value;
        this.neighbours = new ArrayList<>();
    }
}

public class CloneGraph {
    public GraphNode cloneGraphNode(GraphNode node) {
        if (null == node) {
            return null;
        }
        Map<GraphNode, GraphNode> hm = new HashMap<>();
        hm.put(node, new GraphNode(node.value));
        Queue<GraphNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            GraphNode currentNode = queue.poll();
            for (GraphNode neighbor : currentNode.neighbours) {
                // Copy neighbors
                if (!hm.containsKey(neighbor)) {
                    queue.add(neighbor);
                    hm.put(neighbor, new GraphNode(neighbor.value));
                }
                hm.get(currentNode).neighbours.add(hm.get(neighbor));
            }
        }
        return hm.get(node);
    }
}
<file_sep>/src/main/java/com/home/henry/ListNode.java
package com.home.henry;

/**
 * Linked List Node
 */
public class ListNode {
    ListNode next;
    int data;

    ListNode() {}

    ListNode(int data) {
        this.data = data;
        this.next = null;
    }

    public static void printListNode(ListNode node) {
        while (node != null) {
            System.out.print(node.data);
            System.out.print("->");
            node = node.next;
        }
        System.out.println("null");
    }

    void appendToTail(int d) {
        ListNode end = new ListNode();
        end.data = d;
        ListNode n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }

    ListNode deleteNode(ListNode head, int d) {
        ListNode n = head;
        if (n.data == d) {
            return head.next;
        }
        while (n.next != null) {
            if (n.next.data == d) {
                n.next = n.next.next;
                return head;
            }
            n = n.next;
        }
        return head;
    }
}
<file_sep>/src/main/java/com/home/henry/InsertionSort.java
package com.home.henry;

/**
 * Insertion sort perform a bit better than bubble sort
 */
public class InsertionSort {
    private static boolean more(int v1, int v2) {
        return v1 > v2;
    }

    public static void sort(int[] a) {
        int size = a.length;
        int temp, j;
        for (int i = 1; i < size; i++) {
            temp = a[i];
            for (j = i; j > 0 && more(a[j - 1], temp); j--) {
                a[j] = a[j - 1];
            }
            a[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] a = { 9, 1, 8, 2, 7, 3, 6, 4, 5 };
        sort(a);
        for (int result : a) {
            System.out.println(result);
        }
    }
}
<file_sep>/src/main/java/com/home/henry/URLify.java
package com.home.henry;

/**
 * Write a method to replace all spaces in a string with '%20'. You may assume that the string
 * has sufficient space at the end to hold the additional characters,and that you are given the "true"
 * length of the string. (Note: If implementing in Java, please use a character array so that you can
 * perform this operation in place.)
 */
public class URLify {
    String urlFy(String source, int length) {
        if (null == source || source.length() < 1 || source.length() < length) {
            return "";
        }
        source = source.substring(0, length);
        int blankNum = 0;
        char[] chars = source.toCharArray();
        for (char aChar : chars) {
            if (aChar == ' ') {
                blankNum++;
            }
        }
        char[] charFinal = new char[length + blankNum * 2];
        for (int i = length - 1, j = length + blankNum * 2 - 1; i >= 0; i--) {
            char c = chars[i];
            if (c == ' ') {
                charFinal[j--] = '0';
                charFinal[j--] = '2';
                charFinal[j--] = '%';
            } else {
                charFinal[j--] = c;
            }
        }
        return String.valueOf(charFinal);
    }
}
<file_sep>/src/main/java/com/home/henry/FindMinInSortAndReversedArray.java
package com.home.henry;

public class FindMinInSortAndReversedArray {
    public static int findMin(int[] arr, int low, int high) {
        if (high < low) { return arr[0]; }

        // If there is only one element left
        if (high == low) { return arr[low]; }

        // Find mid
        int mid = low + (high - low) / 2;

        // Check if element (mid+1) is minimum element. Consider
        // the cases like {3, 4, 5, 1, 2}
        if (mid < high && arr[mid + 1] < arr[mid]) { return arr[mid + 1]; }

        // Check if mid itself is minimum element
        if (mid > low && arr[mid] < arr[mid - 1]) { return arr[mid]; }

        // Decide whether we need to go to left half or right half
        if (arr[high] > arr[mid]) { return findMin(arr, low, mid - 1); }
        return findMin(arr, mid + 1, high);

    }
}
<file_sep>/src/test/java/com/home/henry/StrStrTest.java
package com.home.henry;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * ALGORITHM  StrStrTest
 * Description: StrStrTest
 * Author: Henry
 * Created on 2018年02月24日
 */
class StrStrTest {

    @Test
    void getStrStrTest() {
        StrStr str = new StrStr();
        Assertions.assertEquals(0, str.getStrStr("a", "a"));
        Assertions.assertEquals(-1, str.getStrStr("", ""));
        Assertions.assertEquals(-1, str.getStrStr("", null));
        Assertions.assertEquals(-1, str.getStrStr("a", "c"));
        Assertions.assertEquals(-1, str.getStrStr("abcdef", "efc"));
        Assertions.assertEquals(-1, str.getStrStr("a", "ac"));
        Assertions.assertEquals(2, str.getStrStr("abcabc", "ca"));
        Assertions.assertEquals(4, str.getStrStr("abcdef", "ef"));
        Assertions.assertEquals(4, str.getStrStr("abcdefefef", "ef"));

        Assertions.assertEquals(0, str.getStrStrBetter("a", "a"));
        Assertions.assertEquals(-1, str.getStrStrBetter("", ""));
        Assertions.assertEquals(-1, str.getStrStrBetter("", null));
        Assertions.assertEquals(-1, str.getStrStrBetter("a", "c"));
        Assertions.assertEquals(-1, str.getStrStrBetter("abcdef", "efc"));
        Assertions.assertEquals(-1, str.getStrStrBetter("a", "ac"));
        Assertions.assertEquals(2, str.getStrStrBetter("abcabc", "ca"));
        Assertions.assertEquals(4, str.getStrStrBetter("abcdef", "ef"));
        Assertions.assertEquals(4, str.getStrStrBetter("abcdefefef", "ef"));
    }
}