第四范式不好吃的凉面
应聘的第四范式的SP专场，岗位是计算机视觉岗，然后昨晚熬夜了（熬到两点），早上起来头很晕，昏昏沉沉的，
面试官一上来就说面试时间有限，我们跳过自我介绍，直接coding吧（那就直接coding吧，不coding还能怎么办），
然后看到题目大脑一片空白（明明剑指offer刷到过，但由于熬夜导致啥都没想起来），好了说多了都是借口，在这立个flag，早睡早起，正式说题
（就两道编程题，其他啥也没问，反正是凉了，放出来造福大家，万一是同一个面试官呢）
第一题：乱序数组，使奇数值排在偶数值之前(要求O(n)时间复杂度，O(1)空间复杂度）
第二题：乱序链表，使奇数值排在偶数值之前(要求O(n)时间复杂度，O(1)空间复杂度）
刚午睡了一下，几分钟就写完了，面试的时候各种卡顿紧张（牛客的视频面，面试官可以看到你在编辑框中的整个coding过程，当然还能看到你）
上代码（有错的话，大家指出哈）
第一题：
#include<iostream>
#include<vector>
using namespace std;
//乱序数组，使奇数值排在偶数值之前(要求O(n)时间复杂度，O(1)空间复杂度）
void func(vector<int> &array)
{
if (array.size() < 2)
return;
int start = 0, end = array.size() - 1;
while (start < end)
{
while (array[start] & 0x0001)
{
if (start == end)
break;
++start;
}
while ((array[end] & 0x0001) == 0)
{
if (end == start)
break;
--end;
}
if (start == end)
break;
int temp = array[start];
array[start] = array[end];
array[end] = temp;
++start;
--end;
}
}
int main()
{
int n;
while (cin >> n)
{
vector<int> input;
int temp;
for (int i = 0; i < n; ++i)
{
cin >> temp;
input.push_back(temp);
}
func(input);
for (auto it : input)
cout << it << ' ';
cout << endl;
}
return 0;
} 第二题： #include<iostream>
#include<vector>
using namespace std;
//乱序链表，使奇数值排在偶数值之前(要求O(n)时间复杂度，O(1)空间复杂度）
struct ListNode{
int val;
ListNode* next;
ListNode(int x) :val(x), next(NULL){}
};
void func(ListNode** root)
{
if (root == NULL)
return;
ListNode* pNode = *root;
ListNode* preNode = *root;
pNode = pNode->next;
while (pNode)
{
if (pNode->val & 0x0001)
{
preNode->next = pNode->next;
pNode->next = *root;
*root = pNode;
pNode = preNode->next;
}
else
{
preNode = pNode;
pNode = pNode->next;
}
}
}
ListNode* constructList(const vector<int> &array)
{
if (array.size() == 0)
return NULL;
ListNode* root = new ListNode(array[0]);
ListNode* pNode = root;
for (int i = 1; i < array.size(); ++i)
{
pNode->next = new ListNode(array[i]);
pNode = pNode->next;
}
return root;
}
void printList(ListNode* root)
{
ListNode* pNode = root;
while (pNode)
{
cout << pNode->val << ' ';
pNode = pNode->next;
}
cout << endl;
}
int main()
{
int n;
while (cin >> n)
{
vector<int> input;
int temp;
for (int i = 0; i < n; ++i)
{
cin >> temp;
input.push_back(temp);
}
ListNode* root = constructList(input);
func(&root);
printList(root);
}
return 0;
} 忽然想到，如果要求保持奇数/偶数相对顺序不变呢？ 对于数组，个人只想到O(n^2)复杂度的冒泡法
对于链表，可以把偶数尾插（O(n)时间复杂度，O(1)空间复杂度）
#第四范式##面经##计算机视觉岗##校招#