一、大樓輪廓（有序表）

給定一個 N×3 的矩陣 matrix，對于每一個長度為 3 的小陣列 arr，都表示一個大樓的三個數據，

arr[0]表示大樓的左邊界，arr[1]表示大樓的右邊界，arr[2]表示大樓的高度(一定大于 0)，

每座大樓的地基都在 X 軸上，大樓之間可能會有重疊，請回傳整體的輪廓線陣列，
【舉例】

matrix = { {2,5,6}, {1,7,4}, {4,6,7}, {3,6,5}, {10,13,2}, {9,11,3}, {12,14,4}, {10,12,5} }
回傳：

{{1,2,4}, {2,4,6}, {4,6,7}, {6,7,4}, {9,10,3}, {10,12,5},{12,14,4}}

/**
 * @Author: 郜宇博 
 */
public class BuildingBorder {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {2,7,3},
                {3,5,5},
                {4,6,4}
        };
        List<List<Integer>> buildingBorder = getBuildingBorder(matrix);
        System.out.println(buildingBorder);
    }
    /**
     * 用于記錄高度變化
     */
    public static class Node{
        public int index;
        public boolean isAdd;
        public int height;
        public Node(int index, boolean isAdd, int height) {
            this.index = index;
            this.isAdd = isAdd;
            this.height = height;
        }
    }
    public static List<List<Integer>> getBuildingBorder(int[][] matrix){
        Node[] nodes = getHeightUpDown(matrix);
        //構造兩個有序表
        //坐標-高度表
        TreeMap<Integer,Integer> indexHeightMap = new TreeMap<>();
        //高度-次數表
        TreeMap<Integer,Integer> heightTimesMap = new TreeMap<>();
        fillMap(indexHeightMap,heightTimesMap,nodes);
        //回傳結果
        return getBorder(indexHeightMap);
    }
    public static List<List<Integer>> getBorder(TreeMap<Integer,Integer> indexHeightMap){
        List<List<Integer>> res = new ArrayList<>();
        int start = indexHeightMap.firstKey();
        int preHeight = indexHeightMap.get(start);
        for (Map.Entry<Integer,Integer> entry: indexHeightMap.entrySet()){
            //如果高度發生變化
            if (entry.getValue() != preHeight){
                //添加（start,curKey,preHeight）
                List<Integer> border= null;
                if (preHeight != 0){
                    border = new ArrayList<>(Arrays.asList(start,entry.getKey(),preHeight));
                    res.add(border);
                }
                //新的list，起始點，高度都變了
                start = entry.getKey();
                preHeight = entry.getValue();
            }
        }
        return res;
    }
    /**
     * 填充map表
     */
    public static void fillMap(TreeMap<Integer,Integer> indexHeightMap,TreeMap<Integer,Integer> heightTimesMap,Node[] nodes){
        for (Node node: nodes){
            //是否為添加
            if (node.isAdd){
                //1.處理heightTimesMap
                //添加過，次數+1
                if (heightTimesMap.containsKey(node.height)){
                    heightTimesMap.put(node.height,heightTimesMap.get(node.height)+1);
                }else {
                    //沒添加guo
                    heightTimesMap.put(node.height,1);
                }
            }else {
                //下降
                if (heightTimesMap.get(node.height)==1){
                    //洗掉后為0，則移除
                    heightTimesMap.remove(node.height);
                }else {
                    heightTimesMap.put(node.height,heightTimesMap.get(node.height)-1);
                }
            }
            //2.處理indexHeightMap
            //沒有高度了，到結尾了
            //獲取最大高度
            Integer maxHeight =  heightTimesMap.isEmpty()?0:heightTimesMap.lastKey();
            indexHeightMap.put(node.index,maxHeight);
        }
    }
    /**
     * 獲取高度變化的陣列,回傳排序后的結果
     */
    public static Node[] getHeightUpDown(int[][] matrix){
        Node[] resultNode = new Node[matrix.length * 2];
        for (int i  = 0; i < matrix.length; i++){
            for (int j = 0; j < matrix[0].length ; j++){
                resultNode[i * 2] = new Node(matrix[i][0],true,matrix[i][2]);
                resultNode[i * 2+1] = new Node(matrix[i][1],false,matrix[i][2]);
            }
        }
        //按照index大小排序，相同的話根據add在前，排序，防止出現線狀樓
        Arrays.sort(resultNode,(x,y)->{
            if (x.index != y.index){
                return x.index - y.index;
            }
            if (x.isAdd != y.isAdd){
                return x.isAdd?-1:1;
            }
            return 0;
        });
        return resultNode;
    }
}

二、最長子陣列等于k(構造單調性、滑動視窗)

給定一個陣列 arr，該陣列無序，但每個值均為正數，再給定一個正數 k，

求 arr 的所有子陣列中所有元素相加和為 k 的最長子陣列長度，

例如，arr=[1,2,1,1,1]，k=3，

累加和為 3 的最長子陣列為[1,1,1]，所以結果回傳 3，
要求：時間復雜度O(N)，額外空間復雜度O(1)

/**
 * @Author: 郜宇博
 * 給定一個陣列 arr，該陣列無序，但每個值均為正數，再給定一個正數 k，
 * 求 arr 的 所有子 陣列中所有元素相加和為 k 的最長子陣列長度，
 */
public class LongestChildArraySumK {
    public static void main(String[] args) {
        int len = 30;
        int k = 15;
        int[] arr = generatePositiveArray(len);
        System.out.println(getLongestCount(arr, k));
    }

    /**
     * 構造單調性，因為陣列都是正數，保持一個區間，
     * 當區間內sum < k時，繼續擴充區間
     * 當區間sum = k 時，以i為起點，此區間最大了，更換區間，r++, l++
     * 當sum > k時，如果l,r在同一位置，都向后移動，不在的話，left++,縮小區域
     */
    public static int getLongestCount(int[] array, int target){
        int left = 0;
        int right = 0;
        // sum =  [left,...,right]
        int sum = array[0];
        int result = Integer.MIN_VALUE;
        while (right != array.length){
            //sum = array[right];
            if (sum == target){
                result = Math.max(result, right - left + 1);
                if (right == array.length-1){
                    return Math.max(result, 0);
                }
                sum = sum - array[left++] + array[++right];
            }
            else if (sum < target){
                if (right == array.length-1){
                    return Math.max(result, 0);
                }
                sum += array[++right];
            }else {
                if (left == right){
                    sum = array[++left];
                    right++;
                }else {
                    sum -= array[left++];
                }
            }
        }
        return Math.max(result, 0);
    }
    public static int[] generatePositiveArray(int size) {
        int[] result = new int[size];
        for (int i = 0; i != size; i++) {
            result[i] = (int) (Math.random() * 10) + 1;
        }
        return result;
    }
}

三、拿硬幣

給定一個非負陣列，每一個值代表該位置上有幾個銅板，

a和b玩游戲，a先手，b后手，輪到某個人的時候，只能在一個位置上拿任意數量的銅板，但是不能不拿，

誰最先把銅板拿完誰贏，假設a和b都極度聰明，請回傳獲勝者的名字，

/**
 * @Author: 郜宇博
 * 給定一個非負陣列，每一個值代表該位置上有幾個銅板，
 * a和b玩游戲，a先手，b后手， 輪到某個人的時候，只能在一個位置上拿任意數量的銅板，但是不能不拿，
 * 誰最先把銅板拿完誰贏，假設a和b都極度聰明，請回傳獲勝者的名字，
 */
public class PickMoneyWin {
    public static void main(String[] args) {
        int[] array = new int[]{3,4,1};
        System.out.println(getWinner(array));
    }
    /**
     * 最后桌子上剩下1個硬幣時，先手贏，否則后手贏
     * 將所有數字求異或和，為0說明先手怎么都贏不了
     */
    public static String getWinner(int[] array){
        int eorResult = 0;
        for (int num: array){
            eorResult ^= num;
        }
        return eorResult==0?"后手":"先手";
    }
}

四、最長子陣列小于等于k（舍去部分解）

給定一個無序陣列 arr，其中元素可正、可負、可 0，給定一個整數 k，

求 arr 所有的子陣列中累加和小于或等于 k 的最長子陣列長度，

例如:arr=[3,-2,-4,0,6]，k=-2，相加和小于或等于-2 的最長子陣列為{3,-2,-4,0}，所以結果回傳4，

/**
 * @Author: 郜宇博
 * 給定一個無序陣列 arr，其中元素可正、可負、可0，給定一個整數k，
 * 求arr 所有的子陣列累加和小于或等于k的最長子陣列長度，
 */
public class LongestChildArraySumLessK {
    public static void main(String[] args) {
        int[] array = new int[]{3,-2,-4,0,6};
        System.out.println(getSumLessK(array,-2));
    }
    public static int getSumLessK(int[] array, int target) {
        //準備兩個陣列
        //1.以i開始，向后最小sum
        //2.到達最小sum的邊界坐標
        int[] minSum = new int[array.length];
        int[] minBorder = new int[array.length];
        minSum[array.length - 1] = array[array.length - 1];
        minBorder[array.length - 1] = array.length - 1;
        for (int i = array.length - 2; i >= 0; i--) {
            minSum[i] = array[i];
            minBorder[i] = i;
            //如果右邊的最小和<0，那么應該向右拓展
            if (minSum[i + 1] <= 0) {
                minSum[i] += minSum[i + 1];
                minBorder[i] = minBorder[i + 1];
            }
        }
        int left = 0;
        int right = 0;
        int result = 0;
        int curSum = 0;
        for (; array.length - left > result; left++) {
            //不越界，并且滿足條件
            while (right < array.length && minSum[right] + curSum <= target) {
                //更新curSum
                curSum += minSum[right];
                right = minBorder[right] + 1;
            }
            //找到了以left為左邊界最長滿足條件的陣列，更新
            result = Math.max(result,right - left);
            //邊界整體向右移動(!重點)
            if (left == right){
                right++;
            }else {
                curSum -= array[left];
            }
        }
        return result;
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/378100.html

標籤：Java

上一篇：Spring Boot 分層打包 Docker 鏡像實踐及分析

下一篇：利用python爬取城市公交站點

演算法高級學習1

一、大樓輪廓（有序表）

二、最長子陣列等于k(構造單調性、滑動視窗)

三、拿硬幣

四、最長子陣列小于等于k（舍去部分解）