第四范式不好吃的凉面

应聘的第四范式的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)空间复杂度）

#第四范式##面经##计算机视觉岗##校招#