三星的兩道編程題2019-10-30

#include<iostream>
#include<sstream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
vector<int> sparseInput(string A, const int n){
    vector<int> res;
    res.reserve(2 * (n + 2));
    string result;
    int counter = 0;
    //將A賦值給一個(gè)stringstream流
    stringstream input(A);
    while (input >> result){
        //string轉(zhuǎn)int
        res.push_back(stoi(result.c_str()));
    }
    return res;
}
struct point
{
    int x;
    int y;
};
vector<point> parsePoints(vector<int> data){
    vector<int>::iterator it = data.begin();
    vector<point> points;
    point p;
    for (it; it < data.end(); it++){
        p.x = *it;
        it++;
        p.y = *it;
        points.push_back(p);
    }
    points.shrink_to_fit();
    return points;
}
vector<vector<int>> enumDistance(vector<int> data, vector<point> points){
    vector<point>::iterator itStart = points.begin(), itDistinct = points.begin();
    int row = 0, col = 0, d;
    vector<vector<int>> distinct;
    for (itStart; itStart < points.end(); itStart++){
        vector<int> vec;
        for (itDistinct; itDistinct < points.end(); itDistinct++){
            d = abs((*itStart).x - (*itDistinct).x) + abs((*itStart).y - (*itDistinct).y);
            vec.push_back(d);
            cout << d << ' ';
        }
        cout << endl;
        itDistinct = points.begin();
        vec.shrink_to_fit();
        distinct.push_back(vec);
    }
    distinct.shrink_to_fit();
    return distinct;
}

void findOptimalPath(vector<vector<int>> dist, vector<point> points){
    vector<int> keys;
    int counter = 0;
    for (int i = 0; i < points.size(); i++)
        keys.push_back(i);
    keys.shrink_to_fit();
    while (next_permutation(keys.begin(), keys.end()))
    {
        counter++;
        vector<int>::iterator it = keys.begin();
        for (it; it < keys.end(); it++){
            cout << '(' << (points[*it]).x << ',' << (points[*it]).y << ')' << ' ';
        }
        cout << endl;
    }
    cout << counter;//五個(gè)元素時(shí)counter為119丑搔,此處不算初始序列
}
int main(){
    string firstLine = "end";
    //讀入一個(gè)字符串硫惕,并以回車結(jié)束
    string secondLine;
    vector<vector<int>> dist;
    while (1){
        cin >> firstLine;
        if (firstLine == "end")
            break;
        getchar();
        getline(cin, secondLine, '\n');
        vector<int> resSecond = sparseInput(secondLine, stoi(firstLine.c_str()));
        int home[2] = { resSecond[0], resSecond[1] };
        int office[2] = { resSecond[2], resSecond[3] };
        resSecond.erase(resSecond.begin(), resSecond.begin() + 4);
        resSecond.shrink_to_fit();
        vector<point> points = parsePoints(resSecond);
        dist = enumDistance(resSecond, points);
        findOptimalPath(dist, points);
        firstLine = "end";
    }
    system("pause");
    return 0;
}

第二道

#include<iostream>
#include<sstream>
#include<vector>
#include<string>
using namespace std;
vector<int> sparseInput(string A){
    vector<int> res;
    string result;
    //將A賦值給一個(gè)stringstream流
    stringstream input(A);
    while (input >> result){
        //string轉(zhuǎn)int
        res.push_back(atoi(result.c_str()));
    }
    return res;
}
int findParent(vector<int> data, int cur){
    vector<int>::iterator it = data.end() - 1;
    int counter = 0;
    for(it; it >= data.begin(); it--){
        if(counter % 2 == 0){
            if (*it == cur)
                return *(it - 1);
        }
        counter++;
        if (it == data.begin()){
            break;
        }
    }
    return -1;
}
vector<int> enumParents(vector<int> data, int v){
    vector<int> parents;
    int p = findParent(data, v);
    if (p != -1){
        while (p != -1){
            parents.push_back(p);
            p = findParent(data, p);

        }
        return parents;
    }
    parents.push_back(v);
    return parents;
    
}
int find(vector<int> second, int cur){
    int counter = second.size() - 1;
    while (counter + 1){
        if (second[counter] == cur){
            return cur;
        }
        counter--;
    }
    return -1;
}
int findLatestCommonParent(vector<int> first, vector<int> second){
    vector<int>::iterator it = first.begin();
    int p;
    for (it; it < first.end(); it++){
        p = find(second, *it);
        if (p != -1)
            break;
    }
    return p;
    
}
int main(){
    string firstLine = "end";
    //讀入一個(gè)字符串夷家,并以回車結(jié)束
    string secondLine;
    while (1){
        getline(cin, firstLine, '\n');
        if (firstLine == "end")
            break;
        vector<int> resFirst = sparseInput(firstLine);
        getline(cin, secondLine, '\n');
        vector<int> resSecond = sparseInput(secondLine);
        int latestCommonParent;
        vector<int> parentsFirst = enumParents(resSecond, resFirst[2]);
        vector<int> parentsSecond = enumParents(resSecond, resFirst[3]);
        latestCommonParent = findLatestCommonParent(parentsFirst, parentsSecond);
        cout << latestCommonParent << endl;
        firstLine = "end";
    }
    system("pause");
    return 0;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末熟尉,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子莹菱,更是在濱河造成了極大的恐慌鞭呕,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,372評(píng)論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件篇恒,死亡現(xiàn)場(chǎng)離奇詭異扶檐,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)胁艰,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,368評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門款筑,熙熙樓的掌柜王于貴愁眉苦臉地迎上來智蝠,“玉大人,你說我怎么就攤上這事奈梳¤就澹” “怎么了?”我有些...
    開封第一講書人閱讀 162,415評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵攘须,是天一觀的道長漆撞。 經(jīng)常有香客問我,道長阻课,這世上最難降的妖魔是什么叫挟? 我笑而不...
    開封第一講書人閱讀 58,157評(píng)論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮限煞,結(jié)果婚禮上抹恳,老公的妹妹穿的比我還像新娘。我一直安慰自己署驻,他們只是感情好奋献,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,171評(píng)論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著旺上,像睡著了一般瓶蚂。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上宣吱,一...
    開封第一講書人閱讀 51,125評(píng)論 1 297
  • 那天窃这,我揣著相機(jī)與錄音,去河邊找鬼征候。 笑死杭攻,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的疤坝。 我是一名探鬼主播兆解,決...
    沈念sama閱讀 40,028評(píng)論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼跑揉!你這毒婦竟也來了锅睛?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 38,887評(píng)論 0 274
  • 序言:老撾萬榮一對(duì)情侶失蹤历谍,失蹤者是張志新(化名)和其女友劉穎现拒,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體望侈,經(jīng)...
    沈念sama閱讀 45,310評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡印蔬,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,533評(píng)論 2 332
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了甜无。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片扛点。...
    茶點(diǎn)故事閱讀 39,690評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖岂丘,靈堂內(nèi)的尸體忽然破棺而出陵究,到底是詐尸還是另有隱情,我是刑警寧澤奥帘,帶...
    沈念sama閱讀 35,411評(píng)論 5 343
  • 正文 年R本政府宣布铜邮,位于F島的核電站,受9級(jí)特大地震影響寨蹋,放射性物質(zhì)發(fā)生泄漏松蒜。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,004評(píng)論 3 325
  • 文/蒙蒙 一已旧、第九天 我趴在偏房一處隱蔽的房頂上張望秸苗。 院中可真熱鬧,春花似錦运褪、人聲如沸惊楼。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽檀咙。三九已至,卻和暖如春璃诀,著一層夾襖步出監(jiān)牢的瞬間弧可,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,812評(píng)論 1 268
  • 我被黑心中介騙來泰國打工劣欢, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留棕诵,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,693評(píng)論 2 368
  • 正文 我出身青樓氧秘,卻偏偏與公主長得像年鸳,于是被迫代替她去往敵國和親澡屡。 傳聞我的和親對(duì)象是個(gè)殘疾皇子鳍寂,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,577評(píng)論 2 353

推薦閱讀更多精彩內(nèi)容