二分查找

    private static int binarySearch(int a[], int target) {
        if (a == null || a.length == 0) return -1;
        int left = 0, right = a.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (a[mid] == target) return mid;
            else if (a[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }

KMP

    private static int[] getNext(char[] pattern) {
        int[] next = new int[pattern.length + 1];
        int i = 0, j = -1, len = pattern.length;
        next[0] = -1;
        while (i < len) {
            if (j == -1 || pattern[i] == pattern[j]) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    private static int kmp(char[] text, char[] pattern) {
        if (text == null || text.length == 0
                || pattern == null || pattern.length == 0) return -1;
        int[] next = getNext(pattern);
        int i = 0, j = 0, len1 = text.length, len2 = pattern.length;
        while (i < len1 && j < len2) {
            if (j == -1 || text[i] == pattern[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
            if (j == len2) {
                // 返回出现模式串位置
                return i - len2 + 1;
                // 统计出现的次数
                // j=next[j];
                // ans++;
            }
        }
        return -1;
    }

堆排序

    private static void swap(int a[], int x, int y) {
        int tmp = a[x];
        a[x] = a[y];
        a[y] = tmp;
    }

    private static void sift(int a[], int root, int hight) {
        if (root >= hight) return;
        int left = root * 2, right = left + 1;
        if (left < hight && a[root] < a[left]) {
            swap(a, root, left);
            sift(a, left, hight);
        }
        if (right < hight && a[root] < a[right]) {
            swap(a, root, right);
            sift(a, right, hight);
        }
    }

    private static void heapSort(int a[]) {
        if (a == null || a.length == 0) return;
        // init
        int b[] = new int[a.length + 1];
        for (int i = 1, len = b.length; i < len; i++) {
            b[i] = a[i - 1];
        }
        // build max heap
        for (int i = b.length / 2; i >= 1; i--) {
            sift(b, i, b.length);
        }
        // sort
        for (int i = 1, len = b.length; i < len; i++) {
            swap(b, 1, len - i);
            a[i-1] = b[len - i];
            sift(b, 1, len - i);
        }
    }

快速排序

    private static void swap(int a[], int x, int y) {
        int tmp = a[x];
        a[x] = a[y];
        a[y] = tmp;
    }

    private static void quickSort(int[] a) {
        if (a == null || a.length == 0) return;
        quickSort(a, 0, a.length - 1);
    }

    private static void quickSort(int[] a, int left, int right) {
        if (left < right) {
            int i = left, j = right;
            int key = a[left];
            while (i < j) {
                while (i < j && a[j] >= key) {
                    j--;
                }
                if (i < j) {
                    swap(a, i, j);
                    i++;
                }
                while (i < j && a[i] <= key) {
                    i++;
                }
                if (i < j) {
                    swap(a, i, j);
                    j--;
                }
            }
            a[i] = key;
            quickSort(a, left, i - 1);
            quickSort(a, i + 1, right);
        }
    }

    private void quickSort(int a[]) {
        if (a == null || a.length == 0) return;
        quickSort(a, 0, a.length - 1);
    }

快速排序非递归版

    private static void swap(int a[], int x, int y) {
        int tmp = a[x];
        a[x] = a[y];
        a[y] = tmp;
    }

    private static int quickSort(int[] a, int left, int right) {
        int i = left, j = right;
        int key = a[left];
        while (i < j) {
            while (i < j && a[j] >= key) {
                j--;
            }
            if (i < j) {
                swap(a, i, j);
                i++;
            }
            while (i < j && a[i] <= key) {
                i++;
            }
            if (i < j) {
                swap(a, i, j);
                j--;
            }
        }
        a[i] = key;
        return i;
    }

    private static class Status {
        int left, right;

        public Status(int left, int right) {
            this.left = left;
            this.right = right;
        }

        public int getLeft() {
            return left;
        }

        public int getRight() {
            return right;
        }
    }

    private static void quickSort(int a[]) {
        if (a == null || a.length == 0) return;
        Stack<Status> stack = new Stack<>();
        int left = 0, right = a.length - 1;
        stack.push(new Status(left, right));
        while (!stack.empty()) {
            Status currStatus = stack.pop();
            int partitionPos = -1;
            if (currStatus.getLeft() >= currStatus.getRight()) continue;
            partitionPos = quickSort(a, currStatus.getLeft(), currStatus.getRight());
            if (partitionPos == -1) continue;
            if (currStatus.getLeft() < partitionPos - 1) {
                stack.push(new Status(currStatus.getLeft(), partitionPos - 1));
            }
            if (partitionPos + 1 < currStatus.getRight()) {
                stack.push(new Status(partitionPos + 1, currStatus.getRight()));
            }
        }
    }

Dijkstra

    private static int Dijkstra(int map[][], int start, int end) {
        if (map == null || map.length == 0 || map[0].length == 0) return -1;
        int dis[] = new int[map.length];
        boolean vis[] = new boolean[map.length];
        for (int i = 0, len = map.length; i < len; i++) {
            dis[i] = map[start][i];
            vis[i] = false;
        }
        for (int i = 0, len = map.length; i < len - 1; i++) {
            int minx = Integer.MAX_VALUE, k = -1;
            for (int j = 0; j < len; j++) {
                if (!vis[j] && dis[j] < minx) {
                    minx = dis[j];
                    k = j;
                }
            }
            if (k == -1) return -1;
            else {
                vis[k] = true;
                for (int j = 0; j < len; j++) {
                    if (!vis[j] && dis[j] < dis[k] + map[k][j]) {
                        dis[j] = dis[k] + map[k][j];
                    }
                }
            }
        }
        return dis[end] == Integer.MAX_VALUE ? -1 : dis[end];
    }

Floyd

     private static int Floyd(int map[][], int start, int end) {
        if (map == null || map.length == 0 || map[0].length == 0) return -1;
        int dp[][] = new int[map.length][map[0].length];
        for (int i = 0, len = map.length; i < len; i++) {
            for (int j = i; j < len; j++) {
                dp[i][j] = map[i][j] == -1 ? Integer.MAX_VALUE : map[i][j];
            }
        }
        for (int k = 0, len = map.length; k < len; k++) {
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp[start][end];
    }

最长公共子序列

    private static int LCS(String a, String b) {
        if (a == null || b == null || "".equals(a) || "".equals(b)) return -1;
        int dp[][] = new int[a.length()][b.length()];
        for (int i = 1, lena = a.length(); i <= lena; i++) {
            for (int j = 1, lenb = b.length(); j <= lenb; j++) {
                char cha = a.charAt(i - 1);
                char chb = b.charAt(j - 1);
                if (cha == chb) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[a.length()][b.length()];
    }

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        // write code here
        int dp[][] = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }
}

最小编辑距离

    private static int Levenshtein(String a, String b) {
        if (a == null || b == null || "".equals(a) || "".equals(b)) return -1;
        int dp[][] = new int[a.length()][b.length()];
        for (int i = 0, lena = a.length(); i < lena; i++) {
            dp[i][0] = i;
        }
        for (int i = 0, lenb = b.length(); i < lenb; i++) {
            dp[0][i] = i;
        }
        for (int i = 1, lena = a.length(); i <= lena; i++) {
            for (int j = 1, lenb = b.length(); j <= lenb; j++) {
                char cha = a.charAt(i - 1);
                char chb = b.charAt(j - 1);
                int cost = 1;
                if (cha == chb) {
                    cost = 0;
                }
                dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + cost);
            }
        }
        return dp[a.length()][b.length()];
    }

最长回文子串

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        boolean isPalindrome[][] = new boolean[n][n];
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            isPalindrome[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                if (j == i + 1) {
                    isPalindrome[i][j] = A.charAt(i) == A.charAt(j);
                } else {
                    isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && A.charAt(i) == A.charAt(j);
                }
                if (isPalindrome[i][j]) {
                    ans = Math.max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
}

最长递增子序列

    private static int solve(int a[]) {
        int dp[] = new int[a.length];
        for (int i = 0, len = a.length; i < len; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (a[j] < a[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 0, len = a.length; i < len; i++) {
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }