购买和销售股票的最佳时机，编程兄，你懂的！

别急别急，先来两道编程题热热身！

 1．两数之和

【题目】

给定整数的一个数组，找出这样的两个数，它们的加和等于一个特定的目标数字（target）。

twoSum函数应该返回两个数的索引，这两个数相加等于目标数字，其中index1必须小于index2。请注意，返回的结果（index1和index2）不是基于0的。

可以假设对每一个输入来说，都只有一个解决方案。

输入：numbers={2, 7, 11, 15}，target=9

输出：index1=1，index2=2

【解析】

最直观明了的解法是通过暴力搜索，使用两个嵌套的循环来遍历所有可能，时间复杂度为O(n*n)。但是很明显，这不是出题者想看到的结果。

有两种解法。

解法一，哈希方法。

从左往右扫描一遍，然后将整数及其索引存到map中。然后再扫描一遍，对每一个整数K，搜索target-K在map中是否存在即可。如果存在，则输出K及target-K的下标。时间复杂度为O(n)。

解法二，双指针扫描。

首先将数组排序，然后双指针从首尾往中间扫描。时间复杂度为O(n*lgn)。因为要求返回原数组的下标，所以在排序的时候还要有额外的数组来存储下标信息。

注意：双指针扫描

双指针问题是对于普通问题的一种特殊解法，往往要求问题是线性的，可以用双指针来遍历，从许多解中找到一个最大或者最小的解。双指针一般可以分别放在首尾处，用来往中间靠拢，或者都放在头部，用来划分区间。

【代码】

解法一的代码实现如下：

1:　 vector< int> twoSum(vector< int>&numbers, int target) {　

2:　　　map< int, int> mapping;　

3:　　　vector< int> result;　

4:　　　for(int i =0; i<  numbers.size(); i++)　　　　　

5:　　　{　

6:　　　　mapping[numbers[i]]=i;　

7:　　　}　

8:　　　for(int i =0; i<  numbers.size(); i++)　

9:　　　{　

10:　　　　int searched = target - numbers[i];　

11:　　　　if(mapping.find(searched) != mapping.end()&&i!=mapping [searched])　

12:　　　　{　

13:　　　　　result.push_back(i+1);　

14:　　　　　result.push_back(mapping[searched]+1);　

15:　　　　　break;　

16:　　　　}　

17:　　　}　

18:　　　return result;　

19:　　}　

解法二的代码实现如下：

1:struct Node　

2: {　

3:　　int val;　

4:　　int index;　　　

5:　　Node(int pVal, int pIndex):val(pVal), index(pIndex){}　

6: };　

7: static bool compare(const Node &left, const Node &right)　

8: {　

9:　　return left.val <  right.val;　

10:}　

11: vector< int> twoSum(vector< int>&numbers, int target) {　

12:　　vector< Node> elements;　

13:　　for(int i =0; i<  numbers.size(); i++)　

14:　　{　

15:　　　 elements.push_back(Node(numbers[i], i));　

16:　　}　

17:　　std::sort(elements.begin(), elements.end(), compare);　

18:　　int start = 0, end = numbers.size()-1;　

19:　　　　 vector< int> result;　

20:　　　　 while(start <  end)　

21:　　　 {　

22:　　　　 int sum = elements[start].val + elements[end].val;　

23:　　　　if(sum == target)　

24:　　　　　{　

25:　　　　　result.push_back(elements[start].index+1);　

26:　　　　　　　if(elements[start].index <  elements[end].index)　

27:　　　　result.push_back(elements[end].index+1);　

28:　　　　　　　else　

29:　　　　result.insert(result.begin(),elements[end].index+1);　

30:　　　　　　　break;　

31:　　　　　 }　

32:　　　　　 else if(sum > target)　

33:　　　　　　　end--;　

34:　　　　　 else　

35:　　　　　　　start++;　　　　　　　　 

36:　　　　}　

37:　　　　return result;　

38:　}　

2.  能装最多的水的容器

给定n个非负的整数a1,a2, ...,an，其中，每个整数表示坐标为(i,ai)的一个点。从(i,ai)到(i,0)的两点之间，绘制线段i，从而绘制出n条垂直的线段。找到两条线段，它们和x轴一起形成一个容器，这个容器所能装的水最多。

注意，不能倾斜该容器。

【解析】

这是很有意思的一道题目，思考起来很费劲，但是一旦找到了突破点，一切就很好理解了。

关键的思路在于：对于任意的容器，它的容积取决于最短的那个板子。

思路转过来了吗？解法其实很简单。用双指针从首尾往中间扫描数组。扫描过程中，只移动短板端的指针。因为容器的容积取决于短板，只有在改变短板的时候才有可能产生新的最大值。

【代码】

1:　　int maxArea(vector< int>&height) {　

2:　　　// Start typing your C/C++ solution below　

3:　　　// DO NOT write int main() function　

4:　　　int start =0;　

5:　　　int end = height.size()-1;　

6:　　　int maxV = INT_MIN;　

7:　　　while(start< end)　

8:　　　{　

9:　　　　int contain = min(height[end], height[start]) * (end-start);　

10:　　　　maxV = max(maxV, contain);　

11:　　　　if(height[start]< = height[end])　

12:　　　　{　

13:　　　　　start++;　

14:　　　　}　

15:　　　　else　

16:　　　　{　

17:　　　　　end--;　

18:　　　　}　

19:　　　}　

20:　　　return maxV;　

21:　　}

重点来啦~~购买和销售股票的最佳时机

1. 假设有一个数组，其第i个元素是一支给定的股票在某一天i的价格。

如果最多只允许你完成一次交易（例如，购买或销售一次该股票的份额），设计一个算法，来找到最大的赢利点。

【解析】

这个题目比较简单。因为题目设定了只能交易一次，所以只要找到数组中任意两元素间最大的一个差值就可以了。当从左往右扫描数组的时候，用两个变量来记录当前最低价minV和当前最大利润maxP。对于每一个数组元素，计算其与最低价minV的差价，如果该差价小于maxP，那么该元素不可能为所求元素，直接跳过；如果该差价大于maxP，则该元素产生了更大利润，用该差价替换maxP。

【代码】

1:　　int maxProfit(vector< int>&prices) {　

2:　　　// Start typing your C/C++ solution below　

3:　　　// DO NOT write int main() function　

4:　　　int minV=INT_MAX; int max =0;　

5:　　　int diff=0;　

6:　　　for(int i =0; i<  prices.size(); i++)　

7:　　　{　

8:　　　　 if(prices[i]< minV) minV = prices[i];　

9:　　　　 diff = prices[i] - minV;　

10:　　　　if(max< diff)　

11:　　　　　max = diff;　

12:　　　}　

13:　　　return max;　

14:　　}　

2.  假设有一个数组，其第i个元素是一支给定的股票在某一天i的价格。

设计一个算法，来找到最大的赢利点。你可以进行任意多次的交易（例如，多次购买和销售该股票的份额）。然而，你不能同时进行多次交易（例如，在再次购买之前，必须先销售该股票）。

【解析】

因为可以交易无限次数，所以最大的交易利润，就是所有交易利润的总和。从左往右扫描数组，只要是交易利润（差价>0），都加起来，即为所求。

【代码】

1:　　int maxProfit(vector< int>&prices) {　

2:　　　// Start typing your C/C++ solution below　

3:　　　// DO NOT write int main() function　

4:　　　int max=0;　

5:　　　int sum = 0;　

6:　　　for(int i =1; i<  prices.size(); i++)　

7:　　　{　

8:　　　　int diff = prices[i] -prices[i-1];　

9:　　　　if(diff>0)　

10:　　　　　sum+=diff;　

11:　　}　

12:　　　 return sum;　

13:　　}　

3.  假设有一个数组，其第i个元素是一支给定的股票在某一天i的价格。

设计一个算法，来找到最大的赢利点。你最多可以进行两次交易。

注意，你不能同时进行多次交易（例如，在再次购买之前，必须先销售该股票）。

【解析】

当题目把交易次数限定为两次，那么此题就变为一道一维动态规划问题。根据任意一个数组的下标i，可以将数组分为两个部分：A[0,i]和A[i+1, n]，那么两个数组分别产生两个利润MaxProfit(0,i)和MaxProfit(i+1,n)，所以对于最大利润，我们可以用如下表达式来表述：

FinalMaxProfix = max(MaxProfit(0,i) + MaxProfit(i+1, n))　0< =i<n

这样，题目就变简单了，事先预处理一下数组，计算好MaxProfit(0,i)和MaxProfit(i+1,n)。然后将数组再扫描一遍，就可以轻松地计算出FinalMaxProfit。

【代码】

1:　int maxProfit(vector< int>&prices) {　 

2:　　　 if(prices.size() < = 1) return 0;　

3:　　　 vector< int> maxFromLeft(prices.size(), 0);　

4:　　　 vector< int> maxFromRight(prices.size(), 0);　

5:　　　 int minV = INT_MAX, maxP = INT_MIN;　

6:　　　 for(int i =0; i<  prices.size(); i++)　

7:　　　 {　

8:　　　　　　if(minV > prices[i]) minV = prices[i];　

9:　　　　　　int temp = prices[i] - minV;　

10:　　　　　　if(temp > maxP) maxP = temp;　

11:　　　　　　maxFromLeft[i] = maxP;　

12:　　　 }　

13:　　　 int maxV = INT_MIN;　

14:　　　 maxP = INT_MIN;　

15:　　　 for(int i =prices.size()-1; i>=0; i--)　

16:　　　 {　

17:　　　　　　if(maxV <  prices[i]) maxV = prices[i];　

18:　　　　　　int temp = maxV - prices[i];　

19:　　　　　　if(temp > maxP) maxP = temp;　

20:　　　　　　maxFromRight[i] = maxP;　

21:　　　 }　

22:　　　 int maxProfit = INT_MIN;　

23:　　　 for(int i =0; i<  prices.size()-1; i++)　

24:　　　 {　

25:　　　　　　int sum = maxFromLeft[i] + maxFromRight[i+1];　

26:　　　　　　if(sum > maxProfit) maxProfit = sum;　

27:　　　 }　

28:　　　 if(maxProfit <  maxFromRight[0])　

29:　　　　　　maxProfit = maxFromRight[0];　

30:　　　 return maxProfit;　 

31:　}　 

【说明】

代码第6～12行和代码第15～21行可以合并到一个for循环中，这里将其分开是考虑可读性。

以上内容节选自《编程谜题》。

关于本书：

《Coding Puzzles》英文版最早起源于我在博客（http://fisherlei.blogspot.com）上的连载文章。因为我个人喜欢对leetcode的算法和编程题目做出分析和解答并写成博客在网络上分享，长期以来，积累了不少解题分析和思路方面的素材。编纂成书后受到了很多读者的欢迎，当然，也收到了很多的建议和批评。

读者的热情反馈，超出了我最早编写本书的预期，也促使我进一步编写和出版了英文版《Coding Puzzles》（第2版）（电子版）。该版本发布不久，我就收到了国内出版社的邀约，于是，有了大家手中这本《编程谜题》。

和最早的英文版相比，本书主要做了以下的修改和改进。

1．根据读者反馈，修改了第1版的错误及疏漏，补充了新的图示及分析，使得内容上可读性更好。

2．增加了更多的趣题。相比第1版，本版增加了23道新的题目。

3．本书最后增加了一个附录，包括了业界一些常用分布式理论及产品设计的一些资料。希望可以帮助读者更好地了解业界的发展。

这本书的主要思路，是利用计算机算法知识，以分析和解决谜题的形式，总结如何把计算机常用算法及数据结构等知识应用到相关的问题上，提高读者分析问题、解决问题的能力；进而，希望培养读者的编程素养，帮助读者更好地从事程序设计的相关工作。

在分析解题思路的过程中，涉及一些算法和数据结构的知识，由于本书是面向解题方法和思路的，并没有针对这些算法和数据结构知识给出详细的讲解和介绍。如果读者需要温习计算机常用算法及数据结构的相关知识，建议阅读Thomas H. Cormen的《Introduction to Algorithms》或相关教科书。

需要说明的是，本书中的题目只是在程序员面试中一些比较有代表性的题目，而不是一个包罗万象的习题集。如何在纷繁复杂的题目中，找到其后不变的东西，才是算法分析的真谛。

如果读者希望亲自实践书中的题目，可以访问北美最流行的网站https://leetcode.com/。如果希望参与后续的讨论，可以访问我的博客：http://www.cnblogs.com/codingtmd/或http://fisherlei-blogspot.com。书中的示例代码，可以到https://github.com/codingtmd/leetcode下载。

作者：

codingtmd，2001～2005年于中国科学技术大学获得计算机学士学位。2008年获中国科学院软件所软件工程中心工学硕士学位。2008～2014年供职于微软，从事于数据库、分布式系统、云计算基础架构及服务等方向的工作，参与了Bing和Windows Azure等系统的研发工作。目前就职于Facebook，负责新产品研发及第三方云服务平台建设。

codingtmd，曾供职于微软，从事于数据库、分布式系统、云计算基础架构及服务等方向，参与

了Bing和Windows Azure等系统的研发工作。目前就职于Facebook，负责新产品研发及第三

方云服务平台建设。爱好算法及系统架构设计，酷爱读书，喜欢冒险。 他的博客是http://www.cnblogs.com/codingtmd或http://fisherlei-blogspot.com

本文转载自异步社区

原文链接：