#手写代码竞赛# 6月28日前需要完成的题目： Combination Sum 2, Restore IP Addresses, Best Time to Buy and Sell Stock III, Insert Interval, Lawnmower 前四题目描述见LeetCode http://leetcode.com/onlinejudge 最后一题是Google Code Jam今年资格赛的第二题,也有Online Judge https://code.google.com/codejam/contest/2270488/dashboard#s=p1

best_time_to_buy_ans_sell_stock_3.cc

int maxProfit(vector<int> &prices) {
    if (prices.size() == 0) {
        return 0;
    }
    vector<int> dp(prices.size(), 0);
    int curr = prices[0];
    for (int i = 1; i < prices.size(); i++) {
        curr = min(curr, prices[i]);
        dp[i] = max(dp[i-1], prices[i]-curr);
    }
    curr = prices[prices.size() - 1];
    int ans = dp.back();
    for (int i = prices.size() - 2; i > 0; i--) {
        curr = max(curr, prices[i]);
        ans = max(ans, dp[i-1] + max(0, curr - prices[i]));
    }
    return ans;
}

combination_sum_2.cc

void helper(vector<int>::iterator begin, vector<int>::iterator end,
            int target, set<vector<int> > &result) { 
    if (begin == end || target < *begin) {
        return; 
    }
    if (target == *begin) {
        result.insert(vector<int>(1, target));
    }
    helper(begin + 1, end, target, result);
    set<vector<int> > tmp;
    helper(begin + 1, end, target - (*begin), tmp);
    for (auto it = tmp.begin(); it != tmp.end(); it++) {
        vector<int> t = *it;
        t.insert(t.begin(), *begin);
        result.insert(t); 
    }
}

vector<vector<int> > combinationSum2(vector<int> &num, int target) { 
    set<vector<int> > result;
    sort(num.begin(), num.end());
    if (num.size() == 0 || target < num[0]) {
        return vector<vector<int> >();
    }
    helper(num.begin(), num.end(), target, result); 
    vector<vector<int> > ans;
    for (auto it = result.begin(); it != result.end(); it++) {
        ans.push_back(*it);
    }
    return ans;
}

insert_interval.cc

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
    if (intervals.size() < 1) {
        intervals.push_back(newInterval);
        return intervals;
    }
    int j = 0;
    int flag = 1;
    for (int i=0; i < intervals.size(); i++, j++) {
        if (intervals[i].start <= newInterval.start && 
            intervals[i].end >= newInterval.end) {
            return intervals;
        } else if ( !(newInterval.end < intervals[i].start || 
                      intervals[i].end < newInterval.start) ) {
            newInterval.start = min(intervals[i].start, newInterval.start);
            newInterval.end = max(intervals[i].end, newInterval.end);
            flag = 1;
            j--;
        } else if (flag && intervals[i].start > newInterval.end) {
            intervals.insert(intervals.begin() + j, newInterval);
            flag = 0;
        } else if (i != j) {
            intervals[j] = intervals[i];
        }
    }
    if (flag) {
        intervals.insert(intervals.begin() + j, newInterval);
        j++;
    }
    return vector<Interval>(intervals.begin(), intervals.begin() + j);
}

Lawnmower.cc

//https://code.google.com/codejam/contest/2270488/dashboard#s=p1
int main()
{
    int test_case_num = 0;
    cin >> test_case_num;
    for (int test_case=1; test_case <= test_case_num; test_case++) {
        int N, M;
        cin >> N >> M;
        vector<vector<int> > lawn(N, vector<int>(M, 100));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> lawn[i][j];
            }
        }
        vector<vector<int> > plat(N, vector<int>(M, 100));
        for (int h = 100; h > 0; h--) {
            for (int i = 0; i < N; i++) {
                int height = 0;
                for (int j = 0; j < M; j++) {
                    height = max(height, lawn[i][j]);
                }
                for (int j = 0; j < M; j++) {
                    plat[i][j] = min(plat[i][j], height);
                }
            }
            for (int j = 0; j < M; j++) {
                int height = 0;
                for (int i = 0; i < N; i++) {
                    height = max(height, lawn[i][j]);
                }
                for (int i = 0; i < N; i++) {
                    plat[i][j] = min(plat[i][j], height);
                }
            }
        }
        if (lawn == plat) {
            cout << "Case #" << test_case << ": YES" << endl;
        } else {
            cout << "Case #" << test_case << ": NO" << endl;
        }
    }
    return 0;
}

restore_ip_addresses.cc

vector<string> restoreIpAddresses(string s) {
    set<string> ans;
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            for (int k = 1; k <= 3; ++k) {
                int x = s.length() - i - j - k;
                if (valid(s, 0, i) && valid(s, i, j) &&
                    valid(s, i+j, k) && valid(s, i+j+k, x )) {
                    string t = s.substr(0, i) + "." + s.substr(i, j) + "." + 
                               s.substr(i+j, k) + "." + s.substr(i+j+k, x);
                    ans.insert(t);
                } 
            }
        }
    }
    vector<string> ret;
    for(auto it = ans.begin(); it != ans.end(); it++) {
        ret.push_back(*it);
    }
    return ret;
}

bool valid(const string &s, int begin, int len) {
    if (begin+1 > s.length() || len < 1 || len > 3) {
        return false;
    }
    if (len != 1 && s[begin] == '0') {
        return false;
    }
    int x = atoi(s.substr(begin, len).c_str());
    if (x > 255) {
        return false;
    }
    return true;
}