- 给定一个正整数M，请构造出一个长度为M的数组arr，要求对任意的i、j、k三个位置，如果i<j<k，都有arr[i] + arr[k] != 2*arr[j],返回构造出的arr。
1.如果一个数组中的数是达标标的，那么同事变换他的值为奇数也是达标的，如[1,2,5] -> [1,3,9]。同事变换为偶数也是达标的。[1,2,5] ->[2,4,10],所以我们就找到了一个达标种子[1,2,5] 得到了两个达标的数组[1,3,9]和[2,4,10],可以证明这两个新数组组成的数组也是达标的[1,3,9,2,4,10],在奇数部分选一个加上偶数部分选一个，一定是奇数，任何一个数的2倍必是偶数达标。所以我们可以用分治的思想，把求M个数的问题化解为求M/2 M/4 M/8 一直到一个达标种子。所有可能都可以由这个达标种子加工而来。
/**
* 给定一个正整数M，请构造出一个长度为M的数组arr，要求对任意的i、j、k三个位置，
* 如果i<j<k，都有arr[i] + arr[k] != 2*arr[j],返回构造出的arr。
*/
public class DaBiaoArr {
public static int[] daBiaoArr(int m){
if(m <= 0){
return null;
}
return process(m);
}
// 给你一个数m，生成达标的数组arr,元素m个
private static int[] process(int m){
if(m == 1){
// 如果需要一个元素达标，元素为1的数组天然达标
return new int[]{1};
}
// 如果m大于1，那么可以分治下去
// 如果m为奇数 7 需要4个达标种子 -> （7+1）/ 2
// 如果m为偶数 8 需要4个达标的种子 -> (8+1) / 2
int half = (m + 1) / 2;
int[] resA = process(half);
int n = resA.length;
// 由达标种子加工新的数组
int[] arr = new int[m];
// 奇数达标数组
int index = 0;
for(;index < n;index++){
arr[index] = resA[index] * 2 - 1;
}
// 偶数达标
for (int i = 0; i < m - half - 1 ; i++) {
arr[index++] = resA[i] * 2;
}
// 返回达标新数组
return arr;
}
}
- 给定一个二叉树的头节点head，路径的规定有以下三种不同的规定：
1）路径必须是头节点出发，到叶节点为止，返回最大路径和
2）路径可以从任何节点出发，但必须往下走到达任何节点，返回最大路径和
3）路径可以从任何节点出发，到任何节点，返回最大路径和
- 二叉树递归套路。
