月度归档： 2021年7月

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如：”0.1.2.201″ 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312″ 和 “192.168@1.1” 是 无效 IP 地址。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 0 <= s.length <= 3000
• s 仅由数字组成

题解

回溯。具体思路就是，每次尝试截取1-3位字符，判断是否符合0-255之间的数值，这里单独写个方法判断截取出来的字符串是否符合ip中的数字的要求。不能是0开头的字符，但是可以是单独的一个字符“0”。

另外，终止条件必须是凑齐了4个数字，且最后截取到了提供的字符串的最后一位

if (strArr.size()==3 && lastIndex < s.length()){
                continue;
            }

这样的逻辑是，已经存了3个数字，且最后截取到了提供的字符的最后一位才会继续执行。这部分甚至可以继续深入优化下，比如已经存了2个数字，且剩余字符位数小于7位，因为每个数字可能为1-3位数。或者，已经存了1个数字，且剩余字符位数小于10位这样的逻辑。

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private List<String> res = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        List<String> strArr = new ArrayList<>();
        dfs(strArr,s,0);

        return res;
    }


    private void dfs(List<String> strArr, String s, int startIndex){
        for (int i = 1; i <= 3; i++) {
            //尝试往后截取1-3位
            int lastIndex = startIndex+i;
            //如果当前递归收集到的数组中已经有三个，并且，后面要截取的字符没能截取到给定字符串的最后一位
            //结束当前长度的尝试，进入下一个更长长度的截取尝试
            if (strArr.size()==3 && lastIndex < s.length()){
                continue;
            }
            if (lastIndex > s.length()){
                //substring最后一次截取如果index超出了长度，会产生重复，且这个分支说明已经结束了
                return;
            }

            String str = s.substring(startIndex,lastIndex);
            if (validateIpNum(str, strArr.size())){
                strArr.add(str);
                if (strArr.size()==4 && lastIndex == s.length()){
                    String newStr = String.join(".",strArr);
                    System.out.println(newStr);
                    res.add(newStr);

                }
                dfs(strArr,s,lastIndex);
                strArr.remove(strArr.size()-1);
            }

        }
    }

    private boolean validateIpNum(String numStr,int numIndex){
        if (numStr.length()>1 && numStr.startsWith("0")){
            return false;
        }
        int num = Integer.parseInt(numStr);
        return num < 256;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1：

输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

题解

有点水的困难题，从前到后，从后到前各来一遍就可以了

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int candy(int[] ratings) {
        int[] resArr = new int[ratings.length];
        resArr[0] = 1;
        for (int i = 0; i < ratings.length-1; i++) {
            if (ratings[i+1] > ratings[i]){
                resArr[i+1] = resArr[i]+1;
            }else{
                resArr[i+1] = 1;
            }
        }

        int count = resArr[ratings.length-1];
        //这里的循环是最后一位开始往前，计算前一位的需要符合的值
        for (int k = ratings.length-1; k > 0; k--) {
            if (ratings[k-1] > ratings[k] && resArr[k-1] <= resArr[k]){
                //ratings中的前一位比当前这位大，且结果中的前一位不比当前位置大
                resArr[k-1] = resArr[k]+1;
            }
            //前一位的值已经确定
            count += resArr[k-1];
        }
        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1

示例 2:

输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:
7

注意: 您可以假设树（即给定的根节点）不为 NULL。

题解

BFS或者DFS

两个解法都写了，BFS看到网友有个写法，先插入右子节点，再插入左子节点，这样最终queue的最后一个节点，必定是最深一层，最左侧的节点，这样的好处是，不用分层循环

我的写法还是先插入左子节点，再插入右子节点，而每层循环的时候第一个peek到的值则是本层的最左侧节点

分层循环的时候，踩了个小坑，之前没太注意

//这是更正后的
int size = queue.size();
for (int i = 0; i < size; i++) {
    //poll逻辑
}

//更正前的
for (int i = 0; i < queue.size(); i++)

因为每次循环都会poll下，queue的size是会动态变化的，而每次循环的时候i值还在增加，会导致逻辑出错。

深搜DFS的时候也是，先遍历左节点，这样，只有深度更深的时候才更新查到的节点，深度相同的时候，肯定先取到的是左节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */


class Solution {
    public int findBottomLeftValue(TreeNode root) {
        dfs(root,0);

        bfs(root);
        return val;//theDeepNode.val
    }
    private int val;


    private TreeNode theDeepNode;

    private int depth = 0;

    private void dfs(TreeNode node, int currentDepth){
        if (null != node.left){
            dfs(node.left, currentDepth+1);
        }
        if (null != node.right){
            dfs(node.right, currentDepth+1);
        }
        if (node.left ==null && node.right == null){
            if (currentDepth > this.depth || this.theDeepNode == null){
                theDeepNode =  node;
                this.depth = currentDepth;
            }
        }
    }

    private Queue<TreeNode> queue = new LinkedList<>();

    private void bfs(TreeNode node){
        val = node.val;
        if (node.left!=null){
            queue.offer(node.left);
        }
        if (node.right!=null){
            queue.offer(node.right);
        }
        while (!queue.isEmpty()){
            val = queue.peek().val;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode currentNode = queue.poll();
                if (currentNode.left!=null){
                    queue.offer(currentNode.left);
                }
                if (currentNode.right!=null){
                    queue.offer(currentNode.right);
                }
            }
        }
    }

//
//    public class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        TreeNode() {}
//        TreeNode(int val) { this.val = val; }
//        TreeNode(int val, TreeNode left, TreeNode right) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//        }
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

题解

回溯，嗯

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    private List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        tryNext(new ArrayList<>(),nums);
        return list;
    }


    private void tryNext(List<Integer> ls, int[] nums){
        if (ls.size()== nums.length){
            List<Integer> l = new ArrayList<>();
            for (Integer integer : ls) {
                l.add(integer);
            }
            list.add(l);
            return;
        }
        for (int num : nums) {
            if (ls.contains(num)){
                continue;
            }
            ls.add(num);
            tryNext(ls,nums);
            ls.remove(ls.size()-1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

• 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
  • 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

示例 1：

输入：nums = [9], maxOperations = 2
输出：3
解释：
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

示例 2：

输入：nums = [2,4,8,2], maxOperations = 4
输出：2
解释：
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。

示例 3：

输入：nums = [7,17], maxOperations = 2
输出：7

提示：

• 1 <= nums.length <= 105
• 1 <= maxOperations, nums[i] <= 109

题解

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public int minimumSize(int[] nums, int maxOperations) {
        int l=1;
        int r = 1000000000;
        int lastAvailable = 0;
        while (l <= r){
            int mid = l + (r-l)/2;
            if (available(nums, mid, maxOperations)){
                //当前mid值能满足在maxOperations次数内，分袋完成
                //可以尝试继续缩小mid值
                r = mid-1;
                lastAvailable = mid;
            }else{
                //当前mid值不能满足在maxOperations次数内，分袋完成
                //需要加大mid值再次尝试
                l = mid+1;
            }
        }
       return lastAvailable;
    }

    /**
     *
     * @param nums 给予的数组
     * @param minShap  期望值
     * @param maxOperations
     * @return
     */
    private boolean available(int[] nums, int minShap, int maxOperations){
        int operateTimes = 0;
        for (int num : nums) {
            //挨个加上需要分袋的次数
            operateTimes += num/minShap;
            if (num % minShap == 0){
                //如果是能整除的。比如有6个，每次分两个，只需要分2次，最后余下的2个留在袋子里
                //而不是6/2=3次
                operateTimes--;
            }
            if (operateTimes > maxOperations){
                return false;
            }
        }

        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制：

• 1 <= push_back,pop_front,max_value的总操作数 <= 10000
• 1 <= value <= 10^5

题解

思路和上一题【239】滑动窗口最大值类似，单调队列

根据题面，我们必然需要维护一个队列用来从尾部插入新值，从头部弹出旧的值。接下来的问题就是怎么维护这个最大值，且这个最大值在从头部弹出后需要自动维护到比他小的一个值。所以这边就想到了用一个有序集合来维护这个大小排序的关系。

同样的因为题面中的单向性，只从尾部新增，只从头部弹出，且只需要维护一个最大值的情况。可以试想下这样的场景，我们在依次从集合头部弹出数值，而此时的的最大值关系我们可以知道从头部到最大值之间的关系是不需要维护的。

而当最大值弹出的时候，我们只需要知道从最大值的位置到末尾的位置之间的最大值即可。那么思路就自然出来了。

import java.util.LinkedList;

//leetcode submit region begin(Prohibit modification and deletion)
class MaxQueue {

    private LinkedList<Integer> maxValueList = new LinkedList<>();

    private LinkedList<Integer> queue = new LinkedList<>();

    public MaxQueue() {

    }

    //取最大值
    public int max_value() {
        if (!maxValueList.isEmpty()){
            return maxValueList.getFirst();
        }
        return -1;
    }
    //往尾添加一个
    public void push_back(int value) {
        queue.addLast(value);
        while (!maxValueList.isEmpty() && maxValueList.getLast() <= value){
            maxValueList.pollLast();
        }
        maxValueList.addLast(value);
    }
    //从头部弹出
    public int pop_front() {
        if (queue.isEmpty()){
            return -1;
        }
        if (queue.peekFirst().equals(maxValueList.getFirst())){
            maxValueList.pollFirst();
        }
        return queue.pollFirst();
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */
//leetcode submit region end(Prohibit modification and deletion)

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

示例 3：

输入：nums = [1,-1], k = 1
输出：[1,-1]

示例 4：

输入：nums = [9,11], k = 2
输出：[11]

示例 5：

输入：nums = [4,-2], k = 2
输出：[4]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

题解

单调队列解法，从思路来说，最基础的

1.长度为k的区间，每挪一次，算一下区间内的最大值，这是最基础的算法

2.每挪一次，其实相比上次只有两个值有变化，挪动之后去除掉了当前区间的前一位，和新增的当前区间的最后一位

3.基于2的结论，我们需要对当前区间内的K位数字进行排序。到这里，我们可以试着用堆来处理这个问题了

4.基于前面的基础，因为这长度为k的窗口是一直单向的往后滑动的，所以，假如我们在长度为k的窗口内，下标位置为n的位置为当前窗口区间内的最大值，其实我们需要的值就剩下n位置，和n位置到窗口末尾的一个递减的有序集合。而每往后挪动一次，前面比当前位置的值小的就都可以去掉。于是，新的题解思路就出来了

import java.util.LinkedList;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private LinkedList<Integer> list = new LinkedList<Integer>();


    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];

        for (int i = 0; i < nums.length; i++) {
            if (list.size()==0){
                list.add(i);
            }else {

//有个判空，不然会报空指针
                while (list.size()>0 && nums[list.getLast()] <= nums[i]){

//如果末尾的值比当前值小，那么删除
                    list.pollLast();
                }
                list.addLast(i);
                if (list.getFirst() <= i-k){//判断头部最大的值有没有超出当前区间
                    list.pollFirst();
                }
            }
            if (i+1>=k){//边界值比较容易绕，可以拿简单的i=0，k=1的情况来模拟下
                res[i-k+1] = nums[list.peekFirst()];
            }
        }

        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)