爱生气的书店老板

问题描述:

今天,书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。
在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。
书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X 分钟不生气,但却只能使用一次。
请你返回这一天营业下来,最多有多少客户能够感到满意的数量。
 
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/grumpy-bookstore-owner

思路:

题解:

最长的斐波那契子序列的长度

问题描述:

如果序列 X_1, X_2, ..., X_n 满足下列条件,就说它是 斐波那契式 的:
n >= 3
对于所有 i + 2 <= n,都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列,找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在,返回  0 。
(回想一下,子序列是从原序列 A 中派生出来的,它从 A 中删掉任意数量的元素(也可以不删),而不改变其余元素的顺序。例如, [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列)

示例 1:
输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为:[1,2,3,5,8] 。

示例 2:
输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有:
[1,11,12],[3,11,14] 以及 [7,11,18] 。
 
提示:
3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
(对于以 Java,C,C++,以及 C# 的提交,时间限制被减少了 50%)

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence

思路:

题解:

我的日程安排表 I

问题描述:

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排,则可以存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排,注意,这里的时间是半开区间,即 [start, end), 实数 x 的范围为,  start <= x < end。
当两个日程安排有一些时间上的交叉时(例如两个日程安排都在同一时间内),就会产生重复预订。
每次调用 MyCalendar.book方法时,如果可以将日程安排成功添加到日历中而不会导致重复预订,返回 true。否则,返回 false 并且不要将该日程安排添加到日历中。
请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例 1
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
解释:
第一个日程安排可以添加到日历中. 第二个日程安排不能添加到日历中,因为时间 15 已经被第一个日程安排预定了。
第三个日程安排可以添加到日历中,因为第一个日程安排并不包含时间 20 。

说明:
每个测试用例,调用 MyCalendar.book 函数最多不超过 100次。
调用函数 MyCalendar.book(start, end)时, start 和 end 的取值范围为 [0, 10^9]。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/my-calendar-i

思路:

不能加入日程的情况有3种:
1、开始时间不合适,在某个日程的开始和结束日程的中间
2、结束时间不合适,在某个日程的开始和结束日程的中间
3、开始时间和结束时间涵盖某个日程
用一个二维vector来存储所有的日程,其中每行表示一个日程,每行的第一个元素表示每个日程的开始时间,每行的第二个元素表示每个日程的结束时间。
在一个新的日程到来之时,遍历所有已存在的日程,如果有冲突,返回false;否则将新日程插入到日程表中,并返回true。
需要注意,在判断冲突的时候,是大于还是大于等于,是小于还是小于等于。

题解:

class MyCalendar {
public:
    vector<int> tmp;
    vector<vector<int>> vec;

    MyCalendar() {

    }

    bool book(int start, int end) {
        int n = vec.size();
        for (int i = 0; i < n; i++) {
            if ((start >= vec[i][0] && start < vec[i][1]) || (vec[i][0] < end && vec[i][1] >= end) ||
                (start <= vec[i][0] && end >= vec[i][1])) {
                return false;
            }
        }
        tmp.push_back(start);
        tmp.push_back(end);
        vec.push_back(tmp);
        tmp.clear();
        return true;
    }
};

不相交的线

问题描述:

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
现在,我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线,只要 A[i] == B[j],且我们绘制的直线不与任何其他连线(非水平线)相交。
以这种方法绘制线条,并返回我们可以绘制的最大连线数。

示例 1:
输入:A = [1,4,2], B = [1,2,4]
输出:2
解释:
我们可以画出两条不交叉的线,如上图所示。
我们无法画出第三条不相交的直线,因为从 A[1]=4 到 B[2]=4 的直线将与从 A[2]=2 到 B[1]=2 的直线相交。

示例 2:
输入:A = [2,5,1,2,5], B = [10,5,2,1,5,2]
输出:3

示例 3:
输入:A = [1,3,7,1,7,5], B = [1,9,2,5,1]
输出:2
 
提示:
1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/uncrossed-lines

思路:

啊啊啊!!这个题是动态规划中的最长公共子序列问题!!
懒得写思路了,什么都不想干~
等我想起来的时候吧,贴一张图吧,很简单易懂。

题解:

class Solution {
public:
    int maxUncrossedLines(vector<int> &A, vector<int> &B) {
        int n1 = A.size() + 1;
        int n2 = B.size() + 1;
        vector<vector<int>> dp;
        dp.resize(n1);
        for (int i = 0; i < n1; i++) {
            dp[i].resize(n2);
        }
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n2; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else {
                    if(A[i-1]==B[j-1]){
                        dp[i][j]=dp[i-1][j-1]+1;
                    } else{
                        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                    }
                }
            }
        }
        return dp[n1-1][n2-1];
    }
};

在 D 天内送达包裹的能力

问题描述:

传送带上的包裹必须在 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 <= 50000
1 <= weights[i] <= 500

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days

思路:

题解: