演算法基礎提升學習1

語言: CN / TW / HK

一、並查集

題、

島嶼問題

【題目】 一個矩陣中只有0和1兩種值,每個位置都可以和自己的上、下、左、右 四個位置相連,如 果有一片1連在一起,這個部分叫做一個島,求一個矩陣中有多少個島?

【舉例】

001010

111010

100100

000000 這個矩陣中有三個島

進階

使用併發方式計算

答:採用並查集,將大的區域分塊,每個cpu計算一塊,然後考慮邊界問題進行合併。

合併:看邊界的被感染的點是由那個點導致的,記錄這個點。合併開始的時候將這些導致的點看做一個單獨的並查集元素。

​ 然後進行判斷,如果不是一個集合,就合併兩個點為一個集合,並且將島的數量-1,因為重複計算了一次。

​ 最後邊界的被感染的點都計算完畢後,剩餘的個數就是合併的島個數。

/**
 * @Author: 郜宇博
 */
public class IsLandProblem {
    public static void main(String[] args) {
        int[][] m1 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 1, 1, 0, 1, 1, 1, 0 },
                { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        int[][] m2 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 1, 1, 1, 1, 1, 1, 0 },
                { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 0, 1, 1, 0 },
                { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        System.out.println(isLandCount(m2));

    }
    public static int isLandCount(int[][]m){
        if (m.length==0||m==null){
            return 0;
        }
        return process(m);
    }
    public static int process(int[][]m){
        int row = m.length;
        int column = m[0].length;
        int res = 0;
        //遍歷集合
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (m[i][j] == 1){
                    res++;
                    infect(m,i,j,row,column);
                }

            }
        }
        return res;
    }

    /**
     * 遞迴
     * 感染
     * 將1的上下左右為1的,和上下左右的上下左右為1的。。。更改為2
     * 也就是連成一片的感染
     */
    private static void infect(int[][] m, int i, int j, int row, int column) {
        //不感染,越界的和不等於1的
        if (i <0||i >= row||j<0||j>=column ||m[i][j]!=1){
            return;
        }
        m[i][j] = 2;
        //上
        infect(m,i,j-1,row,column);
        //下
        infect(m,i,j+1,row,column);
        //上
        infect(m,i-1,j,row,column);
        //上
        infect(m,i+1,j,row,column);
    }

}

並查集

public class Code04_UnionFind {

	public static class Element<V> {
		public V value;

		public Element(V value) {
			this.value = value;
		}

	}

	public static class UnionFindSet<V> {
		public HashMap<V, Element<V>> elementMap;
		public HashMap<Element<V>, Element<V>> fatherMap;
		public HashMap<Element<V>, Integer> rankMap;

		public UnionFindSet(List<V> list) {
			elementMap = new HashMap<>();
			fatherMap = new HashMap<>();
			rankMap = new HashMap<>();
			for (V value : list) {
				Element<V> element = new Element<V>(value);
				elementMap.put(value, element);
				fatherMap.put(element, element);
				rankMap.put(element, 1);
			}
		}

		private Element<V> findHead(Element<V> element) {
			Stack<Element<V>> path = new Stack<>();
			while (element != fatherMap.get(element)) {
				path.push(element);
				element = fatherMap.get(element);
			}
			while (!path.isEmpty()) {
				fatherMap.put(path.pop(), element);
			}
			return element;
		}

		public boolean isSameSet(V a, V b) {
			if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
				return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
			}
			return false;
		}

		public void union(V a, V b) {
			if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
				Element<V> aF = findHead(elementMap.get(a));
				Element<V> bF = findHead(elementMap.get(b));
				if (aF != bF) {
					Element<V> big = rankMap.get(aF) >= rankMap.get(bF) ? aF : bF;
					Element<V> small = big == aF ? bF : aF;
					fatherMap.put(small, big);
					rankMap.put(big, rankMap.get(aF) + rankMap.get(bF));
					rankMap.remove(small);
				}
			}
		}

	}

}

二、KMP

/**
 * @Author: 郜宇博
 */
public class KMP {
    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
        System.out.println(getIndexOf(str,match));
    }
    /**
      步驟:
      開始str1,str2索引點為0,依次比較
      如果字母相等,那麼索引點都++
      如果字母不相等, 那麼將str2的索引更換為next[s2],此時s1不變,繼續依次比較。(相當於將str2向後推了)
      如果next[s2] = -1了,也就是str2不能再向後推了,就將s1向後移動一個,繼續比較。

     一直到s1,s2有一個越界位置
     如果s2最後的結果為str2的長度,說明都比較完事了,找到了子串,那麼s1-s2的就是開始索引位
     如果不是str2長度,說明找到最後也沒找到,返回-1
     */
    public static int getIndexOf(String str1,String str2){
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length()== 0){
            return -1;
        }
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        //str的索引位置
        int s1 = 0;
        int s2 = 0;
        //next陣列
        int[] next = getNextArray(str2);
        //沒有越界
        while (s1 < char1.length && s2 < char2.length){
            //相等
            if (char1[s1] == char2[s2]){
                //都向後一位
                s1++;
                s2++;
            }
            //不相等
            else {
                //str2推到頭了
                if (next[s2] == -1){
                    s1++;
                }
                //沒推到頭
                else {
                    //更新str2比較位置
                    s2 = next[s2];
                }
            }
        }
        //返回結果
        return s2 == char2.length? s1-s2:-1;
    }

    /**
     * next陣列獲取
     * next[0] = -1,next[1] = 0;
     * 原理: 想要獲取i索引位的next,next[i]
     *       那麼就需要將
     *          i-1上的字母
     *                和
     *          i-1位置的最長公共前後綴最後一個字母位置的 後一個位置
     *       比較
     *       也就是char[i-1] 和 char[ next[i-1] ] 比較
     *      1.如果相等,那麼char[i] = next[i-1]+1,因為多了一個i-1這個位置的字母
     *      2.不相等,繼續
     *                  和
     *               比較位置的字母(char[next[i-1]])的最長公共前後綴最後一個字母位置的後一個位置(next[char[next[i-1]]])字母( char[ next[char[next[i-1]]]]) 比較
     *        也就是char[i-1] 和   char[ next[char[next[i-1]]]]
     *      3.一直比下去,至到next[x] = -1,那麼next[i] = 0;
     */
    private static int[] getNextArray(String str2) {
        if (str2.length() == 1){
            return new int[]{-1};
        }
        int[] next =  new int[str2.length()];
        //規定
        next[0] = -1;
        next[1] = 0;
        //索引位,從2開始計算next陣列
        int i = 2;
        char[] char2 = str2.toCharArray();
        //i-1位置字母要比較的位置索引
        /*
            cn兩個含義:1.要比較的位置
                        2、i-1的最長公共前後綴的個數
         */
        int cn = next[i-1];
        while (i < next.length){
            //相等
            if (char2[i-1] == char2[cn]){
                //賦值
                next[i++] = ++cn;
            }
            //不相等
            else {
                //比較到了第一個,那麼i沒有最長公共前後綴
                if (cn == 0){
                    next[i++] = 0;
                }
                else {
                    //更新cn
                    cn = next[cn];
                }
            }
        }
        return next;
    }
}

三、Manacher演算法

/**
 * @Author: 郜宇博
 */
public class Manacher {
    public static void main(String[] args) {
        String str1 = "abc1234321ab";
        System.out.println(maxLcpsLength(str1));
    }

    /**
     * 最長迴文子串
     * 變數:c:導致R右擴的中心點,R:迴文右邊界 i:當前點, i':i關於c的對稱點
     *      p[]:可以忽略判斷的點個數
     * 分為兩種大情況
     * 1.i在R外,那麼就正常向兩邊擴(不確定迴文數)
     * 2.i在R內,有分為三種情況
     *      2.1。 當i'的迴文區域在[L,R]內,可以忽略的點個數為i'的迴文半徑(已經確定該點回文數)
     *      2.2。 當i'的迴文區域在[L,R]外,也就是超過了L,可以忽略的點個數為R-i(已經確定該點回文數)
     *      2.3.  當i'的迴文區域在[L,R]上,也就是壓線,可以忽略的點個數為R-i(不確定迴文數,需要判斷下一個位置)
     * 當走完陣列後,陣列內最大值就是最大的迴文半徑
     * 因為加入了特殊字元如:#1#2#2#1#
     * 所以迴文長度為 半徑-1
     *
     */
    public static int maxLcpsLength(String str){
        if (str == null || str.length() == 0) {
            return 0;
        }
        //新增特殊符號後的陣列
        char[] charArr = manacherString(str);
        //半徑長度(包括自己)
        int[] pArr = new int[charArr.length];
        int max = Integer.MIN_VALUE;
        //導致右邊界的中心點
        int center = -1;
        //右邊界
        int right = -1;
        for (int i = 0; i < charArr.length; i++) {
            //半徑長度, 也就是獲取可以忽略的點數+1
            pArr[i] = right > i ? Math.min(pArr[2*center-i],right-i):1;
            //雖然有的情況已經確定了迴文數,但是為了減少程式碼量,因此統一一個擴張介面。
            while (i + pArr[i] <charArr.length && i-pArr[i] >= 0){
                //判斷兩邊是否相等
                if (charArr[i + pArr[i] ] == charArr[i-pArr[i] ]){
                    pArr[i]++;
                }
                else {
                    break;
                }
            }
            //擴張後,檢視是否超過了R,超過則更新,並儲存c
            if (i + pArr[i] > right){
                right = i + pArr[i];
                center = i;
            }
            //更新max值
            max = Math.max(max,pArr[i]);
        }
        System.out.println(Arrays.toString(pArr));
        return max-1;

    }

    private static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }
}

四、棧的單調性

定義:陣列中累積和與最小值的乘積,假設叫做指標A。 給定一個數組,請返回子陣列中,指標A最大的值。

/**
 * @Author: 郜宇博
 */
public class AllTimesMinToMax {
    public static void main(String[] args) {
        int[] arr = new int[]{5,7,6,3,2,8};
        System.out.println(max(arr));
    }
    /**
     * 計算指標A,要求出 累加和與最小值乘積的最大值
     * 假定陣列內每個數都是當前子陣列的最小值,因為這樣才可以鎖定一個變數
     * 要滿足這個條件(當前子陣列的最小值)就需要子陣列不能包括比這個數小的數,
     * 因此左邊界是左邊比這個數小的值,右邊界是右邊比這個數小的值。這個邊界內的累加和肯定是滿足這個條件,帶著當前數的最大和。因此乘積A也是最大。
     * 計算出所有數的指標A,在得出最大的A,就是最後的A
     * 此時就需要 棧的單調性
     * 步驟:
     *  準備棧結構(儲存下標),棧頂元素永遠大於棧低元素,保證計算區域時都是大於該值的值的區域,
     *  也就是當出現小於當前數的時候,就開始處理當前數了,此時棧頂元素彈出,因為第i個數是小於當前數的,所以i-1位置的數一定大於當前數,所以區域的最右邊界就是i-1
     *  左邊界就是彈出棧頂元素後,棧頂元素,也就是第最後一個小於當前數的元素,記為peak,所以當前數按照之前的方式計算的P=sum[i-1]-sum[peak]
     *  彈出後
     *  當棧內沒有元素時,P 直接等於sum[i-1],因為沒有小於當前數的了
     *
     *  此時後續加入的元素如果一直大於前一個數的話,就需要第二個步驟了,因為一直沒有小於的數讓棧內元素彈出。
     *  依次彈出棧頂元素,此時右邊沒有比當前元素小的了,也就是沒有右邊界了,左邊界就是彈出後的棧頂peak
     *  所以P = sum[size -1 ]-sum[peak]
     *
     */
    public static int max(int[] arr) {
        //用來儲存索引
        Stack<Integer> stack = new Stack<>();
        //當前位置
        int i;
        //累加和
        int[] sum = new int[arr.length];
        sum[0] = arr[0];
        //求出累加和
        for (i = 1; i < arr.length; i++) {
            sum[i] = sum[i-1]+arr[i];
        }
        //最大值
        int max = Integer.MIN_VALUE;
        //指標
        int P = max;
        //求每個元素的P
        for (i = 0; i < arr.length; i++) {
            //保持加入的永遠大於棧頂
            while (!stack.isEmpty() && arr[i] <= arr[stack.peek()] ){
                //處理彈出元素,也就是計算P
                int pop = stack.pop();
                //彈完判空,計算P
                P =  (stack.isEmpty()? sum[i -1]:sum[i-1]-sum[stack.peek()]) * arr[pop];
                //更新max
                max = Math.max(max,P);
            }
            //向棧中加入元素
            stack.push(i);
        }
        //此時剩下的都是遞增的
        while (!stack.isEmpty()){
            int pop = stack.pop();
            //彈完判空,計算P
            P = (stack.isEmpty()? sum[arr.length -1]:sum[arr.length-1]-sum[stack.peek()]) * arr[pop];
            //更新max
            max = Math.max(max,P);
        }
        return max;
    }
}