月度归档： 2021年6月

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 

示例 2：

输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4

示例 3：

输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

提示：

• 1 <= D <= weights.length <= 5 * 104
• 1 <= weights[i] <= 500

解题

public class LeetCode1011Test {

    public int shipWithinDays(int[] weights, int days) {
        int l = 0;
        int r = 0;

        for (int weight : weights) {
            l = Math.max(l,weight);
            r += weight;
        }

        while (l < r){
            int mid = (l + r) >> 1;
            if (check(weights,days,mid)){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;

    }


    private boolean check(int[] weights, int days, int dayShip){
        int dayCount = 1;//初始一定有一天
        int dayShipReal = 0;
        //挨个取货
        for (int shipCount = 0; shipCount < weights.length; shipCount++) {
            //如果取到当前这个货没有超重，那么把这个装上，并且进入下一个循环取下一个货
            if (dayShipReal + weights[shipCount] <= dayShip){//等于条件需要注意
                dayShipReal +=  weights[shipCount];
            }else{
                //如果取当前货物已经超重，那么进入明天，并且前面的已装的货发掉，开一新船装上当天的重量
                dayCount++;
                dayShipReal = weights[shipCount];
                //如果天数已经超了
                if (dayCount > days){
                    return false;
                }
            }
        }
        return true;

    }
}

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

输入：
[[0,0,0],
 [0,1,0],
 [0,0,0]]

输出：
[[0,0,0],
 [0,1,0],
 [0,0,0]]

示例 2：

输入：
[[0,0,0],
 [0,1,0],
 [1,1,1]]

输出：
[[0,0,0],
 [0,1,0],
 [1,2,1]]

提示：

• 给定矩阵的元素个数不超过 10000。
• 给定矩阵中至少有一个元素是 0。
• 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

题解

import java.util.LinkedList;
import java.util.Queue;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;

        Queue<int[]> list = new LinkedList<>();
        boolean[][] visited = new boolean[row][col];
        int[][] dist = new int[row][col];
        for (int i = 0; i <= row - 1; i++) {
            for (int j = 0; j <= col - 1; j++) {
                if (mat[i][j] == 0){
                    list.offer(new int[]{i,j});
                    visited[i][j] = true;
                }
            }
        }

        int [][] move = {{-1,0}, {1,0},{0,1},{0,-1}};

        while (!list.isEmpty()){
            int[] item = list.poll();
            for (int[] targetPosition : move) {
                int[] target = {item[0]+targetPosition[0],item[1]+targetPosition[1]};
                if (target[0]<0 || target[0]> row-1 || target[1]<0 || target[1] >col-1  || visited[target[0]][target[1]]) {
                    continue;
                }
                dist[target[0]][target[1]] = dist[item[0]][item[1]] + 1;
                list.offer(target);
                visited[target[0]][target[1]] = true;

            }
        }

        return dist;
    }
}

题解2：动态规划

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;

        int bigValue = (Integer.MAX_VALUE-1) >> 1;
        int[][] dist = new int[row][col];
        for (int i = 0; i <= row - 1; i++) {
            for (int j = 0; j <= col - 1; j++) {
                if (mat[i][j] == 0){
                    dist[i][j] = 0;
                }else{
                    dist[i][j] = bigValue;
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dist[i][j] == 0){
                    continue;
                }
                getMin(dist,i,j);
            }
        }
        for (int i = row-1; i >=0; i--) {
            for (int j = col-1; j >= 0; j--) {
                if (dist[i][j] == 0){
                    continue;
                }
                getMin(dist,i,j);
            }
        }

        return dist;
    }


    private static void getMin(int[][] dist ,int i, int j){
        if (i-1>=0){
            dist[i][j] = Math.min(dist[i][j],dist[i-1][j]+1);
        }
        if (j-1>=0){
            dist[i][j] = Math.min(dist[i][j],dist[i][j-1]+1);
        }
        if (i+1 < dist.length){
            dist[i][j] = Math.min(dist[i][j],dist[i+1][j]+1);
        }
        if (j+1 < dist[0].length){
            dist[i][j] = Math.min(dist[i][j],dist[i][j+1]+1);
        }
    }
}

TinyURL是一种URL简化服务， 比如：当你输入一个URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk.

要求：设计一个 TinyURL 的加密 encode 和解密 decode 的方法。你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个URL可以被加密成一个TinyURL，并且这个TinyURL可以用解密方法恢复成原本的URL。

public class LeetCode535Test {

    private static String chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

    private static HashMap<String,String> urlToTiny = new HashMap<>();
    private static HashMap<String,String> tinyToUrl = new HashMap<>();

    private static String to62Str(Long num){
        StringBuilder sb = new StringBuilder();
        int remainder = 0;
        int scale = chars.length();
        while (num > scale - 1) {
            remainder = Long.valueOf(num % scale).intValue();
            sb.append(chars.charAt(remainder));
            num = num / scale;
        }
        sb.append(chars.charAt(num.intValue()));
        return  sb.reverse().toString();
    }

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        if (urlToTiny.containsKey(longUrl)){
            return urlToTiny.get(urlToTiny);
        }
        Long nanoTime = System.nanoTime();
        String key = to62Str(nanoTime);
//        System.out.println(key);
        urlToTiny.put(longUrl,key);
        tinyToUrl.put(key,longUrl);
        return key;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        if (tinyToUrl.containsKey(shortUrl)){
            return tinyToUrl.get(shortUrl);
        }
        return null;
    }
}

这题比较简单，简单的Hash映射

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

示例 1:

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

示例 2:

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

示例 3：

输入：houses = [1,5], heaters = [2]
输出：3

提示：

• 1 <= houses.length, heaters.length <= 3 * 104
• 1 <= houses[i], heaters[i] <= 109

题解：

public class LeetCode475Test {


    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        Arrays.sort(houses);
        int res = 0;
        for (int house : houses) {
            int l = 0;
            int r = heaters.length - 1;
//二分法，这边有点疑问，找到的应该是比较接近的那个，
            while (l < r) {
                int mid = (l + r) >> 1;
                if (heaters[mid] == house) {
                    l = mid;
                    break;
                }
                if (heaters[mid] > house) {
                    r = --mid;
                } else {
                    l = ++mid;
                }
            }
            int dis = Integer.MAX_VALUE;
//二分法比较头疼的部分，边界问题，所以这边取了个巧，再拿前1后1和得到的这个位置做对比
            for (int i = l - 1; i <= l + 1; i++) {
                if (i >= 0 && i <= heaters.length - 1) {
                    dis = Math.min(dis, Math.abs(house - heaters[i]));
                }
            }
//得到每个房屋对应的最小的距离，再取所有房屋的最小值里最大的值
            res = Math.max(res, dis);
        }
        return res;
    }

}

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -109 <= target <= 109

解答

public class LeetCode240Test {


    public static class Vector{
        private int x;
        private int y;

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }
    }


    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length==0){
            return false;
        }
        if (matrix[0].length == 0){
            return false;
        }
        int rowCount = matrix.length;
        int colCount = matrix[0].length;

        Vector vector = new Vector();
        vector.setX(0);
        vector.setY(rowCount-1);
        while (vector.getX() <= colCount-1 && vector.getY()>=0 && vector.getX() >=0){
            int value = matrix[vector.getY()][vector.getX()];
            if (value == target){
                return true;
            }else if (value > target){
                //上移
                vector.setY(vector.getY()-1);
            }else{
                //右移
                vector.setX(vector.getX()+1);
            }
        }
        return false;
    }
}

上面的解题思路是最取巧的，看了分析之后，发现应该有4种方法。正常来说，我看到这题的时候第一思路是看成一颗二叉树，遍历探测。

具体有时间的，后面再补上

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

进阶：

• 这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
• 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

题解：

public class LeetCode81Test {

    public boolean search(int[] nums, int target){
        if (nums.length == 0) {
            return false;
        }
        if (nums[0] == target) {
            return true;
        }
        int mid, l = 0, r = nums.length - 1, head, tail;
        while ( l < r &&
                ( nums[l+1]==nums[0]  ||
                        nums[r-1]==nums[nums.length-1] )
        ){
            if (nums[l+1]==nums[0]) {
                l++;
            }
            if (nums[r-1]==nums[nums.length-1]) {
                r--;
            }
        }
        head = l;
        tail = r;
        while ( l <= r ){
            mid = ( l + r ) >> 1;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] <= nums[tail]){
                if (target > nums[mid] && target <= nums[tail] ){
                    l = ++mid;
                }else {
                    r = --mid;
                }
            }else {
                if (target < nums[mid] && target >= nums[head]){
                    r = --mid;
                }else{
                    l = ++mid;
                }
            }
        }
        return false;
    }

}