class Solution {
public://author:qiuqian,freebug，，思路：用一个hashmap存住words中出现的词的所有次数，然后按照words.size()*words[0]的长度，依次选取s的字串，
    //然后在该字串中按照words[0]的长度在选字串，在hashmap中进行匹配，匹配上就减1，最后判断hashmap中的所有字串数目都为0，为0就把该索引放入结果
    //否则重新循环。time：o(n^2)
    vector<int> findSubstring(string s, vector<string>& words) {
        int vec_len = words.size();
        int word_len = words[0].size();
        int len = vec_len * word_len;
        vector<int> res;
        for(int i = 0;i < s.size()-len+1;i++){
            unordered_map<string,int> m;
            for(auto word:words) m[word]++;
            string tmp = s.substr(i,len);
            for(int j = 0;j < len;j += word_len){
                string cur = tmp.substr(j,word_len);
                if(m.find(cur) != m.end() && m[cur] > 0){
                    m[cur]--;
                }else break;
            }
            auto it = m.begin();
            for(;it != m.end();it++){
                if(it->second != 0) break;
            }
            if(it == m.end()) res.push_back(i);
        }
        return res;
    }
};

class Solution {
private:
    int left = 0;
    int right = 0;
    int begin = 0;
    int end = 0;
    int tmp = INT_MAX;
    vector<int> needfound = vector<int>(128,0);
    vector<int> isfound = vector<int>(128,0);
public://author:qiuqian
    string minWindow(string s, string t) {
        for(auto &x:t) needfound[x]++;
        int count = t.size();
        isfound[s[0]]++;
        if(needfound[s[0]] >= isfound[s[0]]) count--;
        while(1){
            if(count == 0){
                while(isfound[s[begin]] > needfound[s[begin]]){
                    isfound[s[begin]]--;
                    begin++;
                }
                int len = end-begin+1;
                if(len < tmp){
                    right = end;
                    left = begin;
                    tmp = len;
                }
            }
            if(end < s.size()){
                end++;
                isfound[s[end]]++;
                if(needfound[s[end]] >= isfound[s[end]]) count--;
            }else break;
        }
        if(tmp == INT_MAX) return "";
        else return s.substr(left,tmp); 
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == NULL) return NULL;
        ListNode* p = head;
        ListNode* first = new ListNode(0);
        ListNode* newhead = first;
        first->next = p;
        while(p != NULL){
            if(p->val < x){
                first = p;
                p = p->next;
            }else{
                break;
            }
        }
        ListNode* second = new ListNode(0);
        while(p != NULL){
            if(p->val < x){
                p = p->next;
                second->next->next = first->next;
                first->next = second->next;
                first = first->next;
                second->next = p;
            }else{
                second = p;
                p = p->next;
            }
        }
        return newhead->next;
    }
};