LeetCode 128. Longest Consecutive Sequence

Sep 22, 2016

题目描述:

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

从一个无序的数组中找出最长的连续数字序列. 每读入一个数字, 就要判断能否加入到一个已经存在的区间中去, 而如何在常数时间内判断能否加入到某个区间中就是主要的问题. 我的方法是使用两个map, key的值分别为区间的开始和结束, 这样就可以在常数时间内确定能否加入到已经存在的区间的开头或结尾. 当一个值既能插入到某个区间的开头, 也能插入到某个区间的结尾时, 这两个区间就可以合并. 但是这个解法的效率并不是很高.

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
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()) return 0;
        int maxLen = 1;
        unordered_map<int, int> SE, ES; //SE = start<->end, ES = end<->start
        unordered_set<int> included; // 保存区间中已经包含的数
        for(int i = 0; i < nums.size(); i++){
            if(included.count(nums[i])) continue;
            bool SEext = SE.count(nums[i] + 1), ESext = ES.count(nums[i] - 1);
            if(SEext && ESext){
                int newStart = ES[nums[i] - 1], newEnd = SE[nums[i] + 1];
                SE.erase(nums[i] + 1);
                ES.erase(nums[i] - 1);
                SE[newStart] = newEnd;
                ES[newEnd] = newStart;
                maxLen = max(maxLen, newEnd - newStart + 1);
            }
            else if(SEext){
                SE[nums[i]] = SE[nums[i] + 1];
                SE.erase(nums[i] + 1);
                ES[SE[nums[i]]] = nums[i];
                maxLen = max(maxLen, SE[nums[i]] - nums[i] + 1);
            }
            else if(ESext){
                ES[nums[i]] = ES[nums[i] - 1];
                ES.erase(nums[i] - 1);
                SE[ES[nums[i]]] = nums[i];
                maxLen = max(maxLen, nums[i] - ES[nums[i]] + 1);
            }
            else{
                SE[nums[i]] = nums[i];
                ES[nums[i]] = nums[i];
            }
            included.insert(nums[i]);
        }
        
        return maxLen;
    }
};

LeetCode 126. Word Ladder II

Sep 20, 2016

题目描述:

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord toendWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]

Return

1
2
3
4
5
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

这道题使用BFS的问题在于BFS无法保存路径, 所以可以用对于路径的BFS, 也就是在队列中保存的是路径而不是节点. 这样的代码虽然可以AC, 但是非常慢…

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
	vector<vector<string>> ans;
public:
	vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
		queue<vector<string>> BFS;
		BFS.push(vector<string>({ beginWord }));
		vector<string> visited;
		int curLevel = 1;

		while (!BFS.empty()) {
			vector<string> lastPath = BFS.front();
			if (lastPath.size() > curLevel) { // 每一层遍历过的节点必须在进入下一层时才能删除
				for (auto i : visited) {
					wordList.erase(i);
				}
				visited.clear();
				curLevel = lastPath.size();
			}

			if (!ans.empty() && lastPath.size() > ans[0].size()) break;

			if (lastPath.back() == endWord) {
				ans.push_back(lastPath);
			}
			else {
				string &c = lastPath.back();
				for (int i = 0; i < c.length(); i++) {
					string tmp = c;
					for (char j = 'a'; j <= 'z'; j++) {
						tmp[i] = j;
						if (tmp == c) continue;
						if (tmp == endWord || wordList.count(tmp)) {
							vector<string> newPath = lastPath;
							newPath.push_back(tmp);
							BFS.push(newPath);
							visited.push_back(tmp);
						}						
					}
				}
			}
			BFS.pop();
		}
		return ans;
	}
};

LeetCode 127. Word Ladder

Sep 20, 2016

题目描述:

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence frombeginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

使用广度优先搜索, 判断是否连接是通过穷举一个单词的所有可能变化来完成的.

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
32
class Solution {
public:
	int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
		queue<string> BFS;
		queue<int> length;
		BFS.push(beginWord);
		length.push(1);
		int maxLen = INT_MIN;
		while (!BFS.empty()) {
			string &c = BFS.front();
			int l = length.front();
			if (maxLen < l) maxLen = l;

			if(c == endWord) return maxLen;
			for(int i = 0; i < c.length(); i++){
			    string tmp = c;
			    for(char j = 'a'; j <= 'z'; j++){
			        tmp[i] = j;
			        if(wordList.count(tmp)){
			            BFS.push(tmp);
			            length.push(l + 1);
			            wordList.erase(tmp);
			        }
			    }
			}
			BFS.pop();
			length.pop();
		}
		return 0;
	}

};

LeetCode 403. Frog Jump

Sep 19, 2016

题目描述:

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog’s last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

  • The number of stones is ≥ 2 and is < 1,100.
  • Each stone’s position will be a non-negative integer < 231.
  • The first stone’s position is always 0.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

1
2
3
4
[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

虽然tag里说这是个DP题, 但是我觉得更像个图论题. 每个stone是一个node, 根据能否到达来判断有没有边相连, 最终要判断第一个节点与最后一个节点是否连通.

那么既然是这样, 就有DFS和BFS两派了. 用BFS的话要记录抵达每个node的上一跳可能有多远, 同时要记录一个node有没有访问过, 所以比较复杂.

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
32
33
34
35
36
37
38
class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        unordered_map<int, unordered_set<int>> dp;
        unordered_map<int, int> visited;
        for(int i = 0; i < n; i++){
            dp[stones[i]] = unordered_set<int>();
            visited[stones[i]] = 0;
        }
        if(!dp.count(1)) return false;
        if(stones.size() == 2) return true;
        dp[1] = unordered_set<int>({1});
        visited[0] = visited[1] = 1;
        queue<int> BFS;
        BFS.push(1);
        while(!BFS.empty()){
            int stn = BFS.front();
            unordered_set<int> &v = dp[stn];
            for(auto i : v){
                for(int j = i - 1; j <= i + 1; j++){
                    if(j == 0) continue;
                    if(dp.count(stn + j)){
                        if(!visited[stn + j]) {
                            visited[stn + j] = 1;
                            BFS.push(stn + j);
                        }
                        if(stn + j == stones.back() && visited[stn + j]) return true;
                        dp[stn + j].insert(j);
                    }
                }
            }
            
            BFS.pop();
        }
        return false;
    }
};

这个解法的Runtime有近500ms. DFS就不用保存维护这些数据. 在目前的测试数据上DFS只需要6ms.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool canCross(vector<int>& stones) {
        return canCrossImpl(stones, 0, 0);
    }
    
    bool canCrossImpl(vector<int>& stones, int index, int lastStep){
        for(int i = index + 1; i < stones.size(); i++){
            if(stones[i] - stones[index] < lastStep - 1) continue;
            if(stones[i] - stones[index] > lastStep + 1) return false;
            if(canCrossImpl(stones, i, stones[i] - stones[index])) return true;
        }
        return index == stones.size() - 1;
    }
};

Update: LeetCode已经更新了测试数据, 所以像上面那样单纯的DFS已经会超时了, 要使用一些DP的方法. 用一个二维数组来保存第i个节点的前一步为s步时能否到达. 因为步数s和节点编号i都未知且可能很大, 所以用unordered_map来实现二维数组.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    unordered_map<int, unordered_map<int, bool>> m;
public:
    bool canCross(vector<int>& stones) {
        return canCrossImpl(stones, 0, 0);
    }
    
    bool canCrossImpl(vector<int>& stones, int index, int lastStep){
        if(m.count(index) && m[index].count(lastStep)){
            return m[index][lastStep];
        }
        for(int i = index + 1; i < stones.size(); i++){
            if(stones[i] - stones[index] < lastStep - 1) continue;
            if(stones[i] - stones[index] > lastStep + 1) {
                m[index][lastStep] = false;
                return false;
            }
            if(canCrossImpl(stones, i, stones[i] - stones[index])) {
                return true;
            }
        }
        return index == stones.size() - 1;
    }
};

由于节点最多有1099个, 在步长每次都+1的情况下步数是一个从1开始的公差为1的等差数列, 所以虽然stone的编号是<231的, 但是大于0+1+2+…+1099=604450的stone是肯定抵达不了的. 而604450占20个二进制位, 一个32位数剩下的12位正好可以存储步数, 所以上面的二维数组可以变为一维.

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
class Solution {
    unordered_map<int, bool> m;
public:
    bool canCross(vector<int>& stones) {
        return canCrossImpl(stones, 0, 0);
    }
    
    bool canCrossImpl(vector<int>& stones, int index, int lastStep){
        if(index > 604450) return false;
        int mi = index << 12 | lastStep;
        if(m.count(mi)){
            return m[mi];
        }
        for(int i = index + 1; i < stones.size(); i++){
            if(stones[i] - stones[index] < lastStep - 1) continue;
            if(stones[i] - stones[index] > lastStep + 1) {
                m[mi] = false;
                return false;
            }
            if(canCrossImpl(stones, i, stones[i] - stones[index])) {
                return true;
            }
        }
        return index == stones.size() - 1;
    }
};

LeetCode 402. Remove K Digits

Sep 19, 2016

题目描述:

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

Example 1:

1
2
3
4
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

1
2
3
4
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

1
2
3
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

这道题的主要思想就是"如果遇到了一个较小的值, 那么就把已得到的字符串中尾部所有比它大的值删除, 再把它放入末尾; 如果比末尾元素大, 那么就把它直接添加到末尾". 这是一个栈的问题, 但是除了主要的思路以外还有另一个问题: 最终栈的大小必须是num.size()-k, 所以在添加和删除时必须要考虑栈的大小.

在元素比栈顶元素大的情况下还要增加一个条件: 栈的大小还没有达到num.size()-k.

而元素比栈顶元素小的情况下, 在弹出栈顶元素时要求num中剩下的元素数量>=栈的目标大小-栈目前的大小, 这样才能保证栈能被填满.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string removeKdigits(string num, int k) {
        string ans;
        int target = num.size() - k, size = num.size(), i;
        if(target == 0) return "0";
        ans.push_back(num[0]);
        for(i = 1; i < k + ans.size(); i++){
            if(num[i] > ans.back() && ans.size() < target) ans.push_back(num[i]);
            else{
                while(!ans.empty() && ans.back() > num[i] && size - i - 1 >= target - ans.size()) ans.pop_back();
                if(ans.size() < target) ans.push_back(num[i]);
            }
        }
        for(; ans.size() < target; i++){
            ans.push_back(num[i]);
        }
        for(i = 0; ans[i] == '0'; i++);
        if(ans.empty() || i == ans.size()) return "0";
        return ans.substr(i);
    }
};

LeetCode 401. Binary Watch

Sep 18, 2016

题目描述:

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

1
2
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

  • The order of output does not matter.
  • The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
  • The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

由于数据量相当的小, 所以这道题最简单粗暴的方法就是把每种小时和分钟的可能都列出来, 正常一点的思路就是从n个数中选择k个不同的数出来, 对于这道题来说还要加上一个对于是否是合法地时间数据的判断.

我对于小时采用写出所有可能的办法, 对于分钟采用正常的方法. 至于为啥分钟不写, 大概是因为手算有点烦= =.

这道题我还遇到了[无符号数-有符号数=无符号数]的坑, 就是第64行的i <= v.size() - n, 在n>6的情况下是会溢出的. 所以要么把n移到不等式的左边, 要么在第8行就规避n>6的情况.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
    vector<int> hourNum = {1,2,4,8};
    vector<int> minuteNum = {1,2,4,8,16,32};
    vector<string> hours, minutes;
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> ans;
        for(int i = num - 6; i <= num; i++){
            possibleHour(i);
            possibleMinute(num - i);
            for(auto i : hours){
                for(auto j : minutes){
                    ans.push_back(i + ":" + j);
                }
            }
        }
        return ans;
    }
    
    void possibleHour(int n){
        hours.clear();
        switch(n){
            case 0:
                hours = vector<string>({"0"});
                return;
            case 1:
                hours = vector<string>({"1", "2", "4", "8"});
                return;
            case 2:
                hours = vector<string>({"3", "5", "9", "6", "10"});
                return;
            case 3:
                hours = vector<string>({"7", "11"});
                return;
            default:
                hours = vector<string>();
                return;
        }
    }
    
    void possibleMinute(int n){
        minutes.clear();
        if(n == 0){
            minutes.push_back("00");
            return;
        }
        vector<vector<int>> ret;
        vector<int> path;
        selectNFromVector(minuteNum, 0, n, path, ret);
        for(int i = 0; i < ret.size(); i++){
            int sum = 0;
            for(int j = 0; j < n; j++){
                sum += ret[i][j];
            }
            if(sum < 60){
                string str = to_string(sum);
                if(sum < 10) str.insert(str.begin(), '0');
                minutes.push_back(str);
            }
        }
    }
    
    void selectNFromVector(vector<int> &v, int start, int n, vector<int> &path, vector<vector<int>> &ret){
        for(int i = start; i <= v.size() - n; i++){
            path.push_back(v[i]);
            if(n == 1){
                ret.push_back(path);
                path.pop_back();
                continue;
            }
            selectNFromVector(v, i + 1, n - 1, path, ret);
            path.pop_back();
        }
    }
};

LeetCode 400. Nth Digit

Sep 18, 2016

题目描述:

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note: n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

1
2
3
4
5
6
Input:
3

Output:
3

Example 2:

1
2
3
4
5
6
7
8
Input:
11

Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

LeetCode现在每周的比赛都要出四道新题, 像我这种一边做老题一边追新题还要上课(自己选的统计学习, 跪着也要上完)的人来说还真是有点觉得追不上.

这道题算是比较简单, 就是算出1位数有多少个阿拉伯数字, 2位数有多少阿拉伯数字, 3位数有多少个阿拉伯数字…n位数有9×10^(n-1)×n个阿拉伯数字, 然后对于输入的n, 我们就可以通过前面得到的数据确定它有多少位, 进而确定是哪个数, 最终确定要找的数字.

1位数到n位数共有多少个数字可以先计算出来写在程序中,

1
2
3
4
5
6
7
8
9
10
int main () {
    long long sum = 0;
    for(int i = 0;; i++){
        long long t = 9 * (long long)pow(10, i) * (i + 1);
        if(t > INT_MAX) break;
        sum += t;
        cout<<i<<':'<<t<<" sum:"<<sum<<endl;
    }
    return 0;
}

输出:

1
2
3
4
5
6
7
8
0:9 sum:9
1:180 sum:189
2:2700 sum:2889
3:36000 sum:38889
4:450000 sum:488889
5:5400000 sum:5888889
6:63000000 sum:68888889
7:720000000 sum:788888889

这个结果还是挺有规律的. 接下来就是解题的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int arr[9] = {0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889};
public:
    int findNthDigit(int n) {
        int index;
        for(index = 0; index < 9 && arr[index] < n; index++); // 确定位数
        int t = (n - arr[index - 1] - 1);
        int num = (t / index) + (int)pow(10, index - 1); // 确定数
        int p = index - (t % index) - 1; // 确定第几位
        for(int i = 0; i < p; i++){ // 找出该位
            num /= 10;
        }
        return num % 10; // 个位为我们要找的数
    }
};

LeetCode 125. Valid Palindrome

Sep 17, 2016

题目描述:

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome.

Note: Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

双指针从两端向中间遍历即可.

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
class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0, j = s.length() - 1;
        while(i < j){
            if(!isValid(s[i])){
                i++;
            }
            else if(!isValid(s[j])){
                j--;
            }
            else{
                if(s[i] >= 'A' && s[i] <= 'Z') s[i] -= ('A' - 'a');
                if(s[j] >= 'A' && s[j] <= 'Z') s[j] -= ('A' - 'a');
                if(s[i] != s[j]) return false;
                i++;
                j--;
            }
        }
        return true;
    }
    
    bool isValid(char ch){
        return (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9') || (ch >= 'A' && ch <= 'Z');
    }
};

LeetCode 124. Binary Tree Maximum Path Sum

Sep 17, 2016

题目描述:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example: Given the below binary tree,

1
2
3
4
  1
 / \
2   3

Return 6.

这道题我一开始是先用DFS来搜索出所有节点到根节点的路径, 然后再用双重循环来计算出每对节点的路径和. 如果有n个节点的话, 这个方法的时间复杂度是O(n2), 所以超时了.

后来发现了递归的方法. 对于一个二叉树的根节点来说, 这棵树中的最长路径和要么经过它, 要么经过它的后代, 所以我们就可以算出经过根节点的最长路径和是多少, 然后对每一个节点都计算一遍就可以找出最长的路径和.

在递归过程中, 除了维护一个最终的最长路径和以外, 我们还要知道每个节点的左右子树到该节点的最长路径和(注意, 这里的路径必须有一端是该节点)才能找出经过该节点的最长路径和.

同时还要注意路径和与0的大小关系, 如果到某节点的路径和小于0, 那么就不应该把这部分路径包含进去.

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int maxPath = INT_MIN;
public:
    int maxPathSum(TreeNode* root) {
        DFS(root);
        return maxPath;
    }
    
    int DFS(TreeNode *root){
        if(!root) return 0;
        int leftPath = DFS(root->left), rightPath = DFS(root->right);
        // 经过root节点的路径的四种情况, 选择最大的.
        maxPath = max(maxPath, (leftPath + rightPath + root->val));
        maxPath = max(maxPath, root->val);
        maxPath = max(maxPath, root->val + leftPath);
        maxPath = max(maxPath, root->val + rightPath);
        // 如果左右子树都小于0, 那么应该只返回root节点的值
        return root->val + max(0, max(leftPath, rightPath));
    }
};

LeetCode 123. Best Time to Buy and Sell Stock III

Sep 15, 2016

题目描述:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

这道题可以用一种我也不知道算不算动态规划的方法来解. 首先我们可以进行零次, 一次或者两次买入卖出操作, 零次或一次是之前的题目, 比较容易解决. 问题在于两次交易, 由于不能同时持有多个stock, 所以两次交易必须是前后发生的, 那么就可以用两个数组来分别记录[0,i]中获得能获得的最大收益和[i+1, n]中能获得的最大收益, 通过遍历i就可以得到前后两次交易的最大收益.

第一个数组通过遍历一次prices得到, 而第二个数组通过反向遍历一次prices得到.

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
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n < 2) return 0;
        vector<int> profit1(n, 0), profit2(n, 0);
        int lowest = prices[0];
        for(int i = 1; i < n; i++){
            lowest = min(lowest, prices[i]);
            profit1[i] = max(profit1[i - 1], prices[i] - lowest);
        }

        int highest = prices.back();
        for(int i = n - 2; i >= 0; i--){
            highest = max(highest, prices[i]);
            profit2[i] = max(profit2[i + 1], highest - prices[i]);
        }

        int maxProfit = profit1.back();
        for(int i = 0; i < n - 1; i++){
            maxProfit = max(maxProfit, profit1[i] + profit2[i + 1]);
        }
        return maxProfit;
    }
};

而最后两个循环可以合并为一个.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n < 2) return 0;
        vector<int> profit1(n, 0), profit2(n, 0);
        int lowest = prices[0];
        for(int i = 1; i < n; i++){
            lowest = min(lowest, prices[i]);
            profit1[i] = max(profit1[i - 1], prices[i] - lowest);
        }

        int highest = prices.back(), maxProfit = profit1.back();
        for(int i = n - 2; i >= 0; i--){
            highest = max(highest, prices[i]);
            profit2[i] = max(profit2[i + 1], highest - prices[i]);
            maxProfit = max(maxProfit, profit1[i] + profit2[i + 1]);
        }
        return maxProfit;
    }
};