- 一個數(shù)組的異或和是指數(shù)組中所有的數(shù)異或在一起的結(jié)果，給定一個數(shù)組arr，求最大子數(shù)組異或和。
1.思路一：利用預(yù)處理數(shù)組求出以每個位置結(jié)尾時，從0位置到結(jié)尾位置的異或和，由于eor(i) = eor(0~j) ^ eor(j+1~i) -> eor(j+1~i) = eor(0~i) ^ eor(0j)加速求異或和。我們可以以i位置結(jié)尾，0i,1i,2i,...,i~i,分別求出異或和取最大值，每個i位置都求一遍找到最大子數(shù)組異或和。
2.思路二利用前綴樹（把樹轉(zhuǎn)化為二進制）。前綴樹種有所有從0位置開始到i-1位置的前綴樹記錄，當要求以i位置結(jié)尾時的最大子數(shù)組前綴和時，我們不知道前面從哪個位置開始和i位置的數(shù)異或起來是最大的，我們可以求出現(xiàn)在從0位置到i位置的異或和，然后在前綴樹中利用貪心幫我們找一個最大的前綴和。下面是利用前綴樹求的代碼。如果最高位是0,那么他希望遇到和他相反的數(shù)1,后面的位都希望遇到相反的數(shù)，那么該位還是1，如果最高位是1那么希望遇到那么希望遇到1讓他最高位變?yōu)?成為一個整數(shù)，后續(xù)希望遇到和他相反的數(shù)成為1.時間復(fù)雜度O(N)
/**
* 一個數(shù)組的異或和是指數(shù)組中所有的數(shù)異或在一起的結(jié)果，給定一個數(shù)組arr，求最大子數(shù)組異或和
*/
public class MaxSubArrayEorSum {
static class Node{
// 只有兩個分支0，或者1
Node[] nexts;
public Node(){
// 0位置就代表位0，一位置就代表位1
this.nexts = new Node[2];
}
}
// 前綴樹中保存了0~i-1,的所有異或和
// 前綴樹，兩個功能向前綴樹中加入一個樹，形成前綴樹
// 給定一個數(shù)，求出和前綴樹中的最大異或和
static class PrefixTree{
// 定義前綴樹根節(jié)點
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;
// 有就復(fù)用，沒有就新建
cur.nexts[bit] = cur.nexts[bit] == null ? new Node() : cur.nexts[bit];
cur = cur.nexts[bit];
}
}
// 給定一個數(shù)，求出和前綴樹中的最大異或和
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這跳路徑，使其變?yōu)?（整數(shù)）
// 2.bit == 0,那么他會選擇0，這條路，使其保持整數(shù)。
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;
}
// 構(gòu)建前綴樹
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的結(jié)果。
【舉例】
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的結(jié)果。
* 【舉例】
* 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;
}
// 前置校驗字符串是否符合要求
// 字符串必須為偶數(shù)，奇數(shù)位置必須為邏輯運算符，偶數(shù)位置必須為 0，1
if(!isValid(express)){
return 0;
}
// 范圍上嘗試的模型
char[] chars = express.toCharArray();
return process(chars,0,chars.length - 1,desired);
}
// 在L -> R 上返回滿足desired 的組合數(shù)
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;
}
}
// 假設(shè)以i字符作為最后的運算符
int sum = 0;
for(int i = L+1; i < R;i += 2){
// 左邊符合的個數(shù)，右邊符合的個數(shù)
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;
}
// 動態(tài)規(guī)劃
// 有三個可變參數(shù)，第三個參數(shù)只有兩種情況，建立兩張二維表就夠了
public static int dp(String express,boolean desired){
// 如果字符串為空，或者是空字符串不能組成
if(express == null || express.equals("")){
return 0;
}
// 前置校驗字符串是否符合要求
// 字符串必須為偶數(shù)，奇數(shù)位置必須為邏輯運算符，偶數(shù)位置必須為 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];
// 由于是范圍上嘗試模型表的左下半?yún)^(qū)域全都無效
// trueDp表 奇數(shù)列奇數(shù)行不用填
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){
// 左邊符合的個數(shù)，右邊符合的個數(shù)
// 如果是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();
// 是否為奇數(shù)長度
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')){
// 偶數(shù)位置必須為01
return false;
}else if(i % 2 != 0 && (c[i] != '|' && c[i] != '&' && c[i] != '^')){
return false;
}
}
return true;
}
}
- 給出一組正整數(shù)arr，你從第0個數(shù)向最后一個數(shù)，每個數(shù)的值表示你從這個位置可以向右跳躍的最大長度,計算如何以最少的跳躍次數(shù)跳到最后一個數(shù)。
/**
* 給出一組正整數(shù)arr，你從第0個數(shù)向最后一個數(shù)，
* 每個數(shù)的值表示你從這個位置可以向右跳躍的最大長度
* 計算如何以最少的跳躍次數(shù)跳到最后一個數(shù)。
*/
public class MinStepNum {
public static int minStepNum(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
// 當前跳了幾步
int step = 0;
// 當前步數(shù)的最右距離
int right = 0;
// 如果在多跳一步能跳到哪里
int next = arr[0];
int n = arr.length;
for (int i = 0; i < n; i++) {
if(i > right){
// 需要增加步數(shù)
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));
}
}
- 給定兩個有序數(shù)組arr1和arr2，再給定一個正數(shù)K,求兩個數(shù)累加和最大的前K個，兩個數(shù)必須分別來自arr1和arr2
/**
* 給定兩個有序數(shù)組arr1和arr2，再給定一個正數(shù)K
* 求兩個數(shù)累加和最大的前K個，兩個數(shù)必須分別來自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;
}
}
給定一個正數(shù)數(shù)組arr，返回該數(shù)組能不能分成4個部分，并且每個部分的累加和相等，切分位置的數(shù)不要。
例如:
arr=[3, 2, 4, 1, 4, 9, 5, 10, 1, 2, 2] 返回true
三個切割點下標為2, 5, 7. 切出的四個子數(shù)組為[3,2], [1,4], [5], [1,2,2]，
累加和都是5
package newyangfei.trainingcamq3.day06;
import java.util.HashMap;
/**
* 給定一個正數(shù)數(shù)組arr，返回該數(shù)組能不能分成4個部分，并且每個部分的累加和相等，切分位置的數(shù)不要。
* 例如:
* arr=[3, 2, 4, 1, 4, 9, 5, 10, 1, 2, 2] 返回true
* 三個切割點下標為2, 5, 7. 切出的四個子數(shù)組為[3,2], [1,4], [5], [1,2,2]，
* 累加和都是5
*/
public class CutArray {
public static boolean cutArray(int[] arr){
if(arr == null || arr.length < 7){
// 切成四部分，至少也要七個數(shù)
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的累加和假設(shè)為a，
// 則第二刀的位置的前綴和一定等于a + a + arr[i]
// 第三刀的位置前綴和一定滿足 a+ a+a + arr[i] + arr[i2](第二刀的位置)
// 如果前面都存在，驗證最后一段是否等于a
if(map.containsKey(a) && map.get(a) == i){
// 第一刀存在才繼續(xù)往下，否則枚舉下一個第一刀的位置
// 如果有第二刀，第二刀應(yīng)該滿足的前綴和
int cut2 = 2*a+arr[i];
if(map.containsKey(cut2)){
// 有第二刀才繼續(xù)往下進行切分
// 第三道應(yīng)該滿足
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的交錯組成。實現(xiàn)一個函數(shù)，判斷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的交錯組成。實現(xiàn)一個函數(shù)，判斷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];
}
}
