题目描述

https://leetcode-cn.com/problems/implement-strstr/

代码

思路很简单，就是看怎么实现，写了好久。。

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) {
            return 0;
        }
        int m = haystack.size();
        int n = needle.size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (haystack[i+j] != needle[j]) {
                    break;
                }
                if (j == n - 1) {
                    return i;
                }
            }
        }
        return -1;
    }
};

follow up

上面那个是判断是不是子串，这个题是判断是不是子序列，更简单一些。

392. 判断子序列

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0;
        for (int j = 0; j < t.size(); j++) {
            if (i < s.size() && t[j] == s[i]) {
                i++;
            }
        }
        return i == s.size();
    }
};

再follow up

455. 分发饼干

虽然这个题是贪心算法，和以上题目都没啥关系，但是由于代码写法上的相似，所以接下来做这个题会觉得写起来很爽。
这是典型的利用贪婪算法的题目，我们可以首先对两个数组进行排序，让小的在前面。然后我们先拿最小的cookie给胃口最小的小朋友，看能否满足，能的话，我们结果res自加1，然后再拿下一个cookie去满足下一位小朋友；如果当前cookie不能满足当前小朋友，那么我们就用下一块稍大一点的cookie去尝试满足当前的小朋友。当cookie发完了或者小朋友没有了我们停止遍历。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int res = 0;
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0;
        for (int j = 0; j < s.size(); j++) {
            if (i < g.size() && s[j] >= g[i]) { //满足
                i++;
                res++;
            }
        }
        return res;
    }
};