有序数组生成高度最小的二叉搜索树

发表于 2016-03-31 分类于计算机，算法 Disqus：

给一个有序的数组，升序，没有重复的数字，生成一个高度最小的二叉搜索树。

二叉搜索树具有的特点就是左边节点的值比当前节点的小，右边节点的值比当前节点的大。而一个有序数组，恰恰是二叉搜索树的中序遍历结果。
扯了点没用的，想要高度低，就要尽可能的平衡，左右两个子树尽可能的平衡，那么，数组中间的数就是根节点了。左边的树就是数组中间左边的半个数组组成的，右边的树就是数组右边的半个数组组成的。这一段描述，是一个递归的过程，按照这个思路，代码也就有了。

class TreeNode<T>
{
	public TreeNode<T> Left { get; set; }
	public TreeNode<T> Right { get; set; }
	public T Data { get; set; }
}

static TreeNode<T> CreateMinimalBst<T>(T[] arr, int begin, int end)
{
	if (begin > end)
	{
		return null;
	}

	int mid = (end - begin) / 2 + begin;
	var node = new TreeNode<T>();
	node.Data = arr[mid];
	node.Left = CreateMinimalBst(arr, begin, mid - 1);
	node.Right = CreateMinimalBst(arr, mid + 1, end);

	return node;
}

static TreeNode<T> CreateMinimalBst<T>(T[] arr)
{
	return CreateMinimalBst(arr, 0, arr.Length - 1);
}

O(n)的时间复杂度就搞定了这个题目，空间复杂度呢？表面看来，没有使用额外的存储空间，但是递归导致栈空间的增长，O(lg(n))。

找出缺少的那个数字

发表于 2016-03-25 分类于计算机，算法 Disqus：

给一个文件，里面包含40亿个非负数字，但是有某个非负整数不再里面，提供一种算法，输出文件不包含的非负数字，假设我们有1GB内存可以用。
更进一步，假设数字不重复，但是内存只有1MB可以用，又该如何处理呢？

非负整数只有2^31个那么多，1GB内存，对应有8*2^31位，比2^31大多了，那么可以用这些bit位标识该数字是否出现了。思路很简单，创建一个足够大的bit向量来放所有的非负整数，把每一位都清为0；然后开始扫描文件，把对应位置的bit标记为1；遍历bit向量，遇到0说明对应的数字没有在文件中出现过，就打印出来。

下面是代码，需要注意的是，算bit位数的时候，int最大值加1会溢出成int最小值，所以需要转成long再加1。

static void PrintNotContainedNumber()
{
	long count = (long)int.MaxValue + 1;
	byte[] bits = new byte[count / 8];
	using (var reader = new StreamReader("file.txt"))
	{
		while (!reader.EndOfStream)
		{
			int number = int.Parse(reader.ReadLine());
			bits[number / 8] |= (byte)(1 << (number % 8));
		}
	}

	for (int i = 0; i < bits.Length; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if ((bits[i] & 1 << j) == 0)
			{
				Console.WriteLine(i * 8 + j);
			}
		}
	}
}

现在考虑更进一步的问题，内存有限，该怎么办？《编程珠玑》里面有介绍这种情况，两次扫描法。
第一次扫描，我们搞一个数组，比如大小为ArraySize，那么共2^31个数，第一个数组记录0到2^31/ArraySize - 1数字出现的次数，第二个数组记录2^31/ArraySize到2^31/ArraySize*2-1数字出现的次数，以此类推。
我们定义RangeSize = 2^31/ArraySize，如果数字没少的话，数组的每个元素都应该是RangeSize。但是少了一个数字，那么某个元素就是RangeSize-1，那么就可以确定那个少了的数字的范围。
第二次扫描，我们搞一个RangeSize bit的向量，用于标识上一步确定的范围数字是否出现了。
最后，该bit向量有一位是0，就是缺少的那个数字。

我们如何确定ArraySize呢？只有10MB，那么ArraySize * 4 < 2^23 < 10 * 2^20，所以ArraySize < 2^21。RangeSize < 2^26 < 8 * 10 * 2^20，ArraySize=2^31/Range>2^11。综上，ArraySize的大小可选范围还是挺大的。

下面是实现的代码

static int ArraySize = 4096; // 2 ^ 12
static int RangeSize = 524288; // 2 ^ 19
static void PrintNotContainedNumber()
{
	int[] blocks = new int[ArraySize];
	using (var reader = new StreamReader("file.txt"))
	{
		int number = int.Parse(reader.ReadLine());
		blocks[number / RangeSize]++;
	}

	int starting = 0;
	for (int i = 0; i < ArraySize; i++)
	{
		if (blocks[i] < RangeSize)
		{
			starting = i * RangeSize;
			break;
		}
	}

	byte[] bits = new byte[RangeSize / 8];
	using (var reader = new StreamReader("file.txt"))
	{
		int number = int.Parse(reader.ReadLine());
		if (number >= starting && number < starting + RangeSize)
		{
			bits[number / 8] |= (byte)(1 << ((number - starting) % 8));
		}
	}

	for (int i = 0; i < bits.Length; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if ((bits[i] & 1 << j) == 0)
			{
				Console.WriteLine(i * 8 + j + starting);
				return;
			}
		}
	}
}

如果内存更小，比如10KB，该怎么办呢？那么可能需要三次扫描，第一次range给到千万，看到底是第几千万少了一个数字，第二次确定这个千万里面，哪一万少了一个数字，第三次再确定最终的数字。思路是一样的。

找一条通路从点0,0到点X,Y

发表于 2016-03-20 分类于计算机，算法 Disqus：

一个X * Y的矩阵，机器人只能往右走或者往下走，从点(0,0)到点(X,Y)，一共有多少种通路呢？
增加一点难度，假设有些点是不能走的，那么应该如何设计算法来找到一条可能的通路呢？

第一个问题其实很简单，就是从X+Y这么多步数中选择X步往右走，即可。C(X+Y, X) = (X+Y)!/(X!Y!)。

如果找到这条通路呢？其实有没有不可走的点，差距不是很大，就是在判断往哪个方向走的时候增加一个条件判断就好了。还有一个大一点的区别，就是某些点不能走，导致从(0,0)点无法到达一部分点。
现在我们分析一下思路，怎么走到点(X,Y)呢？如果到了(X, Y-1)或者是(X-1,Y)，那么再走一步就能到(X,Y)了。我们问题变成了，找到一条到达(X, Y-1)或(X-1,Y)的路径。
如何到(X, Y-1)呢？再往前想一步，找一条到(X-1,Y-1)或者是(X,Y-2)的路径即可。
如何到(X-1, Y)呢？那么先找到一条到(X-1,Y-1)或者是(X-2,Y)的路径即可。
总体来说，就是一个递归算法。

仔细想一下，上述的递归算法，都需要计算到(X-1,Y-1)点的路径，那么，我们可以考虑把这个结果缓存起来，第二次使用的时候，就不用再次递归计算了。
具体到这个题目，只需要缓存从(0,0)能否到点(M,N)即可。

struct Point
{
    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }

    public int X { get; set; }
    public int Y { get; set; }
}

static bool GetPath(int x, int y, List<Point> path, Dictionary<Point, bool> cache)
{
    Point point = new Point(x, y);
    if (cache.ContainsKey(point))
    {
        // Already visited this cell
        return cache[point];
    }

    if (x == 0 && y == 0)
    {
        // found a path
        return true;
    }

    bool success = false;

    // Try left
    if (x >= 1 && IsFree(x - 1, y))
    {
        success = GetPath(x - 1, y, path, cache);
    }

    // Try up
    if (!success && y >= 1 && IsFree(x, y - 1))
    {
        success = GetPath(x, y - 1, path, cache);
    }

    if (success)
    {
        // Right way! Add to path
        path.Add(point);
    }

    // Cache result
    cache.Add(point, success);

    return success;
}

private static bool IsFree(int x, int y)
{
    return !(x == 0 && y == 1
           || x == 0 && y == 2
           || x == 1 && y == 2
           || x == 2 && y == 2);
}

二叉树是平衡的吗？

发表于 2016-03-14 分类于计算机，算法 Disqus：

给定一个二叉树，判断其是否平衡。平衡的定义是，从任何一个节点去考虑，它的左子树和右子数的高度差不超过1。

很明显，需要一个递归函数来做这个事情。
如果这个函数返回树高度，判断是否平衡，再去递归调用这个函数去判断左右子树是否平衡，这显然是一个解，但是略微暴力了一点。因为递归左右子树时，又要计算其左右子树的高度，而之前以前计算过了，很明显的有着重复的部分。
给定了根节点，想直接自底向上计算，也不是一件容易的事情。

我们稍稍改造一下返回高度的函数，如果其左右子树平衡，才返回高度，否则返回-1，这样子，程序的递归性就自然而然的帮我们自底向上进行判断每个节点处是否平衡了。

下面的代码定义了一个树节点的数据结构，CheckHeight函数就是上面说的函数了，最后，计算平衡就是把根节点传入，检查返回值是否等于-1。

class TreeNode
{
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }
}

static int CheckHeight(TreeNode node)
{
    if (node == null)
    {
        return 0; // Empty
    }

    int leftHeight = CheckHeight(node.Left);
    if (leftHeight == -1)
    {
        return -1; // Not balanced
    }

    int rightHeight = CheckHeight(node.Right);
    if (rightHeight == -1)
    {
        return -1; // Not balanced
    }

    /* Check if current node is balanced. */
    int diff = Math.Abs(leftHeight - rightHeight);
    if (diff &gt; 1)
    {
        return -1; // Not balanced
    }
    else
    {
        return Math.Max(leftHeight, rightHeight) + 1; // Return height
    }
}

bool IsBalance(TreeNode root)
{
    return CheckHeight(root) != -1;
}

算法的时间复杂度是O(N)，只需要遍历每个节点一次。
空间复杂度是O(H)，H是树的高度，就是在递归过程中，最深就是H层罢了，每层需要常量空间去保存节点相关的信息。

不使用额外的数据结构对栈元素进行排序

发表于 2016-03-12 分类于计算机，算法 Disqus：

按照升序对栈进行排序，也就是说，最大元素在栈顶。最多只能使用一个额外的栈来存放临时数据，但是不能使用额外的数据结构，比如数组来保存临时数据。严格要求只能使用O(1)的额外临时空间外加一个O(n)的栈。

假设我们待排序的栈是s1，额外有一个栈s2，s1是无序的，s2是有序的。
考察s1栈顶的元素，pop出来放到临时变量tmp里面，peek s2的栈顶元素，和tmp进行比较，如果比tmp大，那么就pop出来并且push到s1里面，循环，直到s2的栈顶比tmp，然后把tmp push到s2里面，至此，s1里面的tmp按照顺序进入到了s2中。外层再来一层循环，对s1的每个元素进行同样的处理。

static Stack<int> Sort(Stack<int> s)
{
    var result = new Stack<int>();

    while (s.Count != 0)
    {
        var tmp = s.Pop();
        while (result.Count != 0 && result.Peek() > tmp)
        {
            s.Push(result.Pop());
        }
        result.Push(tmp);
    }

    return result;
}

这个算法的时间复杂度是O(n^2)，空间复杂度是O(n)，用了一个额外的栈，再有就只有了一个临时变量存放数据。

黑客与画家 | 小记

发表于 2016-03-08 分类于阅读，心得 Disqus：

这是一本散文集。

为什么书呆子不受欢迎
在不考虑欺负他人的较为受欢迎的孩子所需要的社会认同感的前提下，就自身而言，书呆子把精力放在了其他地方，比如对智力的追求上。人的精力是有限的，显然，多一份精力去保持受欢迎，就会少一份精力去发展智力。书呆子选择了后者。不过，有少数的人能够兼顾两者。
在某些时候，书呆子在用成人的思维活在了青少年这个层次上，导致从某些角度上看，书呆子格格不入，但是一工作，进入成人的世界，貌似他们还挺受欢迎的。
作者还扯了一些事情来描述他所认为的扭曲的世界，主要观点就是这个扭曲的世界造就了叛逆的青少年。

黑客与画家
书的第二章，从书名感觉，这是最中心的一章？不确定。
黑客，与画家一样，是创作东西的人。创造性的工作导致了考核的困难，难道用代码行数去考核一个黑客的工作量吗？
相比他人误解自己的工作，更可怕的事情是自己误解自己的工作。其实作为所谓的软件工程师，日常工作和“计算理论”相去甚远，工作中我们要解决的是实际问题，而不是研究。和之前看到的一句话类似，加了science的都不是真正的science，计算机科学与技术，进入到软件工程师这个领域，就和科学没太大关系了。不过，这并不妨碍我在业余时间搞些“理论”或者和自然科学接近的东西。
大公司的工程师其实和技术工人没啥区别，说白了就是匠人。不过感觉作者在这里说的有点极端了。
黑客，作为创作者，和软件工程师是不一样的，但是创作东西很难，养活自己也难，怎么办呢？找一个day job。这个短暂的寒假，在家里做了点事，也思考了很多，发现自己更喜欢智力上的思考，比如考虑下Project Euler上的题目，学学数学物理啥的，如是而已。我是不是也应该找一个按时上下班的day job呢？
画家想要提高技术，实践，多画；再就是模仿，临摹；先框架，再细节，但是填充细节的时候不是简单的填充，可能涉及修改一开始的构想。黑客，想要提到技术，无它，也就这三条，多写代码；学习开源的东西，试着造自己的轮子；重构，对代码要有追求。
黑客，要想作出一个好的艺术品，要学会换位思考。产品级，设身处地的从用户角度着想，他们可能什么也不懂；代码级，除了写，还要读，要精益求精。
黑客能够流芳百世呢？和画家一样，交给时间去评判吧。

不能说的话
别人告诉你，如果你不认同社会，那么肯定是你自己的问题。你同意这种说法吗？事实上，它不仅不对，而且会让历史倒退。这让我想到在百度看到一条标语，robin说过，如果别人说你错了，那肯定是你错了，你要想办法改正自己的错误，解决问题。呵呵哒。
什么话不能说呢？看似胡扯、大逆不道的话，但会让人思考的话，这句话是不是真的呢？在很多场合，真话，不能说。
作者还提到了一种方法去看什么话不能说，就是机制，看看禁忌是如何产生的，为什么会有这些禁忌。
自由地思考，比畅所欲言更重要。守口如瓶，看似愚钝，其实也有很多好处，至少不会让你和一个SB争论而使得自己无法理智的思考；缺点是无法和别人交流。破解之道，和能说话的人说即可。还有些方法，比如幽默，隐喻，这些相比第一个，少难些。
如果自己就是潮水的一部分，怎么能看见潮流的方向呢？你只能永远保持质疑。问自己，什么话是我不能说的？为什么？

良好的坏习惯
黑客的天性就是不服从管教，自由，还有些自负。

另一条路
作者起到了一种用户使用软件的新方式，其实就跟现在的云计算有点类似，大概相当于saas，有些相当于paas。还有一个事情，他提到了新的敏捷型的互联网的开发模式。作者完成这本书已经有很长的时间了。书中提到的很多很多开发模式上线模式维护模式现在在互联网公司都被使用着。书里面还提到了收费模式就是现在比较流行的订阅模式而不是传统软件买一个版本。一般来说，用户每次只需要支付一点点钱就能使用一段时间，然后再付费就继续使用，期间可能有版本的升级，但是这是用户买的服务，使用它就好了。书中还描绘了一种和客户、用户很近的工作模式，这也是现在开发的所提倡的，但是不管是在微软工作还是在百度工作，这种我理想中的工作模式都很远，也不能说很远吧，比较远。
书中写了未来是互联网的，不过作者写这本书有一段距离时间了，互联网火了之后又出现了移动互联网，但是现在的移动互联网和当年的桌面应用没有区别，安装app/软件这种形式。所以。我觉得，手机端的发展或者说以后的某种可移动的电子设备又或者是现在流行的虚拟现实交织的输出输入设备，应该和现在互联网这种模式类似，web就足够了，而不是app。

如何创造财富
多干活，多挣钱，这是基本定律。创业，压缩一切可工作的时间，提高效率，可以挣更多的钱。
创业这事，除了聪明、勤奋，还需要运气。大公司的问题是无法测量每一个人的贡献值，多数都是平均主义。由此反推导致大公司的员工中有很多人也不会100%的努力工作。举个例子，100个人划一艘大船，努力被平均，反馈也差些，看不到船到底增速多少，偷懒亦是如此。而创业公司就像是三五个人划船，情况就不同了。每个人的努力都基本上会被真实反馈，说白了，努力可测量性大大提成。创业，从整个社会而言，回报是等于付出的，但是，那是一个平均值，多数人，或者说是绝大多数人，都没有回报，极少数人获得了极高的回报。

关于贫富分化
作者讲了挺多经济学的基础，比如财富、分工、共赢、用财富去创造财富等等。技术的发展，某种意义上缩小了穷人和富人的差距，现在多数人都能有手机、计算机、洗衣机、电视机，而以前，穷人和富人的差别是有无的区别，而现在，只是质量不同品牌不同，甚至没有差别，富人也不过是使用iPhone罢了。什么被扩大了呢？钱的数量，技术往往有扛杆作用，使得资本成多项式的发展。

防止垃圾邮件的一种方法
作者使用的方法就是贝叶斯统计法加上白名单，能够高效的过滤垃圾邮件。不过，现在垃圾邮件是少多了。如果越来越少，那么商家发送垃圾邮件的成本，比成本还大以致于无利可图的时候，或许，就没有垃圾邮件了。

设计者的品味
人们对美的追求，很多时候是一致的。数学家、物理学家、艺术家、画家、作曲家、建筑师等等，对美的追求有很多相似之处。作者解释了好的设计是什么样子的设计。是简单的设计，数学公式，往往很简单，但很优美；是永不过时的设计，比如那些美的数学定理；是解决问题的设计，田字形的出风口，控制器设计成田字形的，显然简单易懂，很美；是启发性的设计，比如软件，以模块的形式提供给用户，他们可以像乐高积木一样任意组合；通常是有趣的设计，不是所有的设计都很有趣，但是毫无趣味的设计很难是好的设计；是艰苦的设计，这里的艰苦指的是向前冲刺的艰苦，而不是那种无谓的艰苦；是看似容易的设计，冠军往往看似容易的胜利，背后往往有着艰苦的训练；是对称的设计，对称，多数时候就是重复和递归；是模仿大自然的设计，嗯，法自然；是一种再设计；是能够复制的设计，先模仿，再创造，在复制去解决问题，这是一个否定之否定的过程；往往是奇特的设计，不过奇特，是无法培育的；是成批出现的，让很多有天赋的人聚在一起，共同解决某个难题，互相激励；常常是大胆的设计，颠覆过去的设计，前提是深入地理解过去的设计。

编程语言解析
作者扯了很多语言梗和很多编程语言之争的点。我只能说，PHP是世界上最好的语言，虽然我并不用它，也不喜欢它。

一百年后的语言
对作者的一个观点很赞同，硬件在高速发展，但是新出的编程语言在肆无忌惮的浪费它们。现在，很多场景需要的是提高程序员的效率。作者想要的是内核很小的编程语言，比如字符串和普通数组，甚至和列表相比没有太多区别，整数也可以在语法层面表示成列表，至于字符串优化，整数运算优化，那是编译器的事情。编程语言的发展和现在软件的发展类似，层次越来越多，抽象程度越来越高，速度也相应越来越慢，人们更多的是在最上层解决实际中的问题。

拒绝平庸
先闲扯一句，看到作者说真正的黑客应该学习Lisp，挺开心，我就在学习Scheme，对我的编程思维、思考问题的方式的影响真的很大很大，就像作者说的那样，也许它不会对我找工作升职加薪有太多直接的帮助，但是训练思维，能更好的前进。
看了秘密武器一节，作者已经连续三章说明Lisp的好了，作者是真心喜欢这门语言。Lisp很强大，但是大家为什么不使用呢？语言强大的偏序曲线上，任何一级的程序员都可能会鄙视底层的语言，但是不关心上层的语言，因为多数时候，多数人，他们的思维长期被一种类型的语言束缚住了，不太会换语言。从公司层面考虑，问题就更多了。

书呆子的复仇
顶级书呆子和他的学生，搞出了抽象层次极高的Lisp函数，作者又花了一章来说明它的好，不过，看了作者举得例子，都说明这么语言表达能力是极强的。这能更好的激励我把SICP看完哈哈。
题目中包含复仇，让我想到《荒野猎人》里的一句话，复仇这种事情还是交给上帝吧。或许，那个顶级书呆子就是上帝的杰作。

梦寐以求的编程语言
简单的总结下作者想要的语言，我觉得这也是很多程序员的想法。首先抽象层次要高，互动性好；普遍的问题有现成的库函数可以用，语言核心很小，配套的类库很强大，而且这些类库精心设计，正交，组合起来能够很好的协同工作。语言的句法很简短，少敲字。抽象层次高，很快的写出原型，需要优化的时候，有个很好的性能分析器用，但是我觉得性能分析器不是语言的一部分，而是一个附属工具，不过，这个工具真心很重要。语言的设计更符合直觉，手册简单清晰，例外或者限制很少。语言本身也是分层次的，可以直接使用较高抽象的部分，但是如果需要，也能直接操作低层次的抽象，我觉得这一点挺难的。最后就是源码开放，设计也是开放的，黑客们都有机会去设计属于自己的语言。

设计与研究
设计追求的是好，研究追求的是新。设计是为了用户的需求，而不是他们的要求，区别之间的差异很重要的。
作者扯了下原型和产品的联系，他说他写代码，一个小时之后就能看到运行结果，更鼓舞士气，再继续前进，这和我的习惯差不多，实在无法忍受那种写了半天，不知道程序到底能跑出什么的感觉。

欧拉项目 | 500题 | 因数个数问题

发表于 2016-02-06 分类于数学，欧拉项目 Disqus：

这是欧拉项目的第五百个题目，原题链接

题目描述很简单，120个有16个因数，是最小的拥有16个因数的数字。求最小有2 ^ 500500个因数的数字，因为这个值相当大，要求给出模500500507的结果。

首先，我们要明白，如何求一个数有多少个因数？
这里需要用到Euler’s totient function，这里不得不提一句，出题人很用心，第500题，一个有里程碑意义的题目，需要用到Euler本人的研究成果。

根据这个定理，把前500500个质数相乘，那个数字就有2的500500次方个因数。但是肯定不是最小的，因为当前2出现了一次，对因数的个数贡献是2的1次方，那么再乘以2个2，2的次数是3次，对因数的贡献是2的平方，那么不用乘以第500500个质数，就能使得因数个数是2的500500次方，显然后面比较小，这是第一个数字乘以第500500个质数，再除以4。要让2的贡献再过一次方，达到2的3次方，那么需要再多4个2，使得有7个2，显然4个2比第500504个质数小很多。就这样子继续下去。然后继续考虑3、5、7等等。

Wolfram Alpha理论会告诉我们一些关于质数次方的定理，能够知道每个质数都出现多少次，贡献多少个2的次方。

大致思路如下，具体的看代码吧。

const long mod = 500500507;
long answer = 1;
var primes = Utils.GenPrimes(8000000).ToList();

for (int i = 0; i < 500084; i++)
{
	answer *= primes[i];
	answer %= mod;
}

for (int i = 0; i < 396; i++)
{
	answer *= (long)Utils.Pow((int)primes[i], 2);
	answer %= mod;

}

for (int i = 0; i < 15; i++)
{
	answer *= (long)Utils.Pow((int)primes[i], 4);
	answer %= mod;
}

for (int i = 0; i < 4; i++)
{
	answer *= (long)Utils.Pow((int)primes[i], 8);
	answer %= mod;
}

answer *= (long)Utils.Pow((int)primes[0], 16);

return answer % mod;

欧拉项目 | 82题 | 三方向的最小和路径

发表于 2016-02-03 分类于计算机，算法 Disqus：

原题链接

从矩阵的左边一行的任意一个元素开始，可以往上、往下、往右前进，到达最右边的某个元素为止。由此形成了一条路径，要求使得该路径上的数字之和最小。

题中的5 * 5的矩阵可以用于测试和debug，最后要求给出答案的是一个80 * 80的矩阵。

这是一道典型的动态规划题目。

初始化一个80 * 80的二维数组用于保存结果。第一列就是矩阵的第一列。

然后从j - 1列向j列前进。
考虑第i行，可以是从j - 1列的任何一个位置k向上或者向下到达第i行，然后向右平移过来，选择和最小的记录在第j列第i行。
三层循环，将80 * 80的二维数组填满。

最后要的最小路径和就是最后一列值最小的一个数字。
整个题目不难，代码如下：

long[,] sums = new long[dim, dim];

for (int i = 0; i < dim; i++)
{
	sums[i, 0] = matrix[i, 0];
}

for (int j = 1; j < dim; j++)
{
	// from column j-1 to column j
	for (int i = 0; i < dim; i++)
	{
		// consider row i
		long min = long.MaxValue;
		for (int k = 0; k < dim; k++)
		{
			long temp = sums[k, j - 1] + matrix[i, j];
			int begin = 0;
			int end = 0;
			if (k < i)
			{
				begin = k + 1;
				end = i;
			}
			else
			{
				begin = i;
				end = k - 1;
			}
			for (int index = begin; index <= end; index++)
			{
				temp += matrix[index, j - 1];
			}

			if (temp < min)
			{
				min = temp;
			}
		}

		sums[i, j] = min;
	}
}

var lastColumn = new List<long>();
for (int i = 0; i < dim; i++)
{
	lastColumn.Add(sums[i, dim - 1]);
}

return lastColumn.Min();

欧拉项目 | 504题 | 多少个四边形包含平方个数目的点？

发表于 2016-02-01 分类于数学，欧拉项目 Disqus：

原题链接

四边形ABCD，各点位于四个坐标轴上，坐标分别是A(a, 0), B(0, b), C(−c, 0), D(0, −d)，其中1 ≤ a, b, c, d ≤ m 并且a, b, c, d, m都是整数。

比如m = 4, 四边形ABCD共有256种情况。256个四边形当中，有42四边形精确地包含平方个数目的网格点（坐标为整数）。

如果m = 100, 有多少个四边形包含平方个数目的点呢？

对于现代计算机而言，遍历100 ^ 4其实是很快的一件事情，如果对于每一个四边形而言，如果能在常数量级得到包含点的个数，然后常数量级知道它是不是平方数，那么就基本能在100 ^ 4这个量级搞定这个问题。

常数量级知道某个数是不是平方数很简单，先算出来一个列表，然后去查询就可以了。
ABCD能组成最大的正方形就是边长约为141的正方形，内部点最多也就是140 * 140个，那么，把前140个平方数存下来，之后用二分法查找即可。

1	var squares = Enumerable.Range(1, 140).Select(n => n * n).ToList();

那么如何知道四边形里面点的个数呢？
预先存下来。
显然不是预先存下来每个四边形的点的个数，这不就是我们要的结果嘛。
我们存储直角三角形的内部点的个数。

static private int[,] NumbersOfInsideVector = new int[M + 1, M + 1];

for (int i = 1; i <= M; i++)
{
	for (int j = 1; j <= i; j++)
	{
		int result = GetInsideVector(i, j);
		NumbersOfInsideVector[i, j] = result;
		NumbersOfInsideVector[j, i] = result;
	}
}

private static int GetInsideVector(int a, int b)
{
	int count = 0;

	for (int i = 1; i <= a - 1; i++)
	{
		int yi = b - b * i / a;
		count += (yi - 1);
	}

	return count;
}

使用一个二维数组来存放边长为a b的直角三角形内部的点数。对于边长a b的直角三角形，x轴从1到a - 1，计算高度yi，然后得到对于每个x有的点数，相加起来就是整个直角三角形内部的点数了。
整个计算过程，外层是O(M ^ 2)，GetInsideVector是O(M)，总的复杂度上限是O(M ^ 3)。

有了直角三角形内部点数，计算ABCD四边形内部点数就非常容易了。

private static int GetNumberOfVector(int a, int b, int c, int d)
{
	int number = a + b + c + d + -3;
	number += NumbersOfInsideVector[a, b];
	number += NumbersOfInsideVector[b, c];
	number += NumbersOfInsideVector[c, d];
	number += NumbersOfInsideVector[d, a];

	return number;
}

除了计算几个直角三角形内部的点数，还要加上坐标轴上的点，a b c d相加再减去3个，这是重复计算了原点。
我们有能力在O(1)时间内搞定任意一个四边形内部点的个数，最后就是遍历每一个可能的情况。

long count = 0;

for (int d = 1; d <= M; d++)
{
	for (int c = 1; c <= M; c++)
	{
		for (int b = 1; b <= M; b++)
		{
			for (int a = 1; a <= M; a++)
			{
				int numberOfVector = GetNumberOfVector(a, b, c, d);
				if (squares.BinarySearch(numberOfVector) >= 0)
				{
					count++;
				}
			}
		}
	}
}

return count;

在我的机器上，i5-5257U的电脑，大约8s能够解决这个问题，还算是挺快。

最近好懒，不能这么下去了

发表于 2016-01-19 分类于 Life Disqus：

打2016以来，就没有踏踏实实的看过书了，真不应该。

过去的两个月，装修房子让人操碎了心，但是晚上和周末还是忙里偷闲的看会书的。为什么到了新的一年缺没有行动了呢？

最近这两周的工作是比较忙，这两天又要写评定职称的材料，但是，这也不是偷懒的理由啊！

Xbox one是挺好玩的，下载游戏只能是清晨，让人蛋疼，但是，不能太多心分到他上面，这样子是不对的！

哪怕年终奖和HR当年忽悠入职时说的不一样，级别没有如自己所愿，努力跳槽就是，干嘛要婆婆妈妈的想东想西呢？

始终如一，做好自己，简简单单的，足够了。

想刷的书一本一本的刷，欧拉项目的题目一道一道的思考，英语要一点一点的积累，前进不难，难的是不静下心来慢慢前进。

勿忘初心，就像当年建立这个博客一样，一点一点前进