第二场（11.20）

A、热心的牛牛

我的代码：

public long Maximumcandies (long n, long k) {
        if(k % (n+1) == 0){
            return k/(n+1) -2;
        }else{
            long temp = k%(n+1);
            long res = k/(n+1);
            long p = k/(n+1) + temp/n;
            if(res < p){
                return res;
            }else{
                return res-1;
            }
        }
    }

别人的代码

public long Maximumcandies (long n, long k) {
        return (k - n) / (n + 1);
    }

B、牛牛切木棒

斐波那契数列

三角形的三边定理和斐波那契数列的关系：

由于形成三角形的充要条件是任何两边的和大于第三边，所以构不成三角形的条件则为存在两边之和不超过第三边。

结合题目分析：因为要使得分出来的段数最多，所以前面符合条件的长度要尽可能小。前两段取1，然后第三段取2，然后接着后面取的段数都为全面两段的和，这样即满足了不能构成三角形的条件，也能够保证后面剩下的长度更长。

1,1,2,3,5,8 ················ 这样不就是斐波那契数列了嘛。所以最后当形成的斐波那契数列的和大于总的长度时，即返回数列的下标即为分得的段数。

public int stick (long a) {
        long[] f = new long[61];
        f[0] = 1;
        f[1] = 1;
        for(int i = 2; i < f.length; i++){
            f[i] = f[i-1] + f[i-2];
        }
        long ans = 0;
        for(int i = 0; i < f.length; i++){
            ans += f[i];
            if(ans > a)
                return i;
        }
        return -1;
    }

C、TreeII

常规解法: 队列

解题过程：

1、先将根结点入队

2、队首出队 => now，此时now依次与它的每一个子结点进行异或并累加到返回结果res中，每一个异或操作，都得将该子结点入队

• 第一次的循环，当队列不为空的时候
  • 循环结束的标志，当前结点等于最后一个结点时
• 异或操作的循环，因为为k叉树，所以每一个根节点都有k个子结点
  • 最后一层没满，所以循环的条件为 当前结点小于最后一个结点

3、返回结果 res

public long tree2 (int k, int[] a) {
        //当前子结点下标为1
        int curPos = 1;
        //整个数组的长度
        int len = a.length;
        //返回的结果
        long res = 0;
        Queue<Integer> q = new LinkedList<>();
        //根结点入队
        q.offer(a[0]);
        //循环的条件  队列不为空
        while(!q.isEmpty()){
            // 当前子结点到最后一个结点时，循环直接终止
            if(curPos == len)
                break;
            //当前结点(队首)
            int now = q.poll();
            //K叉树，所以需要异或K次（在当前层完全的情况下）
            for(int i = 1; i <= k; i++){
                //当curPos<len时，才进行操作，因为当 当前子结点到最后一个结点时，那个这一层就是最后一层
                if(curPos < len){
                    res += now ^ a[curPos];
                    q.offer(a[curPos]);  // 该子结点入队
                    curPos++;   // 最后curPos == len
                }
            }
        }
        return res;  // 返回结果
    }

解法优化：

去除队列

public long tree2 (int k, int[] a) {
        int curPos = 1;
        int len = a.length;
        long res = 0;
        for(int i = 0; i < len; i++){
            if(curPos == len)
                break;
            for(int j = 1; j <= k; j++){
                if(curPos < len){
                    res += a[i] ^ a[curPos];
                    curPos++;
                }
            }
        }
        return res;
    }