求和为aim的最长子数组
//
// mosteor.cpp
// AdvancedFour
//
// Created by 吴珝君 on 2019/5/23.
// Copyright © 2019年 闲着也是贤者. All rights reserved.
//
#include "mosteor.hpp"
#include <iostream>
#include <vector>
#include <map>
using namespace std;
/*
求数组异或和的最多划分: 这个问题的本质还是求和为aim值的子数组的问题
当一个数来了之后，我需要判断，将其加进来使其构成新的划分得到了划分数量最多
还是抛弃这个数，利用前面 i -1个数得到的划分多。
*/
class Solution
{
public:
vector<int> mostEor(vector<int> arr)
{
vector<int> res;
int *newarr = new int[arr.size()];
fill(newarr, newarr+arr.size(), 0);
for (int i = 0; i < arr.size(); i++) {
if (arr[i]%2 ==0) {
newarr[i] = -1;
}
else
newarr[i] = 1;
}
//求和为0的最长子数组
int start = -1;
int end = -1;
map<int, int> m;//存值和坐标
int sum = 0;
for (int i = 0; i < arr.size(); i++)
{
sum +=newarr[i];
if (m.count(sum) == 1)
{
if (end - start < i -m.find(sum)->second)
{
start = m.find(sum)->second;
end = i;
cout << "最优划分 " << start <<" " <<end<<endl;
}
}
else
{
m.insert(pair<int, int>(sum,i));
}
}
for (int i = start; i <end; i++) {
res.push_back(arr[i+1]);
}
return res;
}
};
int main()
{
vector<int> arr;
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++) {
arr.push_back(i+ rand()P);
cout <<arr[i] <<" ";
}
cout <<endl;
// int k = rand()0 +100;
// cout <<"aim :"<<k <<endl;
Solution s;
arr = s.mostEor(arr);
for (int i = 0; i < arr.size(); i++) {
cout <<arr[i]%2 << endl;
}
return 0;
}
扩展问题：
求奇数和偶数个数相等的最长子数组
//
// mosteor.cpp
// AdvancedFour
//
// Created by 吴珝君 on 2019/5/23.
// Copyright © 2019年 闲着也是贤者. All rights reserved.
//
#include "mosteor.hpp"
#include <iostream>
#include <vector>
#include <map>
using namespace std;
/*
求数组异或和的最多划分: 这个问题的本质还是求和为aim值的子数组的问题
当一个数来了之后，我需要判断，将其加进来使其构成新的划分得到了划分数量最多
还是抛弃这个数，利用前面 i -1个数得到的划分多。
*/
class Solution
{
public:
vector<int> mostEor(vector<int> arr)
{
vector<int> res;
int *newarr = new int[arr.size()];
fill(newarr, newarr+arr.size(), 0);
for (int i = 0; i < arr.size(); i++) {
if (arr[i]%2 ==0) {
newarr[i] = -1;
}
else
newarr[i] = 1;
}
//求和为0的最长子数组
int start = -1;
int end = -1;
map<int, int> m;//存值和坐标
int sum = 0;
for (int i = 0; i < arr.size(); i++)
{
sum +=newarr[i];
if (m.count(sum) == 1)
{
if (end - start < i -m.find(sum)->second)
{
start = m.find(sum)->second;
end = i;
cout << "最优划分 " << start <<" " <<end<<endl;
}
}
else
{
m.insert(pair<int, int>(sum,i));
}
}
for (int i = start; i <end; i++) {
res.push_back(arr[i+1]);
}
return res;
}
};
int main()
{
vector<int> arr;
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++) {
arr.push_back(i+ rand()P);
cout <<arr[i] <<" ";
}
cout <<endl;
// int k = rand()0 +100;
// cout <<"aim :"<<k <<endl;
Solution s;
arr = s.mostEor(arr);
for (int i = 0; i < arr.size(); i++) {
cout <<arr[i]%2 << endl;
}
return 0;
}
扩展问题：
求子数组异或和为0的最多划分
//
// mosteor.cpp
// AdvancedFour
//
// Created by 吴珝君 on 2019/5/23.
// Copyright © 2019年 闲着也是贤者. All rights reserved.
//
#include "mosteor.hpp"
#include <iostream>
#include <vector>
#include <map>
using namespace std;
/*
求数组异或和的最多划分: 这个问题的本质还是求和为aim值的子数组的问题
当一个数来了之后，我需要判断，将其加进来使其构成新的划分得到了划分数量最多
还是抛弃这个数，利用前面 i -1个数得到的划分多。
*/
class Solution
{
public:
int mostEor(vector<int> arr)
{
if(arr.size() == 0)
return 0;
int xors =0;
map<int, int> m;
int dp[1000] = {0};
if (arr[0] == 0)
{
dp[0] = 1;
}
m.insert(pair<int, int>(arr[0],0));
m[xors] = arr[0];
for (int i = 1; i < arr.size(); i++) {
xors ^=arr[i];
//如果有这样的划分
if (m.count(xors))//
{
int l = dp[m.find(xors)->second] +1;
int r = dp[i - 1];
dp[i] = (l > r ? l : r);
}
else
{
dp[i] = dp[i - 1];
}
m[xors] = i;
}
return dp[arr.size()-1];
}
};
/*
int main()
{
vector<int> arr;
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++) {
arr.push_back(i+ rand());
cout <<arr[i] <<" ";
}
cout <<endl;
Solution s;
int count = s.mostEor(arr);
cout <<count<<endl;
return 0;
}*/
