蓝桥杯 完全二叉树的权值

Problem: 蓝桥杯 完全二叉树的权值

思路

这个问题是关于完全二叉树的权值。完全二叉树的特性是，除了最后一层外，其他各层的节点数都达到最大，且最后一层从左向右连续。在这个问题中，我们需要找到权值最大的层。
我们可以通过两种方法来解决这个问题：前缀和和双指针。

解题方法

前缀和

前缀和是一种常用的解决数组问题的方法。在这个问题中，我们首先计算出每一层的权值，然后找出权值最大的层。
我们首先读入节点的权值，并计算出前缀和。然后，我们计算出完全二叉树的深度。接着，我们遍历每一层，计算出每一层的权值，并更新最大权值。最后，我们找出权值最大的层。

双指针

双指针也是一种常用的解决数组问题的方法。在这个问题中，我们使用两个指针，一个指向当前层的开始，另一个指向当前层的结束。
我们首先读入节点的权值。然后，我们初始化两个指针，一个指向当前层的开始，另一个指向当前层的结束。接着，我们遍历每一层，计算出每一层的权值，并更新最大权值。最后，我们找出权值最大的层。

复杂度

时间复杂度:

前缀和的时间复杂度是$O(n)$，因为我们需要遍历每一个节点。
双指针的时间复杂度是$O(n)$，因为我们需要遍历每一个节点。

空间复杂度:

前缀和的空间复杂度是$O(n)$，因为我们需要存储每一个节点的权值和前缀和。
双指针的空间复杂度是$O(n)$，因为我们需要存储每一个节点的权值。

前缀和Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer sr = new StreamTokenizer(in);
    static int MAXN = (int) (1e5 + 10);
    static int[] res = new int[MAXN];
    static int[] arr = new int[MAXN];
    static int n;
    public static void main(String[] args) throws IOException {
        n = nextInt();
        for(int i = 1; i <= n; i++) {
            arr[i] = nextInt();
            arr[i] += arr[i - 1];
        }
        int k = (int) Math.ceil(Math.log(n + 1) / Math.log(2)); // 完全二叉树的深度
        
        int max = Integer.MIN_VALUE;
        for(int i = 1; i < k; i++) {
            res[i] = arr[(int) Math.pow(2, i) - 1] - arr[(int) Math.pow(2, i - 1) - 1];
            max = Math.max(max, res[i]);
        }
        res[k] = arr[n] - arr[(int) Math.pow(2, k - 1) - 1];
        max = Math.max(max, res[k]);
        for(int i = 1; i <= k; i++) {
            if(res[i] == max) {
                out.println(i);
                break;
            }
        }
        out.flush();
    }
    static int nextInt() throws IOException {
        sr.nextToken();
        return (int) sr.nval;
    }

}

双指针Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int MAXN = (int) (1e5 + 10);
	static int[] arr = new int[MAXN];
	static int n;

	// O(n) / O(nlogn)
	public static void main(String[] args) throws IOException {
		n = nextInt();
		for (int i = 1; i <= n; i++) {
			arr[i] = nextInt();
		}
		int depth = 0;
		long max = Long.MIN_VALUE;
		for (int i = 1, d = 1; i <= n; i *= 2, d++) {
			long s = 0;
			for (int j = i; j < i + (1 << d - 1) && j <= n; j++) {
				s += arr[j];
			}
			if(s > max) {
				max = s;
				depth = d;
			}

		}
		out.println(depth);
		out.flush();

	}

	private static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}