【九章算法强化班】follow up

发表于 | 分类于 ， | 浏览 次
字数统计: 3,265 | 阅读时长 ≈ 17

outline

例题1.Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

找局部最大值。

思路：

  1. baseline：

    遍历，找到i：nums[i-1]<num[i]<num[i+1]

    复杂度

  1. 优化：二分法

    首先我们找到中间节点mid，如果大于两边返回当前index就可以了，如果左边的节点比mid大，那么我们可以继续在左半区间查找，这里面一定存在一个peak，为什么这么说呢？假设此时的区间范围为[0, mid - 1]， 因为num[mid - 1]一定大于num[mid]了，如果num[mid - 2] <= num[mid - 1]，那么num[mid - 1]就是一个peak。如果num[mid - 2] > num[mid - 1]，那么我们就继续在[0, mid - 2]区间查找，因为num[-1]为负无穷，所以最终我们绝对能在左半区间找到一个peak。同理右半区间一样。

    复杂度

代码：

class Solution {
    public int findPeakElement(int[] nums) {
         if(nums.length == 1){
            return 0;
        }
        //遇到这种需要判断元素左右的将start设为1，end设为len-2,放置越界
        int start = 1;
        int end = nums.length-2;
        while(start+1<end){
            int mid = start + (end-start)/2;
            if((nums[mid] > nums[mid+1]) && (nums[mid] > nums[mid-1])){
                return mid;
            }
            else if((nums[mid] < nums[mid+1]) && (nums[mid] < nums[mid-1])){
                start = mid;
            }
            else if ((nums[mid] > nums[mid+1]) && (nums[mid] < nums[mid-1])){
                end = mid;
            }
            else {
                start = mid;
            }
        }
        if(nums[start] < nums[end]){
            return  end;
        }
        else
            return start;
    }
}

follow up: Find Peak Element II

由一维拓展到二维，在矩阵上找peak element

peak element：matrix[i][j] 比其上下左右相邻元素大

思路：

  1. baseline：

    遍历

    复杂度复杂度

  2. 优化：二分法

    • 找到中间行的最大值matrix[i][j]
    • 跟相邻上下元素比较，决定向上/向下走
    • 如果上面的元素比较大，向上走，否则向下走

    复杂度

  3. 优化：行列交替二分

    • 找到中间行的最大值matrix[i][j]
    • 跟相邻上下元素比较，决定向上/向下走 剩下一半矩阵
    • 找中间列的最大值matrix[i][j]
    • 跟相邻左右元素比较，决定向左/向右走 剩下n/4矩阵

    复杂度

例题2. Subarray Sum

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Example

Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

找子数组，和为0

思路：

  1. baseline:

    两指针遍历

    复杂度复杂度

  2. prefix sum:

    用hash表记录前缀和的取值

public List<Integer> subarraySum(int[] nums) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        int sum = 0;
        for(int i = 0 ; i  < nums.length;i++){
            sum += nums[i];
            if(sum == 0){
                result.add(0);
                result.add(i);
                return result;
            }
            if(map.containsKey(sum)){
                result.add(map.get(sum)+1);
                result.add(i);
                return result;
            }
            map.put(sum,i);//key是前缀和，value是idx
        }
        return result;
    }

follow up 1: Submatrix Sum

Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.

Example

Given matrix

> [
>   [1 ,5 ,7],
>   [3 ,7 ,-8],
>   [4 ,-8 ,9],
> ]
>
>

>

return [(1,1), (2,2)]

求元素和为0的子矩阵，返回矩阵的左上角和右下角元素位置

思路：

  1. 先定位子矩阵的首行和尾行（外层循环）

  2. 把首行和尾行之间的元素压成一行，变成一个数组

  3. 对上面的数组做subarray sum，找到和为0的子数组就可以定位子矩阵的首列和尾列。

    ​

预计算presum矩阵：

presum[i][j] = matrix[0][0]到matrix[i][j]的所有元素和

当外层循环固定为l和h时，内层循环j从0开始遍历，矩阵的前缀和为presum[h][j]-presum[l][j]

代码：

public int[][] submatrixSum(int[][] matrix) {
    // write your code here
    int[][] result = new int[2][2];
    int rows = matrix.length;
    if(rows == 0){
        return result;
    }
    int cols = matrix[0].length;
    if(cols == 0){
        return result;
    }
    int[][] presum = new int[rows+1][cols+1];
    //初始化
    for(int i = 0; i < rows+1;i++){
        for(int j = 0;j < cols+1;j++){
            if(i == 0 || j == 0){
                presum[i][j] = 0;
            }
            else{
                presum[i][j] = matrix[i-1][j-1] + presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1];
            }
        }
    }
    for(int i = 0; i < rows;i++) {
        for (int j = i + 1; j < rows + 1; j++) {
            HashMap<Integer, Integer> map = new HashMap();
            for (int k = 0; k < cols + 1; k++) {
                int diff = presum[j][k] - presum[i][k];
                if (map.containsKey(diff)) {
                    result[0][0] = i;
                    result[0][1] = map.get(diff);
                    result[1][0] = j-1;
                    result[1][1] = k-1;
                    return result;
                } else {
                    map.put(diff, k);
                }
            }
        }
    }
    return result;
}

follow up 2: Subarray Sum II

给定一个数组nums和一个区间interval，返回nums数组中和在区间interval中的子数组个数，如nums = [1,2,3,4]，interval = [1,3],return 4,the possible answers are:[0,0],[0,1],[1,1],[2,2]

思路：

low < prefix[j] - prefix[i] < high

low + prefix[i] < prefix[j] < high + prefix[i]

prefix[i] < prefix[j] - low

prefix[i] > prefix[j] - high

所以本题就是要找到在[prefix[j] - high , prefix[j] - low]范围内的prefix[i]

由于prefix[i]是递增的，所以可以存在数组中，用二分法查找

例题3. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

找和最大的子数组

思路：

方法1：prefixsum

维护最小的prefixsum和当前最大的子数组和

方法2：dp

dp[i] = max(dp[i-1] + num[i],num[i])

代码：

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int maxVal = nums[0];
        dp[0] = nums[0];
        for(int i = 1;i < nums.length;i++){
            dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
            maxVal = Math.max(maxVal,dp[i]);
        }
        return maxVal;
    }
}

follow up 循环连续子数组

上题的数组变成循环数组。

处理循环数组三种方法：

  1. 拆开
  2. 扩展
  3. 取反

分别看对于这道题是否可行：

  1. 拆开

    house robber用到了这个方法，抢第一个就不能抢最后一个，抢最后一个就不能抢第一个

  2. 扩展

    将数组翻一倍，[-3, 1, 3, -3, 4]变成[-3, 1, 3, -3, 4,-3,1,3,-3]，然后找最大子数组，但是长度不能超过nums的长度。

  3. 取反

    找循环数组中的最大子数组，有两种情况：

    1. 在数组的中部，正常找就行了
    2. 一半在数组后面，一半在数组头部，因为数组的总和是一定的，因此这种情况可以转化成在数组中部找最小的子数组

    然后取上面两种情况的最大值。

    ​

例题4. Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

代码：

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int start = 0;
        int end = nums.length-1;
        boolean flag = false;
        int[] copy = new int[nums.length];
        int idx = 0;
        while(start <= end){
            if (flag == false){
                copy[idx] = nums[start];
                start++;
                flag = true;
            }
            else {
                copy[idx] = nums[end];
                end--;
                flag = false;
            }
            idx++;
        }
        for(int i = 0;i < nums.length;i++){
            nums[i] = copy[i];
        }
    }
}

follow up Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

思路：

  1. baseline：

    对数组排序，排序之后将数组分成大小两堆，然后依次选取排序

  2. quick sort思想

    利用quick sort 找到中点，然后对左右两边元素一次选取排序

代码：

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int end = nums.length-1;
        int mid = end/2;
        boolean flag = false;
        int[] copy = new int[nums.length];
        int idx = 0;
        while(idx < nums.length){
            if (flag == false){
                copy[idx] = nums[mid];
                mid--;
                flag = true;
            }
            else {
                copy[idx] = nums[end];
                end--;
                flag = false;
            }
            idx++;
        }
        for(int i = 0 ; i < nums.length;i++){
            nums[i] = copy[i];
        }
    }
}

例题5. Building Post Office Best Meeting Point

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

> 1 - 0 - 0 - 0 - 1
> |   |   |   |   |
> 0 - 0 - 0 - 0 - 0
> |   |   |   |   |
> 0 - 0 - 1 - 0 - 0
>

>

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

思路：

  1. baseline：

    遍历所有位置，计算每个位置到所有人的距离，取最小的

  2. 优化：

    看成一维，对于所有人来说，meeting point选在所有人的中位数的位置距离和最近，因此对行和列坐标分别选取中位数，得到meeting point

代码：

class Solution {
    public int minTotalDistance(int[][] grid) {
        List<Integer> rows = new ArrayList<>();
        List<Integer> cols = new ArrayList<>();
        //int  num = 0;
        for(int i = 0 ; i < grid.length;i++){
            for(int j = 0 ; j <grid[0].length;j++){
                if(grid[i][j] == 1){
                    rows.add(i);
                    cols.add(j);
                    //num++;
                }
            }
        }
        int num = rows.size()/2;
        Collections.sort(rows);
        Collections.sort(cols);
        int x = rows.get(num);
        int y = cols.get(num);
        int result = 0;
        for(int i = 0;i < rows.size();i++){
            result += Math.abs(x- rows.get(i));
            result += Math.abs(y- cols.get(i));
        }
        return result;
    }
}

follow up1. Shortest Distance from All Buildings

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

  • Each 0 marks an empty land which you can pass by freely.
  • Each 1 marks a building which you cannot pass through.
  • Each 2 marks an obstacle which you cannot pass through.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

> 1 - 0 - 2 - 0 - 1
> |   |   |   |   |
> 0 - 0 - 0 - 0 - 0
> |   |   |   |   |
> 0 - 0 - 1 - 0 - 0
>

>

The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

思路：

  1. baseline：

    bfs，计算每个点到所有人的距离，取距离和最小的

    时间复杂度：外层循环 然后内层bfs，因此时间复杂度

  2. 反向bfs

    计算每个人到所有位置的距离dis[k][i][j] ，复杂度

    然后再遍历矩阵中每一个点，查询距离，取最小值，复杂度

    因此时间复杂度

代码：

class Solution {
    //计算到所有空地的距离
    public void bfs(int i,int j,int idx,int[][][] distance,int rows, int cols,int[][] grid){
        int[] x_delta = {1,-1,0,0};
        int[] y_delta = {0,0,1,-1};
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i*cols+j);
        int dis = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size > 0){
                int val = queue.poll();
                int x = val/cols;
                int y = val % cols;
                for(int ii = 0; ii < 4;ii++){
                    int x_new = x + x_delta[ii];
                    int y_new = y + y_delta[ii];
                    if(x_new >= 0 && x_new < rows && y_new >= 0 && y_new <cols) {
                        if(grid[x_new][y_new] == 0 && distance[idx][x_new][y_new] == 0){
                            distance[idx][x_new][y_new] = dis;
                            queue.add(x_new * cols + y_new);
                        }
                    }
                }
                size--;
            }
            dis++;
        }
    }
    public int shortestDistance(int[][] grid) {
        int rows = grid.length;
        if(rows == 0){return -1;}
        int cols = grid[0].length;
        if(cols == 0){return -1;}
        //计算有多少个1
        int count = 0;
        for(int i = 0; i < rows;i++){
            for(int j = 0;j < cols;j++){
                if(grid[i][j] == 1){
                    count++;
                }
            }
        }
        int[][][] distance = new int[count][rows][cols];
        //计算（i,j）到所有0点的距离
        int idx = 0;
        for(int i = 0; i < rows;i++){
            for(int j = 0;j < cols;j++){
                if(grid[i][j] == 1){
                    bfs(i,j,idx,distance,rows,cols,grid);
                    idx++;
                }
            }
        }
        int minDist = Integer.MAX_VALUE;
        //找距离和最短的
        for(int i = 0; i < rows;i++){
            for(int j = 0;j < cols;j++){
                if(grid[i][j] == 0){
                    int sum = 0;
                    boolean flag = true;
                    for(int k = 0;k < distance.length;k++){
                        if(distance[k][i][j] == 0){
                            flag = false;
                            break;
                        }
                        else{
                            sum += distance[k][i][j];
                        }
                    }
                    if(flag){
                        minDist = Math.min(minDist,sum);
                    }
                }
            }
        }
        if(minDist == Integer.MAX_VALUE){
            return -1;
        }
        return minDist;
    }
}

follow up 2. Bomb Enemy

Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.

Example:

> For the given grid
>
> 0 E 0 0
> E 0 W E
> 0 E 0 0
>
> return 3. (Placing a bomb at (1,1) kills 3 enemies)
>

思路：

  1. baseline：

    bfs，计算每个点能够炸到的到所有人

    时间复杂度：外层循环 然后内层，因此时间复杂度

  2. 反向bfs

    申请四个数组：

    left[i][j]:在(i,j)放炸弹，向左最多炸人数

    right[i][j]:在(i,j)放炸弹，向右最多炸人数

    up[i][j]:在(i,j)放炸弹，向上最多炸人数

    dowm[i][j]:在(i,j)放炸弹，向下最多炸人数

    将四个数组相加就得到在(i,j)放炸弹，总共炸人数

    因此时间复杂度

代码：

public class BombEnemy {
    public int maxKilledEnemies(char[][] grid) {
        int rows = grid.length;
        if(rows == 0){
            return 0;
        }
        int cols = grid[0].length;
        if(cols == 0){
            return 0;
        }
        int[][] left = new int[rows][cols];
        int[][] right = new int[rows][cols];
        int[][] up = new int[rows][cols];
        int[][] down = new int[rows][cols];
        for(int i = 0;i < rows;i++){
            int leftsum = 0;
            int rightsum = 0;
            for(int j = 0;j < cols;j++){
                if(grid[i][j] == '0'){ left[i][j] = leftsum; }
                if(grid[i][j] == 'W'){ leftsum = 0; }
                if(grid[i][j] == 'E'){ leftsum++; }
                if(grid[i][cols-1-j] == '0'){ right[i][cols-1-j] = rightsum; }
                if(grid[i][cols-1-j] == 'W'){ rightsum = 0; }
                if(grid[i][cols-1-j] == 'E'){ rightsum++; }
            }
        }
        for(int i = 0;i < cols;i++){
            int upsum = 0;
            int downsum = 0;
            for(int j = 0;j < rows;j++){
                if(grid[j][i] == '0'){ up[j][i] = upsum; }
                if(grid[j][i] == 'W'){ upsum = 0; }
                if(grid[j][i] == 'E'){ upsum++; }
                if(grid[rows-1-j][i] == '0'){ down[rows-1-j][i] = downsum; }
                if(grid[rows-1-j][i] == 'W'){ downsum = 0; }
                if(grid[rows-1-j][i] == 'E'){ downsum++; }
            }
        }
        int maxnum = 0;
        for(int i = 0;i < rows;i++){
            for(int j = 0;j < cols;j++){
                maxnum = Math.max(maxnum,left[i][j] + right[i][j] + up[i][j] + down[i][j]);
            }
        }
        return maxnum;
    }
}

例题6. N个数组的第K大问题

在N个数组中找到第K大的元素

排序+heap

类似merge K sorted list