一.题目描述
Assign Cookies
二题目解法
2.1 暴力大法
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
map<int ,int > index;
int count=0;
for(int i =0;i<g.size();i++){
for(int j = i ;j<s.size();j++){
if(s[j] >= g[i]&&index[j]==0){
count++;
index[j]=i+1;
break;
}
}
}
return count;
}
};
首先我们输入的输入可能是没有序的，这样我们最好先排序然后从前往后找的时候只要找到第一个符合要求的就可以啦,所以用到了这个方法，进行排序
sort(g.begin(),g.end());
然后我们在用双层循环的时候第二层循环的初始条件很难判断(等等，好像这个地方可以优化呀)，可能第一个孩子的要求很高，然后cookie的序号就会很大，等第二个孩子开始的时候从第二个蛋糕开始判断就会导致重复计算，所以加了一个map进行判断，只有符合条件且不在map中的时候才可以。然后现在就还有一个问题，当不在map类中的时候默认返回值为0，而我们实际的位置元素可能就是0，所以对map中cookie对应的孩子序号+1，这样就可以保证不会是0，我们要的仅仅是判断当前的cookie是否有孩子对应，所以序号并不重要。从而解决问题。
2.2 暴力解法的优化
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int count = 0;
int currentj = 0;
for(int i =0;i<g.size();i++){
for(int j = currentj ;j<s.size();j++){
if(s[j] >= g[i]){
count++;
currentj=j+1;
break;
}
}
}
return count;
}
};
由于已经对Cookie的大小进行了判断，所以说，当第i个孩子被第j个cookie满足的同时，第i+1个孩子要想被满足，需要从第j+1个开始，从而简化了之前的许多判断。
看结果
优化后结果
综上，继续加油啦~
