Chris

3.8 题意为：将一棵二叉树看成一个图，求树上两点之间的距离。距离定义为两点之间边的条数，如下图的二叉树中，节点8和5之间的距离为3。

3.9题意为已知二叉树的前序遍历结果和中序遍历结果，要求重建二叉树。之所以在这里说3.9，是因为解第八题的时候为了处理输入建成二叉树，实现了一个重建二叉树的函数。
Continue reading »

题目是这样的：给定一个正整数N，从1到N一共出现过多少个1？

如N=12，则f(12)=5，因为1,2,3,4,5,6,7,8,9,10,11,12共出现5次“1”。

当年第一次看这个题的时候觉得无从下手，这次到迅速有了思路，还是有进步的嘛。

思路就是分别统计个位、十位、百位…上的1的数目。先考虑个位上的1的数目，个位上的1是每10个数中会出现1次的，即1-10出现一次，11-20出现一次…因此可以计算N/10，对于N%10的部分，只要N%10>=1，就有一个1，也只能有一个1。同理再考虑十位上的1，十位上的1是每100个数字中会出现10次，如1-100出现10次（10-19），101-200出现10次（110-119）…因此可以计算N/100*10，对于N%100的部分，只有在10-19之间会出现1，因此可以分情况讨论。百位上、千位上的情况依此类推，再举一例，说一下千位上的情况吧，对于千位上的1，是每10000个数里出现1000次，例如1-10000里出现1000次（1000-1999），10001-20000里出现1000次（11000-11999）…因此可以计算N/10000*1000，对于N%10000的部分，只有在1000-1999之间会出现千位上的1，同样分情况讨论之。

代码如下：

   1:  __int64 func(__int64 N)

   2:  {

   3:      __int64 onesCount = 0;

   4:      __int64 factor = 10;

   5:      __int64 a,b,c;

   6:      do 

   7:      {

   8:          a = N/factor;

   9:          b = N%factor;

  10:          c = a*(factor/10);

  11:   

  12:          onesCount += c;

  13:   

  14:          if (b >= factor/10)

  15:          {

  16:              if (b > 2*(factor/10) - 1)

  17:              {

  18:                  onesCount += factor/10;

  19:              }

  20:              else

  21:              {

  22:                  onesCount += b - (factor/10) + 1;

  23:              }

  24:          }

  25:          factor *= 10;

  26:      } while (a != 0);

  27:   

  28:      return onesCount;

  29:  }

有一个有意思的现象是，对于N=111…110这样的数，即a个1加一个0组成的数，其f(N)恰好等于连续a个(a+1)，如f(1110)=444，f(11111110)=8888888。以f(1110)=444为例，一共有四位，每一位上的一都是111个，因此f(1110)=444。

扩展问题问到了对于2进制的情况该怎么解答，例如f(11)=100，因为“0,10,11”中共出现了四个1。其实思路是一样的，也是分别考察右侧第一位上出现1的次数、右侧第二位上出现1的次数…以此类推。比如考虑f(11)=f(1011),

1,10,11,100,101,110,111,1000,1001,1010,1011

先考虑第一位上的1（第几位一律从右侧数起），第一位上的1是每两个数出现一次，因此可以先计算11/2=5，然后对于11%2=1的部分，由于等于1，因此出现了一次1，因此第一位上共出现了6次1；再考虑第二位，这一位上是每4个数出现2次1，先计算11/4*2=4，对于11%4=3部分，只有在10-11之间会出现2次1，因此第二位上出现6次1；第三位，(11/8*4)+0=4次，第四位，0+(11-7)=4。因此f(1011)=10100=20。代码就不写了吧。

有些数可以写成连续N（>1）个自然数之和，比如14=2+3+4+5；有些不能，比如8.那么如何判断一个数是否可以写成连续N个自然数之和呢？这是这一节的基本问题。

一个数M若可以写成以a开头的连续n个自然数之和，则M=a+(a+1)+(a+2)+…+(a+n-1)=n*a+n*(n-1)/2，要求a!=0，否则就是以a+1开头的连续n-1个整数了，也就是要求(M-(n+n*(n-1)/2))%n==0，即(M-(n*(n+1)/2))%n==0，这样就很容易判断一个数可不可以写成连续n个自然数的形式了，遍历n=2…sqrt(M)*2，还可以输出所有解。

第二个问题是什么样的数可以写成连续n个自然数之和，什么样的数不能？

通过编程实验发现，除了2^n以外，其余所有数都可以写成该形式。下面说明为什么。

若数M符合条件，则有M=a+(a+1)+(a+2)+…+(a+n-1)=(2*a+n-1)*n/2，而2*a+n-1与n肯定一个为奇数一个为偶数，即M一定要有一个奇数因子，而所有2^n都没有奇数因子，因此肯定不符合条件。

再证明只有M有一个奇数因子，即M!=2^n，M就可以写成连续n个自然数之和。假设M有一个奇数因子a，则M=a*b。

1)若b也是奇数，只要b-(a-1)/2>0，M就可以写成以b-(a-1)/2开头的连续a个自然数；将这条结论里的a和b调换，仍然成立。15=3*5=1+2+3+4+5=4+5+6.

2)若b是偶数，则我们有一个奇数a和一个偶数b。

2.1)若b-(a-1)/2>0，M就可以写成以b-(a-1)/2开头的连续a个自然数。24=3*8=7+8+9.

2.2)若(a+1)/2-b>0，M就可以写成以(a+1)/2-b开头的连续2*b个自然数。38=19*2=8+9+10+11.

上述两个不等式必然至少有一个成立，所以可以证明，只要M有一个奇数因子，就一定可以写成连续n个自然数之和。

第三个问题是，在64位整数范围内，能写成最多种连续n个自然数之和的数是哪个？

对于数M，考察其所有奇数因子，是否满足上述的三个不等式，每满足一个不等式，就可以有一种用连续n个自然数相加将其表示的方法，当然不可能三个都满足，因为b不可能同时为奇数和偶数。