腾讯笔试 8.22 客户端 AC代码

1.不会写链表，一开始直接写了个存进vector排序的写法，后面有时间改了这种写法

class Solution {
	public:
		/**
		 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
		 *
		 * @param pHead1 ListNode类
		 * @param pHead2 ListNode类
		 * @param pHead3 ListNode类
		 * @return ListNode类
		 */
		ListNode* mergeThreeList(ListNode* pHead1, ListNode* pHead2, ListNode* pHead3) {
			// write code here
			int id = 0;
			ListNode* pre = NULL;
			ListNode* res = NULL;

			while(true) {
				int mx = -1;
				if(pHead1 != NULL) {
					mx = max(mx,pHead1 -> val);
				}

				if(pHead2 != NULL) {
					mx = max(mx,pHead2 -> val);
				}

				if(pHead3 != NULL) {
					mx = max(mx,pHead3 -> val);
				}
				
				if(mx == -1) break;
				bool f = false;
				
				if(pHead1 != NULL) {
					if(mx == pHead1 -> val) {
						pHead1 = pHead1 -> next;
						f = true;
					} else f = false;
				}
				if(!f && pHead2 != NULL) {
					if(mx == pHead2 -> val) {
						pHead2 = pHead2 -> next;
						f = true;
					}
				}
				
				if(!f && pHead3 != NULL){
					if(mx == pHead3 -> val) {
						pHead3 = pHead3 -> next;
						f = true;
					} else f = false;
				}
				if(!f) break;
				ListNode* tmp = new ListNode(mx);
				if(pre != NULL) pre -> next = tmp;
				if(id == 0) res = tmp;
				++ id;
				pre = tmp;
			}
			return res;
		}
} slo;

2.括号匹配

	for(scanf("%d",&T); T ; T --) {
		scanf("%s",s + 1);
		n = strlen(s + 1);
		int ans = 0;
        top = 0;
		for(int i = 1;i <= n; ++ i){
			if(top == 0) stk[++ top] = s[i];
			else{
				if(s[i] == stk[top]){
					++ ans;
					-- top;
				} else stk[++ top] = s[i]; 
			}			
		}		
		printf("%d\n",ans);
	}

3.坑点全1时，需要输出-1 dp数组可以优化成常量

    scanf("%s",s + 1);
    n = strlen(s + 1);
    int minn = 0,ans = 0;
    bool f = false;
    for(int i = 1;i <= n; ++ i){
        if(s[i] == '0'){
            dp[i] = dp[i - 1] + 1;
            f = true;
        } else dp[i] = dp[i - 1] - 1;
        ans = max(ans,dp[i] - minn);
        minn = min(minn,dp[i]);
//        cout << i <<  " " << dp[i] << " " << minn << endl;
    }
    if(!f) ans = -1;
    cout << ans;

4.数组需要排序，虽然题面说是升序（？

	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; ++ i) scanf("%d",a + i);
	for(int i = 1; i <= n; ++ i) scanf("%d",b + i);
	
	sort(a + 1,a + n + 1);
	sort(b + 1,b + n + 1);
	
	for(int i = 1; i <= n; ++ i) {
		q.push({i,n,a[i] + b[n]});
	}

	while(m) {
		P nowp = q.top();
		int res = nowp.val;
		int x = nowp.x,y = nowp.y - 1;
		q.pop();
		if(y > 0) {
			q.push({x,y,a[x] + b[y]});
		}
		-- m;
		printf("%d%c",res," \n"[m == 0]);
	}

5.区间dp

for(scanf("%d",&T); T ; T --) {
		scanf("%d",&n);
		for(int i = 1; i <= n; ++ i) scanf("%d",a + i);
		
		for(int i = 1;i <= n;++ i){
			for(int j = 1;j <= n; ++ j){
				f[i][j][0] = f[i][j][1] = 0;
			}
		} 
		for(int i = 1; i <= n; ++ i) {
			f[i][i][a[i]] = 1;
			f[i][i][1 - a[i]] = 0;
		}

		for(int len = 2; len <= n; ++ len) {
			for(int i = len; i <= n; ++ i) {
				int l = i - len + 1,r = i;
				for(int j = l; j <= r - 1; ++ j) {
					f[l][r][0] = (f[l][r][0] || (f[l][j][1] && f[j + 1][r][1]));
					f[l][r][1] = (f[l][r][1] || (f[l][j][0] && f[j + 1][r][0]));
				}
			}
		}
		printf("%d %d\n",f[1][n][0],f[1][n][1]);
	}

#腾讯笔试##腾讯##笔经#