- 一个数组的异或和是指数组中所有的数异或在一起的结果，给定一个数组arr，求最大子数组异或和。
1.思路一：利用预处理数组求出以每个位置结尾时，从0位置到结尾位置的异或和，由于eor(i) = eor(0~j) ^ eor(j+1~i) -> eor(j+1~i) = eor(0~i) ^ eor(0j)加速求异或和。我们可以以i位置结尾，0i,1i,2i,...,i~i,分别求出异或和取最大值，每个i位置都求一遍找到最大子数组异或和。
2.思路二利用前缀树（把树转化为二进制）。前缀树种有所有从0位置开始到i-1位置的前缀树记录，当要求以i位置结尾时的最大子数组前缀和时，我们不知道前面从哪个位置开始和i位置的数异或起来是最大的，我们可以求出现在从0位置到i位置的异或和，然后在前缀树中利用贪心帮我们找一个最大的前缀和。下面是利用前缀树求的代码。如果最高位是0,那么他希望遇到和他相反的数1,后面的位都希望遇到相反的数，那么该位还是1，如果最高位是1那么希望遇到那么希望遇到1让他最高位变为0成为一个整数，后续希望遇到和他相反的数成为1.时间复杂度O(N)
/**
* 一个数组的异或和是指数组中所有的数异或在一起的结果，给定一个数组arr，求最大子数组异或和
*/
public class MaxSubArrayEorSum {
static class Node{
// 只有两个分支0，或者1
Node[] nexts;
public Node(){
// 0位置就代表位0，一位置就代表位1
this.nexts = new Node[2];
}
}
// 前缀树中保存了0~i-1,的所有异或和
// 前缀树，两个功能向前缀树中加入一个树，形成前缀树
// 给定一个数，求出和前缀树中的最大异或和
static class PrefixTree{
// 定义前缀树根节点
Node root;
public PrefixTree(){
// node 中的 nexts 0和1位置分别代表是否存在0和1这条路
root = new Node();
}
// 向前缀树中添加元素
public void add(int num){
Node cur = root;
// 从最高位开始添加,int类型的值为32位
for (int index = 31; index >= 0; index--) {
// 当前的index位是几（0或者1）
int bit = (num >> index) & 1;
// 有就复用，没有就新建
cur.nexts[bit] = cur.nexts[bit] == null ? new Node() : cur.nexts[bit];
cur = cur.nexts[bit];
}
}
// 给定一个数，求出和前缀树中的最大异或和
public int getMaxEorSum(int num){
Node cur = root;
// 选择哪条路
int path;
int res = 0;
// 从最高位开始选
for (int index = 31; index >= 0 ; index--) {
// 当前的index位是几（0或者1）
int bit = (num >> index) & 1;
// 如果bit是最高位
// 1.bit == 1,那么他会选择1这跳路径，使其变为0（整数）
// 2.bit == 0,那么他会选择0，这条路，使其保持整数。
if(index == 31){
path = bit == 1 ? 1 : 0 ;
}else{
// 普遍位置
path = bit == 1 ? 0 : 1;
}
// 判断这条路径有没有路，如果没有路那么只能选另一条路(不可能每条路都是空，初始时会把0加入前缀树，代表前缀和为0)
int temp = cur.nexts[path] == null ? path ^ 1 : path;
// temp就是最高位的值了
res |= (temp ^ bit) << index;
cur = cur.nexts[temp];
}
return res;
}
}
public static int maxSubArrayEorSum(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
// 构建前缀树
PrefixTree prefixTree = new PrefixTree();
// 开始前缀树为空，里面的前缀和为0；
prefixTree.add(0);
int max = Integer.MIN_VALUE;
int eor = 0;
for (int i = 0; i < arr.length; i++) {
// 0到i位置的异或和
eor ^= arr[i];
int maxEorSum = prefixTree.getMaxEorSum(eor);
max = Math.max(max,maxEorSum);
prefixTree.add(eor);
}
return max;
}
}
- 给定一个只由 0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成 的字符串express，再给定一个布尔值 desired。返回express能有多少种组合 方式，可以达到desired的结果。
【举例】
express="1^0|0|1"，desired=false
只有 1^((0|0)|1)和 1^(0|(0|1))的组合可以得到 false，返回 2。 express="1"，desired=false
无组合则可以得到false，返回0
/**
* 给定一个只由 0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成 的字符串express，
* 再给定一个布尔值 desired。返回express能有多少种组合 方式，可以达到desired的结果。
* 【举例】
* express="1^0|0|1"，desired=false
* 只有 1^((0|0)|1)和 1^(0|(0|1))的组合可以得到 false，返回 2。 express="1"，desired=false
* 无组合则可以得到false，返回0
*/
public class BooleanNum {
// 暴力递归
public static int booleanNum(String express,boolean desired){
// 如果字符串为空，或者是空字符串不能组成
if(express == null || express.equals("")){
return 0;
}
// 前置校验字符串是否符合要求
// 字符串必须为偶数，奇数位置必须为逻辑运算符，偶数位置必须为 0，1
if(!isValid(express)){
return 0;
}
// 范围上尝试的模型
char[] chars = express.toCharArray();
return process(chars,0,chars.length - 1,desired);
}
// 在L -> R 上返回满足desired 的组合数
private static int process(char[] c,int L,int R,boolean desired){
if(L == R){
if(desired){
return c[L] == '1' ? 1 : 0;
}else{
return c[L] == '0' ? 1 : 0;
}
}
// 假设以i字符作为最后的运算符
int sum = 0;
for(int i = L+1; i < R;i += 2){
// 左边符合的个数，右边符合的个数
if(desired){
// 如果是true
switch (c[i]){
case '|': sum += process(c,L,i-1,true) * process(c,i+1,R,true) +
process(c,L,i-1,true) * process(c,i+1,R,false) +
process(c,L,i-1,false) * process(c,i+1,R,true);
break;
case '&': sum += process(c,L,i-1,true) * process(c,i+1,R,true);
break;
case '^': sum += process(c,L,i-1,false) * process(c,i+1,R,true) +
process(c,L,i-1,true) * process(c,i+1,R,false);
break;
}
}else {
switch (c[i]){
case '|': sum += process(c,L,i-1,false) * process(c,i+1,R,false);
break;
case '&': sum += process(c,L,i-1,true) * process(c,i+1,R,false)+
process(c,L,i-1,false) * process(c,i+1,R,true)+
process(c,L,i-1,false) * process(c,i+1,R,false);
break;
case '^': sum += process(c,L,i-1,false) * process(c,i+1,R,false) +
process(c,L,i-1,true) * process(c,i+1,R,true);
break;
}
}
}
return sum;
}
// 动态规划
// 有三个可变参数，第三个参数只有两种情况，建立两张二维表就够了
public static int dp(String express,boolean desired){
// 如果字符串为空，或者是空字符串不能组成
if(express == null || express.equals("")){
return 0;
}
// 前置校验字符串是否符合要求
// 字符串必须为偶数，奇数位置必须为逻辑运算符，偶数位置必须为 0，1
if(!isValid(express)){
return 0;
}
char[] c = express.toCharArray();
int n = c.length;
int[][] trueDp = new int[n][n];
int[][] falseDp = new int[n][n];
// 由于是范围上尝试模型表的左下半区域全都无效
// trueDp表 奇数列奇数行不用填
for (int i =0;i < n; i+=2){
trueDp[i][i] = c[i] == '1' ? 1 : 0;
falseDp[i][i] = c[i] == '0' ? 1 : 0;
}
for (int row = n - 3; row >= 0; row = row - 2) {
for (int col = row + 2; col < n; col = col + 2) {
for(int i = row+1; i < col;i += 2){
// 左边符合的个数，右边符合的个数
// 如果是true
switch (c[i]){
case '|': trueDp[row][col] += trueDp[row][i-1] * falseDp[i+1][col] +
falseDp[row][i-1] * trueDp[i+1][col] +
trueDp[row][i-1] * trueDp[i+1][col];
break;
case '&':trueDp[row][col] += trueDp[row][i-1] * trueDp[i+1][col];
break;
case '^': trueDp[row][col]+= trueDp[row][i-1] * falseDp[i+1][col]+
falseDp[row][i-1]* trueDp[i+1][col];
break;
}
switch (c[i]){
case '|': falseDp[row][col]+= falseDp[row][i-1]* falseDp[i+1][col];
break;
case '&': falseDp[row][col]+= trueDp[row][i-1] * falseDp[i+1][col]+
falseDp[row][i-1] * trueDp[i+1][col]+
falseDp[row][i-1] * falseDp[i+1][col];
break;
case '^': falseDp[row][col]+= trueDp[row][i-1] * trueDp[i+1][col] +
falseDp[row][i-1] * falseDp[i+1][col];
break;
}
}
}
}
return desired ? trueDp[0][n-1]:falseDp[0][n-1];
}
private static boolean isValid(String express){
char[] c = express.toCharArray();
// 是否为奇数长度
if(express.length() % 2 == 0){
return false;
}
for (int i = 0; i < c.length; i++) {
if(i % 2 == 0 && (c[i] != '1' && c[i] != '0')){
// 偶数位置必须为01
return false;
}else if(i % 2 != 0 && (c[i] != '|' && c[i] != '&' && c[i] != '^')){
return false;
}
}
return true;
}
}
- 给出一组正整数arr，你从第0个数向最后一个数，每个数的值表示你从这个位置可以向右跳跃的最大长度,计算如何以最少的跳跃次数跳到最后一个数。
/**
* 给出一组正整数arr，你从第0个数向最后一个数，
* 每个数的值表示你从这个位置可以向右跳跃的最大长度
* 计算如何以最少的跳跃次数跳到最后一个数。
*/
public class MinStepNum {
public static int minStepNum(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
// 当前跳了几步
int step = 0;
// 当前步数的最右距离
int right = 0;
// 如果在多跳一步能跳到哪里
int next = arr[0];
int n = arr.length;
for (int i = 0; i < n; i++) {
if(i > right){
// 需要增加步数
step++;
right = next;
}
if(i+arr[i] > next){
next = i + arr[i];
}
}
return step;
}
public static void main(String[] args) {
int[] arr = { 3, 2, 3, 1, 1, 4 };
System.out.println(minStepNum(arr));
}
}
- 给定两个有序数组arr1和arr2，再给定一个正数K,求两个数累加和最大的前K个，两个数必须分别来自arr1和arr2
/**
* 给定两个有序数组arr1和arr2，再给定一个正数K
* 求两个数累加和最大的前K个，两个数必须分别来自arr1和arr2
*/
public class MaxSum {
static class Node{
// arr1中的下标
int index1;
// arr2中的下标
int index2;
// 累加和
int sum;
public Node(int index1,int index2,int sum){
this.index1 = index1;
this.index2 = index2;
this.sum = sum;
}
}
// 大根堆比较器
static class MaxHeapComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2) {
return o2.sum - o1.sum ;
}
}
public static int[] maxSum(int[] arr1,int[] arr2,int k){
if(arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0){
return null;
}
int n1 = arr1.length;
int n2 = arr2.length;
k = Math.min(k,arr1.length*arr2.length);
// 大根堆
PriorityQueue<Node> heap = new PriorityQueue(new MaxHeapComparator());
// 去重表
boolean[][] set = new boolean[arr1.length][arr2.length];
int[] res = new int[k];
int index = 0;
heap.offer(new Node(n1 -1,n2-1,arr1[n1-1]+arr2[n2-1]));
set[n1-1][n2-1] = true;
while (index < k && !heap.isEmpty()){
Node poll = heap.poll();
res[index++] = poll.sum;
// 当前位置的左边和上边加入到大根堆中，这两个位置的和是除了当前位置最大的值
if(poll.index1-1 >=0 && !set[poll.index1-1][poll.index2]){
heap.offer(new Node(poll.index1-1,poll.index2,arr1[poll.index1-1]+arr2[poll.index2]));
set[poll.index1-1][poll.index2] = true;
}
if(poll.index2-1 >=0 && !set[poll.index1][poll.index2-1]){
heap.offer(new Node(poll.index1,poll.index2-1,arr1[poll.index1]+arr2[poll.index2-1]));
set[poll.index1][poll.index2-1] = true;
}
}
return res;
}
}
给定一个正数数组arr，返回该数组能不能分成4个部分，并且每个部分的累加和相等，切分位置的数不要。
例如:
arr=[3, 2, 4, 1, 4, 9, 5, 10, 1, 2, 2] 返回true
三个切割点下标为2, 5, 7. 切出的四个子数组为[3,2], [1,4], [5], [1,2,2]，
累加和都是5
package newyangfei.trainingcamq3.day06;
import java.util.HashMap;
/**
* 给定一个正数数组arr，返回该数组能不能分成4个部分，并且每个部分的累加和相等，切分位置的数不要。
* 例如:
* arr=[3, 2, 4, 1, 4, 9, 5, 10, 1, 2, 2] 返回true
* 三个切割点下标为2, 5, 7. 切出的四个子数组为[3,2], [1,4], [5], [1,2,2]，
* 累加和都是5
*/
public class CutArray {
public static boolean cutArray(int[] arr){
if(arr == null || arr.length < 7){
// 切成四部分，至少也要七个数
return false;
}
// 用一个map记录某个位置的前缀和
HashMap<Integer,Integer> map = new HashMap<>();
// 生成前缀和位置表
int sum = arr[0];
for (int i = 1; i < arr.length; i++) {
map.put(sum,i);
sum += arr[i];
}
int n = arr.length;
// 由题意可知，第一刀的位置必须从第二个元素开始（下标1）,不能超过n-6
int a = arr[0];
for (int i = 1; i < n-5; i++) {
// 枚举所有第一刀的可能性
// 假如在i位置切了第一刀，那么我们可以得到0~i-1的累加和假设为a，
// 则第二刀的位置的前缀和一定等于a + a + arr[i]
// 第三刀的位置前缀和一定满足 a+ a+a + arr[i] + arr[i2](第二刀的位置)
// 如果前面都存在，验证最后一段是否等于a
if(map.containsKey(a) && map.get(a) == i){
// 第一刀存在才继续往下，否则枚举下一个第一刀的位置
// 如果有第二刀，第二刀应该满足的前缀和
int cut2 = 2*a+arr[i];
if(map.containsKey(cut2)){
// 有第二刀才继续往下进行切分
// 第三道应该满足
int cut3 = 3*a+arr[i]+arr[map.get(cut2)];
if(map.containsKey(cut3)){
// 有第三单，判断是否第四部分也是a
int index = map.get(cut3);
int lastSum = cut3 + arr[index] + a;
if(lastSum == sum){
return true;
}
}
}
}
a += arr[i];
}
return false;
}
}
- 给定三个字符串str1、str2和aim，如果aim包含且仅包含来自str1和str2的所有字符， 而且在aim中属于str1的字符之间保持原来在str1中的顺序，属于str2的字符之间保持 原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现一个函数，判断aim是 否是str1和str2交错组成
【举例】 str1="AB"，str2="12"。那么"AB12"、"A1B2"、"A12B"、"1A2B"和"1AB2"等都是 str1 和 str2 的 交错组成
/**
- 给定三个字符串str1、str2和aim，如果aim包含且仅包含来自str1和str2的所有字符，
- 而且在aim中属于str1的字符之间保持原来在str1中的顺序，属于str2的字符之间保持 原来在str2中的顺序，
- 那么称aim是str1和str2的交错组成。实现一个函数，判断aim是 否是str1和str2交错组成
- 【举例】 str1="AB"，str2="12"。那么"AB12"、"A1B2"、"A12B"、"1A2B"和"1AB2"等都是 str1 和 str2 的 交错组成
*/
public class Staggered {
public static boolean isStaggered(String str1,String str2,String aim){
if(str1 != null && str2 != null && str1.length()+str2.length() != aim.length()){
return false;
}
char[] c1 = str1.toCharArray();
char[] c2 = str2.toCharArray();
char[] a = aim.toCharArray();
int len1 = c1.length;
int len2 = c2.length;
int lenA = a.length;
// 定义二维dp表，dp[i][j] 表示，在c1中取0~i-1,个字符，在c2中取0~j-1字符
// 在a中取0~i+j-1个字符，能否形成交错组成。
boolean[][] dp = new boolean[len1+1][len2+1];
// 两个字符串都取0个形成一个0个的aim
dp[0][0] = true;
// 第一行
for (int i = 1; i < dp[0].length; i++) {
dp[0][i] = c2[i-1] == a[i-1] ? dp[0][i-1] : false;
}
// 第一列
for (int i = 1; i < dp.length; i++) {
dp[i][0] = c1[i-1] == a[i-1] ? dp[i-1][0] : false;
}
// 普遍位置
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
// c1中取0 - i-1,个字符，c2中取0 - j-1个字符
// 和a中 0~i+j-1比较
if(c1[i-1] == a[j+i-1] && dp[i-1][j]){
dp[i][j] = dp[i-1][j];
}
if(c2[j-1] == a[j+i-1] && dp[i][j-1]){
dp[i][j] = dp[i][j-1];
}
}
}
return dp[len1][len2];
}
}
