链表求和 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

 

示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912
进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912
通过次数19,209提交次数41,659

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-lists-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return l1;

        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode dummyNode = new ListNode(0);

        dummyNode.next = l1;
        ListNode pre = null;

        ListNode sumNode = dummyNode.next;

        int carry = 0;
        while (p1 != null && p2 != null) {              //l1和l2共同的
            int sum = p1.val + p2.val + carry;
            if (sum > 9) {
                sum = sum % 10;
                carry = 1;
            } else {
                carry = 0;
            }
            sumNode.val = sum;
            pre = sumNode;
            sumNode = sumNode.next;
            p1 = p1.next;
            p2 = p2.next;
        }

        while (p1 != null) {                            //l1比l2多出的
            int sum = p1.val + carry;
            if (sum > 9) {
                sum = sum % 10;
                carry = 1;
            } else {
                carry = 0;
            }
            sumNode.val = sum;
            pre = sumNode;
            sumNode = sumNode.next;
            p1 = p1.next;
        }
        while (p2 != null) {                            //l2比l1多出的
            int sum = p2.val + carry;
            if (sum > 9) {
                sum = sum % 10;
                carry = 1;
            } else {
                carry = 0;
            }
            if (sumNode == null) {
                pre.next = new ListNode(0);
                sumNode = pre.next;
                pre = sumNode;
            }
            sumNode.val = sum;
            pre = sumNode;
            sumNode = sumNode.next;
            p2 = p2.next;
        }
        if (carry > 0) {
            pre.next = new ListNode(carry);
        }

        return dummyNode.next;
    }
}

展开全文 >>

分割链表

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

示例:

输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return head;
        ListNode dummyNode1 = new ListNode(0);
        ListNode dummyNode2 = new ListNode(0);

        ListNode cur = head;

        ListNode node1 = dummyNode1;
        ListNode node2 = dummyNode2;

        while (cur != null) {
            ListNode nex = cur.next;            //当前节点的下一节点
            if (cur.val < x) {                  //小于x放到dummyNode1
                node1.next = cur;
                node1 = node1.next;
                node1.next = null;              //从原链表断开
            } else {                            //大于等于x放到dummyNode2
                node2.next = cur;
                node2 = node2.next;
                node2.next = null;              //从原链表断开
            }
            cur = nex;
        }

        node1.next = dummyNode2.next;

        return dummyNode1.next;
    }
}

展开全文 >>

买卖股票的最佳时机4 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

0 <= k <= 109
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
通过次数41,979提交次数130,412
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0 || k == 0) return 0;
        if (k > prices.length / 2) {
            return maxProfit(prices);
        }

        int[][][] dp = new int[prices.length][k + 1][2];
        //第一维是第i天，第二维是目前交易的次数j，第三维是当前是否持有股票dp[i][j][0]是不持有股票，dp[i][j][1]是持有股票

        //只有买入股票时才消耗交易的次数

        for (int i = 0; i <= k; i++) {
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }

        for (int i = 1; i < prices.length; i++) {
            for (int j = 1; j<=k; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[prices.length - 1][k][0];
    }

    
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;                                                   //第一天不持有股票，既没有花钱也没有盈利
        dp[0][1] = -prices[0];                                          //第一天持有股票是当天买入的结果
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);//今天没有持有股票=（昨天没有持有股票）和（昨天持有股票，今天卖出）
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);//今天持有股票=（昨天持有股票）和（昨天没有持有股票，今天买入）
        }
        return dp[prices.length - 1][0];                                //最后一天不持有股票一定比持有股票的盈利多
    }
}

展开全文 >>

股票问题通解

动态规划表设置

第一维是第i天，第二维是目前交易的次数k，第三维是当前是否持有股票dp[i][k][0]是不持有股票，dp[i][k][1]是持有股票

基准情况

1
2
dp[-1][k][0] = 0, dp[-1][k][1] = -Infinity
dp[i][0][0] = 0, dp[i][0][1] = -Infinity

状态转移方程

1
2
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


注意到允许的最大交易次数是不变的，因为每次交易包含两次成对的操作，**买入**和**卖出**。只有**买入**操作会改变允许的最大交易次数。



1、对于状态转移方程中的```dp[i][k][0]```,第```i```天进行的操作只能是**休息**或**卖出**，因为在第```i```天结束时持有的股票数量是0. 


- ```dp[i-1][k][0]```是**休息**操作可以得到的最大收益
- ```dp[i-1][k][1]+pricepi[i]```是**卖出**操作可以得到的最大收益。


2、对于状态转移方程中的```dp[i][k][1]```,第i天进行的操作只能是**休息**或**买入**，因为在第```i```天结束时持有的股票数量是```1```. 

- ```dp[i-1][k][1]```是**休息**操作可以得到的最大收益
- ```dp[i-1][k-1][1]+price[i]```是**买入**操作可以得到的最大收益。

注意到允许的最大交易次数减少了一次，因为每次**买入**操作会使用一次交易。


为了得到最后一天结束时的最大收益，可以遍历股票价格数组，根据状态转移方程计算```dp[i][k][0]``` 和 ```dp[i][k][1]``` 的值。最终答案是 ```dp[n - 1][k][0]```，因为结束时持有 ```0``` 份股票的收益一定大于持有 ```1``` 份股票的收益。

----
<br>

# 当k=1时，即仅允许交易一次


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

1
2
3
4

所有的k都是1，即退化为

**基准情况**

dp[0][0] = 0;
dp[0][1] = -prices[0];

1
**状态转移方程**

dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+price[i])
dp[i][1]=Math.max(dp[i-1][1],-price[i]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

```java
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        return dp[length - 1][0];
    }
}

当k为正无穷时，可以任意次交易

如果 k 为正无穷，则 k 和 k - 1 可以看成是相同的

1
2
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]) = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])

基准情况

1
2
dp[0][0] = 0;
dp[0][1] = -prices[0];

状态转移方程

1
2
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+price[i])
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-price[i]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[length - 1][0];
    }
}

当k=2时，即仅允许交易两次

基准情况

1
2
3
4
dp[0][1][0] = 0;
dp[0][1][1] = -prices[0];
dp[0][2][0] = 0;
dp[0][2][1] = -prices[0];

状态转移方程

1
2
3
4
dp[i][2][0] = max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
dp[i][2][1] = max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]) = max(dp[i - 1][1][1], -prices[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][][] dp = new int[length][3][2];
        dp[0][1][0] = 0;
        dp[0][1][1] = -prices[0];
        dp[0][2][0] = 0;
        dp[0][2][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i]);
            dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i]);
            dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i]);
            dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]);
        }
        return dp[length - 1][2][0];
    }
}

当 0<= K <=price.length/2 时

一个有收益的交易至少需要两天（在前一天买入，在后一天卖出，前提是买入价格低于卖出价格）。如果股票价格数组的长度为 n，则有收益的交易的数量最多为 $n / 2$（整数除法）。因此 k 的临界值是 $n / 2$。如果给定的 k 不小于临界值，即 $k >= n / 2$，则可以将 k 扩展为正无穷，此时问题等价于情况二。

可以写出时间复杂度为 $O(nk)$ 和空间复杂度为 $O(nk)$ 的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        if (k >= length / 2) {
            return maxProfit(prices);
        }
        int[][][] dp = new int[length][k + 1][2];
        for (int i = 1; i <= k; i++) {
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }
        for (int i = 1; i < length; i++) {
            for (int j = k; j > 0; j--) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[length - 1][k][0];
    }

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[length - 1][0];
    }
}

k为正无穷但有冷却时间

但是在有「冷却时间」的情况下，如果在第 i - 1 天卖出了股票，就不能在第 i 天买入股票。因此，如果要在第 i 天买入股票，第二个状态转移方程中就不能使用dp[i - 1][k][0]，而应该使用 dp[i - 2][k][0]。状态转移方程中的别的项保持不变，新的状态转移方程如下：

1
2
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 2][k][0] - prices[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);               //今天没有持有股票=（昨天没有持有股票）和（昨天持有股票，今天卖出）
            dp[i][1] = Math.max(dp[i - 1][1], (i >= 2 ? dp[i - 2][0] : 0) - prices[i]);//今天持有股票=（昨天持有股票）和（前天没有持有股票今天买入）
        }
        return dp[length - 1][0];
    }
}

k为正无穷但有手续费

由于需要对每次交易付手续费，因此在每次买入或卖出股票之后的收益需要扣除手续费，新的状态转移方程有两种表示方法。

第一种表示方法，在每次买入股票时扣除手续费：

1
2
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i] - fee)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0] - fee;
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);
        }
        return dp[length - 1][0];
    }
}

第二种表示方法，在每次卖出股票时扣除手续费：

1
2
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i] - fee)
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[length - 1][0];
    }
}

参考文献

作者：Storm股票问题系列通解（转载翻译）

1
2
3
4
作者：Storm
链接：https://leetcode-cn.com/circle/article/qiAgHn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

吃苹果的最大数目

1705. 吃苹果的最大数目

难度：中等

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。

你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。

给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

示例 1：

1
2
3
4
5
6
7
输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
输出：7
解释：你可以吃掉 7 个苹果：
- 第一天，你吃掉第一天长出来的苹果。
- 第二天，你吃掉一个第二天长出来的苹果。
- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
- 第四天到第七天，你吃的都是第四天长出来的苹果。

示例 2：

1
2
3
4
5
6
输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
输出：5
解释：你可以吃掉 5 个苹果：
- 第一天到第三天，你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天，你吃的都是第六天长出来的苹果。

提示：

  • apples.length == n
  • days.length == n
  • 1 <= n <= 2 * 104
  • 0 <= apples[i], days[i] <= 2 * 104
  • 只有在 apples[i] = 0 时，days[i] = 0 才成立

优先队列

新产生的和过期日期早的相比，过期日期早的先吃掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int eatenApples(int[] apples, int[] days) {
        PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(x -> x[0]));
        int day = 0;
        for (int i = 0; ; i++) {
            if (i < apples.length && apples[i] > 0) {
                q.offer(new int[]{i + days[i], apples[i]});                     //在i+days[i]过期日期有apples[i]个苹果
            } else if (i >= apples.length && q.isEmpty()) {                     //当没有苹果产生时，队列为空就不会再有苹果了
                break;
            }
            while (!q.isEmpty() && (q.peek()[0] <= i || q.peek()[1] <= 0)) {    //如果已经过期或者当前index有0个苹果
                q.poll();                                                       //取出
            }
            if (!q.isEmpty()) {                                                 //如果队列不为空
                q.peek()[1] -= 1;                                               //把过期日期早的苹果吃掉
                day++;                                                          //天数+1
            }
        }
        return day;
    }
}

参考文献

作者：xhldtc，优先队列方法

展开全文 >>

平均等待时间 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
有一个餐厅，只有一位厨师。你有一个顾客数组 customers ，其中 customers[i] = [arrivali, timei] ：

arrivali 是第 i 位顾客到达的时间，到达时间按 [非递减] 顺序排列。
timei 是给第 i 位顾客做菜需要的时间。
当一位顾客到达时，他将他的订单给厨师，厨师一旦空闲的时候就开始做这位顾客的菜。每位顾客会一直等待到厨师完成他的订单。厨师同时只能做一个人的订单。厨师会[严格按照 订单给他的顺序 ]做菜。

请你返回所有顾客需要等待的 [平均] 时间。与标准答案误差在 10-5 范围以内，都视为正确结果。

示例 1：

输入：customers = [[1,2],[2,5],[4,3]]
输出：5.00000
解释：
1) 第一位顾客在时刻 1 到达，厨师拿到他的订单并在时刻 1 立马开始做菜，并在时刻 3 完成，第一位顾客等待时间为 3 - 1 = 2 。
2) 第二位顾客在时刻 2 到达，厨师在时刻 3 开始为他做菜，并在时刻 8 完成，第二位顾客等待时间为 8 - 2 = 6 。
3) 第三位顾客在时刻 4 到达，厨师在时刻 8 开始为他做菜，并在时刻 11 完成，第三位顾客等待时间为 11 - 4 = 7 。
平均等待时间为 (2 + 6 + 7) / 3 = 5 。
示例 2：

输入：customers = [[5,2],[5,4],[10,3],[20,1]]
输出：3.25000
解释：
1) 第一位顾客在时刻 5 到达，厨师拿到他的订单并在时刻 5 立马开始做菜，并在时刻 7 完成，第一位顾客等待时间为 7 - 5 = 2 。
2) 第二位顾客在时刻 5 到达，厨师在时刻 7 开始为他做菜，并在时刻 11 完成，第二位顾客等待时间为 11 - 5 = 6 。
3) 第三位顾客在时刻 10 到达，厨师在时刻 11 开始为他做菜，并在时刻 14 完成，第三位顾客等待时间为 14 - 10 = 4 。
4) 第四位顾客在时刻 20 到达，厨师拿到他的订单并在时刻 20 立马开始做菜，并在时刻 21 完成，第四位顾客等待时间为 21 - 20 = 1 。
平均等待时间为 (2 + 6 + 4 + 1) / 4 = 3.25 。

提示：

1 <= customers.length <= 105
1 <= arrivali, timei <= 104
arrivali <= arrivali+1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/average-waiting-time
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

其实是一道简单题，需要注意是否出现溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public double averageWaitingTime(int[][] customers) {
        if (customers.length == 0) return 0;
        int curTime = 0;
        long sumWait = 0;
        curTime = customers[0][0];
        for (int i = 0; i < customers.length; i++) {

            curTime = Math.max(customers[i][0], curTime);
            curTime = curTime + customers[i][1];
            int wait = curTime - customers[i][0];
            sumWait += wait;
        }

        return sumWait * 1.0 / customers.length;
    }
}

展开全文 >>

无法吃午餐的学生数量 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：

如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
否则，这名学生会 放弃这个三明治 并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i​​​​​​ 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j​​​​​​ 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。

示例 1：

输入：students = [1,1,0,0], sandwiches = [0,1,0,1]
输出：0 
解释：
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,0,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,0,1,1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [0,1,1]，三明治栈为 sandwiches = [1,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,1,0]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1,0]，三明治栈为 sandwiches = [0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1]，三明治栈为 sandwiches = [1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = []，三明治栈为 sandwiches = []。
所以所有学生都有三明治吃。
示例 2：

输入：students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
输出：3
 

提示：

1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i] 要么是 0 ，要么是 1 。
students[i] 要么是 0 ，要么是 1 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-students-unable-to-eat-lunch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

因为学生的数量比较少，所以直接暴力模拟，不新建队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {

    public int countStudents(int[] students, int[] sandwiches) {
        if (students.length == 0) return 0;
        if (sandwiches.length == 0 && students.length > 0) return students.length;
        boolean[] stu = new boolean[students.length];                               //指示是否已经吃到午餐
        int stuPoint = 0;                                                           //当前学生的指针
        int sanPoint = 0;                                                           //当前午餐的指针
        int stuLen = students.length;                                               //学生的数量
        int sanLen = sandwiches.length;                                             //午餐的数量

        int stuCount = stuLen;                                                      //当前没吃到午餐的学生的数量
        boolean stepFlag = true;
        int step = 0;                                                               //指示是否走了一圈但是没人能吃到午餐，如果大于stuLen就说明这一圈谁也没吃到
        while (stepFlag) {
            if (step > stuLen) {                                                    //走了一圈没人吃到，那么结束         
                return stuCount;
            }
            int stuIndex = stuPoint % stuLen;                                       //当前学生的index
            int sanIndex = sanPoint % sanLen;                                       //当前午餐的index
            while (stu[stuIndex]) {                                                 //如果已经吃到午餐了，就换下一个
                stuPoint++;
                stuIndex = stuPoint % stuLen;
            }
            if (!stu[stuIndex] && students[stuIndex] == sandwiches[sanIndex]) {     //如果这个午餐符合学生的胃口，就被吃掉

                stu[stuIndex] = true;
                stuPoint++;                                                         //学生和午餐指针同时步进1
                sanPoint++;
                step = 0;                                                           //走的数量归0
                stuCount--;                                                         //没吃到午餐的人的数量减1
                if (stuCount == 0) return 0;                                        //所有学生都吃到午餐了，那么结束
            } else {
                stuPoint++;
            }

            step++;
        }
        return 0;
    }
}

维护喜欢每种三明治的人的数量，当喜欢某个种类的三明治的人的数量为0时，所有的人都不喜欢栈顶部的三明治，剩下的人都吃不长了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        if (students == null || students.length == 0) return 0;
        if (sandwiches == null || sandwiches.length == 0) return students.length;
        // stuLike[0] 喜欢圆形的学生数，stuLike[1]喜欢方形的学生数
        int[] stuLike = new int[2];
        for (int student : students) {
            stuLike[student]++;
        }
        for (int i = 0; i < sandwiches.length; i++) {
            if (stuLike[sandwiches[i]] == 0) {
                // 学生是转圈来的，此时说明喜欢圆形或者方形的学生已经没有了，顶部的三明治没人取走了。
                break;
            }
            // 对应的学生满足一个，减少一个
            stuLike[sandwiches[i]]--;
        }
        return stuLike[0] + stuLike[1];
    }
}

参考文献

作者：bo-he-f 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

同构字符串 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

输入: s = "egg", t = "add"
输出: true
示例 2:

输入: s = "foo", t = "bar"
输出: false
示例 3:

输入: s = "paper", t = "title"
输出: true
说明:
你可以假设 s 和 t 具有相同的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/isomorphic-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一个哈希表一个集合

只要保证t中每个字符到s中的每个字符的映射可以还原s，并且t中的键对应的值是唯一的，就可以保证s和t是同构的。

1
2
3
4
5
6
7
8
9
10
11
12
s：    egg
       |||
t:     add

映射为e-a,g-d.  通过遍历t,再用map映射回去可以得到egg,并且t中的每个键值的对应都是双向唯一的，所以是同构的字符串


s:    foo
      |||
t:    bar

映射为b-f,a-o,r-o  通过遍历t，再用map映射回去可以得到foo，但是t中的每个键值的对应不是双向唯一的，所以不是同构的字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null || t == null) return false;
        if (s.length() != t.length()) return false;
        Map<Character, Character> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {                      //将t的每个字符映射到s
            char sc = s.charAt(i);
            char st = t.charAt(i);
            map.put(st, sc);
        }

        Set<Character> set = new HashSet<>();                       //保证t的每个键对应的值是唯一的
        StringBuilder bd = new StringBuilder();
        for (int i = 0; i < t.length(); i++) {
            char tChar = t.charAt(i);
            char sChar = map.get(tChar);
            bd.append(sChar);
            set.add(sChar);
        }
        String tTos = bd.toString();                                //查看通过t的映射可不可以得到s

        if (set.size() == map.size() && tTos.equals(s)) return true;
        return false;
    }
}

双哈希表

需要我们判断 s 和 t 每个位置上的字符是否都一一对应，即 s 的任意一个字符被 t 中唯一的字符对应，同时 t 的任意一个字符被 s 中唯一的字符对应。这也被称为「双射」的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<Character, Character>();
        Map<Character, Character> t2s = new HashMap<Character, Character>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }
}

参考文献

作者：LeetCode-Solution来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

1至n整数中1出现的次数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5
示例 2：

输入：n = 13
输出：6

限制：

1 <= n < 2^31
注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
10,11,12,13,14,15,16,17,18,19,

1

1
2


展开全文 >>

栈的压入弹出序列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
注意：本题与主站 946 题相同：https://leetcode-cn.com/problems/validate-stack-sequences/

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (popped.length != pushed.length) return false;
        if (pushed.length == 0 || popped.length == 0) return true;

        Stack<Integer> stack = new Stack<>();

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < pushed.length; i++) {
            map.put(pushed[i], i);                                      //哈希表记录每个元素在入栈序列中的index
        }

        int lastIndex = -1;
        for (int i = 0; i < popped.length; i++) {
            int index = map.get(popped[i]);                            //获取这个元素在入栈序列中的index
            if (!stack.isEmpty() && stack.peek() == popped[i]) {       //这个元素是栈顶元素，那么符合条件可以弹出
                stack.pop();
            } else {
                for (int j = lastIndex + 1; j < index; j++) {          //把入栈序列中它左边的元素全部加入栈中
                    stack.push(pushed[j]);
                }
            }
            lastIndex = Math.max(index, lastIndex);                    //记录上次的最靠右的那个index
        }

        if (!stack.isEmpty()) {                                        //如果最后栈不为空说明有元素不满足条件
            return false;
        }

        return true;
    }
}

不使用哈希表

  • 如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；
  • 如果下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字压入栈中，直到把下一个需要弹出的数字压入栈顶为止；
  • 如果所有数字都压入栈后仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (popped.length != pushed.length) return false;
        if (pushed.length == 0 || popped.length == 0) return true;
        Stack<Integer> stack = new Stack<>();
        int maxIndex = -1;

        for (int i = 0; i < popped.length; i++) {
            if (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
            } else if (stack.isEmpty() || stack.peek() != popped[i]) {
                for (int j = maxIndex + 1; j < pushed.length; j++) {
                    maxIndex = j;
                    if (pushed[j] != popped[i]) {
                        stack.push(pushed[j]);
                    } else {
                        break;
                    }
                }
            }
        }

        if (!stack.isEmpty()) {
            return false;
        }

        return true;
    }
}

参考文献

剑指Offer第二版

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走