将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：
image.png

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]
 

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode();
        ListNode* p = head;
        while(list1 && list2){
            ListNode* tmp = nullptr;
            if(list1->val < list2->val){
                tmp = list1;
                list1 = list1->next;
            } else {
                tmp = list2;
                list2 = list2->next;
            }
            p->next = tmp;
            p = p->next;
        }
        while(list1){
            p->next = list1;
            list1 = list1->next;
            p = p->next;
        }
        while(list2){
            p->next = list2;
            list2 = list2->next;
            p = p->next;
        }
        return head->next;
    }
};

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

 

示例 1：

输入：nums = [1,3,4,2,2]
输出：2
示例 2：

输入：nums = [3,1,3,4,2]
输出：3
 

提示：

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
 

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

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

二分

要知道对于一个数v，若其不重复则数组中1~v的个数一定≤v 因为如果其重复的话则1~v至少存在两个v 则1~v小于v的个数至少为v+1。
而为什么是≤呢？因为重复数字的个数可能不止一个，所以重复数字越多则1~v中缺失的数就越多所以 要小于等于。
如果cnt <= mid 说明结果一定在 mid+1~nums.size()中 反之亦然，因此可以对结果进行二分。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size(), ans = 0;
        while(l <= r){
            int mid = (l + r) / 2;
            int cnt = 0;
            for(int i = 0; i < nums.size(); i++){
                if(nums[i] <= mid){
                    cnt++;
                }
            }
            // 如果cnt <= mid 说明结果一定在 mid+1~nums.size()中 反之亦然
            if(cnt <= mid){
                l = mid + 1;
            } else {
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }
};

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

 
示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：

输入：n = 1, bad = 1
输出：1
 

提示：

1 <= bad <= n <= 231 - 1

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

二分

不断逼近

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 0, r = n, ans = 0;
        while(l <= r){
            int mid = (r - l)/2 + l;
            if(isBadVersion(mid)){
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
};

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

 

示例 1：

输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 

提示：

0 <= x <= 231 - 1

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

二分

每次取中间不断逼近

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x, ans = 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if((long long)mid*mid <= x){
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。
注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。

输入格式：

每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式：

对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。

输入样例：

3 20 18 15 10 75 72 45

输出样例：

94.50

贪心

每斤最贵。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n;
float d;
struct cake {
    float allPrice;
    float sum;
    float unitPrice;
}cakes[1002];

bool cmp(cake a, cake b){
    return a.unitPrice >= b.unitPrice;
}

int main() {
    cin >> n >> d;
    for(int i = 0; i < n; i++){
        cin >> cakes[i].sum;
    }
    for(int i = 0; i < n; i++){
        cin >> cakes[i].allPrice;
        cakes[i].unitPrice = cakes[i].allPrice / cakes[i].sum;
    }

    sort(cakes, cakes + n, cmp);
    double res = 0;
    for(int i = 0; i < n; i++){
        if(cakes[i].sum <= d){
            res += cakes[i].allPrice;
        } else {
            res += (d * cakes[i].unitPrice);
        }

        d -= min(d, cakes[i].sum) ;
        if(d <= 0){
            break;
        }
    }

    printf("%.2f", res);
    return 0;
}
  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. ...
  9. 109