面試算法代碼知識梳理系列

面試算法知識梳理(1) - 排序算法
面試算法知識梳理(2) - 字符串算法第一部分
面試算法知識梳理(3) - 字符串算法第二部分
面試算法知識梳理(4) - 數(shù)組第一部分
面試算法知識梳理(5) - 數(shù)組第二部分
面試算法知識梳理(6) - 數(shù)組第三部分
面試算法知識梳理(7) - 數(shù)組第四部分
面試算法知識梳理(8) - 二分查找算法及其變型
面試算法知識梳理(9) - 鏈表算法第一部分
面試算法知識梳理(10) - 二叉查找樹
面試算法知識梳理(11) - 二叉樹算法第一部分
面試算法知識梳理(12) - 二叉樹算法第二部分
面試算法知識梳理(13) - 二叉樹算法第三部分

一森篷、概要

本文介紹了有關(guān)數(shù)組的算法第四部分的Java代碼實現(xiàn)兼吓，所有代碼均可通過 在線編譯器 直接運行，算法目錄：

• 求數(shù)組當中的最長遞增子序列（求數(shù)組當中的最長遞減子序列）
• 區(qū)間重合判斷
• 一個整數(shù)數(shù)組步绸，長度為n尝丐，將其分為m份显拜，使各份的和相等，求m的最大值

二爹袁、代碼實現(xiàn)

2.1 求數(shù)組當中的最長遞增子序列

代碼實現(xiàn)

class Untitled {
    
    //查找最長遞增子序列远荠。
    static void searchMaxIncSubArray(int p[], int length) {
        //maxValue[i]表示長度為i的遞增子序列的最大元素的最小值。
        int[] maxValue = new int[length+1];
        maxValue[1] = p[0];
        int k=1;
        for (int i=1; i<length; i++) {
            if (p[i] > maxValue[k]) {
                k++;
                maxValue[k] = p[i];
            } else if (p[i] == maxValue[k]) { //如果p[i]和maxValue[k]失息，那么越過譬淳。
                continue;
            } else { //如果p[i]小于maxValue[k]档址。
                if (p[i] < maxValue[1]) {
                    maxValue[1] = p[i];
                    continue;
                }
                int first = 1;
                int last = k;
                //二分查找：目的是在maxValue數(shù)組中找到大于p[i]的第一個元素，如果它大于p[i]邻梆，那么就替換它守伸。
                while (first < last) {
                    int mid = (last-first) >> 1;
                    if (maxValue[first+mid] < p[i]) {
                        first=first+mid+1;
                    } else if (maxValue[first+mid] > p[i]) {
                        last=first+mid;
                    } else {
                        first=first+mid+1;
                    }
                }
                //進行替換。
                if (p[i] < maxValue[first]) {
                    p[i] = maxValue[first];
                }
            }
        }
        System.out.println("k=" + k);
    }
    
    
    public static void main(String[] args) {
        int[] p = {1,2,31,4,20,-7,8};
        searchMaxIncSubArray(p, p.length);
    }
}

運行結(jié)果

>> k=3

2.2 區(qū)間重合判斷

代碼實現(xiàn)

class Untitled {

    static class Area {

        int start;
        int end;

        Area(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    //首先對區(qū)間進行排序浦妄，按照start進行遞增排序尼摹。
    static void sortArea(Area areas[], int start, int end) {
        if (start==end) {
            return;
        }
        int mid = start;
        Area midValue = areas[start];
        for (int i=start+1; i<=end; i++) {
            Area data = areas[i];
            if (data.start < midValue.start) {
                mid++;
                areas[i] = areas[mid];
                areas[mid] = data;
            }
        }
        Area temp = areas[mid];
        areas[mid] = areas[start];
        areas[start] = temp;
        if (mid > start) {
            sortArea(areas, start, mid-1);
        }
        if (mid < end) {
            sortArea(areas, mid+1, end);
        }
    }
    
    //合并區(qū)間，使得兩個區(qū)間之間互不重合剂娄。
    static int mergeArea(Area areas[], int len) {
        int lastIndex = 0;
        Area lastArea = areas[0];
        for (int i=1; i<len; i++) {
            Area cur = areas[i];
            if (cur.start <= lastArea.end) {
                if (cur.end > lastArea.end) {
                    lastArea.end = cur.end;
                    areas[lastIndex] = lastArea;
                }
            } else {
                lastArea = cur;
                lastIndex++;
                areas[lastIndex] = lastArea;
            }
        }
        return lastIndex+1;
    }
    
    //通過二分查找蠢涝，確定目標區(qū)間是否在其范圍之內(nèi)。
    static boolean searchArea(Area areas[], int areasLen, Area target) {
        int startIndex = 0;
        int endIndex = areasLen-1;
        while (startIndex <= endIndex) {
            int mid = (startIndex+endIndex) >> 1;
            Area midValue = areas[mid];
            if (target.start < midValue.start) {
                if (target.end > midValue.end) {
                    return false;
                } else {
                    endIndex=mid-1;
                }
            } else if (target.start >= midValue.start && target.start <= midValue.end) {
                if (target.end <= midValue.end) {
                    return true;
                } else {
                    return false;
                }
            } else {
                startIndex = mid+1;
            }
        }
        return false;
    }
    
    static void printArea(Area areas[], int len) {
        for (int i=0; i<len; i++) {
            Area area = areas[i];
            System.out.println("start=" + area.start + ",end=" + area.end);
        }
    }
    
    public static void main(String[] args) {
        Area areas[] = new Area[] {
                new Area(1, 3),
                new Area(5, 9),
                new Area(2, 4),
                new Area(10, 11),
        };
        sortArea(areas, 0, areas.length-1);
        System.out.println("- 排序結(jié)果 -");
        printArea(areas, areas.length);
        int mergeLen = mergeArea(areas, areas.length);
        System.out.println("- 合并結(jié)果 -");
        printArea(areas, mergeLen);
        Area target = new Area(3, 4);
        System.out.println("處于區(qū)間內(nèi)=" + searchArea(areas, mergeLen, target));
    }
}

運行結(jié)果

>> - 排序結(jié)果 -
>> start=1,end=3
>> start=2,end=4
>> start=5,end=9
>> start=10,end=11
>> - 合并結(jié)果 -
>> start=1,end=4
>> start=5,end=9
>> start=10,end=11
>> 處于區(qū)間內(nèi)=true

2.3 一個整數(shù)數(shù)組阅懦，長度為 n和二，將其分為 m 份，使各份的和相等耳胎，求 m 的最大值

代碼實現(xiàn)

class Untitled {

    static Boolean testGroup(int p[], int aux[], int pLen, int groupLen, int curSum, int groupSum, int groupID){
        if (curSum < 0)
            return false;
        if (curSum == 0){
            groupID++;
            curSum = groupSum;
            if (groupID == groupLen+1) {
                return true;
            }
        }
        for (int i=0; i<pLen; i++){
            if (aux[i] != 0) {
                continue;
            }
            aux[i] = groupID;
            if (testGroup(p, aux, pLen, groupLen, curSum-p[i], groupSum, groupID)) {
                return true;
            }
            aux[i] = 0;
        }
        return false;
    }


    static void maxGroup(int p[], int len) {
        int aux[] = new int[len];
        int sum = 0;
        for (int i=0; i<len; i++) {
            aux[i] = 0;
            sum += p[i];
        }
        for (int m=len; m>=2; m--) {
            if (sum%m != 0) {
                continue;
            }
            if (testGroup(p, aux, len, m, sum/m, sum/m, 1)) {
                System.out.println("m=" + m);
                for (int i=0; i<len; i++) {
                    System.out.println("aux[" + i + "]=" + aux[i]);
                }
            }
        }
    }
    public static void main(String[] args) {
        int a[] = {3,2,4,3,6};
        maxGroup(a, a.length);
    }
}

運行結(jié)果

>> m=3
>> aux[0]=1
>> aux[1]=2
>> aux[2]=2
>> aux[3]=1
>> aux[4]=3

更多文章惯吕，歡迎訪問我的 Android 知識梳理系列：

• Android 知識梳理目錄：http://www.reibang.com/p/fd82d18994ce
• Android 面試文檔分享：http://www.reibang.com/p/8456fe6b27c4