leetcode——151.Reverse Words in a String和152.Maximum Product Subarray

151. Reverse Words in a String

1
2
3
4
5
6
7
8
Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

一开始考虑用python实现,思路来的非常快.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
if s == '' or s == ' ':
return s.strip()
s_list = s.split(' ')
ret = ''
for ss in s_list:
if ss == '':
continue
ret = ' ' + ss + ret
return ret.strip()

将字符串用空格切开,然后重新构造就可以了,这里不需要空间复杂度为O(1)

出现一个小问题是当空格很多时,比如

1
"    a    b"

这种字符串,得到的list会夹杂空字符串

1
['', '', '', '', 'a', '', '', '', 'b']

之后开始考虑空间复杂度O(1)的写法

普遍的思路都是所有单词往右靠拢,消去多余的空格

每个单词进行一次颠倒,然后整个字符串再一次颠倒即可

上述处理顺序可以改变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void reverse(char *start,char *end)
{
while(end > start)
{
char temp = *start;
(*start) = (*end);
(*end) = temp;
start++;
end--;
}
}

void reverseWords(char *s) {

int i = 0;
int j = 0;
int size = strlen(s);
while(i < size) {
while(i < size && s[i] == ' ')
i++;
if (i < size && j > 0)
s[j++] = ' ';
int start = j;
while(i < size && s[i] != ' ') {
s[j++] = s[i++];
}
reverse(s + start, s + j - 1);
}
s[j] = '\0';
reverse(s, s + j - 1);
}

152. Maximum Product Subarray

1
2
3
4
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.

这道题主要考虑两个问题一个是0,一个是负数。

对于0很简单,假设任意长度的数组中有任意个0,那么这个可以看做是用0分割开的任意个子数组只要求出每个子数组的最大乘积就可以了

对于负数,存在两种情况——奇数个和偶数个

对于偶数个,负数没有起到作用,所有元素相乘即可

那么对于奇数个

假设为有1个负数

1
[positive1, positive2, negative1, positive3, positive4]

最大数要么是负数前的所有数相乘要么是负数后的所有数相乘

如果有n个负数,也是一样的,要么是从左往右直到最后数组的最后一个负数之前的数相乘,要么是从右往左直到数组第一个负数相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int maxProduct(vector<int>& nums) {
if(nums.empty())
return 0;
int len = nums.size();
int s_pro = 1;
int e_pro = 1;
int ret = INT_MIN;
for(int i = 0; i < len; i++) {
s_pro *= nums[i];
e_pro *= nums[len - 1 - i];
ret = max(ret, max(s_pro, e_pro));
s_pro = s_pro == 0 ? 1 : s_pro;
e_pro = e_pro == 0 ? 1 : e_pro;
}
return ret;
}
};