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

1、

不要看到这个就以为是背包问题，这个是从大到小的，也就是说什么面值的货币都有，所以就不存在比如货币是{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、

 

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

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、

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

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、

看到这题，是不是感觉跟计算最长子串的思想有点那么相似，如果你要这么想，就往复杂里面想了。相信学过计算机网络的同学应该都听说过滑动窗口，滑动窗口应该就是在传送报文时可以动态更新的长度，窗口长度受对方主机反馈的影响。我觉得这个意思很像啊，说下我的思路，因为要求所有颜色要命中，于是用一个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);
        }
    }

结果：

5、

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