# 手写代码竞赛 7月6日前要完成的题目 1. Maximal Rectangle 1. Interleaving String 1. Distinct Subsequences 1. Implement strStr 1. Search for a Range 题目描述见 Leetcode <http://leetcode.com/onlinejudge>

Distinct Subsequences.cc

//f(i,j) = f(i+1, j) + (S[i] == T[j]) * f(i+1,j+1)
//means numDistinct(S.substr(i), T.substr(j))
int numDistinct(string S, string T) {
    vector<vector<int> > dp(S.length() + 1, vector<int>(T.length() + 1, 0));
    dp[S.length()][T.length()] = 1;
    for (int i = S.length() - 1; i >= 0; --i) {
        dp[i][T.length()] = 1; //!! empty is every string's subseq
        for (int j = T.length() - 1; j >= 0; --j) {
            dp[i][j] = dp[i+1][j];
            if (S[i] == T[j]) {
                dp[i][j] += dp[i+1][j+1];
            }
        }
    }
    return dp[0][0];
}

Implement strStr.cc

vector<int> next(const char* needle) {
    vector<int> ans;
    ans.push_back(0);
    int k=0;
    for(const char* p=needle+1;*p;p++) {
        while(k>0 && needle[k] != *p) {
            k = ans[k-1];
        }
        if(needle[k] == *p) {
            k++;
        }
        ans.push_back(k);
    }
    return ans;
}
char *strStr(char *haystack, char *needle) {
    if(!needle || !*needle) {
        return haystack;
    }
    vector<int> n = next(needle);
    int k = 0;
    for(char *p=haystack; *p; p++) {
        while(k>0 && needle[k] != *p) {
            k = n[k-1];
        }
        if(needle[k] == *p) {
            k++;
        }
        if(!needle[k]) {
            return p-k+1;
        }
    }
    return NULL;
}

Interleaving String.cc

bool isInterleave(string s1, string s2, string s3) {
    if (s1.length() + s2.length() != s3.length()) {
        return false;
    }
    //dp[i][j] = isInterleave(s1.substr(0,i), s2.substr(0,j))
    vector<vector<int> > dp(s1.length() + 1, vector<int>(s2.length() + 1, 0));
    dp[0][0] = true;
    for (int i = 1; i <= s1.length(); ++i) {
        dp[i][0] = (dp[i - 1][0] && s1[i - 1] == s3[i - 1]) ? 1 : 0;
    }
    for (int j = 1; j <= s2.length(); ++j) {
        dp[0][j] = s2[j - 1] == s3[j - 1] ? 1 : 0;
    }
    for (int i = 1; i <= s1.length(); ++i) {
        for (int j = 1; j <= s2.length(); ++j) {
            if (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]) {
                dp[i][j] = 1;
            }
            if (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) {
                dp[i][j] = 1;
            }
        }
    }
    return dp[s1.length()][s2.length()];
}

maximal rectangle.cc

int maximalRectangle(vector<vector<char> > &matrix) {
    int ans = 0;
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = 0; j < matrix[i].size(); ++j) {
            int maxi = matrix.size();
            for (int jj = j; jj < matrix[i].size(); ++jj) {
                for (int ii = i; ii < maxi; ++ii) {
                    if (matrix[ii][jj] == '1') {
                        ans = max(ans, (ii - i + 1) * (jj - j + 1));
                    } else {
                        maxi = ii;
                        break;
                    }
                }
            }
        }
    }
    return ans;
}

Search for a Range.cc

vector<int> searchRange(int A[], int n, int target) {
    vector<int> ans(2,-1);
    int l, r, mid;
    l=0;
    r=n;
    while(l<r) {
        mid = l + (r-l)/2;
        if(A[mid]<target) { //move only when it's smaller
            l = mid+1;
        }else {
            r = mid;
        }
    }
    if(A[l] != target) {
        return ans;
    }
    ans[0] = l;

    r=n;
    while(l<r) {
        mid = l+(r-l)/2;
        if(A[mid]<=target) {//move only when it's not larger
            l = mid+1;
        }else {
            r = mid;
        }
    }
    ans[1] = r-1;
    return ans;
}