快手校招真题一

快手 获得最多的奖金

题目描述
小明在越南旅游，参加了当地的娱乐活动。小明运气很好，拿到了大奖， 到了最后的拿奖金环节。小明发现桌子上放着一列红包，每个红包上写着奖金数额。
现在主持人给要求小明在这一列红包之间“切”2刀，将这一列红包“切”成3组，并且第一组的奖金之和等于最后一组奖金和（允许任意一组的红包集合是空）。最终第一组红包的奖金之和就是小明能拿到的总奖金。小明想知道最多能拿到的奖金是多少，你能帮他算算吗。

举例解释：桌子上放了红包 1, 2, 3, 4, 7, 10。小明在“4,7”之间、“7,10” 之间各切一刀，将红包分成3组 [1, 2, 3, 4] [7] [10]，其中第一组奖金之和=第三组奖金之和=10，所以小明可以拿到10越南盾。
输入描述:
第一行包含一个正整数n，(1<=n<= 200 000)，表示有多少个红包。

第二行包含n个正整数d[i]，表示每个红包包含的奖金数额。其中1<= d[i] <= 1000 000 000

5
1 3 1 1 4

5

思路是先将红包求出 sum数组，依次求和，sum[i] = sum[n] - sum[j]

如果直接暴力O(n) 查找的话，时间超出，所以改为二分查找， 这里的二分一定要查出相等的值

其次，注意每一个红包 最大可以 1000 000 000 ，所有红包之和可能超出整数范围，所以采用long进行存储

import java.util.*;

public class Main {

    // 思路先求缓存和，然后 sum[i] = sum[n] - sum[k] ,使用 max来保存最大值
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        long[] sums = new long[n+1];
        for(int i=0;i<n;i++){
            nums[i] = in.nextInt();
            sums[i+1] = sums[i] + nums[i];
        }
        long max = 0;
        for(int i=1;i<n;i++){
            /// 这里可以改为二分查找
            long ans = sums[n] - sums[i];
            int left = 0,right = i;
            while (left <= right){
                int mid = left + (right - left)/2;
                if(sums[mid] == ans){
                    max = Math.max(max,ans);
                    break;
                }else if(sums[mid] < ans){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        System.out.println(max);
    }

}

快手 将满二叉树转换为求和树

给满出二叉树，编写算法将其转化为求和树

什么是求和树：二叉树的求和树， 是一颗同样结构的二叉树，其树中的每个节点将包含原始树中的左子树和右子树的和。

二叉树：
10
/
-2 6
/ \ / \
8 -4 7 5

求和树：
20(4-2+12+6)
/
4(8-4) 12(7+5)
/ \ / \
0 0 0 0

二叉树给出前序和中序输入，求和树要求中序输出；
所有处理数据不会大于int；

输入描述:
2行整数，第1行表示二叉树的前序遍历，第2行表示二叉树的中序遍历，以空格分割
输出描述:
1行整数，表示求和树的中序遍历，以空格分割

10 -2 8 -4 6 7 5
8 -2 -4 10 7 6 5

0 4 0 20 0 12 0

思路很简单就是代码比较多，但是题还是比较常规

首先通过先序和中序创建二叉树

然后通过后序在原树上求和

最后中序遍历输出

import java.util.*;

public class Main {

    // 思路先通过前序遍历 和 中序遍历 创建二叉树，然后进行后序遍历

    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }

    static List<Integer> res = new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] preOrder = in.nextLine().split(" ");
        String[] inOrder = in.nextLine().split(" ");
        int[] preArray = new int[preOrder.length];
        int[] inArray = new int[preOrder.length];
        for (int i=0;i<preArray.length;i++){
            preArray[i] = Integer.parseInt(preOrder[i]);
        }
        for (int i=0;i<preArray.length;i++){
            inArray[i] = Integer.parseInt(inOrder[i]);
        }
        // 完成树的建立
        TreeNode root = rebuildTree(preArray, inArray, 0, preArray.length - 1, 0, inArray.length - 1);
        sumTree(root);
        inOrder(root);
        for (int i=0;i<res.size();i++){
            if(i == res.size()-1){
                System.out.print(res.get(i));
            }else{
                System.out.print(res.get(i) + " ");
            }
        }
    }

    private static void inOrder(TreeNode root) {
        if (root == null){
            return;
        }
        inOrder(root.left);
        res.add(root.val);
        inOrder(root.right);
    }

    private static int sumTree(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = sumTree(root.left);
        int right = sumTree(root.right);
        int res = root.val;
        int lval = root.left == null?0:root.left.val;
        int rval = root.right == null?0:root.right.val;
        root.val = left + right + lval + rval;
        return res;
    }

    private static TreeNode rebuildTree(int[] preArray, int[] inArray, int l1, int r1,int l2,int r2) {
        if(r1 < l1 || r2 <l2){
            return null;
        }
        int val = preArray[l1];
        TreeNode root = new TreeNode(val);
        int index = getIndex(inArray,val,l2,r2);
        int leftLen = index - l2;
        root.left = rebuildTree(preArray,inArray,l1+1,l1+leftLen,l2,index-1);
        root.right = rebuildTree(preArray,inArray,l1+leftLen+1,r1,index+1,r2);
        return root;
    }

    private static int getIndex(int[] inArray, int val, int l2, int r2) {
        for (int i=l2;i<=r2;i++){
            if (val == inArray[i]){
                return i;
            }
        }
        return -1;
    }


}

本题当然可以另一个解法，就是满二叉树的话，只需中序遍历就可以确定整颗树

满二叉树是奇数个，中间节点就是树的根节点，所以不用创建树，直接操作数组即可

import java.util.*;
 
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.nextLine();//满二叉树应该只需要中序遍历就可以确定唯一的树，所以不保存第一行输入
        String zhong = sc.nextLine();
        String[] split = zhong.split(" ");
        int[] a = new int[split.length];//中序遍历保存到数组a中
        for(int i=0;i<a.length;i++) {
            a[i] = Integer.parseInt(split[i]);
        }
        int[] ans = new int[a.length];//保存中序遍历的输出结果
        fun(a,0,a.length-1,ans);
        for(int i:ans){
            System.out.print(i+" ");
        }
        sc.close();
    }
 
    private static int fun(int[] a,int left,int right,int[] ans) {
        int mid = (right+left)/2;//中间元素不参与这一轮的计算
        if(right-left==2) {//出口条件
            ans[mid] = a[right] + a[left];
            ans[left] = 0;
            ans[right] = 0;
            return a[mid]+ans[mid];
        }else {
            ans[mid] = fun(a,left,mid-1,ans) + fun(a,mid+1,right,ans);
            return a[mid]+ans[mid];
        }
         
    }
     
}

搭积木

小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在积木B的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？
定义每一个长方形的长L和宽W都为正整数，并且1 <= W <= L <= INT_MAX, 袋子里面长方形的个数为N, 并且 1 <= N <= 1000000.
假如袋子里共有5个积木分别为 (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), 则不难判断这些积木最多可以搭成4层, 因为(2, 2) < (2, 4) < (2, 5) < (4, 5)。
输入描述:
第一行为积木的总个数 N

之后一共有N行，分别对应于每一个积木的宽W和长L
输出描述:
输出总共可以搭的层数

5
2 2
2 4
3 3
2 5
4 5

4

思路是最长递增子序列的解法，使用动态规划解法，时间复杂度太高，采用二分查找进行插入的解法，这题只是把最长递增子序列改为了二维，所以我们在插入时只插入其的索引数组

import java.util.*;

public class Main {

    // 思路是先排序，然后解法依然类似与找零钱的dp,来进行求最大值

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<int[]> list = new ArrayList<>();
        for(int i=0;i<n;i++){
            list.add(new int[]{in.nextInt(),in.nextInt()});
        }
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]){
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });

        int max = 1;
        int[] tmp = new int[n];
        int end = 0;
        // 这里可以使用二分法插入来加快时间复杂度
        for (int i=0;i<n;i++){
           int left = 0,right = end;
           while (left < right){
               int mid = left + (right - left)/2;
               if (list.get(tmp[mid])[0] <= list.get(i)[0] && list.get(tmp[mid])[1] <= list.get(i)[1]){
                   left = mid + 1;
               }else{
                   right = mid;
               }
           }
           if(left == end){
               end = end + 1;
           }
           tmp[left] = i;
        }
        System.out.println(end);
    }



}

魔法深渊

前几个月放映的头号玩家简直火得不能再火了，作为一个探索终极AI的研究人员，月神自然去看了此神剧。
由于太过兴奋，晚上月神做了一个奇怪的梦，月神梦见自己掉入了一个被施放了魔法的深渊，月神想要爬上此深渊。

已知深渊有N层台阶构成（1 <= N <= 1000)，并且每次月神仅可往上爬2的整数次幂个台阶(1、2、4、....)，请你编程告诉月神，月神有多少种方法爬出深渊
输入描述:
输入共有M行，(1<=M<=1000)

第一行输入一个数M表示有多少组测试数据，

接着有M行，每一行都输入一个N表示深渊的台阶数
输出描述:
输出可能的爬出深渊的方式

4
1
2
3
4

1
2
3
6

dp 生成1 到最大值 爬出方式的次数

import java.util.*;

public class Main {

    // 思路是先排序，然后解法依然类似与找零钱的dp,来进行求最大值

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        // 动态规划问题
        int max = 0;
        int[] nums = new int[m];
        for (int i=0;i<m;i++){
            nums[i] = in.nextInt();
            max = Math.max(nums[i],max);
        }
        int len = (int)Math.sqrt(max);
        int[] square = new int[len+1];
        for(int i=0;i<=len;i++){
            square[i] = (int) Math.pow(2,i);
        }
        int[] dp = new int[max+1];
        dp[0] = 1;
        for(int i=1;i<=max;i++){
            int count = 0;
            for (int j=0;j<square.length && square[j] <= i;j++){
                count += dp[i-square[j]];
                count = count % 1000_000_003;
            }
            dp[i] = count;
        }
        for (int i=0;i<nums.length;i++){
            System.out.println(dp[nums[i]]);
        }
    }
}