不相交的线

问题描述：

我们在两条独立的水平线上按给定的顺序写下 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

思路：

题解：

区间子数组个数

问题描述：

给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。
求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。

例如 :
输入:
A = [2, 1, 4, 3]
L = 2
R = 3
输出: 3
解释: 满足条件的子数组: [2], [2, 1], [3].

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-subarrays-with-bounded-maximum

思路：

题解：

最长重复子数组

问题描述：

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1:
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。

说明:
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray

思路：

题解：

常数时间插入、删除和获取随机元素

问题描述

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();
// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);
// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);
// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);
// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();
// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);
// 2 已在集合中，所以返回 false 。
randomSet.insert(2);
// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1

思路

基本思路是用map来实现，map<int,int> table;

• 插入
  插入val前先查看table[val]是否等于0；
  如果等于0，则table[val]++,表示集合中插入了val，并return true；
  否则return false；
• 删除
  删除val前先查看table[val]是否等于1；
  如果等于1，则table[val]--,表示从集合中删除val，并return true；
  否则return false；
• 随机返回

将集合中元素存到一个数组中，然后 int n=tmp.size();return tmp[random()%n]即可。

题解

class RandomizedSet {
public:
    /** Initialize your data structure here. */
    map<int,int> table;
    RandomizedSet() {
        
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(table[val]>=1){
            return false;
        } 
        table[val]++;
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(table[val]==1){ 
            table[val]--;
            return true;
        }
        return false;
    }

    /** Get a random element from the set. */
    int getRandom() {
        vector<int> tmp;
        for(auto each:table){
            if(each.second==1){
                tmp.push_back(each.first);
            }
        }
        int n=tmp.size();
        return tmp[random()%n];
    }
};