Monthly Archives: January 2017

LeetCode Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note:

  • All of the nodes’ values will be unique.
  • p and q are different and both values will exist in the BST.

给定一棵二叉搜索树和两个节点,问这两个节点的最近公共祖先(LCA)。LCA问题很久以前在hihoCoder上做过好多,用到一些比较高级的算法。 这个题的一个特点是二叉树是二叉搜索树,二叉搜索树的特点是左孩子小于等于根节点,根节点小于等于右孩子。不失一般性,令p<=q,所以如果p<=root<=q,则p,q分立root两边,则root就是p,q的LCA。如果p,q都小于root,则递归在root->left找。如果p,q都大于root,则递归在root->right找。 递归的算法很容易就实现了,代码如下:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (p->val > q->val)
            swap(p, q);
        if (p->val <= root->val && q->val >= root->val)
            return root;
        if (p->val < root->val && q->val < root->val)
            return lowestCommonAncestor(root->left, p, q);
        if (p->val > root->val && q->val > root->val)
            return lowestCommonAncestor(root->right, p, q);
    }
};

本代码提交AC,用时32MS。

二刷。遍历二叉树,把p和q的祖先找出来,然后寻找公共前缀:

class Solution {
	void BSTSearch(TreeNode* root, TreeNode* p, vector<TreeNode*>& ancestors) {
		while (root->val != p->val) {
			ancestors.push_back(root);
			if (p->val > root->val)root = root->right;
			else root = root->left;
		}
		ancestors.push_back(root);
	}
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		vector<TreeNode*> pa, qa;
		BSTSearch(root, p, pa);
		BSTSearch(root, q, qa);
		int i = 0;
		for (; i < pa.size() && i < qa.size(); ++i) {
			if (pa[i] != qa[i])break;
		}
		return pa[i - 1];
	}
};

本代码提交AC,用时40MS。感觉还是第一种递归解法漂亮。

LeetCode Insert Delete GetRandom O(1) – Duplicates allowed

LeetCode Insert Delete GetRandom O(1) – Duplicates allowed Design a data structure that supports all following operations in average O(1) time. Note: Duplicate elements are allowed.

  1. insert(val): Inserts an item val to the collection.
  2. remove(val): Removes an item val from the collection if present.
  3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
Example:
// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();
// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);
// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);
// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);
// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();
// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);
// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

这一题在LeetCode Insert Delete GetRandom O(1)的基础上,增加了有重复元素的约束。还是用数组+Hash实现,但是Hash表中不再只是存储单个元素的下标了,而是存储所有相同元素的下标的集合,采用最大堆(priority_queue)来存储相同元素的下标集合。 插入时,数值插入到数组末尾,下标插入到hash表中该数值对应的最大堆中,如果堆原来为空的话,说明这是第一次插入该数值。删除时,取出val在数组中的最大下标(priority_queue.top()即为堆中最大值),如果不是数组末尾,则和数组末尾的数值交换,同时更新原数组末尾数值的下标最大堆,最后删掉数组末尾的数。产生随机数同样好办,直接rand下标。 完整代码如下: [cpp] class RandomizedCollection { private: unordered_map<int, priority_queue<int>> hash; vector<int> nums; public: /** Initialize your data structure here. */ RandomizedCollection() { } /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ bool insert(int val) { hash[val].push(nums.size()); nums.push_back(val); return hash[val].size() == 1; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ bool remove(int val) { if (hash[val].empty())return false; int pos = hash[val].top(); hash[val].pop(); if (pos != nums.size() – 1) { nums[pos] = nums[nums.size() – 1]; hash[nums[pos]].pop(); hash[nums[pos]].push(pos); } nums.pop_back(); return true; } /** Get a random element from the collection. */ int getRandom() { return nums[rand() % nums.size()]; } }; [/cpp] 本代码提交AC,用时85MS。 但是为什么要用最大堆来存储相同数值的下标集合呢,而且最大堆的插入和删除效率不是O(1)的呀,难道是因为相同的数比较少?所以每个数值的下标堆很小,所以插入和删除的复杂度近似为O(1)? 那么能否用数组来存储相同数值的下标集合呢,即用unordered_map<int, vector> hash,答案是不可以。举例如下: 假设经过了6次插入之后,数组为[10,10,20,20,30,30],此时不同数值的下标集合为:
  • 10:[0,1]
  • 20:[2,3]
  • 30:[4,5]
此时删除10,则会把第二个10删掉,同时把末尾的30放到第二个10的位置,数组变为[10,30,20,20,30],此时下标集合为:
  • 10:[0]
  • 20:[2,3]
  • 30:[4,1]
如果此时再次删除10,则会把第一个10删掉,同时把末尾的30放到第一个10的位置,数组变为[30,30,20,20],但是此时的下标集合变为了:
  • 10:[]
  • 20:[2,3]
  • 30:[4,0]
即30的下标集合出现了错误,因为存储下标集合的数据结构是vector,O(1)的删除只能是pop_back(),但是这样并不能保证删掉最大的下标,本来这次我们是要删掉最大的下标4的,但是结果却删了0,依然保存了已不存在的下标4。所以用最大堆的目的就是为了每次删除都删掉最大的下标。 但是最大堆的插入和删除毕竟不是O(1),再次使用Hash存储下标才是真正的O(1)做法,即用unordered_map> hash,这样的话,在上面的例子中,我可以用O(1)的时间删除下标4。 [cpp] class RandomizedCollection { private: unordered_map<int, unordered_set<int>> hash; vector<int> nums; public: /** Initialize your data structure here. */ RandomizedCollection() { } /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ bool insert(int val) { hash[val].insert(nums.size()); nums.push_back(val); return hash[val].size() == 1; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ bool remove(int val) { if (hash[val].empty())return false; int pos = *hash[val].begin(); hash[val].erase(pos); if (pos != nums.size() – 1) { nums[pos] = nums[nums.size() – 1]; hash[nums[pos]].erase(nums.size() – 1); hash[nums[pos]].insert(pos); } nums.pop_back(); return true; } /** Get a random element from the collection. */ int getRandom() { return nums[rand() % nums.size()]; } }; [/cpp] 本代码提交AC,用时79MS。]]>

LeetCode Insert Delete GetRandom O(1)

LeetCode Insert Delete GetRandom O(1) Design a data structure that supports all following operations in average O(1) time.

  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();
// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);
// Returns false as 2 does not exist in the set.
randomSet.remove(2);
// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);
// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();
// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);
// 2 was already in the set, so return false.
randomSet.insert(2);
// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

本题要求实现这样一种数据结构,插入、删除和产生集合中的一个随机数的时间复杂度都是O(1)。 插入和删除要是O(1),可以借助Hash,但Hash表不能以O(1)时间生成随机数。如果把数存在数组中,则能以O(1)的时间生成随机数,但数组的删除不能O(1)。所以可以把Hash和数组结合起来。 数字存储在数组中,Hash表中存储数字在数组中的下标。插入时,插入到数组末尾,同时更新Hash表中的下标。删除时,把数字和数组末尾的数字交换,这样删除数组末尾元素可以用O(1)时间完成,同时也要把Hash表中的下标抹掉,并更新原数组最后一个元素的下标。产生随机数就好办了,知道数组长度,rand下标就好。 完整代码如下: [cpp] class RandomizedSet { private: vector<int> nums; unordered_map<int, int> hash; public: /** Initialize your data structure here. */ RandomizedSet() { } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ bool insert(int val) { if (hash.find(val) != hash.end())return false; hash[val] = nums.size(); nums.push_back(val); return true; } /** Removes a value from the set. Returns true if the set contained the specified element. */ bool remove(int val) { if (hash.find(val) == hash.end())return false; int pos = hash[val]; swap(nums[pos], nums[nums.size() – 1]); //下面两句顺序不能乱,因为有可能删除的就是最后一个元素 hash[nums[pos]] = pos; hash.erase(val); nums.pop_back(); return true; } /** Get a random element from the set. */ int getRandom() { return nums[rand() % nums.size()]; } }; [/cpp] 本代码提交AC,用时59MS。]]>

LeetCode Best Time to Buy and Sell Stock with Cooldown

LeetCode Best Time to Buy and Sell Stock with Cooldown 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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

  • You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
  • After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

又是股票买卖问题。在LeetCode Best Time to Buy and Sell Stock II的基础上,限制一次交易之后必须冷却一天,隔天才能再次买入。此时就不能再用贪心策略了,还需要用DP。参考这篇博客解法I。 定义两个数组sells和buys,sells[i]表示第i天的动作是卖出,截止当前的最大收益;buys[i]表示第i天的动作是买入,截止当前的最大收益。显然buys[0]=prices[0], sells[0]=0。 令profit=prices[i]-prices[i-1],递推公式如下:
  1. sells[i]=max(buys[i-1]+prices[i], sells[i-1]+profit)
  2. buys[i]=max(sells[i-2]-prices[i], buys[i-1]-profit)
含义为:
  1. 第i天卖出的收益=max(第i-1天买入+第i天卖出的收益,第i-1天卖出~但反悔了~改为第i天卖出)
  2. 第i天买入的收益=max(第i-2天卖出~第i-1天冷却~第i天买入的负收益,第i-1天买入~但反悔了~改为第i天买入)
而事实上:
  1. 第i-1天卖出后反悔,改为第i天卖出 等价于 第i-1天持有股票,第i天再卖出
  2. 第i-1天买入后反悔,改为第i天买入 等价于 第i-1天没有股票,第i天再买入
所求的最大收益为max(sells)。显然,卖出股票时才可能获得收益。完整代码如下: [cpp] class Solution { public: int maxProfit(vector<int>& prices) { int days = prices.size(); if (days < 2)return 0; vector<int> sells(days), buys(days); buys[0] = -prices[0]; int ans = 0; for (int i = 1; i < days; ++i) { int profit = prices[i] – prices[i – 1]; sells[i] = max(buys[i – 1] + prices[i], sells[i – 1] + profit); buys[i] = max(i > 1 ? sells[i – 2] – prices[i] : INT_MIN, buys[i – 1] – profit); ans = max(ans, sells[i]); } return ans; } }; [/cpp] 本代码提交AC,用时6MS。]]>

LeetCode Best Time to Buy and Sell Stock IV

188. Best Time to Buy and Sell Stock IV

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

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

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

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

这是股票买卖最难的一题!问最多进行k次交易能获得的最大收益是多少。参考网上题解1题解2。 令mustSell[i][j]表示前i天最多交易j次能获得的最大收益,且第i天必须卖出;globalBest[i][j]表示前i天最多交易j次能获得的最大收益,不要求第i天必须卖出。则有如下递推关系:

  1. mustSell[i][j]=max(globalBest[i-1][j-1]+profit, mustSell[i-1][j]+profit)
  2. globalBest[i][j]=max(globalBest[i-1][j], mustSell[i][j])

解释一下,profit=prices[i]-prices[i-1]为第i-1天买入,第i天卖出的收益。

第一个公式中,前i天最多交易j次且第i天卖出的最大收益为“前i-1天最多交易j-1次的全局最大收益+第i-1天买入第i天卖出的收益”“前i-1天最多交易j次且第i-1天卖出的最大收益+第i-1天买入第i天卖出的收益”的较大者。第一部分好理解,第二部分为什么还是j次交易呢,第一眼看上去好像有j+1次交易了,但是因为mustSell[i-1][j]表示第i-1天必须卖出,而profit表示第i-1天要买入,第i天卖出,两者加起来的效果相当于第i-1天的卖出买入抵消了,即交易次数还是j次,而且恰好变成了第i天卖出,和mustSell[i][j]的含义一致。

第二个公式就好理解了,前i天最多交易j次的全局最大收益为“最后一次交易不在第i天发生,则globalBest[i-1][j]”与“最后一次交易在第i天发生,则mustSell[i][j]”的较大者。
如果允许交易的次数k很大,那么以上DP效率较低,可以换成LeetCode Best Time to Buy and Sell Stock II的贪心策略。因为一次交易至少涉及到两天,所以如果k>=prices.size()/2时,可以采用贪心策略。

完整代码如下:

class Solution {
public:
    int maxProfit(int k, vector<int>& prices)
    {
        int days = prices.size();
        if (days < 2)
            return 0;
        if (k >= days / 2) {
            int ans = 0;
            for (int i = 1; i < days; ++i) {
                if (prices[i] > prices[i – 1])
                    ans += (prices[i] – prices[i – 1]);
            }
            return ans;
        }
        vector<vector<int> > mustSell(days, vector<int>(k + 1, 0)), globalBest(days, vector<int>(k + 1, 0));
        for (int i = 1; i < days; ++i) {
            int profit = prices[i] – prices[i – 1];
            for (int j = 1; j <= k; ++j) {
                mustSell[i][j] = max(globalBest[i – 1][j – 1] + profit, mustSell[i – 1][j] + profit);
                globalBest[i][j] = max(globalBest[i – 1][j], mustSell[i][j]);
            }
        }
        return globalBest[days – 1][k];
    }
};

本代码提交AC,用时9MS。

LeetCode Best Time to Buy and Sell Stock III

123. Best Time to Buy and Sell Stock III

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 (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

股票买卖题三。这次限制最多交易两次,问最大能获利多少。这确实是个hard题,研一卜神算法作业中遇到过。 先来回顾一下股票买卖第一题LeetCode Best Time to Buy and Sell Stock,当时的做法是从左往右找到除了当前值的最小值min_so_far,然后用当前值减去min_so_far,表示如果在当前卖出(即用min_so_far买入)能获得的最大收益profit1。这一题允许最多两次交易,那么如果求到在当前买入能获得的最大收益profit2,则profit1+profit2表示在当前卖出后买入能获得的最大收益。计算所有的profit1+profit2的最大值,就是两次交易能获得的最大收益。 计算profit2的方法和计算profit1类似,此时我们从右往左找到除了当前值的最大值max_so_far,则用max_so_far减去当前值,就表示在当前买入(max_so_far卖出)能获得的最大收益profit2。

整理一下思路:我们尝试把每个点作为两次交易的分界点,那么这个点在上一个交易中卖出了,同时在下一个交易中买入了,我们要分别求到在这个点卖出和买入能获得的最大收益,然后把两个值加起来就是在这个点两次交易的最大收益。求所有点的最大收益的最大值就是最终结果。 举个例子,如下表,表中的min_so_far和profit1是从左往右计算的,max_so_far和profit2是从右往左计算的,profit1/2计算的都是当前profit和历史profit的最大值,和代码中的含义一致。

prices326503
min_so_farINT_MAX32220
max_so_far66533INT_MIN
profit1004444
profit2443330
total447774

完整代码如下:

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int n = prices.size();
        if (n < 2)
            return 0;
        vector<int> minprice(n), maxprice(n);
        for (int i = 0; i < n; ++i) {
            minprice[i] = i == 0 ? INT_MAX : min(minprice[i – 1], prices[i – 1]);
            maxprice[n – i – 1] = i == 0 ? INT_MIN : max(maxprice[n – i], prices[n – i]);
        }
        vector<int> profit1(n), profit2(n);
        for (int i = 0; i < n; ++i) {
            profit1[i] = i == 0 ? 0 : max(profit1[i – 1], prices[i] – minprice[i]);
            profit2[n – i – 1] = i == 0 ? 0 : max(profit2[n – i], maxprice[n – i – 1] – prices[n – i – 1]);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, profit1[i] + profit2[i]);
        }
        return ans;
    }
};

本代码提交AC,用时9MS。

二刷。类似的代码,或许更好理解:

class Solution {
public:
	int maxProfit(vector<int>& prices) {
		int n = prices.size();
		if (n == 0 || n == 1)return 0;
		vector<int> cur_min(n, INT_MAX), cur_max(n, INT_MIN);
		cur_min[0] = prices[0];
		cur_max[n - 1] = prices[n - 1];
		for (int i = 1; i < n; ++i) {
			cur_min[i] = min(cur_min[i - 1], prices[i]);
			cur_max[n - i - 1] = max(cur_max[n - i], prices[n - i - 1]);
		}
		vector<int> dp_sell(n, 0), dp_buy(n, 0);
		for (int i = 1; i < n; ++i) {
			dp_sell[i] = max(dp_sell[i - 1], prices[i] - cur_min[i]);
			dp_buy[n - i - 1] = max(dp_buy[n - i], cur_max[n - i - 1] - prices[n - i - 1]);
		}
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			ans = max(ans, dp_sell[i] + dp_buy[i]);
		}
		return ans;
	}
};

本代码提交AC,用时16MS。

LeetCode Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II

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 as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

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

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

还是股票买卖题。这一题不限制交易次数,但还是要求必须先卖出再买入,同一天可以先卖出再买入。 贪心策略,只要当前的股价比前一天高,则在前一天买入,当天卖出,能赚一点是一点,然后把每天赚的累加起来。 可能稍微会担心是否能得到最优解,比如价格是1,2,900,901,如果只交易一次,最好在第一天买入,最后一天卖出,收益901-1=900,但是贪心策略也一样:(2-1)+(900-2)+(901-900)=(901-1)=900。所以贪心能得到最优解。完整代码如下:

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int ans = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] > prices[i – 1])
                ans += (prices[i] – prices[i – 1]);
        }
        return ans;
    }
};

本代码提交AC,用时9MS。

LeetCode Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock

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

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

股票买卖问题。给定股票每天的价格,问哪天买入和哪天卖出能获得最大收益。动态规划问题,本科就遇到过了。之前一贯的做法是这样的:要使prices[j]-prices[i]的差值最大,因为prices[j]-prices[i]=(prices[j]-prices[j-1])+(prices[j-1]-prices[j-2])+…+(prices[i+1]-prices[i]),等式右边的每一项就是相邻两天的股价差。所以我们可以对每相邻两天的股价做差,得到一个新的n-1长的数组diff,然后对diff求最大连续子串和。最大连续子串和又可以用DP解决,令dp[i]为包含diff[i]的最大连续子串和,如果dp[i-1]>0,则dp[i]=dp[i-1]+diff[i];否则dp[i]=diff[i]。最后dp数组的最大值即为最大收益。
这种思路的代码如下:

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        if (prices.size() < 2)
            return 0;
        vector<int> diff(prices.size() – 1);
        for (int i = 1; i < prices.size(); ++i) {
            diff[i – 1] = prices[i] – prices[i – 1];
        }
        vector<int> dp(diff.size());
        int ans = 0;
        for (int i = 0; i < diff.size(); ++i) {
            if (i == 0 || dp[i – 1] < 0)
                dp[i] = diff[i];
            else
                dp[i] = dp[i – 1] + diff[i];
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

本代码提交AC,用时9MS。
还可以对上述思路简化,我们记录当前遇到的最小值min_so_far,那么如果第i天卖出的话,最大的收益就是prices[i]-min_so_far了,所以我们用dp[i]记录第i天卖出的最大收益。最后对dp数组求最大值,即为最大收益。
这种思路的代码如下:

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        if (prices.size() < 2)
            return 0;
        vector<int> dp(prices.size());
        int min_so_far = prices[0], ans = 0;
        for (int i = 1; i < prices.size(); ++i) {
            dp[i] = prices[i] – min_so_far;
            min_so_far = min(min_so_far, prices[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

本代码提交AC,用时6MS。
还有一种解法,用minprice和maxprice分别记录从左往右当前的最小值和从右往左当前的最大值,最大收益就是用maxprice-minprice的最大值。完整代码如下:

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int n = prices.size();
        if (n < 2)
            return 0;
        vector<int> minprice(n), maxprice(n);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            minprice[i] = (i == 0 ? prices[0] : min(minprice[i – 1], prices[i]));
            maxprice[n – i – 1] = (i == 0 ? prices[n – 1] : max(maxprice[n – i], prices[n – i – 1]));
        }
        for (int i = 0; i < n; ++i) {
            ans = max(ans, maxprice[i] – minprice[i]);
        }
        return ans;
    }
};

本代码提交AC,用时9MS。

LeetCode Search in Rotated Sorted Array II

81. Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Follow up:

  • This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
  • Would this affect the run-time complexity? How and why?

这一题在LeetCode Search in Rotated Sorted Array的基础上,增加了数组有重复元素的约束,其实相当于LeetCode Search in Rotated Sorted ArrayLeetCode Find Minimum in Rotated Sorted Array II的结合,搜索框架采用前者(即先找到有序的半个部分,再决定丢弃哪半个部分),边界判断采用后者(即遇到中间和边缘相等时,移动边缘)。代码上只是在前者代码的基础上增加了一个else分支。完整代码如下:

class Solution {
public:
    bool search(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size() – 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target)
                return true;
            if (nums[mid] < nums[r]) {
                if (target > nums[mid] && target <= nums[r]) {
                    l = mid + 1;
                }
                else {
                    r = mid – 1;
                }
            }
            else if (nums[mid] > nums[r]) {
                if (target >= nums[l] && target < nums[mid]) {
                    r = mid – 1;
                }
                else {
                    l = mid + 1;
                }
            }
            else {
                –r;
            }
        }
        return false;
    }
};

本代码提交AC,用时12MS。因为多了一个else分支,算法最坏情况下,会达到O(n)的复杂度。

二刷。思路相同,使用递归实现,代码如下:

class Solution {
public:
	bool SearchRange(vector<int>& nums, int l, int r, int target) {
		if (l > r)return false;
		if (l == r)return nums[l] == target;

		int mid = l + (r - l) / 2;
		if (nums[mid] == target)return true;

		if (nums[l] < nums[mid]){
			if (target >= nums[l] && target < nums[mid])return SearchRange(nums, l, mid - 1, target);
			else return SearchRange(nums, mid + 1, r, target);
		}
		else if (nums[l] > nums[mid]) {
			if (target > nums[mid] && target <= nums[r])return SearchRange(nums, mid + 1, r, target);
			else return SearchRange(nums, l, mid - 1, target);
		}
		else {
			++l;
			return SearchRange(nums, l, r, target);
		}
	}
	bool search(vector<int>& nums, int target) {
		return SearchRange(nums, 0, nums.size() - 1, target);
	}
};

本代码提交AC,用时4MS。

LeetCode Search in Rotated Sorted Array

33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

这一题和LeetCode Find Minimum in Rotated Sorted Array类似,只不过不是查找最小值,而是查找某个target是否存在。也是采用二分查找的思路,首先判断nums[m]和nums[r]的关系,如果nums[m]<nums[r],说明右半部分是有序的,看看target是否在该部分范围内,如果在,则l=mid+1;否则r=mid-1。如果nums[m]>nums[r],说明右半部分无序,则左半部分有序,看看target是否在左半部分范围内,如果在,则r=mid-1;否则l=mid+1。如此循环下去。

完整代码如下:

class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size() – 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[mid] < nums[r]) {
                if (target > nums[mid] && target <= nums[r]) {
                    l = mid + 1;
                }
                else {
                    r = mid – 1;
                }
            }
            else {
                if (target >= nums[l] && target < nums[mid]) {
                    r = mid – 1;
                }
                else {
                    l = mid + 1;
                }
            }
        }
        return -1;
    }
};

本代码提交AC,用时9MS。

二刷。用递归方法实现,每次判断区间的左边是否小于右边,如果是的话,说明是有序的,常规二分即可;如果不是,则取中点,递归在其左边和右边搜索。由于取了中点后,必定有一边是有序的,则要么在有序区间搜索,要么在另一边搜索,即每次是减半的,所以时间复杂度也是O(lgN)。

完整代码如下:

class Solution {
public:
	int BinarySearch(vector<int>& nums, int target, int left, int right) {
		if (left > right)return -1;
		if (left == right) {
			if (nums[left] == target)return left;
			else return -1;
		}
		if (nums[left] < nums[right]) {
			if (target >= nums[left] && target <= nums[right]) {
				int mid = left + (right - left) / 2;
				if (nums[mid] == target)return mid;
				else if (nums[mid] < target)return BinarySearch(nums, target, mid + 1, right);
				else return BinarySearch(nums, target, left, mid - 1);
			}
			else {
				return -1;
			}
		}
		else {
			int mid = left + (right - left) / 2;
			int lans = BinarySearch(nums, target, left, mid);
			int rans = BinarySearch(nums, target, mid + 1, right);
			if (lans != -1)return lans;
			if (rans != -1)return rans;
			return -1;
		}
	}
	int search(vector<int>& nums, int target) {
		return BinarySearch(nums, target, 0, nums.size() - 1);
	}
};

本代码提交AC,用时0MS。

三刷。迭代方法还是主流,和常规二分搜索的代码框架是一致的。但是一刷的时候是先判断右半部分是否有序,有点不符合直觉,如果简单的先判断左半部分,会出bug,比如[3,1],要找1的时候,此时m=0,和l=0是相同的,如果简单的用nums[l]<nums[m]来判断左边是否有序的话,会有问题,此时m==l,所以左边也可以看做是有序的,但不满足nums[l]<nums[s]。所以需要额外加一个l==m的判断。完整代码如下:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r) {
            int m = l + (r - l) / 2;
            if(nums[m] == target) return m;
            
            if(l == m || nums[l] < nums[m]) { // l == m 左边只有一个元素,左边也是有序的
                if(target >= nums[l] && target < nums[m]) r = m - 1;
                else l = m + 1;
            } else {
                if(target > nums[m] && target <= nums[r]) l = m + 1;
                else r = m - 1;
            }
        }
        
        return -1;
    }
};

本代码提交AC, 用时8MS。