最接近的三数之和

问题描述：

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest

思路：

暴力法

题解：

class Solution {
public:
    int threeSumClosest(vector<int> &nums, int target) {
        int n = nums.size();
        int a[n + 100];
        int count = 0;
        for (vector<int>::iterator m = nums.begin(); m != nums.end(); m++) {
            a[count] = *m;
            count++;
        }
        sort(a, a + n);
        int linshi;
        int min=0x3f3f3f3f;
        int flag;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int m = j + 1; m < n; m++) {
                    linshi = (a[i] + a[j] + a[m]) - target;
                    if (linshi < 0) {
                        if (0 - linshi <= min) {
                            min = 0 - linshi;
                            flag = linshi+target;
                        }
                    } else {
                        if (linshi <= min) {
                            min = linshi;
                            flag = linshi+target;
                        }
                    }

                }
            }
        }

        return flag;
    }

};

求众数 II

问题描述

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1：
输入: [3,2,3]
输出: [3]

示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element-ii

思路

• 基本思路是用map（之前介绍过map内部实质是pair类型的）。
• 对于map中的每一项，只要它的second值大于n/3，就将其存入返回结果ret中。

题解

class Solution {
public:
    vector<int> majorityElement(vector<int> &nums) {
        map<int, int> table;
        vector<int> ret;
        int n = nums.size();
        if (n == 0) return ret;
        for (int i = 0; i < n; i++) {
            table[nums[i]]++;
        }
        for(auto each:table){
            if(each.second>n/3) ret.push_back(each.first);
        }
        return ret;
    }
};

爱生气的书店老板

问题描述：

今天，书店老板有一家店打算试营业 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;
    }
};