今天經(jīng)營(yíng)著世界最大的搜索業(yè)務(wù)的某公司在位于廣州市海珠區(qū)珠江河畔的某著名大學(xué)開(kāi)了一次招聘會(huì)，申請(qǐng)實(shí)習(xí)軟件工程師的都要筆試。于是我也去寫(xiě)了，雖然我不是位于廣州市海珠區(qū)珠江河畔的某著名大學(xué)的學(xué)生，反正人人都能去。

    第一道題，把字符串中相連的重復(fù)字符處理成一個(gè)。例如aaabbcddcc處理成abcdc。因?yàn)楹俚臅r(shí)候才往Vczh Free Script 2.0中添加了一個(gè)Mark-Compact Collector，因此算法也就模仿了一下Mark-Compact Collector，也就是把所有該刪掉的字符換成'\0'，依次讀取并跟右邊最近的非'\0'字符置換一直到完。

    第二道題，已知數(shù)列中有1、2、3三種數(shù)字，并且可以?xún)蓛芍脫Q。求最小置換次數(shù)的方法讓數(shù)列遞增。

    我用了這樣的方法：
    ·找到并保存每一個(gè)位置中應(yīng)該存放的數(shù)字，也就是一1、2、3的數(shù)目都跟數(shù)列相同的遞增數(shù)列bi。
    ·遍歷ai，找到ai≠bi的i并做如下處理：
        ·尋找aj使得j>i且bi＝aj且bi≠bj
        ·在這些j中尋找k使得bk＝ai
        ·如果k非空則讓m∈k，否則讓m∈j并讓下一步的k的勢(shì)最大
        ·置換ai和am

    一個(gè)好像很和諧但是事實(shí)上不知道和諧不和諧的證明：
        j>i且bi＝aj且bi≠bj這個(gè)條件是必定滿(mǎn)足的。如果不滿(mǎn)足，則很容易證明ai和bi中1、2、3的數(shù)目不完全相同。
        k非空使得一次置換產(chǎn)生了兩個(gè)正確的結(jié)果。
        對(duì)于每一次置換，如果讓m1∈j且{m1}∩k為空，m2∈k，則有
            選擇m1而不是m2有可能減少、保持或增大下一次置換中k的勢(shì)；
            選擇m2則下一次置換中k的勢(shì)不變。
        這樣的話，選擇m1最好的結(jié)果就是讓這次置換不影響全部的置換，最壞的結(jié)果是增加了置換的次數(shù)；
        選擇m2則不會(huì)影響全部的置換。
        因此只需每一次都盡量選擇m2中的值，對(duì)于k∩j為空的情況，則計(jì)算所有j得到的下一步的k的勢(shì)dj，選擇最大的j即可。

    第三道題，華容道解謎器。只好弄了個(gè)寬度優(yōu)先搜索。

    以上純屬YY。

    P.S.
    ·選擇題里面有一道問(wèn)ABCDEFGHIJ的全排列中滿(mǎn)足A在B前面的數(shù)量有多少？答案：因?yàn)锳和B是對(duì)稱(chēng)的，因此對(duì)于任意一個(gè)確定的A和B的位置的集合，A在B前的概率是0.5，因此答案為10!/2。

    ·同時(shí)擁有操作系統(tǒng)、開(kāi)發(fā)工具、數(shù)據(jù)庫(kù)引擎、辦公軟件、游戲平臺(tái)等多項(xiàng)業(yè)務(wù)的某著名軟件公司的招聘活動(dòng)我也參加了一次，結(jié)果發(fā)現(xiàn)經(jīng)營(yíng)著世界最大的搜索業(yè)務(wù)的某公司和同時(shí)擁有操作系統(tǒng)、開(kāi)發(fā)工具、數(shù)據(jù)庫(kù)引擎、辦公軟件、游戲平臺(tái)等多項(xiàng)業(yè)務(wù)的某著名軟件公司【好像】有一個(gè)特點(diǎn)。經(jīng)營(yíng)著世界最大的搜索業(yè)務(wù)的某公司喜歡出最優(yōu)解題目，同時(shí)擁有操作系統(tǒng)、開(kāi)發(fā)工具、數(shù)據(jù)庫(kù)引擎、辦公軟件、游戲平臺(tái)等多項(xiàng)業(yè)務(wù)的某著名軟件公司喜歡出最高速題目。而且經(jīng)營(yíng)著世界最大的搜索業(yè)務(wù)的某公司很喜歡去在位于廣州市海珠區(qū)珠江河畔的某著名大學(xué)，而同時(shí)擁有操作系統(tǒng)、開(kāi)發(fā)工具、數(shù)據(jù)庫(kù)引擎、辦公軟件、游戲平臺(tái)等多項(xiàng)業(yè)務(wù)的某著名軟件公司則很喜歡去位于廣州市五山的某著名理工大學(xué)。