記一道完美展現出資料結構高大尚的位元組跳動算法題

偶然在公衆号裡看到今日頭條的一道算法題(如下圖)，一共有三道題，要求40分鐘内做完其中的兩道(聽說頭條的面試一般都比較變态)。

在網上找了找答案感覺都比較繁瑣，自己當時也就沒當回事就不準備做了。過了半個小時突然靈機一動，想到一種非常清晰的思路來做這道題—用環形連結清單來做。第一次周遊建構環形連結清單，并且算出周長。第二次周遊根據目前節點與下一個節點的距離來計算等分點的位置，同時将等分點作為新節點插入環形連結清單中。整體思路大概就是這樣，這樣隻需兩次周遊，時間複雜度O(N)搞定。在這種環形連結清單的思路下做這道題差不多20分鐘就能做完。

一點感悟：1.做這種算法題一定要先有個大概想法和思路再做，花點時間理清思路比上來就悶頭一股腦的瞎做強多了。2.一道現實中的數學算法題，用上簡簡單單的環形連結清單這種資料結構就能思路非常清晰，可見資料結構的高大尚！

附上代碼，寫的有點亂，如有不對，歡迎拍磚。

#define precision 10e-6
struct Node {
    float x;
    float y;
    Node* next;
    Node(float a,float b):x(a),y(b),next(nullptr){}
};

Node* Construct_Circle(vector<vector<float>> Points,float& c_meter) { /*根據輸入建構環形連結清單，并計算周長*/

    Node dummy(0.0,0.0);
    Node* tail = &dummy;

    for (int i = 0; i < Points.size(); ++i) {

        Node* node = new Node(Points[i][0],Points[i][1]);
        tail->next = node;
        tail = tail->next;

        if (i == 0)
            c_meter += (fabs(Points[i][0] - Points.back()[0])\
                         + fabs(Points[i][1] - Points.back()[1]));
        else
            c_meter += (fabs(Points[i][0] - Points[i - 1][0])\
                          + fabs(Points[i][1] - Points[i - 1][1]));

    }
    tail->next = dummy.next;
    return dummy.next;

}
float dist_between_Node(Node* node1,Node* node2) {   /*計算目前節點與下一個節點之間的距離*/
    return fabs(node1->x - node2->x) + fabs(node1->y - node2->y);
}

vector<vector<float>> get_Ksplit(const vector<vector<float>> Points,const int k) {   /*求等分點主程式*/

    if (Points.size() < 4 || k < 1)
        return {{}};

    vector<vector<float>> ans{{Points[0][0],Points[0][1]}};
    float C_meter= 0;
    Node* head = Construct_Circle(Points,C_meter);
    float split_len = C_meter / k;

    for (int i = 0; i < k ; ++i) {

        if (dist_between_Node(head,head->next) - split_len > precision) {


            Node* new_node = (fabs(head->x - head->next->x) < precision) ?\
                              new Node(head->x, head->y + (head->y - head->next->y < precision ? 1.0 : -1.0)*split_len)\
                             : new Node(head->x + (head->x - head->next->x < precision ? 1.0 : -1.0)*split_len, head->y);


            new_node->next = head->next;
            head->next = new_node;

            ans.push_back({new_node->x,new_node->y});
            head = head->next;


        } else if (dist_between_Node(head,head->next) - split_len < -1.0 * precision) {
            float len = split_len;
            while (dist_between_Node(head,head->next) - len < -1.0 * precision) {
                len -= dist_between_Node(head,head->next);
                head = head->next;
            }

            if (dist_between_Node(head,head->next) - len > precision) {

                Node* new_node = (fabs(head->x - head->next->x) < precision) ?\
                                  new Node(head->x, head->y + (head->y - head->next->y < precision ? 1.0 : -1.0) * len)\
                                 : new Node(head->x + (head->x - head->next->x < precision ? 1.0 : -1.0) * len, head->y);

                new_node->next = head->next;
                head->next = new_node;
                ans.push_back({new_node->x,new_node->y});
                head = head->next;

            } else {
                head = head->next;
                ans.push_back({head->x,head->y});
            }

        } else {
            head = head->next;
            ans.push_back({head->x,head->y});
        }

    }

    return ans;

}