算法小測(cè)試

實(shí)驗(yàn)室大師兄開(kāi)了個(gè)小灶，講了一些簡(jiǎn)單的算法題給我們開(kāi)拓一下思路。現(xiàn)在把這次講到的幾個(gè)測(cè)試題記錄在這里艺蝴，一來(lái)是再過(guò)一遍加深印象，二來(lái)以后也可以看看鸟废。

測(cè)試題1--判斷和為s的元素的存在性

題目：已知數(shù)組a[0],a[1],...,a[i],a[i+1],...,a[n]以及一個(gè)整數(shù)s;其中n范圍為10^5,a[i]的范圍為10^9,判斷數(shù)組a[n]中是否存在a[i]和a[j],使得s=a[i]+a[j],其中i可以等于j猜敢。

我的思路：最快能想到的自然是枚舉法，就是將數(shù)組a[n]中的每?jī)蓚€(gè)元素都相加看能不能等于s盒延，但是這個(gè)方法很蠢缩擂，時(shí)間復(fù)雜度是o(n^2)。
那有沒(méi)有更好的方法兰英？當(dāng)然有撇叁，其實(shí)這種從數(shù)組中找數(shù)的題如果一遍遍歷無(wú)法解決問(wèn)題供鸠，那么就要先進(jìn)行一下排序處理了畦贸，雖然排序過(guò)程會(huì)增加復(fù)雜度，但是排序后就可以利用元素之間的相關(guān)信息解題，事半功倍薄坏。
所以先對(duì)數(shù)字進(jìn)行排序趋厉，方法很多，快排來(lái)做就是o(nlog(n))胶坠。
堆排序后的數(shù)組從兩頭開(kāi)始遍歷君账，i=0開(kāi)始，j=n開(kāi)始沈善，此時(shí)a[i]最小乡数，a[j]最大。然后按照下面的規(guī)則進(jìn)行移動(dòng)：

<pre>
while(i<=j){
if a[i]+a[j]==s
return true;
else if a[i]+a[j]<s
i++;
else if a[i]+a[j]>s
j--;
}
return false;
</pre>

這種方法對(duì)于排序后的數(shù)組來(lái)說(shuō)得到結(jié)果的時(shí)間復(fù)雜度是o(n);再考慮前面排序的過(guò)程闻牡，整體的復(fù)雜度就是max(o(nlog(n)),o(n))=o(nlog(n))净赴。

要理解這種方法其實(shí)可以把a(bǔ)[i]+a[j]想象為一個(gè)二維矩陣，縱軸和橫軸都是a[0]...a[n]罩润，形狀如：
<pre>
--------------------------------->
| a[0], a[1], a[2],..., a[n]
| a[0] - - - -
| a[1] - - - -
| ...
| a[n] - - - -
/
</pre>

矩陣中元素的特點(diǎn)是隨著箭頭的方向玖翅，矩陣中元素所對(duì)應(yīng)橫縱坐標(biāo)a[i]和a[j]之和不斷增大。再明顯點(diǎn)就是：
<pre>
--------------------------------->
| a[0], a[1], a[2],..., a[n]
| a[0] 小 小 小 未2
| a[1] 小 小 X 大
| ...
| a[n] 未1 未1 大 大
/
</pre>

矩陣中每個(gè)元素的值都是其橫縱坐標(biāo)a[i]與a[j]的和割以，當(dāng)前位置為X金度，“小”對(duì)應(yīng)位置的值小于“X”對(duì)應(yīng)的值，“大”對(duì)應(yīng)位置的值大于“X”對(duì)應(yīng)的值严沥，剩余的“未1”和“未2”對(duì)應(yīng)的值和“X”的關(guān)系是未知的猜极。這道題就轉(zhuǎn)化為判斷在這個(gè)矩陣中是否存在值為s的元素。
現(xiàn)在假設(shè)當(dāng)前值x比s小消玄，說(shuō)明“小”對(duì)應(yīng)的值都要小于s魔吐，那么我們應(yīng)該在“大”，“未1”和“未2”中繼續(xù)找莱找；反之亦然酬姆，當(dāng)前置x比s大時(shí)，說(shuō)明“大”對(duì)應(yīng)的值都要大于s奥溺，那么我們就應(yīng)該在“小”辞色，“未1”和“未2”中繼續(xù)找。這個(gè)過(guò)程就是對(duì)搜索區(qū)域進(jìn)行簡(jiǎn)化排除的過(guò)程浮定。
那么現(xiàn)在又有一個(gè)問(wèn)題相满，這每一次的簡(jiǎn)化得到的剩余的區(qū)域是個(gè)多邊形，并不是矩形桦卒，不能很好的實(shí)現(xiàn)在一個(gè)矩形模板上簡(jiǎn)化問(wèn)題的目的立美。如何才能做到每一次簡(jiǎn)化后剩余的還是一個(gè)矩形呢。很簡(jiǎn)單方灾，直到隨意選擇左下角或者右上角作為起始判斷位置建蹄，然后進(jìn)行簡(jiǎn)化就可以了碌更。比如從右上角開(kāi)始，那么第一次簡(jiǎn)化時(shí)x>s就可以排除最右邊那一列洞慎，如果x<s就可以排除最上邊那一行痛单，剩下的就還是一個(gè)矩形了。然后不斷簡(jiǎn)化劲腿，直到排除掉所有的元素旭绒，或者找到x==s時(shí)為止，問(wèn)題就解決了焦人。
把這個(gè)理論實(shí)現(xiàn)為代碼時(shí)就是像上面的偽代碼一樣挥吵，從最左和最右同時(shí)開(kāi)始遍歷。
當(dāng)然還有很多其他的方法可以解這道題花椭，但是這種方法應(yīng)該是時(shí)間復(fù)雜度最小的了蔫劣，如果有人有更好的方法可以下來(lái)交流。

測(cè)試題2--計(jì)算三角形面積

題目：給定一個(gè)三角形三個(gè)定點(diǎn)的坐標(biāo)个从，計(jì)算這個(gè)三角形的面積脉幢。
解法：這個(gè)題有很多解法，較簡(jiǎn)單的就是通過(guò)公式計(jì)算嗦锐，比如：

1. 海倫公式：sqrt(d(d-a)(d-b)(d-c))嫌松，其中a,b,c為三角形的三邊長(zhǎng)，d為三邊和的一般奕污，就是d=(a+b+c)/2;這種解法需要使用公式先計(jì)算出三條邊的長(zhǎng)度萎羔。算法缺點(diǎn)就是計(jì)算機(jī)計(jì)算時(shí)會(huì)有誤差存在。
2. 使用面積=底×高/2的公式碳默，同樣的也需要使用其他公式計(jì)算高贾陷，還有邊長(zhǎng)，缺點(diǎn)也是會(huì)有誤差嘱根。
3. 利用向量外積公式：向量的外積還是一個(gè)向量髓废，新向量的模為：|AB×AC|=(|AB|×|AC|×sin(θ));三角形面積=(1/2)(AB×AC)=(1/2)(|AB|×|AC|×sin(θ))；所以可以根據(jù)向量的外積得到三角形的面積该抒。外積的坐標(biāo)表示為：(x1,y1,z1)×(x2,y2,z2)=(y1z2-y2z1,z1x2-z2x1,x1y2-x2y1)慌洪，向量的外積是建立在三維空間上的，我們要求三角形的面積就可以把其中一個(gè)維度的坐標(biāo)定位0凑保，比如z1=z2=0冈爹，這樣就得到(x1,y1,0)×(x2,y2,0)=(0,0,x1y2-x2y1)。假設(shè)三點(diǎn)A(x1,y1),B(x2,y2),C(x3,y3)欧引，則AB=(x2-x1,y2-y1),AC=(x3-x1,y3-y1);則面積=(1/2)|AB×AC|=(1/2)((x2-x1)×(y3-y1)-(y2-y1)×(x3-x1));
4. 多邊形面積公式：就是將多邊形分割為多個(gè)三角形频伤，然后求所有三角形的總和，所以本質(zhì)也是利用了上邊的向量外積公式芝此。

測(cè)試題3--求最短距離

題目：在二維直角坐標(biāo)系中有一個(gè)與坐標(biāo)平行的矩陣憋肖，給出這個(gè)矩陣的四個(gè)點(diǎn)A,B,C,D的坐標(biāo)因痛，以及一個(gè)矩陣外的P點(diǎn)坐標(biāo)，計(jì)算P點(diǎn)到矩陣邊界上任意一點(diǎn)的距離中的最短距離瞬哼。

我的思路：這個(gè)題最開(kāi)始我想到的是把矩形的四條邊無(wú)限延長(zhǎng)，這樣坐標(biāo)系就被分為了8個(gè)區(qū)域租副，當(dāng)P點(diǎn)在這8個(gè)區(qū)域中的正上下左右方時(shí)坐慰，最短距離就是P點(diǎn)橫坐標(biāo)和縱坐標(biāo)與A,B,C,D四個(gè)點(diǎn)坐標(biāo)的橫坐標(biāo)和縱坐標(biāo)差值中的最小值；而當(dāng)P點(diǎn)在剩余的四個(gè)區(qū)域時(shí)用僧，最短距離就是P點(diǎn)和A,B,C,D四個(gè)點(diǎn)距離中的最小值结胀。
我的這個(gè)思路當(dāng)然是可行的，但是不夠簡(jiǎn)潔责循，雖然和最優(yōu)答案很接近了糟港，但是沒(méi)有抓住本質(zhì)。下面來(lái)說(shuō)以下更好的解法院仿。

假定最短連線中除P(p1,p2)點(diǎn)外的另一個(gè)點(diǎn)為S(s1,s2)秸抚，那么s1=max(min(a1,b1),min(max(a1,b1),p1));s2=max(min(a2,c2),min(max(a2,c2),p2)),然后直接求SP的距離就可以了。這里的s1就是a1歹垫，b1和p1三個(gè)數(shù)排序后位于中間的那個(gè)數(shù)的值剥汤，s2就是a2，c2和p2三個(gè)數(shù)排序后位于中間的那個(gè)數(shù)的值排惨。

吭敢。。暮芭。未完待續(xù)鹿驼。。辕宏。