HHR的小站
享受代码带来的快乐吧
首页

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值  gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj  。如果  sj >= g  ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

注意:

你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。

示例 1:

输入: [1,2,3], [1,1]

输出: 1

解释:
 你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
 虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
 所以你应该输出1。

示例 2:

输入: [1,2], [1,2,3]

输出: 2

解释:  
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。 
你拥有的饼干数量和尺寸都足以让所有孩子满足。 
所以你应该输出2. 

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int findContentChildren(vector<int> &g, vector<int> &s) {
        if (s.empty()) return 0;
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int seat = -1, num = 0;
        for (int child:g) {
            seat++;
            while (seat < s.size() && child > s[seat]) {
                seat++;
            }
            if (seat == s.size()) break;
            num++;
        }
        return num;
    }
};

从胃口小的孩子开始分配,如果胃口小的孩子没饼干吃,那胃口大的左佑就只能饿着了。

https://leetcode-cn.com/problems/assign-cookies/

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值index1 和 index2,其中 index1 必须小于 index2

说明:

  • 返回的下标值(index1 和 index2)不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        int i = 0, j = numbers.size() - 1;
        while (target != numbers[i] + numbers[j]) {
            if (target > numbers[i] + numbers[j]) {
                i++;
            } else {
                j--;
            }
        }
        vector<int> ans;
        ans.push_back(i + 1);
        ans.push_back(j + 1);
        return ans;
    }
};

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明:

  1. 不能更改原数组(假设数组是只读的)。
  2. 只能使用额外的 O(1) 的空间。
  3. 时间复杂度小于 O(n2) 。
  4. 数组中只有一个重复的数字,但它可能不止重复出现一次。

class Solution {
public:
    int findDuplicate(vector<int> &nums) {
        int i = 1, j = nums.size() - 1;
        while (i != j) {
            int m = (i + j) / 2, count = 0;
            for (int num:nums) {
                if (num <= m) count++;
            }
            if (count > m) {
                j = m;
            } else {
                i = m + 1;
            }
        }
        return i;
    }
};

/*
 * 5,1,2,3,4,5,5,7,8,9,10,11
 * 在1-11中寻找
 * 重复的数是6或更小嘛?
 * 数一数发现,<=6的数有7个,说明重复的数<=6
 * 那去1-6中寻找
 * 重复的数<=3嘛?
 * <=3的数只有三个,没问题,重复的数比3大
 * 在4-5中寻找
 * 重复的数<=4嘛?
 * 比4小的数有四个,重复的数比4大
 * 所以,重复的数是5
 */

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]

示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]

说明:

  • 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

进阶:

  • 如果给定的数组已经排好序呢?你将如何优化你的算法?
  • 如果 nums1 的大小比 nums2 小很多,哪种方法更优?
  • 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

#include <vector>
#include <hash_map>

using namespace std;
using namespace __gnu_cxx;

class Solution {
public:
    vector<int> intersect(vector<int> &nums1, vector<int> &nums2) {
        hash_map<int, int> num, num2;
        vector<int> ans;
        for (auto n:nums1) {
            num[n]++;
        }
        for (auto n:nums2) {
            if (num.find(n) != num.end() && num[n] != 0) {
                num[n]--;
                ans.push_back(n);
            }
        }
        return ans;
    }
};

使用hashmap存储第一个数组的内容,然后对数组2中的元素进行遍历,找到重复元素返回

https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。

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

对分查找,注意选好上界

https://leetcode-cn.com/problems/sqrtx/