2019腾讯春招暑期实习提前批编程题

墨蓝 2022-03-07 08:42 346阅读 0赞

错过了腾讯的春招编程题（在牛客笔试前已经电话面所以就没参加，有自己做C++的笔试，对C++不熟，感觉已经凉了），但是朋友做了便截图下来然后自己练习一下，给我的感觉就是，会做的就很快写完，不会的基本没有什么思路，总之很快写完了三道题，但是有两道是不会的。下面按题目给出我的代码，有错的恳请指正。

1、

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70][]

不要看到这个就以为是背包问题，这个是从大到小的，也就是说什么面值的货币都有，所以就不存在比如货币是\{1，6，7\}，而输入30的情况下，如果按下面的算法就出错了，按下面的算法，此时应该得到4\*7+2\*1=30，要6个货币，但假如是6\*5=30只要5个货币。但题目给的是n种货币，所以假如先4\*7+1\*2=30，也是只要5个货币，所以本题很简单。。。

public static void lessCoins(){
            String [] lines = scanner.nextLine().split(" ");
            int n = Integer.parseInt(lines[0]),m = Integer.parseInt(lines[1]);
            int count = 0,temp = 0;
    
            while (m>0){
                temp = n;
                while (temp>m){
                    temp--;
                }
                m-=temp;
                count++;
            }
            System.out.println(count);
        }

如果按照前面说的，那要简单动态规划了，动态规划基本就是两个步骤，定义状态，然后递推转移方程，如果想要详细了解动态规划，那么可以参考别的文章。

public static int getLessCoinsCount(int []coins,int amount){
            int []dp = new int[amount+1];
            for(int i=1;i<=amount;i++){
                int min = Integer.MAX_VALUE;
                for(int j=0;j<coins.length;j++)
                    if(coins[j]<=i)min = Math.min(min,dp[i - coins[j]]+1);
                dp[i] = min == Integer.MAX_VALUE?0:min;
            }
            return dp[amount]>amount?-1:dp[amount];
        }

2、

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 1][]

这个![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 2][]其实就是累加的意思，只是要对加数做个求余判断。

public static int getSum(int start,int end){
            int sum = 0;
            for (int i = start;i<=end;i++){
                if(i%2==0) sum += i;
                else sum -= i;
            }
            return sum;
        }
            int n  = Integer.parseInt(scanner.nextLine());
            int [][]res = new int[n][2];
            int []r = new int[n];
            String [] strs = null;
            for (int i = 0;i<n;i++){
                strs = scanner.nextLine().split(" ");
                res[i][0] = Integer.parseInt(strs[0]);
                res[i][1] = Integer.parseInt(strs[1]);
            }
            for (int i = 0;i<n;i++){
                r[i] = getSum(res[i][0],res[i][1]);
                System.out.println(r[i]);
            }

3、

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 3][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 4][]

这题可能同学想到的，就是先枚举所有排列，再和原来的数组做比较，得到结果相等时计数加1，当超过1e9+7时对计数取1e9+7的余数，相信大部分人都这么想，但是，这肯定是不可取的，17的阶乘都超过了int的最大范围，何况这里有最多2000个数，那肯定是不可计算的。想一下，假设在相等的情况，有s个1，其他均为0，那么就有Cn的s种，而其他的还有2的（n-s）次方，因为0、1、2，只能有2种可能是能赢的，而这些数也是有n-s个数，于是得到公式![gif.latex_C_7Bn_7D_5E_7Bs_7D_5Ccdot2_5E_7B_28n-s_29_7D][]。所以代码就很简单了：

public static int calC(int n,int s){
            int count = 1, e = n - s;
            for (int i = s + 1;i<=n;i++){
                count *=i;
                if(count>1000000007)count%=1000000007;
            }
            while (e>0){
                count *= 2;
                if(count>1000000007)count%=1000000007;
                e --;
            }
            return count;
        }

因为我没有提交过题目，也不知道对不对，但是举几个例子都是没有问题的，在s,n的范围内也是算得很快，如果不对的请指正。

4、

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 5][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 6][]

看到这题，是不是感觉跟计算最长子串的思想有点那么相似，如果你要这么想，就往复杂里面想了。相信学过计算机网络的同学应该都听说过滑动窗口，滑动窗口应该就是在传送报文时可以动态更新的长度，窗口长度受对方主机反馈的影响。我觉得这个意思很像啊，说下我的思路，因为要求所有颜色要命中，于是用一个list去装这个序列，这个序列肯定都包含所有颜色但也可能有重复的颜色，因为这个滑动窗口就是记录原来数组中连续最少的枪数，此外我们还要判断什么这个list满足包含所有颜色，当包含所有颜色时，就得到一个序列，这个满足条件的序列长度就被保存下来到一个res\_list中，到最后对res\_list排序，取最前面的数就是最小的长度。那么关键问题就是，滑动窗口怎么设计，其实很简单，因为滑动窗口要满足包含所有颜色，暂且用一个队列来保存这个滑动窗口，只有当要入队元素和队首元素一样时，我们才对队列操作，即队首元素出队，然后再入队，这就能保证当前队列不会有多余的步长，当然，你非要说中间有相同的数，那我只能说没有影响。当得到一个可用序列后，滑动窗口要更新的，就是删除队首，当队首元素后有队首元素时，删除队首元素直到没有。于是代码就出来了：

public static int lessShotCounts(int a[],int m){
            ArrayList<Integer> res_list = new ArrayList<>();//所有满足条件的窗口长度
            ArrayList<Integer> list = new ArrayList<>();//得到一条路线的标志
            LinkedList<Integer> t_list = new LinkedList<>();//滑动窗口的数组
            for(int i = 0;i<a.length;i++){
                if(!list.contains(a[i])){
                    list.add(a[i]);
                    t_list.add(a[i]);
                }
                else{
                    if(t_list.get(0) == a[i]){
                        t_list.remove((Object)a[i]);
                    }
                    t_list.add(a[i]);
                }
                boolean flag = false;
                if(list.contains(0) && list.size() == m + 1) flag = true;
                if(!list.contains(0) && list.size() == m ) flag = true;
                if(flag){
                    System.out.println(Arrays.toString(t_list.toArray()));
                    res_list.add(t_list.size());
                    if(t_list.get(0)!=null){
                        int temp = t_list.get(0);
                        t_list.remove((Object)temp);
                        list.remove((Object)temp);
                        if(t_list.get(0)!=null){
                            temp = t_list.get(0);
                            while (t_list.lastIndexOf(temp) !=0 && t_list.get(0)!=null){
                                t_list.remove((Object)temp);
                                temp = t_list.get(0);
                            }
                        }
                    }
                }
            }
            if(res_list.size()==0)return -1;
            else{
                Collections.sort(res_list);
                return res_list.get(0);
            }
        }

结果：

![20190316175942335.png][]

5、

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 8][]

这个题目我暂时还没有头绪，等我想到了再分享，或者有会的同学可以分享给我，十分感谢。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70]: /images/20220307/c5f94aa369564b2095ddf221b61616bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 1]: /images/20220307/366c14dbef594b268f8fbedf3e0f96b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 2]: /images/20220307/bebfdbe12c964af4b1de595f98439a68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190316162044673.JPG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 4]: /images/20220307/4137c7cf97854b53a266bd493a8d7039.png
[gif.latex_C_7Bn_7D_5E_7Bs_7D_5Ccdot2_5E_7B_28n-s_29_7D]: https://private.codecogs.com/gif.latex?C_%7Bn%7D%5E%7Bs%7D%5Ccdot2%5E%7B%28n-s%29%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20190316165724768.JPG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 6]: /images/20220307/2f3d63cd19ba455591395ce95170a43b.png
[20190316175942335.png]: /images/20220307/bdc7ed5a1dd04aa7a48124c821c794d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 7]: /images/20220307/2b4c100f88b54daa9a1af48beda0d65b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 8]: /images/20220307/c3f583448ce449bf945ab2787b539a3e.png