月度归档： 2021年8月

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

示例 1：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

提示：

• 1 <= n <= 2 * 104
• 1 <= bookings.length <= 2 * 104
• bookings[i].length == 3
• 1 <= firsti <= lasti <= n
• 1 <= seatsi <= 104

题解

一看题目啊，emmm，这不简单嘛，直接遍历循环套循环，好处理的嘛

public int[] corpFlightBookings(int[][] bookings, int n) {
    int [] res = new int[n];
    for (int[] booking : bookings) {
        plus(res, booking[0]-1,booking[1]-1,booking[2]);
    }

    return res;
}


public void plus(int[] arr, int start, int end, int count){
    while (start <= end){
        arr[start] += count;
        start++;
    }
}

你看这不还过了

解答成功:
执行耗时:879 ms,击败了29.46% 的Java用户
内存消耗:53.5 MB,击败了44.81% 的Java用户	

但是想一下这中间的过程，应该没那么简单。以官方给出的示例来分析

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25

通过分析这份数据我们可以知道，在1航站新增了10名旅客，直到2航站才下机，所以到3航站的时候这10名旅客就不在了。

2航站有两批数据，一匹是20 一匹是25，一共新增了45名乘客，加上之前1航站的10名乘客一共是有55名。那么在4航站的时候就有20名下机了，而另外25名可以认为直到一个不存在的6才下机或者不处理也可以。

那么实际的逻辑就应该是在1的位置新增了10，这个10需要再3的位置减去，在2的位置新增了20、25，分别在4位置和不存在6位置减去。

所以用一个新的数组保存每个的变更情况，如果为0，则说明没有变更，则需要继承前一个位置的值，如果为正则说有净增加，需要由前一个位置的值加上这个值，如果为负数，则说明有净减少，需要由前一个位置的值减去对应的值。

思路对应代码

class Solution {

    public int[] corpFlightBookings(int[][] bookings, int n) {
        int [] res = new int[n];
        for (int[] booking : bookings) {
            res[booking[0]-1] += booking[2];
            if (booking[1]<n){
                res[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < res.length; i++) {
            res[i] += res[i-1];
        }
        return res;
    }
}

提交下，可以，没毛病

解答成功:         
执行耗时:2 ms,击败了100.00% 的Java用户         
内存消耗:53.3 MB,击败了67.00% 的Java用户

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

示例 1：

输入：
["Solution","pickIndex"]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

示例 2：

输入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。

由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。

提示：

• 1 <= w.length <= 10000
• 1 <= w[i] <= 10^5
• pickIndex 将被调用不超过 10000 次

题解

8月30日 每日一题

class Solution {

    int[] preSum;
    public Solution(int[] w) {
        for (int i = 1; i < w.length; i++) {
            w[i] = w[i]+w[i-1];
        }
        preSum = w;
    }
    
    public int pickIndex() {
        int randNum = (int)(Math.random() * preSum[preSum.length-1])+1;
        int left = 0;
        int right = preSum.length-1;
        while (left < right){
            int mid = (left + right) >> 1;
            if (preSum[mid] < randNum){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        System.out.println(left);
        return left;
    }
}

大致思路，比如数组[1,2,3]，要求值对应概率的话，最直观的就会想到创建一个集合，里面放入1个“1”，放入两个“2”，方式3个“3”，然后随机取一个值，这个取到的概率满足1的几率是1/6，2的几率是2/6，3的几率是3/6，找到这个值在原数组中的下标即可。

有了这样一个思路之后，我们看下生成后的数组[1,2,2,3,3,3]，每一位上的概率相等，所以应当是生成一个1<=x<=6的随机整数，而这个6对应的也是原数组[1,2,3]所有值之合，所以就变成了新的关系

【1】=》1，【2,3】=》2，【4,5,6】=》3

这样是不是大概就可以看出来了，此处前缀和的方式比较合适，把原来的[1,2,2,3,3,3]的数组，压缩成为[1,3,6]的数组，随机了一个1到6之间的值之后，在这个数组中找到对应的索引，就是原来数组[1,2,3]对应的索引值，返回即可。查找的这个过程一般来说用二分查找，不过看数据量，直接遍历查找也可以。

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

• 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
• 翻转后单词间应当仅用一个空格分隔。
• 翻转后的字符串中不应包含额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。

示例 4：

输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"

示例 5：

输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

进阶：

• 请尝试使用 O(1) 额外空间复杂度的原地解法。

public String reverseWords2(String s) {
        String[] arr = s.split(" ");
        if (arr.length == 1){
            return arr[0];
        }
        StringBuilder sb = new StringBuilder();
        sb.append(arr[arr.length-1]);
        int i = arr.length-2;
        while (i >= 0) {
            if (arr[i].length()>0){//判空很重要
                sb.append(" ").append(arr[i]);
            }
            i--;
        }
        return sb.toString();
    }

O（1）空间的java里面应该是实现不了，如果哪位大神有啥思路的可以提供下，我就整出来个char[]上原地翻转实现的，而且最后还是的new String ,再trim()实现

思路是这样的，先把String型的字符转成char[]，在这过程中需要把中间重复的空格去掉，或者说是挪到char[]的结尾部分。写了一个moveRedundantSpace方法，把中间多余的空格去除掉，或者说挪到数组结尾。

然后对char[]数组从头到整体翻转，然后再次遍历，根据空格判断单词分割，分别对每个单词重新翻转，这样单个单词的字符顺序就翻转回来了。代码里面这边的单词翻转部分是在写去除重复空格之前写的，所以还保留了之前有重复空格时候的do/while判断。

  class Solution {
    public String reverseWords(String s) {
        char[] arr = s.toCharArray();
        moveRedundantSpace(arr);
        int left = 0;
        int right = arr.length-1;
        reverse(arr,left,right);

        //挨个单词翻转
        int index1;
        int index2;
        int i = 0;
        while (i <= arr.length-1){
            if (arr[i] != ' ') {
                index1 = i;
                do {
                    i++;
                } while (i <= arr.length - 1 && arr[i] != ' ');
                index2 = i-1;
                reverse(arr,index1,index2);
            }
            i++;
        }
        return (new String(arr)).trim();
    }

    public void reverse(char[] arr, int left ,int right){
        while (left < right){
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }

    public void moveRedundantSpace(char[] arr){
        int cur = 1;
        for (int index = 1;index < arr.length; index++){
            while (cur < arr.length && arr[cur] == ' ' && arr[cur-1] == ' '){
                cur++;
            }
            if (cur < arr.length){
                arr[index] = arr[cur];
            }else{
                arr[index] = ' ';
            }
            cur++;
        }
    }
}

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
示例 2：

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
示例 3：

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]
 

提示：

1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6

题解

8月28每日一题

class Solution {
    public int[] runningSum(int[] nums) {
        int i = 1;
        while(i <= nums.length-1){
            nums[i] = nums[i] + nums[i-1];
            i++;
        }
        return nums;
    }
}

求前序合基本操作

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

• 给定链表的结点数介于 1 和 100 之间。

题解

直观第一反应就是双指针，一个直接往末尾跑，另一个每当往末尾跑的指针跑了两下的时候，往后跑一下。不过也可以最简单的，从头跑到尾知道有多长了之后再取中间那个，取中间那个可以再从头跑一遍，也可以把跑过的记录存起来记录是第几个，然后直接取对应的中间那个。

先双指针：

class Solution {

    int curIndex = 1;

    public ListNode middleNode(ListNode head) {
        ListNode mid = head;
        ListNode cur = head;
        while (cur.next != null){
            cur = cur.next;
            curIndex = curIndex==2?1:curIndex+1;
            if (curIndex==2){
                mid = mid.next;
            }
        }
        return mid;
    }
}

也可以不用curIndex变量记录。直接在while循环里尝试访问cur.next.next

class Solution {

    public ListNode middleNode(ListNode head) {
        ListNode mid = head;
        ListNode cur = head;
        while (cur.next != null){
            cur = cur.next;
            if (cur.next !=null){
                cur =cur.next;
            }
            mid = mid.next;
        }
        return mid;
    }
}

再写个List集合的

class Solution {

    public ListNode middleNode(ListNode head) {
        if (head==null)return null;
        List<ListNode> list = new ArrayList<>();
        list.add(head);
        while (head.next != null){
            head = head.next;
            list.add(head);
        }
        return list.get(list.size()/2);
    }
}

跑了一下看看好像List集合的比双指针的占用内存还小点？还是服务器问题？

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。

示例 1：

输入：root = [1,0,1,0,1,0,1]
输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

示例 2：

输入：root = [0]
输出：0

示例 3：

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

示例 4：

输入：root = [1,1]
输出：3

提示：

• 树中的结点数介于 1 和 1000 之间。
• Node.val 为 0 或 1 。

题解

二叉树、二进制。好说，顺便复习下上次的LeetCode刷题【190】 颠倒二进制位，具体的二进制相关操作符和逻辑：

与&：0&0=0 0&1=0 1&0=0 1&1=1
或|：0|0=0 0|1=1 1|0=1 1|1=1
异或^：0^0=0 0^1=1 1^0=1 1^1=0
取反~：~1=0 ~0=1
左移<<：左边的二进制位丢弃，右边补0
右移>>：正数左补0，负数左补1，右边丢弃
无符号左移<<<：左边的二进制位丢弃，右边补0
无符号右移>>>：忽略符号位，空位都以0补齐

深搜往下，每下一层，左移（<<）一位，此时末位为0，然后把当前节点的值放在末位，也就是或（|）或者是异或（^）操作都可以。

然后就是判断什么是叶子节点了，这个也简单，只要是没有子节点了的都是叶子节点，也就是左右子节点都为空。遇到叶子节点的时候，把这个时候得到的值加到结果上即可。

class Solution {
    int res = 0;
    public int sumRootToLeaf(TreeNode root) {
        dfs(0,root);
        return res;
    }

    public void dfs(int num, TreeNode root){
        if(root == null){
            return;
        }
        num = num << 1 | root.val;
        if (root.left == null && root.right == null){
            res += num;
        }
        dfs(num, root.left);
        dfs(num, root.right);
    }
}

左移一位也可以改为直接乘以2

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

提示：

• 1 <= people.length <= 50000
• 1 <= people[i] <= limit <= 30000

题解

8月26每日一题

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        //limit 必然大于 people的最大值，不然就有人走不了
        //所以从最重的人开始上船。每次尝试看看能否带上当前还没上船的最轻的人，如果不能则自己走，
        // 等下一个稍微轻一点的人再来尝试带走这个轻一点的人
        int  count = 0;
        int left = 0;
        int right = people.length-1;
        while (left < right){
            if (people[right]+people[left] <= limit){
                left++;
            }
            right--;
            count++;
        }
        //最后只剩下一个人了
        if (left==right){
            count++;
        }
        return count;
    }
}

直接用了Arrays.sort(people)，本题应该重点还是是双指针，排序这块省去