建信金科笔试编程题

1、给一个字符串，只包含字母和空格，其中由连续的字母组成的是单词，问你字符串中有几个连续的三个单词满足：第一个单词=第二个单词，且不等于第三个单词。

解题思路：先做字符串分割，然后把分割出来的单词放入列表(C++中的或者Java中的)，然后就是简单的枚举判断，符合条件计数器+1.

2、给定一个链表，要求把不存在相邻元素相等的连续段进行反转操作，返回操作后的链表。

解题思路：我的做法是先把链表转成列表，方便访问相邻元素，然后枚举元素，若存在相邻元素与之相等，那么就直接将该元素尾插到新链表中，否则就先存放到列表中，直到出现存在相邻元素与之相等的元素，再将反转后的列表尾插到新链表中。

由于采用的是枚举，就算加上反转操作，时间复杂度也还是线性的。

考试代码参考：

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
    ListNode *convert_to_list(vector<int>&a) {
        ListNode *head = new ListNode(-1);
        head->next = NULL;
        ListNode *p = head;
        for(int i = 0; i < a.size(); i++) {
            ListNode *q = new ListNode(a[i]);
            p->next = q;
            p = q;
        }
        p->next = NULL;
        return head->next;
    }
    void output(ListNode *head) {
        ListNode *p = head;
        while(p) {
            cout << p->val << " ";
            p = p->next;
        }
    }
    ListNode *solve(ListNode *head) {
        if(head == NULL)    return NULL;
        vector<int>a, v;
        ListNode *p = head;
        while(p) {
            a.pb(p->val);
            p = p->next;
        }
        ListNode *L = new ListNode(-1);
        L->next = L;
        p = L;
        for(int i = 0; i < a.size(); i++) {
            if(i == 0) {
                if(a[i] == a[i + 1]) {
                    ListNode *q = new ListNode(a[i]);
                    p->next = q;
                    p = q;
                }
                else {
                    v.pb(a[i]);
                }
                continue;
            }
            if(i == a.size() - 1) {
                if(a[i] == a[i - 1]) {
                    ListNode *q = new ListNode(a[i]);
                    p->next = q;
                    p = q;
                }
                else {
                    v.pb(a[i]);
                }
                continue;
            }
            if(a[i] == a[i - 1] || a[i] == a[i + 1]) {
                reverse(v.begin(), v.end());
                for(auto val : v) {
                    ListNode *q = new ListNode(val);
                    p->next = q;
                    p = q;
                }
                v.clear();
                ListNode *q = new ListNode(a[i]);
                p->next = q;
                p = q;
            }
            else {
                v.pb(a[i]);
            }
        }
        if(v.size()) {
            reverse(v.begin(), v.end());
            for(auto val : v) {
                ListNode *q = new ListNode(val);
                p->next = q;
                p = q;
            }
        }
        p->next = NULL;
        return L->next;
    }
};
int main() {
    int n;
    cin >> n;
    vector<int>a(n);
    for(int i = 0; i < n; i++)    cin >> a[i];
    Solution sol = Solution();
    ListNode *list = sol.convert_to_list(a);
    ListNode *res = sol.solve(list);
    sol.output(res);
}
/*
input:
11
1 2 2 3 4 5 3 3 3 4 5
output:
1 2 2 5 4 3 3 3 3 5 4
*/

通过率：100%

当然考虑代码量的话，也可以先操作列表，再由列表转链表。与此同时，代码可读性可能就差点了。

参考代码：

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
    ListNode *convert_to_list(vector<int>&a) {
        ListNode *head = new ListNode(-1);
        head->next = NULL;
        ListNode *p = head;
        for(int i = 0; i < a.size(); i++) {
            ListNode *q = new ListNode(a[i]);
            p->next = q;
            p = q;
        }
        p->next = NULL;
        return head->next;
    }
    void output(ListNode *head) {
        ListNode *p = head;
        while(p) {
            cout << p->val << " ";
            p = p->next;
        }
    }
    ListNode *solve(ListNode *head) {
        if(head == NULL)    return NULL;
        vector<int>a;
        ListNode *p = head;
        while(p) {
            a.pb(p->val);
            p = p->next;
        }
        int l = 0;
        bool f = false;//是否位于不存在相邻元素相等的连续段 
        for(int i = 1; i < a.size(); i++) {
            if(i == a.size() - 1) {
                if(a[i] != a[i - 1]) {
                    reverse(a.begin() + l, a.end());
                }
                continue;
            }
            if(a[i] == a[i - 1] || a[i] == a[i + 1]) {
                if(f) {
                    reverse(a.begin() + l, a.begin() + i);
                }
                f = false;
            }
            else {
                if(!f) {
                    l = i;//记录一下开始出现相邻元素不相等的元素的位置 
                    f = true;
                }    
            }
        }
        ListNode *L = convert_to_list(a);
        return L;
    }
};
int main() {
    int n;
    cin >> n;
    vector<int>a(n);
    for(int i = 0; i < n; i++)    cin >> a[i];
    Solution sol = Solution();
    ListNode *list = sol.convert_to_list(a);
    ListNode *res = sol.solve(list);
    sol.output(res);
}
/*
input:
11
1 2 2 3 4 5 3 3 3 4 5
output:
1 2 2 5 4 3 3 3 3 5 4
*/