Reverse Words in a String
Given an input string, reverse the string word by word.
For example,
Given s = "
the sky is blue
",return "
blue is sky the
".
---------------------------------------------------------
另外可以用三步翻转法
class Solution { public: void reverseWords(string &s) { string rt = ""; for (int i = 0; i < s.length(); i++) { string word = ""; while (i < s.length() && !isspace(s[i])) { word += s[i]; i++; } if (word == "") continue; if (rt == "") { rt = word; }else { rt = word + " " + rt; } word = ""; i--; } s = rt; } };
Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.For example, given the array
[2,3,-2,4]
,the contiguous subarray
[2,3]
has the largest product = 6
.
---------------------------------------------------------------
DP,dp[i] has the max(min) product subarray that ends at i
#1 can be optimized with two max and min variables
#2 can get rid of if condition, minDp = min(A[i],A[i] * minDp,A[i] * maxDp)
class Solution { public: int maxProduct(int A[], int n) { vector<int> maxDp(n); vector<int> minDp(n); maxDp[0] = A[0]; minDp[0] = A[0]; int maxP = maxDp[0]; int i = 1; while (i < n) { if (A[i] < 0) { minDp[i] = min(A[i],A[i] * maxDp[i - 1]); maxDp[i] = max(A[i],A[i] * minDp[i - 1]); }else { minDp[i] = min(A[i],A[i] * minDp[i - 1]); maxDp[i] = max(A[i],A[i] * maxDp[i - 1]); } maxP = max(maxP,maxDp[i]); i++; } return maxP; } };
O(1) space
class Solution { public: int maxProduct(vector<int>& nums) { int high = 1, low = 1; int maxSub = INT_MIN; for (int i = 0; i < nums.size(); i++) { if (nums[i] > 0) { high = max(nums[i],nums[i] * high); low = min(nums[i],nums[i] * low); }else { int th = high; high = max(nums[i],nums[i] * low); low = min(nums[i],nums[i] * th); } maxSub = max(maxSub,high); } return maxSub; } };
No comments:
Post a Comment