题目太长，这里就不描述了，这里是题目

字符串是16位，那么数字10肯定在外圈，因为内圈的数字会被用两次，长度就是17了。
题目一个要求是从外围的最小数开始，现在又要保证字符串最大，那么如果6,7,8,9,10都在外圈，字符串就是6开头，否则至少是5开头，比6开头要小，所以要使得其最大化，6,7,8,9,10都在外圈。
参考三角环中数字最大的形式，4,5,6三个数字逆时针旋转，于是乎我也如法炮制，让6,7,8,9,10挨着并逆时针排列着，如图：

在此基础上，每行最小和是10+1+2 = 13。我们现在就推理下每行13的可行性：
6和10要共享一个数字B，B只能是1或者2，那么6所在的这一行要想到13，至少还差5。此时，B=2，A=5，C=1。
考虑7所在的行，13-7-5 = 1。但是1已经被用掉了。
排除这种情况。

每行的最大和是6+5+4 = 15。
很显然，B不能是5，所以B=4。那么A=5。那么E=3。那么D=4。4已经被用过了。
也要排除这种可能性。

那么，每行和就是14了。
6所在的哪行，只能是一个5一个3。B又不能是5。所以A=5，B=3。那么C=1。那么D=4。最后的E是2。
根据这种排列，6531031914842725就是答案了。

虽然每一部推理都很有根据，最后也得到了答案，但是所有推理的基础不不牢靠的，也就是给出示意图的那一步。
为什么要挨着排放呢？虽说6的顺时针右侧是10而不是9呢？显然9比10的第一位要大的。
为什么呢？
6要和一个数字共享A，A越大越好，显然那个被共享的数字越小越好啊，那就设定成7了。但用这种想法再逆时针推理显然也站不稳啊。

这就像吐槽程序员的一句话，程序运行起来了，但不知道为什么。

已经2015年了。简单的总结一下去年吧，再展望一下今年。

1. 阅读
   想好了一个月读一本书，但是没有做到。过去的一年就读了几本吧。
   活出生命的意义，逃离德黑兰，天才引导的历程，图解HTTP，Pro JavaScript，敏捷模式开发，漫谈设计模式，程序员健康指南，很多期码农杂志，还有很多书都看了个开头，没有结束。。。
   不过，Kindle是个好东西，晚上躺在床上，随意的看上几页，也不重，还不伤眼。但是好几本都看了个开头。。。
   以后还是要静下心，一本一本来看，贪多嚼不烂。
   希望2015年能够做到每个月读一本书。

2. 手术
   大事，最近的一次检查显示，一切都正常，慢慢的要加强体育锻炼，再然后就像主刀的主任说的一样，enjoy life

3. 感情
   和她的感情越来越好了。过年估计去她们家提亲吧。
   预计今年去欧洲玩一圈，但是我要是真的拿到了小米offer，然后再去了小米，就五天年假，怎么可能有时间玩呢，一声叹息啊。

4. 工作

5. 07-1014.06这个财年，居然拿了1分，从L59到了L60，工资涨了不少，算是过去一年辛勤的搞Office Portal的奖励吧。不过下半年就没有这么顺利了。两次re-org。第一次比较小，就是合并了Dev和Test。第二次比较大，嗯，开始做WAC了。三个一线Manager转了IC，其中一个是我老板，现已去了小米，另一个去了美国总部。最令人担忧的是，这次re-org引起了波动，很多人因此离职了。除了两个老板走了，还有三个原本就是Sr. Dev的，也走了，一个去了美国总部，两个去了小米。我擦，这么多人去小米，细思极恐啊。原本和我一个组的，一个也去了小米，一个要去美国总部。哎，人心惶惶啊。
   未来的打算，先去小米面一下，拿到offer，看下待遇，一切都还不错的话，就跳槽。
   拿不到Offer的话，就好好的接着在微软干，看下今年9月的结果然后再考虑发展吧。亦或者4月又re-org了呢哈哈。

6. 学习
   过去一年，女朋友说英语进步不少，但自我感觉没什么进步。如果不去小米，这玩意还待努力，即使去了，作为通用语言，也要学习才是。
   其他方面，想看的太多，读的太少，好在元旦休息三天，思考了下，希望未来一年能静心研习。

加油！最后说句俗话，新的一年，新的开始！

要求Push，Pop，GetMin这些方法都是常数时间的。
仔细想下这个问题，最小值不会经常的变，除非我们插入了一个更小的值，或者是当前的最小值出栈了。
我们自己写一个栈类，维护一个保存最小值的栈。当新元素插入的时候，如果新元素的值小于等于当前最小值，除了往存放所有数据的栈里面存一份，还要往最小值栈里面存一份。当弹出元素的时候，如果弹出元素和最小值一样的话，最小值栈也弹出。这种做法利用的额外空间比较小，虽然是O(n)，但是，从概率上说，最小值栈只用保存一小部分数据就足够了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class StackWithMin : Stack<int>;
{
    private Stack<int>; minStack;

    public StackWithMin()
    {
        this.minStack = new Stack<int>();
    }

    public new void Push(int value)
    {
        base.Push(value);
        if (value <= this.GetMin())
        {
            minStack.Push(value);
        }
    }

    public new int Pop()
    {
        int value = base.Pop();
        if (value == this.GetMin())
        {
            minStack.Pop();
        }

        return value;
    }

    public int GetMin()
    {
        if (minStack.Count == 0)
        {
            return int.MaxValue;
        }
        else
        {
            return minStack.Peek();
        }
    }
}

具体问题是说，如果给两个字符串s1，s2，写一个方法，判断s1能否通过旋转变成s2。比如watset按照某个点旋转编程setwat，还能旋转成tsetwa。限制是只能用一次isSubstring方法。

编程珠玑这本书有提到类似的问题。思路挺简单：
如果能旋转的话，假定x和y都是字符串
s1=xy
s2=yx
那么s2可能是s1s1的子字符串，具体说来就是yx一定是xyxy的子字符串。

1
2
3
4
5
6
7
8
9

public static bool IsRotation(string s1, string s2)
{
    if (s1.Length != s1.Length)
    {
        return false;
    }

    return IsSubstring(s1 + s1, s2);
}

粗一看，扫面矩阵，遇到0之后把所在行所在列的都设置成0。但是，很快会发现，整个矩阵都是0了。这显然不符合题目的要求。

正确的做法应该是先扫面一次矩阵，看那些位置上出现了0，我们不用精确的记录位置，只要记录要标记为0的行号和列号就好了，这里，使用bool数组完成这件事。接着第二次扫描数组，根据第一次扫描记录的结果，把对应元素设置成0即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public static void SetZeros(int[,] matrix)
{
    int m = matrix.GetLength(0);
    int n = matrix.GetLength(1);
    bool[] row = new bool[m];
    bool[] col = new bool[n];

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (matrix[i, j] == 0)
            {
                row[i] = true;
                col[j] = true;
            }
        }
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (row[i] || col[j])
            {
                matrix[i, j] = 0;
            }
        }
    }
}

具体问题是说，使用一种极为简单的算法来压缩字符串。该算法就是字符后面跟上该字符连续出现的次数。比如”aabcccccaaa”压缩完之后就是”a2b1c5a3”。如果压缩过的字符串比原始的字符串还长，那么就返回原始的字符串。

解法也很直接。从第一个字符开始遍历字符串，并记录连续的次数。遇到下一个不一样的字符时，就把上一个字符和字数都添加到一个StringBuilder里面。然后看该字符连续的次数。遍历完成之后，判断新字符串和旧字符串的长度，如果新的长度短，则返回新字符串，否则，返回旧字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public static string Compress(string s)
{
    StringBuilder sb = new StringBuilder();
    char last = s[0];
    int count = 1;
    for (int i = 1; i < s.Length; i++)
    {
        if (last == s[i])
        {
            count++;
        }
        else
        {
            sb.Append(last).Append(count);
            last = s[i];
            count = 1;
        }
    }
    sb.Append(last).Append(count);

    if (sb.ToString().Length >= s.Length)
    {
        return s;
    }

    return sb.ToString();
}

具体题目是说，给定一个N x N的矩阵，要求就地（空间复杂度为O(1)）旋转九十度。

旋转矩阵，元素所在的层数是不变的，所以我们一层一层的迭代对每层进行旋转。对于每层来说，上面的元素到了右边，右边的元素到了下面，以此类推。
可以把上面的元素全部拷贝到某个数组，然后左边的元素拷贝过来，下面的元素拷贝到左边，以此类推，但是这样就占用了O(n)的空间。应用类似的想法，但是一次只移动一个元素即可，对应四边的四个元素交换位置，这样不会影响到其他元素，也同样达到了目的。

下面是算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public static void Rotate(int[,] matrix)
{
    int n = matrix.GetLength(0);
    for (int layer = 0; layer < n / 2; layer++)
    {
        int first = layer;
        int last = n - 1 - layer;
        for (int i = first; i < last; i++)
        {
            int offset = i - first;

            // save top
            int top = matrix[first, i];

            // left -> top
            matrix[first, i] = matrix[last - offset, first];

            // bottom -> left
            matrix[last - offset, first] = matrix[last, last - offset];

            // right -> bottom
            matrix[last, last - offset] = matrix[i, last];

            // top -> right
            matrix[i, last] = top;
        }
    }
}

算法的时间复杂度是O(n^2)，应该说已经是最优的了，因为旋转矩阵，至少要把N^2个元素都移动一次。

有两个链表，代表两个数，其中每个结点都包含一个数字。每个链表是倒序排列，比如数字617，那么链表是7 -> 1 -> 6。如何求和呢？如果是正序排列，又该如何求和呢？

如果反序排列的话，链表头就是个位，接着是十位，以此类推。就和普通的手算一致，先算低位，如果大于10，需要进位，接着计算高位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

private static LinkedListNode<int> AddLists(LinkedListNode<int> l1, LinkedListNode<int> l2, int carry)
{
    if (l1 == null && l2 == null && carry == 0)
    {
        return null;
    }

    int value = (l1 != null ? l1.Data : 0) + (l2 != null ? l2.Data : 0) + carry;
    var result = new LinkedListNode<int>(value % 10);
    if (l1 != null || l2 != null)
    {
        var more = AddLists(l1 != null ? l1.Next : null, l2 != null ? l2.Next : null, value >= 10 ? 1 : 0);
        result.Next = more;
    }

    return result;
}

如果链表是正序表示一个数字，该如何做呢？一个可行的方案是，反转两个链表，然后就回到了上一种情况。
这里，采用和上面类似的思想去解决这个问题，显然，比上面的问题要复杂，需要考虑的更多：

1. 如果一个链表比另外一个长，该怎么办？比如1 -> 2 -> 3 -> 4和5 -> 6 -> 7两个链表，显然，5应该和2相加而不是1。我们可以遍历两个链表，向短的前面补充上零。
2. 在上面那种情况下，计算结果被加到了链表的尾部，这意味着递归程序本身就可以处理进位，但是现在不行了。所以我们需要添加一些数据结构对象来处理进位。把后面的进位结果带到前面来。

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

   private static LinkedListNode<int> AddLists(LinkedListNode<int> l1, LinkedListNode<int> l2) { int length1 = GetLength(l1); int length2 = GetLength(l2); if (length1 < length2) { l1 = PadList(l1, length2 - length1); } else { l2 = PadList(l2, length1 - length2); } PartialSum sum = AddListsHelper(l1, l2); return sum.Carry == 0 ? sum.Sum : InsertBefort(sum.Sum, 1); } private static PartialSum AddListsHelper(LinkedListNode<int> l1, LinkedListNode<int> l2) { if (l1 == null && l2 == null) { return new PartialSum(); } PartialSum sum = AddListsHelper(l1.Next, l2.Next); int value = sum.Carry + l1.Data + l2.Data; var fullResult = InsertBefort(sum.Sum, value % 10); sum.Sum = fullResult; sum.Carry = value / 10; return sum; } private static LinkedListNode<int> InsertBefort(LinkedListNode<int> l, int p) { var node = new LinkedListNode<int>(p); if (l != null) { node.Next = l; } return node; } private static LinkedListNode<int> PadList(LinkedListNode<int> l, int p) { var head = l; for (int i = 0; i < p; i++) { LinkedListNode<int> newNode = new LinkedListNode<int>(0); newNode.Next = head; head = newNode; } return head; } private static int GetLength(LinkedListNode<int> l1) { int count = 0; while (l1 != null) { count++; l1 = l1.Next; } return count; } private class PartialSum { public LinkedListNode<int> Sum = null; public int Carry = 0; }

给一个单链表和一个键值k，分割单链表，使得链表的前面都是小于k的值，链表的后面都是大于或等于k的值。

我们创建两个链表，一个用于存放小于k的结点，一个用于存放大于k的结点。遍历原来的链表，把结点分到两个新的链表上，然后把这两个链表链接起来即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

private static LinkedListNode<int> Partition(LinkedListNode<int> node, int k)
{
    LinkedListNode<int> beforeStart = null;
    LinkedListNode<int> beforeEnd = null;
    LinkedListNode<int> afterStart = null;
    LinkedListNode<int> afterEnd = null;

    while (node != null)
    {
        LinkedListNode<int> next = node.Next;
        node.Next = null;
        if (node.Data < k)
        {
            if (beforeStart == null)
            {
                beforeStart = node;
                beforeEnd = beforeStart;
            }
            else
            {
                beforeEnd.Next = node;
                beforeEnd = node;
            }
        }
        else
        {
            if (afterStart == null)
            {
                afterStart = node;
                afterEnd = afterStart;
            }
            else
            {
                afterEnd.Next = node;
                afterEnd = node;
            }
        }

        node = next;
    }

    if (beforeStart == null)
    {
        return afterStart;
    }

    beforeEnd.Next = afterStart;
    return beforeStart;
}

原题链接
如果一个盒子里有21个有色的碟子，15个蓝色的和6个红色的。从中随机取两个，可知取到两个蓝碟子的几率是 P(BB) = (15/21)×(14/20) = 1/2。
下一个满足此条件（即随机取两个碟子的情况下取到两个蓝色碟子的几率是50%）的情况是85个蓝碟子和35个红碟子。
对于包含超过10 ^ 12 = 1,000,000,000,000个碟子的情况中，满足上述条件的并包含最少碟子的情况，该情况下共需要多少个蓝碟子？

假设碟子总数是T，蓝色盘子总数是B，那么它们需要满足(B/T)((B-1)/(T-1)) = 1/2
可以转化为求方程
(T - 1/2) ^ 2 + 2 * (B - 1/2) ^ 2 = -1/4
的整数解。
两边同时乘以4
(T/2 - 1/4) ^ 2 + 2 * (B/2 - 1/4) ^ 2 = -1
令
T = (x+1)/2
B = (y+1)/2
其中，x和y要是奇数
方程转化为
x ^2 - 2 * y ^ 2 = -1
这是一个Pell方程，最小的正整数解是
x = 1
y = 1
根据Pell方程的通解
$$\begin{cases}
x_n=\frac 1 2\left[ {(x_1+\sqrt d y_1)}^{2n-1} + {(x_1-\sqrt d y_1)}^{2n-1}\right] \
y_n=\frac 1 {2\sqrt d }\left[ {(x_1+\sqrt d y_1)}^{2n-1} - {(x_1-\sqrt d y_1)}^{2n-1}\right]
\end{cases}$$
可以算出整数解，不难看出，x(n)和y(n)都是奇数。

用程序计算得到第一个超过2 * 10 ^ 12的x，这样对应满足题意T，通过对应的y计算得到我们要求的答案B。
公式里的d是2。

1
2
3
4
5
6
7
8
9
10
11
12

double sqrt2 = Math.Sqrt(2);

for (int i = 1; ; i++)
{
    long x = (long)((Math.Pow(1 + sqrt2, 2 * i - 1) + Math.Pow(1 - sqrt2, 2 * i - 1)) / 2) + 1;
    long y = (long)((Math.Pow(1 + sqrt2, 2 * i - 1) - Math.Pow(1 - sqrt2, 2 * i - 1)) / 2 / sqrt2) + 1;

    if (x > 2000000000000)
    {
        return (y + 1) / 2;
    }
}

程序中，在计算x和y的时候都+1了，因为前面的double类型运算可能会损失精度，强转成long的时候少了1，所以最后又加了个1。