牛客高频面试题

• https://www.nowcoder.com/ta/job-code-high

链表

78.反转链表

• 1.迭代：辅助指针
• 2.递归

ListNode* ReverseList(ListNode* head) {
	if (head == NULL || head->next == NULL)
		return head;

	ListNode* pre = NULL;
	ListNode* next = NULL;

	while(head){
	    next = head->next;
	    head->next = pre;
	    pre = head;
	    head = next;
	}

	return pre;
}

ListNode* ReverseList(ListNode* head) {
	if (head == NULL || head->next == NULL)
		return head;

	ListNode* tmp = head->next;
	ListNode* res = ReverseList(tmp);

	tmp->next = head;
	head->next = NULL;

	return res;
}

94.LRU缓存实现(页面置换)

STL容器

94.LRU缓存实现(页面置换)

• LRU页面置换算法——最久未使用
• 利用List和unordered_map来实现，list存放元素，
• list存放元素，unordered_map存放迭代器

int get(int key) {
	auto it = vis.find(key);
	if (it == vis.end()) {
		return -1;
	}
	else {
		pair<int, int>tmp = *vis[key];
		arr.erase(vis[key]);
		arr.push_front(tmp);

		vis.erase(key);
		vis[key] = arr.begin();
		return tmp.second;
	}
}
void set(int key, int value) {
	auto it = vis.find(key);
	if (it == vis.end()) {
		if (arr.size() == size) {
			pair<int, int>tmp = arr.back();
			arr.pop_back();
			arr.push_front({ key,value });

			vis.erase(tmp.first);
			vis[key] = arr.begin();
		}
		else {
			arr.push_front({ key,value });
			vis[key] = arr.begin();
		}
	}
	else {
		arr.erase(vis[key]);
		arr.push_front({ key,value });

		vis[key] = arr.begin();
	}

}

二分查找

105.lower_bound / upper_bound

//大于或等于target的第一个数
int lower_bound(vector<int>& nums, int target) {
	int L = 0;
	int R = nums.size();
	while (L < R) {
		int mid = (L + R) >> 1;
		if (nums[mid] < target)
			L = mid + 1;
		else
			R = mid;
	}
	return L;
}

//大于target的第一个数
int upper_bound(vector<int>& nums, int target) {
	int L = 0;
	int R = nums.size();
	while (L < R) {
		int mid = (L + R) >> 1;
		if (nums[mid] <= target)
			L = mid + 1;
		else
			R = mid;
	}
	return L;
}