第四范式不好吃的凉面

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

#第四范式##面经##计算机视觉岗##校招#
全部评论
奇偶只能想到归并nlogn思想
点赞 回复
分享
发布于 2019-08-17 16:57
春招专场
校招火热招聘中
官网直投
我想问一下,coding需要自己写测试用例么
点赞 回复
分享
发布于 2019-08-17 20:13
良心!!!感谢!!!
点赞 回复
分享
发布于 2019-09-25 17:17

相关推荐

4 33 评论
分享
牛客网
牛客企业服务