【腾讯】暑期实习-PC客户端开发岗位笔试

1. 链表反转

以4个元素为一组，两个元素为1个小组，反转，组内元素顺序不变。瞎几把写的，因为我想火速AC。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* reorderList(ListNode* head) {
        cout << 1 << endl;
        vector<int> vec;
        auto p = head;

        while(p){
			vec.push_back(p->val);
			p=p->next;
        }
		if(vec.size() <= 2) return head;
		for(int i = 0 ;i+3 <vec.size() ; i +=4){
			int b,c,d;
			int a = i;
			b = i+1;
			c = i + 2;
			d = i+3;
			swap(vec[a],vec[c]);
			if(d < vec.size())
				swap(vec[b],vec[d]);
			else
				swap(vec[b],vec[c]);
		}
		for(auto it: vec)
			cout << it << " ";
		cout << endl;
		ListNode* new_head = new ListNode({});
		p = new_head;
        for(int i = 0 ; i < vec.size() ; ++i){
			if(i == 0){
				p->val = vec[i];
				p->next = nullptr;
			}else{
				auto temp = new ListNode({});
				temp->val = vec[i];
				temp->next = nullptr;
				p->next = temp;
				p = temp;
			}
		}
        return new_head;
    }
};

2 树的节点判断

满二叉树，给你节点，问你是不是叶子节点，存不存在。

#include <iostream>
#include <cmath>
#include <vector>
// #include <map>
#include <unordered_map>
using namespace std;

int main(){
	int n; //level
	cin >> n;
	unordered_map<int,int> mp;
	int m = pow(2,n)-1;
	vector<int> vec(m+1);
	for(int i =1 ; i <= m ; ++i){
		cin >> vec[i];
		int v;
		v = vec[i];
		// mp[vec[i]]
		mp[v] = i;
	}
	// int level = sqrt(n) + 1;
	int q;
	cin >> q;
	while(q--){
		int node;
		cin >> node;
		if(mp.find(node) == mp.end()) cout << "NO" << endl;
		else{
			cout << "YES" << endl;
			int pos = mp[node];
			int left,right;
			left = 2*pos;
			right = left+1;
			if(left >= m && right >= m){
				cout << "LEAF" << endl;
			}else{
				if(left <= m)
					cout << vec[left];
				if(right <= m )
					cout << " " << vec[right];
				cout << endl;
			}
		}
	}
	return 0;
}

5 寻路

障碍寻路，弱智dp。

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
ll mod = 1e9 +7 ;
int vec[2000+1][2000+1];
int dp[2000+1][2000+1];
bool row[2000+1];
bool col[2000+1];
int main(){
	int m,n;
	cin >> m >> n;

	for(size_t i = 1 ; i <= m ; ++i){
		for (size_t j = 1; j <= n; j++)
		{
			char ch;
			cin >> ch;
			if(ch == '.')
			vec[i][j] = 1;
			else{
				vec[i][j] = 0;
			}
		}
	}
	for(int i = 1; i <=m ; ++i)
	{
		for(int j = 1 ; j <= n ; ++j)
		{
			if(i ==1 && j == 1 ){
				dp[i][j] = 1;
				continue;
			}
			if(vec[i][j] == 1){
				for(int k = j -1 ; k >= 1 && vec[i][k] == 1; --k)
					dp[i][j] = (dp[i][j] + dp[i][k])%mod;
				for(int k = i -1 ; k >= 1 && vec[k][j] == 1; --k)
					dp[i][j] = (dp[i][j] + dp[k][j])%mod;
			}
		}
	}
	cout <<dp[m][n] << endl;
	return 0;
}

3 字符串

想用的模拟，没写出来，debug太长时间了。。

题目就是给你字符串，可以对子串（如果是回文）进行折叠，比如说aabaa->aab/bba->ab\ba...

#include <iostream>
#include <set>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<string,int> mp;
bool isstr(string str){
	if(mp[str] != 0){
		return true;
	}
	int len = str.length();
	for(int i = 0 ; i < len/2 ; ++i){
		if(str[i] != str[len-i-1]) return false;
	}
	
	return true;
}
int ans = 0;
void calc(string str){
	int len = str.length();
	if(len == 1) return ;
	if(mp[str]){
		ans += mp[str];
		return ;
	}
	int ans = 0;
	for (size_t i = 0; i < len; i++)
	{
		for (size_t j = i; j < len; j++)
		{	
			string temp = str.substr(i,j-i+1);
			if(temp.size() > 1 && isstr(temp)){
				string a ;
				string b ;
				// cout << temp << endl;
				if(len%2){
					int len = temp.length();
					a = temp.substr(0,len/2+1);
					b = temp.substr(len/2,len/2);
					// cout << temp << "->" << a << " " << b << endl;
					if(a == b){
						// cnt += 1;
						mp[temp] = 1;
					}else{
						// cnt +=1
						mp[temp] = 2;
					}
				}else{
					int len = temp.length();
					a = temp.substr(0,len/2);
					// cout << "A=" << a << endl;
					b = temp.substr(len/2,len/2-1);
					// cout << "B=" << b << endl;
					// cout << temp << "->" << a << " " << b << endl;
					if(a == b) mp[temp] = 1;
					else mp[temp] = 2;
					// ans += mp[str];
				}
				calc(a); 
				calc(b);
			}
		}		
	}
	// return ans;
}
int main(){
	int len;
	cin >> len;
	string str;
	cin >> str;
	// string aa = "aa";
	// cout << aa.substr(1,1) << endl;
	calc(str);
	cout << ans  << endl;
	return 0;
}