中级提升班7

题目一

把一个数字用中文表示出来。数字范围为[0, 99999]。
为了方便输出，使用字母替换相应的中文，万W千Q百B十S 零L。使用数字取代中文数字注:对于11应该表示为一十一(1S1)，而不是十一(S1)
输入描述:
数字0（包含）到99999(包含）。输出描述:
用字母替换相应的中文，万W千Q百B 十S 零L示例1:
输入
12001输出1W2QL1

题目二

给定一个整数数组A，长度为n，有1<= A[i] <=n，且对于[1,n]的整数，其中部分整数会重复出现而部分不会出现。
实现算法找到[1, n]中所有未出现在A中的整数。
提示:尝试实现0(n)的时间复杂度和0(1)的空间复杂度（返回值不计入空间复杂度）。
输入描述:
一行数字，全部为整数，空格分隔A0 A1 A2 A3.. .
输出描述:
一行数字，全部为整数，空格分隔RO R1 R2 R3.. .

示例1:
输入1 3 4 3输出2

public static void printNumberNotInArray(int[] arr){
    if (arr == null || arr.length==0){
        return;
    }

    // 做到i位置上，放的数是i+1
    for (int value:arr){
        modify(value, arr);
    }
    for(int i = 0; i <arr.length ; i++){
        if (arr[i] != i+1){
            System.out.println(i+1);
        }
    } 
    
}

private static void modify(int value, int[] arr) {
    while (arr[value - 1] != value){
        int tmp = arr[value - 1];
        arr[value - 1] = value;
        value = tmp;
    }
}

题目三 数量被3整除

小Q得到一个神奇的数列:1,12,123,. ..12345678910,1234567891011...。

并且小Q对于能否被3整除这个性质很感兴趣。
小Q现在希望你能帮他计算一下从数列的第I个到第r个(包含端点)有多少个数可以被3整除。输入描述:
输入包括两个整数l和r(1<= l <= r <= 1e9)，表示要求解的区间两端。输出描述:
输出一个整数,表示区间内能被3整除的数字个数。示例1:
输入2 5
输出3

解：

看1+2...+10是否能被整除

1034%3转换为(1+0+3+4) %3等效

题目四

CC里面有一个土豪很喜欢一位女直播Kiki唱歌，平时就经常给她点赞、送礼、私聊。最近CC直播平台在举行中秋之星主播唱歌比赛，假设一开始该女主播的初始人气值为start，能够晋升下一轮人气需要刚好达到end土豪给主播增加人气的可以采取的方法有:

a. 点赞花费x c币，人气+2
b. 送礼花费y c币，人气*2
c. 私聊花费z C币，人气-2

其中end远大于start且end为偶数，请写一个程序帮助土豪计算一下，最少花费多少C币就能帮助该主播Kiki将人气刚好达到end，从而能够晋级下一轮?

输入描述:
第一行输入5个数据，分别为: x y z start end，每项数据以空格分开。其中:0<x,y，z<=10000，0<start, end<=1000000

输出描述:
需要花费的最少c币。

示例1:
输入 3 100 1 2 6
输出 6

解：

找到剪枝的方法，

题目五 完全二叉树节点个数

完全二叉树节点个数

解

找到左子树最深和右子树最深，如果一样，左树为完全二叉树，不一样右树为完全二叉树。

public int countNodes(TreeNode root) {

    if (root == null) {
        return 0;
    }
    if (root.left == null){
        return 1;
    }
    if (root.right == null){
        return 2;
    }

    TreeNode left = root.left;
    int leftHigh = 0;
    while (left != null) {
        left = left.left;
        leftHigh++;
    }
    TreeNode right = root.right;
    int rightHigh = 0;
    while (right != null) {
        right = right.left;
        rightHigh++;
    }
    // 左子树是完全二叉树
    if (leftHigh == rightHigh) {

        return 1 + (int) Math.pow(2, leftHigh) - 1 + countNodes(root.right);
    } else { //右子树是完全二叉树
        return 1 + (int) Math.pow(2, rightHigh) - 1+ countNodes(root.left);
    }
}

题目六 最大奖励

CC直播的运营部门组织了很多运营活动，每个活动需要花费一定的时间参与，主播每参加完一个活动即可得到一定的奖励，参与活动可以从任意活动开始，但一旦开始，就需要将后续活动参加完毕（注意:最后一个活动必须参与)，活动之间存在一定的依赖关系（不存在环的情况），现在给出所有的活动时间与依赖关系，以及给出有限的时间，请帮主播计算在有限的时候内，能获得的最大奖励，以及需要的最少时长。

如上图数据所示，给定有限时间为10天。可以获取得最大奖励为n 11700，需要的时长为t 9天。参加的活动为BDCFH四个。
输入描述:

第一行输入数据N与D，表示有N顷活动。D表示给予的时长。0<N<=1000，0<D<=10000.
从第二行开始到N+1行，每行福述一个活动的信息，其中第一项表示当前活动需要花费的时间t。第二项表示可以获得的奖励a，之后有N真数据，表示当前活动与其他活动的依赖关系，1表示有依赖，0表示无依赖。每项数据用空格分开。

输出措述:
输出两项数据A与T，用空格分割。A表示所获得的最大奖励，T表示所需要的时长。

输入8 10
3 2000 0 1 1 0 0 0 0 0
3 4000 0 0 0 1 1 0 0 0 
2 2500 0 0 0 1 0 0 0 0 
1 1600 0 0 0 0 1 1 1 0
4 3800 0 0 0 0 0 0 0 1
2 2600 0 0 0 0 0 0 0 1
4 4000 0 0 0 0 0 0 0 1
3 3500 0 0 0 0 0 0 0 0
输出
11700 9

解：

从最后一个点出发，每个节点准备一个有序表，key为到最后的的总天数，value为钱。

利用bfs推出每个点的有序表，并且利用剪枝的方法，减去时间长但挣钱少的分支，保证每个节点的表，天数变大，收益必须变大。最后得到所有点的结果后，合并在一起，再清洗数据。

// m活动， limit时长
public int[] maxRewardMinDays(int[][] m, int limit) {
    TreeMap<Integer, Integer> treeMap = new TreeMap<>();//天数:奖励
    builtTreeMap(m, treeMap);
    int day = treeMap.floorKey(limit); //返回小于等于limit的最大键
    int reward = treeMap.get(day);
    return new int[]{day, reward};
}

private void builtTreeMap(int[][] m, TreeMap<Integer, Integer> treeMap) {
    int len = m.length;
    //对于每一个节点,都需要创造一张属于它自己的(天数:奖励)表
    TreeMap<Integer, Integer>[] maps = new TreeMap[len];
    //初始化,最后一个结点的表为它自己的天数:奖励
    TreeMap<Integer, Integer> map = new TreeMap<>();
    map.put(m[len - 1][0], m[len - 1][1]);
    maps[len - 1] = map;
    for (int i = 0; i < len - 1; i++) {
        maps[i] = new TreeMap<>();
    }

    for (int i = len - 2; i >= 0; i--) {
        for (int j = 2; j < m[i].length; j++) {
            if (m[i][j] == 0) {
                continue;
            }
            // 获取后序节点进行计算
            for (Map.Entry<Integer, Integer> entry : maps[j - 2].entrySet()) {
                update(m[i][0] + entry.getKey(),
                        m[i][1] + entry.getValue(),
                        maps[i]);

            }
        }
    }

    // 将所有结果整合到最后结果中
    for (Map<Integer, Integer> mp : maps) {
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
            update(entry.getKey(), entry.getValue(), treeMap);
        }
    }
}

// 按关系策略更新
private void update(int day, int reword,
                    TreeMap<Integer, Integer> map) {

    boolean isAdd = false;
    if (map.floorKey(day) == null) {
        map.put(day, reword);
        isAdd = true;
    } else { // 找到了小的
        int ceilDay = map.floorKey(day);
        int ceilRead = map.get(ceilDay);
        if (reword > ceilRead) {
            map.put(day, reword);
            isAdd = true;
        }

    }

    // 调整map使其保证单调性
    if (isAdd) {
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            // 删除时间长钱少的
            if (entry.getKey() > day && entry.getValue() <= reword) {
                map.remove(entry.getKey());
            }
        }
    }
}

public static void main(String[] args) {
    int[][] matrix = new int[][]{
            {3, 2000, 0, 1, 1, 0, 0, 0, 0, 0},
            {3, 4000, 0, 0, 0, 1, 1, 0, 0, 0},
            {2, 2500, 0, 0, 0, 1, 0, 0, 0, 0},
            {1, 1600, 0, 0, 0, 0, 1, 1, 1, 0},
            {4, 3800, 0, 0, 0, 0, 0, 0, 0, 1},
            {2, 2600, 0, 0, 0, 0, 0, 0, 0, 1},
            {4, 4000, 0, 0, 0, 0, 0, 0, 0, 1},
            {3, 3500, 0, 0, 0, 0, 0, 0, 0, 0}
    };
    P06MaxRewardMinDays p06MaxRewardMinDays = new P06MaxRewardMinDays();
    System.out.println(Arrays.toString(p06MaxRewardMinDays.maxRewardMinDays(matrix, 10)));
}

题目七 最长递增子序列

leetcode 300. 最长递增子序列

解

使用dp数组，每一位dp[i]表示子序列必须以i结尾的情况下最长递增子序列长度，找到前面所有比他小的数，dp[i]最大的，然后+1就是当前位置最大的子序列。

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++) {
        // 找到比他小的值 + 1
        int max = Integer.MIN_VALUE;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    int max = 0;
    for (int i = 0; i < n; i++) {
        max = Math.max(max, dp[i]);
    }
    return max;
}

使用辅助数组优化，构建单调性，加入ends数组代表所有长度为i+1的递增子序列中最小结尾是统计谁，所有都是无效区，有效区中没有比自己大的就扩充，有就更新，统计左侧连同自己有几个数，就是答案

3 2 4 5 1 7 
数组更新如下
3 
2 
2 4 扩充有效区
2 4 5 
1 4 5 
1 4 5 7