腾讯2020届内推+正式批笔试部分题解

内推第四题

leetcode 76变形

思路

滑动窗口。

举例鬼才：最少买几包的小浣熊，可以集齐108张水浒；

AC代码

import java.util.Scanner;
public class Main4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        // 卡池
        int[] counter = new int[m+1];
        for (int i=0;i<m+1;i++){
            counter[i] = 1;
        }
        // 透视眼看到可以买的n包小浣熊里面的卡是什么
        int[] seq = new int[n];
        for (int i=0;i<n;i++){
            seq[i] = sc.nextInt();
        }
        int window = n+1;
        int begin = 0;
        int end = 0;
        int c=m;
        int head =0;
        while(end<n)
        {
            // 这张卡还没有收集到
            if((counter[seq[end++]]--)==1)
                m--;
            // 收集齐了
            while(m==0)
            {
                //  记录购买包数
                if(end-begin<window)
                    window=end-begin;
                //滑动窗口，吐出一开始没有必要买的小浣熊；
                if(counter[seq[begin++]]++==0) 
                    m++;
            }
        }
        // 黑心商家返回-1，否则返回窗口大小；
        System.out.println(((window==n+1)?-1:window));
    }
}

内推第五题

牛客网有题目描述

思路

dp，倒着从后往前做，dp[j][k]代表颜色已经变换了J次且最后颜色为k，时间复杂度为O(n^2*L)

可能AC的代码

#include <stdio.h> 
#include <algorithm> 
typedef long long ll; 
const int mod = 1e9+9; 
const int maxn = 1300; 
int c[maxn]; 
ll dp[maxn][maxn];///变化i次颜色为j 
int main(){ 
    int n,L;  
    scanf("%d%d",&n,&L);  
    dp[0][0]=1;  
    for(int i=n;i>=1;i--){ 
        for(int j=L;j>=0;j--){
            dp[j][c[i]]=dp[j][c[i]]*(n-i+1)%mod;  
            for(int k=0;k<=n;k++){ 
                if(c[i]!=k){
                    dp[j+1][c[i]]+=dp[j][k];
                    dp[j][k]=dp[j][k]*(n-i)%mod;  
                }
            }
            dp[j+1][c[i]]%=mod;  
        }
    } 
    ll sum=0;  
    for(int i=0;i<=n;i++)
        sum+=dp[L][i];  
    printf("%d\n",(int)(sum%mod));  
    return 0; 
}

正式批算法第二题

思路

前缀和+贪心；UVA 11054。
其实酒都是向右移动的，其实，这些各个卖家的酒的移动都可以同时算的(负数的时候可以思考为移动空酒桶)：

把第一家的酒交给下一家，路费就是酒×1了；或者把负数(空酒桶)交给下一家，表示待会计算下家时有酒了就会反方向运过来，路费也是桶x1。然后继续下一家，由于上一家运费和供求都处理完了，第二家也可以同样处理它的当前供求。

AC代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0, need = 0;
        for(int i=1;i<=n;i++){
            int b = sc.nextInt();
            ans+=fabs(need);
            need+=b;
        }
        System.out.println(ans);
    }
}