分类目录归档:算法类

KMP算法

public int indexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < 1 || s.length() < m.length())
            return -1;
        char[] ss = s.toCharArray();
        char[] ms = m.toCharArray();
        int si = 0, mi = 0;
        int[] next = nextIndex(ms);
        while (si < ss.length && mi < ms.length) {
            if (mi == -1 || ss[si] == ms[mi]) {
                si++;
                mi++;
            } else {
                mi = next[mi];
            }
        }
        return mi == ms.length ? si - mi : -1;
    }

    public int[] nextIndex(char[] str) {
        if (str.length == 1)
            return new int[]{-1};
        int[] next = new int[str.length];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < next.length) {
            if (str[pos - 1] == str[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
        return next;
    }

 

鸡蛋掉落问题

一、暴力递归法

首先,我们来看扔鸡蛋这个事儿本身,假设在N层的高楼中有K个鸡蛋,这个时候我们在n层扔了一个鸡蛋,那么这一次动作,把整个高楼其实就分成了两部分,一部分是1楼到n楼,这是一个层高为n的新楼,我们暂时叫它一号楼;另一部分是n+1N楼,这是一栋新产生的层高为N-(n+1)+1=N-n的新楼,我们叫他二号楼。

继续阅读

Java并查集问题

并查集是一种数据结构, 常用于描述集合,经常用于解决此类问题:某个元素是否属于某个集合,或者 某个元素 和 另一个元素是否同属于一个集合。可以用于点的分堆、判断点的互相可达性。

/**
 * @Author: Sumail-Lee
 * @Date: 2019/1/4 15:57
 * @Description: 将一个集合内的点分堆,每个分好堆的点内都互相可达,公用同一个爹
 */
public class 并查集 {
    private int[] parent;
    private int size;

    public 并查集(int size) {
        this.size = size;
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    public int findParent(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }

    public boolean isConnected(int firstElement, int secondElement) {
        return findParent(firstElement) == findParent(secondElement);
    }

    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = findParent(firstElement);
        int secondRoot = findParent(secondElement);
        if (firstRoot == secondRoot) {
            return;
        }
        parent[firstRoot] = secondRoot;
    }
}

 

动态规划解最长公共子序列及最长公共字串问题

【问题】 求两字符序列的最长公共字符子序列

问题描述:

字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列<i0,i1,…,ik-1>,使得对所有的j=0,1,…,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。

继续阅读