下次自动登录
现在的位置:
& 综合 & 正文
算法习题45：对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一；；；一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
.雅虎：1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
----------------------------------------------------------------------
1：这题我我们自己试着模拟一遍，发现有点类似，扫雷，但是还是有差别的。
我想到了两个制约条件：
（1）某个非零元的值一定小于等于它上下左右的和
（2）整个矩阵的和必须是偶数（因为加1就跟着加另一个1，肯定是偶数）
似乎这两个条件就可以了，难道是必要条件？？？
我想不到从数学上证明，希望有人能给个清晰的答案。
2：这题我们应该逐步分解，
首先是平均分问题，我们可以分成几份呢？当然最多就是每个元素单独出来，所以最多n份；
其次，是不是1--n这么多都可以呢？不是的，必须总和能够整除份数才行
如果现在需要分成m份，而且能够被数组总和整除，那么就可以计算了，
接下来就是一个数组里找出某几个元素和为total/m 的序列了，
这里类似背包，需要用到递归
我这里就引用下面这篇博客了，写得比我整齐多了。。。
#include &cstdio&
#include &cstdlib&
#define NUM 8
int maxShares(int a[], int n);
//aux[i]的值表示数组a中第i个元素分在哪个组,值为0表示未分配
//当前处理的组的现有和 + goal的值 = groupsum
int testShares(int a[], int n, int m, int sum, int groupsum, int aux[], int goal, int groupId);
int main()
//int a[] = {2, 6, 4, 1, 3, 9, 7, 5, 8, 10};
//int a[]={2,2,3,5,6,6};
int a[]={1,1,2,2,3,4,5,6};
//打印数组值
printf("数组的值：");
for (int i = 0; i & NUM; i++)
printf(" %d ", a[i]);
printf("\n可以分配的最大组数为：%d\n", maxShares(a, NUM));
int testShares(int a[], int n, int m, int sum, int groupsum, int aux[], int goal, int groupId)
if (goal & 0)
if (goal == 0)
groupId++;
if (groupId == m+1)
for (int i = 0; i & i++)
if (aux[i] != 0)
aux[i] = groupId;
if (testShares(a, n, m, sum, groupsum, aux, goal-a[i], groupId))
aux[i] = 0;
//a[i]分配失败，将其置为未分配状态
int maxShares(int a[], int n)
int sum = 0;
int *aux = (int *)malloc(sizeof(int) * n);
for (int i = 0; i & i++)
sum += a[i];
for (int m = m &= 2; m--)
if (sum%m != 0)
for (int i = 0; i & i++)
aux[i] = 0;
if (testShares(a, n, m, sum, sum/m, aux, sum/m, 1))
//打印分组情况
printf("\n分组情况：");
for (int i = 0; i & NUM; i++)
printf(" %d ", aux[i]);
free(aux);
aux = NULL;
free(aux);
aux = NULL;
我的思路和上面差不多，不过上面这个方法借助辅助数组aux[]来表示被访问和分配组别这两个信息
这个技巧不错
而我却是用一个数组来记录当前累加的数字，而是否分配过则通过更改原数组值为0来实现
我的思路比较乱。。
#include &iostream&
void Print(int *ans, int index);
void H(int k, int sum, int n, int *arr, int dst, int *ans, int index);
bool H2(int k, int sum, int n, int *arr, int dst, int *ans, int index, int* m);
int main() {
int ans[8];
int index=0;
//每组需要达到的和
int n = 8;//数组元素个数
int total = 24;//这里是数组的总和
for(m=n;m&0;m--){
int test[] = {1,1,2,2,3,4,5,6};
int groupN =
if(total%m == 0)
dst = total/m;
if(test[n-1]&dst)
cout&&"分成"&&m&&"组,"&&"每组和为"&&dst&&
for(i=n-1;i&=0;i--){
ans[0] = test[i];
index = 1;
if(ans[0] == dst){
Print(ans, index);groupN--;
if(ans[0] & dst)
H2(0, ans[0], i, test, dst, ans, index, &groupN);
if(groupN != 0)
cout&&"失败"&&
cout&&"成功"&&
cout&&"***************"&&
* k表示当前访问到第几个元素
* sum表示当前已累加的和
* arr表示原数组
* dst我们需要达到的和
* ans记录答案
* m 用来表示是否分组成功，每成功一组就减一，直至为0则成功
bool H2(int k, int sum, int n, int *arr, int dst, int *ans, int index, int* m){
for(;i&n;i++){
if(arr[i] == 0)
int temp = sum + arr[i];
if(temp&dst){
ans[index++] = arr[i];
arr[i] = 0;
if(!H2(i+1, temp, n, arr, dst, ans, index,m))
arr[i] = ans[index];
else if(temp == dst){
ans[index++] = arr[i];
arr[i] = 0;
Print(ans, index);
void Print(int *ans, int index){
int i = 0;
for(i=0;i&i++)
cout&&ans[i]&&" ";
我是打印出所有结果
分成4组，每组和为6
***************
分成3组，每组和为8
***************
分成2组，每组和为12
***************
分成1组，每组和为24
6 1 1 2 2 3 4 5
***************
还是比较喜欢上面他的做法，这种记录方式很清晰
&&&&推荐文章:
【上篇】【下篇】2015年3月 总版技术专家分月排行榜第二2014年12月 总版技术专家分月排行榜第二2014年9月 总版技术专家分月排行榜第二
2015年3月 .NET技术大版内专家分月排行榜第一2015年2月 .NET技术大版内专家分月排行榜第一2015年1月 .NET技术大版内专家分月排行榜第一2014年12月 .NET技术大版内专家分月排行榜第一2014年11月 .NET技术大版内专家分月排行榜第一
2015年3月 总版技术专家分月排行榜第二2014年12月 总版技术专家分月排行榜第二2014年9月 总版技术专家分月排行榜第二
2015年3月 .NET技术大版内专家分月排行榜第一2015年2月 .NET技术大版内专家分月排行榜第一2015年1月 .NET技术大版内专家分月排行榜第一2014年12月 .NET技术大版内专家分月排行榜第一2014年11月 .NET技术大版内专家分月排行榜第一
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。import java.util.*;
public class Solution {
* 1、只删除3个元素，等分为四份。
* 2、数组元素为正整数。
* 3、疑问：后面又说整数取值范围介于-1,000,000到1,000,000之间？明显混淆视听，看来阿里的题考查阅读与观察啊！
* 方法一：
* 1、先二等分，去除中间那个元素。至少中间左边还是右边有待考证
*此方法有bug
* indexBegin开始索引，indexEnd结束索引。
* 在sumArr,与chooseRemove中均计算的是indexBegin&=i&indexEnd的元素。
* 元素分布：0至v1-1,v1+1到v2-1,v2+1到N-1
/**测试用例：
* {1,1,1,1,7,1,3,4,1,2,1,5,2,2}把7换成10，把4换成1，原式也可等分，但却如下
* {1,1,1,1,10,1,3,1,1,2,1,5,2,2}
* {2,2,5,1,2,1,1,3,1,10,1,1,1,1}上面的倒序。看来与顺序无关，算法还是存在问题，此种解法存在问题。
//方法二**********************************************
* 从两边开始找，找到之后再找中间
* 技巧，注意到只删除3个元素，又因为要第一分组与第四分组相等.
* 设等分值为v,第一分组n1与第二分组元素n4个数共为n,则2&=N-3-n&=2v;
* 此方问题，能够解决方法一的问题*/
static boolean resolve2(int[] A) {
int[] re=findValLocate(A);
System.out.println(&寻找完毕，开始检查: &+Arrays.toString(re));
re[2]=checkingFind(A,re[0],re[1]+1,re[3]-1); //减1是由于有4部分，最后一部分至少占用1个位置。
System.out.println(&检查: &+Arrays.toString(re));
int v3=checkingFind(A,re[0],re[2]+1,re[3]);//检查第四部分，的分割点是否为re[3]
if(v3==re[3]){
static int checkingFind(int[] A ,int val,int begin,int end){
for(int i=i&++i){
if(s==val){
//返回要去除那个点。
return i+1;
return -1;
/*返回均分值，与要去除的第一个和第三个位置*/
static int[] findValLocate(int[] A){
int v1=0,v4=0;
for(int i=0,j=A.length-1;i&j;){
if(v1&v4){
v1=v1+A[i];
}else if(v1&v4){
v4=v4+A[j];
/*验证：2&=N-3-n&=2v*/
int m=A.length-3-(i+1+A.length-j);
if(m&=2 && m&=2*v1 ){
/*这里返回的是去除点的位置，i,j没有加减，
是因为以前的操作都让它向后移了一位了，
现在指的就是要去除的点*/
int re[]={v1,i,0,j};
v1=v1+A[i];
//方法二结束**********************************************
//方法一（此方有问题）**********************************************
static boolean resolve(int[] A) {
int v2=chooseRemove(A,0,A.length-1);
int v1=chooseRemove(A,0,v2-1);
int v3=chooseRemove(A,v2+1,A.length-1);
int s1=sumArr(A,0,v1-1);
int s2=sumArr(A,v1+1,v2-1);
int s3=sumArr(A,v2+1,v3-1);
int s4=sumArr(A,v3+1,A.length-1);
System.out.println(&去除的元素依次是：A[&+v1+&]=&+A[v1]+& ; &
+&A[&+v2+&]=&+A[v2]+& ; &
+&A[&+v3+&]=&+A[v3]+& ; &);
System.out.println(&四个部分和是：&+&s1=&+s1+& ; &
+&s2=&+s2+& ; &
+&s3=&+s3+& ; &
+&s4=&+s4+& ; &);
if(s1==s2&&s3==s4&&s2==s3){
static int sumArr(int[] A, int indexBegin, int indexEnd){
int sum=0;
for(int i=indexB i&=indexE++i){
sum =sum +A[i];
static int chooseRemove(int[] A, int indexBegin, int indexEnd){
int ave=sumArr(A,indexBegin,indexEnd)/2;
int val=0;
for(int i=indexBi&=indexE++i){
val=val+A[i];
if(val&ave){
return -1;
//方法一结束**********************************************
public static void main(String[] args){
/*ArrayList&Integer& inputs = new ArrayList&Integer&();
Scanner in = new Scanner(System.in);
String line = in.nextLine();
while(line != null && !line.isEmpty()) {
int value = Integer.parseInt(line.trim());
if(value == 0)
inputs.add(value);
line = in.nextLine();
int[] A = new int[inputs.size()];
for(int i=0; i&inputs.size(); i++) {
A[i] = inputs.get(i).intValue();
//int[] A={1,1,1,1,7,1,3,4,1,2,1,5,2,2};
int[] A={1,1,1,1,10,1,3,1,1,2,1,5,2,2};
Boolean res = resolve2(A);
System.out.println(String.valueOf(res));
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：11273次
积分：1953
积分：1953
排名：第16888名
原创：187篇
(2)(7)(7)(3)(8)(12)(52)(72)(27)(2)}