[Leetcode] 搜索 二叉查找树 堆 二分查找 etc.

satjd

2018/12/02

Categories: Algorithm 基础知识 Tags: leetcode

480. Sliding Window Median

class Solution {
    /**
     * 解法1:
     * 使用两个堆进行记录,左侧堆为大根堆,用于记录数组左半部分的最大值
     * 右侧堆为小根堆,记录数组右半部分的最小值
     * 那么,只要两个堆中的元素是相等的,那么中位数就是两个堆的根的平均值
     * 或者某个堆比另一个堆size大1,那么size大的那个堆的根就是所求的中位数
     * 那么,不妨保持左侧堆比右侧堆size大1或相等,每次扫描到一个新元素需要加入堆时:
     * 1.先判断加入哪个堆
     * 2.加入对应堆后平衡两个堆,让两个堆的size保持大1或相等的关系
     * 插入堆复杂度:O(log k),插入次数O(n),每次平衡O(1),所以总的时间复杂度:O(n*log k)
     * 
     * 解法2:
     * 保持窗口内元素有序,每次插入新元素后进行二分,找到新元素的对应位置,然后根据新元素和原来窗口中中位数的前后关系,
     * 来判断新的中位数。
     * 每次二分搜索:O(log k)
     * 扫描一遍:O(n)
     * 所以总的时间复杂度:O(n*log k)
     *  */
    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] ret = new double[nums.length - k + 1];
        
        PriorityQueue<Integer> left = new PriorityQueue<>(nums.length, Collections.reverseOrder());
        PriorityQueue<Integer> right = new PriorityQueue<>(nums.length);
        
        boolean isWindowFull = false;
        int resIndex = 0;
        for (int i=0; i < nums.length; i++) {
            if (i == k - 1) {
                isWindowFull = true;
            }
            if (right.size() > 0 && nums[i] >= right.peek()) {
                right.add(nums[i]);
            } else {
                left.add(nums[i]);
            }
            // 每次插入新元素之后进行平衡
            rebalance(left,right);
            
            if (isWindowFull) {
                if ((k & 1) == 1) {
                    ret[resIndex] = (double)left.peek();
                } else {
                    ret[resIndex] = ((double)left.peek() + (double)right.peek()) / 2.0;
                }
                
                if (left.remove(nums[resIndex]) == false) {
                    right.remove(nums[resIndex]);
                }
                resIndex++;
            }
        }
        
        return ret;
    }
    
    // 平衡的时候从大根堆取出,放入小根堆
    private void rebalance(Queue left, Queue right) {
        while (true) {
           if (left.size() - 1 > right.size()) {
                right.add(left.poll());
            } else if (left.size() < right.size()) {
                left.add(right.poll());
            }  else break;
        }
    }
}

440. K-th Smallest in Lexicographical Order

/**
 * 将取值范围内的数字想象成一棵trie树
 * 可以对这棵trie树进行搜索,但数据量太大,会超时
 * 由于这棵树同层的兄弟节点之间相隔的数字个数是可以通过n算出来的:
 * 具体的算法是:
 * 我们一层一层地向下计算,假设需要计算的兄弟节点是k和k+1
 * 那么下一层对应的节点就是k*10到(k+1)*10
 * 再下一层是k*100到(k+1)*100 ...
 * 我们一层一层地向下计算,一直算到数最大的一层,发现这一层需要计算的取值范围比n还大
 * 那么对于这一层,我们按照n作为取值范围的最右端进行计算
 * 具体来说,是Math.min (r - 1, n) - l + 1,其中r是这层右边的节点,l是这层左边的节点
 * 
 * 我们计算出相邻的兄弟节点之间的距离后,按照k作为总的步数,每次向兄弟节点移动一个
 * 就需要扣掉相应的兄弟节点之间的距离的步数
 * 如果步数不够扣,则向下移动一层,再算下一层的左兄弟的两个儿子节点,以此类推
 * 最后步数用完,指向的数字就是所求
 */
class Solution {
    public int findKthNumber(int n, int k) {
        int cur = 1;
        int moveForward = 0;
        k --;
        while (k > 0) {
            moveForward = getDiff(n, cur, cur + 1);
            if ((k - moveForward) >= 0) {
                k -= moveForward;
                cur ++;
            } else {
                k -= 1;
                cur *= 10;
            }
        }

        return cur;
    }

    private int getDiff(int n, long l, long r) {
        int ret = 0;
        while (l <= n) {
            ret += Math.min (r - 1, n) - l + 1;
            l *= 10;
            r *= 10;
        }
        return ret;
    }
}

410. Split Array Largest Sum

/**
 * 我们既然要求最小的largest sum,那么首先想到的就是对largest进行搜索
 * 看数据量,如果对每种可能的分段都算的话,显然会超时
 * 注意到分段的个数和每种分段方案的largest sum是一个此消彼长的关系
 * 那么我们可以考虑对largest sum进行二分搜索:
 * 对于一个largest sum,我们可以算出它在满足largest sum情况下最少能分成多少段
 * 如果比目标的分段个数m要多,说明我们的largest sum取小了
 * 如果比m少,说明largest sum取大了
 * 如果等于m,这时也不能停止二分,而是继续向largest sum减小的方向搜索
 * 综上所述,我们要求出的是一个分段数等于m的largest sum的最小值
 * 代码中getSetCnt算出的是给定一个最大的子段和,求出数组最少能分出多少段
 */
class Solution {
    private int getSegCnt(int[] nums, long sum) {
        if (nums.length == 1) {
            if (nums[0] <= sum) return 1;
            else return 0;
        }

        long tmp = nums[0];
        int segs = 1;
        for (int i = 0; i < nums.length - 1; i++) {
            if ((tmp + nums[i + 1]) <= sum) {
                tmp += nums[i + 1];
            } else {
                tmp = nums[i + 1];
                segs++;
            }
        }

        return segs;
    }

    public int splitArray(int[] nums, int m) {
        int numsMax = 0;
        long numsSum = 0;
        for (int i : nums) {
            numsSum += i;
            if (numsMax < i) {
                numsMax = i;
            }
        }

        long left = numsMax;
        long right = numsSum;
        long mid = 0;

         do {
            mid = left + (right - left) / 2;
            if (getSegCnt(nums,mid) > m) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        } while (left <= right);

        return (int)left;
    }
}

407. Trapping Rain Water II

/**
 * 这道题是42 trapping rain water的一个2D情况
 * 乍一看感觉就是把42题中的双指针解法改为4指针就可以了
 * 但实际情况并不是这样
 * 想一个反例:
 * 0 0 3 0 0
 * 0 0 2 0 0
 * 3 2 1 2 3
 * 0 0 2 0 0
 * 0 0 3 0 0
 * 当我们往中央的1灌水时,并不能灌到3,灌到2之后,再往高灌水就会从2和3的缝隙里流出去
 * 再仔细思考一下,我们在42题中的双指针解法实际上是从两边向中间走的唯一一种路径
 * 但是如果扩展成二维的,从边界到中央,并不一定非要直着走,水也有可能是通过一条非直的路线流出去的
 * (比如上面这种情况)
 * 
 * 那么,我们实际上在算灌水的实际体积时,要考虑到的是从边界走到这一点的全部可能经过的路径
 * 中每条路径走过的最大值的最小值作为这个点灌水的“短板”
 * 那么,要枚举这些路径,就需要使用BFS了
 * 具体来讲,首先我们要把图四周的点加入优先级队列
 * 然后从优先级队列中依次取点,对于取到的某个点,看它尚未遍历过的邻居
 * 若:
 * 邻居的高度 > 自己的高度:直接将这个点加入优先级队列
 * 否则:用(自己的高度-邻居的高度)就是这个点实际的灌水值,然后比较巧妙的是
 * 将邻居的高度增高为自己的高度,然后入队(抹平了两点的高度差)。
 * 这样就可以保证队列中存在的点的高度一定是某条路径上的最大值
 */
class Solution {
    private class Point implements Comparable<Point>{
        public int x;
        public int y;
        public int height;
        public Point(int x, int y, int height) {
            this.x = x;
            this.y = y;
            this.height = height;
        }
        
        @Override
        public int compareTo(Point p) {
            return this.height - p.height;
        }
    }
    
    private void storeBoarderToQueue(int[][] heightMap, Queue<Point> q, boolean[][] vis) {
        int rowSize = heightMap[0].length;
        int colSize = heightMap.length;
        for (int i = 0; i < colSize; i++) {
            q.add(new Point(i,0,heightMap[i][0]));
            q.add(new Point(i,rowSize - 1,heightMap[i][rowSize - 1]));
            vis[i][0] = true;
            vis[i][rowSize - 1] = true;
        }
        if (heightMap.length == 1) {
            return;    
        }
        for (int i = 1; i < rowSize - 1; i++) {
            q.add(new Point(0,i,heightMap[0][i]));
            q.add(new Point(colSize - 1,i,heightMap[colSize - 1][i]));
            vis[0][i] = true;
            vis[colSize - 1][i] = true;
        }
    } 
    
    public int trapRainWater(int[][] heightMap) {
        if (heightMap.length == 0 || heightMap[0].length == 0)
            return 0;
        
        boolean vis[][] = new boolean[heightMap.length][heightMap[0].length];
        PriorityQueue<Point> q = new PriorityQueue<>(heightMap[0].length);
        storeBoarderToQueue(heightMap,q,vis);
        int rowSize = heightMap[0].length;
        int colSize = heightMap.length;
        
        int[] nx = new int[]{1,0,-1,0};
        int[] ny = new int[]{0,1,0,-1};
        int ret = 0;
        
        while(!q.isEmpty()) {
            Point p = q.poll();
            for (int i = 0; i <= 3; i++) {
                int xx = p.x + nx[i];
                int yy = p.y + ny[i];
                if (xx > 0 && xx < colSize && yy > 0 && yy < rowSize && !vis[xx][yy]) {
                    if (heightMap[xx][yy] > p.height) {
                        q.add(new Point(xx,yy,heightMap[xx][yy]));
                    } else {
                        ret += (p.height - heightMap[xx][yy]);
                        q.add(new Point(xx,yy,p.height));
                    }
                    vis[xx][yy] = true;
                }
            } 
        }
        
        return ret;
    }
}

363. Max Sum of Rectangle No Larger Than K

/**
 * 我们既然要求出每个子矩阵的和不超过K的最大值
 * 一个很自然的想法就是把这些子矩阵的和一一求出来,然后筛选出不超过K的最大值
 * 求每个子矩阵的和,一种方法是直接暴力求解,需要两层循环遍历子矩阵的区域,然后两层循环求和 时间复杂度是O(m*n*m*n*m*n)=O(m^3*n^3)
 * 这样的姿势显然不够优雅
 * 我们可以借鉴一维数组使用前缀和来优化区间和问题的思路,提前处理出每行和每列的前缀和,然后每个区域的和就可以在O(1)求出
 * 这种方式类似304. Range Sum Query 2D - Immutable这道题
 * 
 * 但是这样做虽然时间复杂度降到了O(m^2*n^2),虽然能过题,但还不算是最优解
 * 我们把二维区域拍扁成一维之后,问题就转化成了如何求和不超过K的子数组和的最大值
 * 这里的解决方案是使用TreeSet+前缀和+二分的方式
 * 对于任何一个前缀和pre[j],我们需要找到值不小于(pre[j]-K)的pre[i],这里 i < j
 * 在找这个pre[i]的过程中,我们可以使用treemap进行存储,保证TreeSet中保存的所有pre[i]有序
 * 之后我们对这部分有序的pre[i]进行二分查找(下面的代码中直接调用了treeset的ceiling函数)
 * 找到值不小于(pre[j]-K)的pre[i]的下界,这样pre[i]是符合条件的最小的,
 * 那么自然pre[j]-pre[i]就是符合条件的最大区间和了。
 * 所以拍扁之后,求出满足要求的区间和最大值,时间复杂度是O(nlogn)
 * 所以总的时间复杂度是O(m^2*n*logn)
 * 
 * 和这道题比较相似的一个问题是,不限制K了,直接求子矩阵中的和最大的
 * 这个问题解法的前半部分和本题一样,还是要把矩阵拍扁
 * 拍扁之后,我们使用dp来求子数组的最大和区间,这是一个经典问题,使用kadane算法即可 
 */
class Solution {
    private boolean mode = false;
    
    public int maxSumSubmatrix(int[][] matrix, int k) {
        if (matrix.length == 0)
            return 0;
        int[] sumSub;
        mode = (matrix.length > matrix[0].length);
        if (mode) {
            sumSub = new int[matrix.length];
        } else {
            sumSub = new int[matrix[0].length];
        }
        
        int maxSum = Integer.MIN_VALUE;
        if (mode) {
            // merge each colomn into sumSub
            int left  = 0, right = 0;
            while (left < matrix[0].length) {
                right = left;
                while (right < matrix[0].length) {    
                    for (int i = 0; i < matrix.length; i++) {
                        sumSub[i] += matrix[i][right];
                    }
                    int curSum = getSum1D(sumSub,k);
                    maxSum = maxSum < curSum ? curSum : maxSum;
                    right ++;
                }
                left ++;
                clearArray(sumSub);
            }
        } else {
            // scan each row into sumSub
            int up = 0, down = 0;
            while (up < matrix.length) {
                down = up;
                while (down < matrix.length) {
                    for (int i = 0; i < matrix[0].length; i++) {
                        sumSub[i] += matrix[down][i];
                    }
                    int curSum = getSum1D(sumSub,k);
                    maxSum = maxSum < curSum ? curSum : maxSum;
                    down ++;
                }
                up ++;
                clearArray(sumSub);
            }
        }
        
        return maxSum;
    }
    
    private void clearArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = 0;
        }
    }
    
    private int getSum1D(int[] arr, int k) {
        TreeSet<Integer> prevSumSet = new TreeSet<Integer>();
        int curSum = 0;
        int maxSum = Integer.MIN_VALUE;
        prevSumSet.add(curSum);
        for (int i = 0; i < arr.length; i++) {
            curSum += arr[i];
            Integer prevSumCeiling = prevSumSet.ceiling(curSum - k);
            if (prevSumCeiling != null) {
                maxSum = Math.max(maxSum,curSum - prevSumCeiling);
            }
            prevSumSet.add(curSum);
        }
        
        return maxSum;
    }
}