一点一点前进...

0%

发表于 分类于 ， Disqus：

这是一个很经典的面试题目。

首先，我们要检测一个链表是否包含环
典型的思路，快慢指针。快指针每次移动两个结点，慢指针移动一个结点。就像两辆车在环形跑道上比赛，速度差一倍，那么快的肯定会追上慢的（套圈）。
如果快的指针到头了，两者还是没有相遇，那么说明这个链表不包含环。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var slow = head;
var fast = head;

while (fast != null && fast.Next != null)
{
    slow = slow.Next;
    fast = fast.Next.Next;
    if (slow == fast)   // 相遇了
    {
        break;
    }
}

// 快的指针到头了，说明没有环，也就无所谓环的起始结点，所以返回null 
if (fast == null || fast.Next == null)
{
    return null;
}

我们需要知道，他们在哪里相遇了呢？
假设非环部分的长度是k，那么，慢指针走了k步，位于环的起始位置，快指针走了2k步，除去非环部分的k步，快指针在环里面走了k步，考虑k可能比环的长度大，我们可以认为，快指针从环起始位置往前走了M = k % LoopSize步，也就是说，快指针比慢指针快了M步，从另一个角度看，快指针比慢指针慢了LoopSize - M步。

之后，慢指针走LoopSize - M步，快指针走2 * (LoopSize - M)步，两者相遇。相遇点距离环的起始位置距离是LoopSize - M（从环的起始结点向前走）。

找到了相遇位置，如何利用这个信息找到环的起始结点呢？
从相遇点再走多远能到环的起始点呢？M。
M和k有什么关系呢？模。k= M + N * LoopSize。那么，从另外一个角度看，从链表开始到环的开始之间是k步;从相遇点继续向前，也是k步就到了环的起始结点，无非是在环里面绕零圈，还是多绕几圈的区别。
知道了这个我们就可以解决这个问题了。
当找到相遇点之后，把慢指针拿到链表开头，快指针不动，但是每次只移动一步，当两个指针再次相遇的时候，就到了环起始结点。 

1
2
3
4
5
6
7
8
slow = head;
while (slow != fast)
{
    slow = slow.Next;
    fast = fast.Next;
}

return fast;

发表于 分类于 ， Disqus：

首先，我们要搞明白什么是回文，举个简单的例子，单链表0 -> 1 -> 2 -> 1 -> 0就是回文，具体说来就是正着看和反着看是一样的。
从这个定义出发，我们可以得到第一种解决方案：反转比较法。
将单链表反转，然后和原来的进行比较，如果两者一致，那么该单链表表示的内容是回文，否则就不是。
但是比较的时候不用比较全部链表，只需要比较到一半就可以了。因为反转链表的后半段就是原链表的前半段，反转链表的前半段就是原链表的后半段，两段是等价的，所以只需比较一半即可。

原问题等价于链表的前半段是否是链表的后半段的反转。
如何解决等价问题呢？把前半段反转的形式存起来，再遍历即可。恰巧栈Stack这种数据结构就是专门来做这事的。于是，我们得到了第二种解决方案。
第一个阶段是把前半段放到一个栈里面，第二阶段是比较后半段和栈中的内容是否一致。
现在问题来了，如果我不知道链表的长度，我咋知道第一阶段结束了呢？使用快慢指针的方法。
这里提一下，这种方法真是解决单链表问题的制胜法宝，很多问题都可以用到。
把慢指针的内容放入栈中，当快指针走到头的时候，那么慢指针刚好把一半的内容放入栈中。这里要注意以下，如果是奇数，也就是fast.Next.Next == null，但是fast.Next != null，需要把慢指针再向前一步。对于回文来说，正中间位置的内容不影响判断的结果。好了，第一阶段的内容做完了，第二阶段很容易，一个while循环就好了。

发表于 分类于 ， Disqus：

只给了一个参数，就是要删除的结点。由于是单链表，你可以访问下一个结点，但是无法访问上一个结点。解决的方法是把下一个结点的内容复制到当前的结点，然后删除下一个结点。 

1
2
3
4
5
6
7
8
9
10
11
12
13
private static bool DeleteNode<T>(LinkedListNode<T> n)
{
    if (n == null || n.Next == null)
    {
        return false;
    }

    LinkedListNode<T> next = n.Next;
    n.Data = next.Data;
    n.Next = next.Next;

    return true;
}

这道题目看似简单，但是有一个坑，就是如果给定结点是链表的最后一个结点该怎么办。上述代码排除这种情况，返回了false，意味着删除失败。你应该指出存在这个问题，并和面试官讨论如何解决这种特殊情况。

发表于 分类于 ， Disqus：

如果是正数第k个结点，很容易，依次往后遍历就好，现在是倒数第k个，该怎么办呢？
我们使用两个指针p1和p2，p1指向开始位置，p2指向第k个结点，使得两者之间距离是k。然后同步的移动这两个指针，当p2指向最后一个结点的时候，p1指向的就是倒数第k个结点。
算法的时间复杂度是O(n)，空间复杂度是O(1)。

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
private static LinkedListNode<T> KthToLast<T>(LinkedListNode<T> head, int k)
{
    if (k <= 0)
    {
        return null;
    }

    LinkedListNode<T> p1 = head;
    LinkedListNode<T> p2 = head;

    for (int i = 0; i < k - 1; i++)
    {
        if (p2 == null)
        {
            return null;    // Link length is less than k
        }

        p2 = p2.Next;
    }

    if (p2 == null)
    {
        return null;    // Link length is less than k
    }

    while (p2.Next != null)
    {
        p1 = p1.Next;
        p2 = p2.Next;
    }

    return p1;
}

发表于 分类于 ， Disqus：

如何从单链表里面删除内容一样的结点呢？

为了能够删除内容重复的结点，首先我们要能追踪到那些重复的内容。使用Set这种数据结构就很不错。
我们的解法很简单，就是去遍历整个链表，如果集合中没有该结点内容，就放入集合，如果已经存在，说明是重复内容，删除该结点。
算法时间复杂度是O(n)，还需要额外的存储空间O(n)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void DeleteDups<T>(LinkedListNode<T> n)
{
    HashSet<T> datas = new HashSet<T>();
    LinkedListNode<T> previous = null;
    while (n != null)
    {
        if (datas.Contains(n.Data))
        {
            previous.Next = n.Next;
        }
        else
        {
            datas.Add(n.Data);
            previous = n;
        }

        n = n.Next;
    }
}

现在，增加一个限制条件，不能使用额外的存储空间。又该如何做呢？
我们使用两个指针去遍历这个链表，current结点去遍历，再有一个结点runner从current之后的一个去遍历，如果两者内容一样，就删除runner指向的结点。
该算法时间复杂度是O(n^2)，好处是不用占用额外的存储空间。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static void DeleteDups<T>(LinkedListNode<T> n)
{
    LinkedListNode<T> current = n;
    while (current != null)
    {
        LinkedListNode<T> runner = current;
        while (runner.Next != null)
        {
            if (runner.Next.Data.Equals(current.Data))
            {
                runner.Next = runner.Next.Next;
            }
            else
            {
                runner = runner.Next;
            }
        }

        current = current.Next;
    }
}

发表于 分类于 ， Disqus：

题目是：文件中的三角形中有多少个内部包含原点？

在笛卡尔平面上随机取三个不同的点，其中-1000 ≤ x, y ≤ 1000，会形成一个三角形。
考虑如下两个三角形：
A(-340,495), B(-153,-910), C(835,-947)
X(-175,41), Y(-421,-714), Z(574,-645)
可以证明三角形ABC包含原点在其内部，而三角形XYZ则不包含。
triangles.txt 包含一千个随机三角形，求其中有多少个三角形的内部包含原点。

如何判断一个点是不是在某个三角形内呢？
一个不太笨的方法是，如果点C和点O在直线AB的同侧，点B和点O在直线AC的同侧，点A和点O在直线BC同侧，那么点O就在三角形ABC里面。
好了，问题转化为，如何判断两个点在某直线的同侧。
算法导论中有说这个问题，向量AB和向量AC叉积，向量AB和向量AO叉积，如果两个叉积结果的符号相同，那么说明点C和点O在AB的同侧。
思路都解释完了，下面写代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
private static bool IsSameSide(int xa, int ya, int xb, int yb, int xc, int yc, int xo, int yo)
{
    return (long)CrossProduct(xa, ya, xb, yb, xc, yc) * CrossProduct(xa, ya, xb, yb, xo, yo) > 0;
}

private static int CrossProduct(int xa, int ya, int xb, int yb, int xc, int yc)
{
    int xv = xb - xa;
    int yv = yb - ya;
    int xu = xc - xa;
    int yu = yc - ya;
    return xv * yu - yv * xu;
}

需要解释的是，坐标小于1000，叉积结果大约是十的六次方数量级，IsSameSide判断的时候如果不强转成long型，可能会溢出，造成判断错误。

给出的数据比较大，需要写一点点代码去解析它们。
下面是完成的代码： 

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
int count = 0;
string[] triangles = Triangles.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);

int xo = 0;
int yo = 0;

foreach (string triangle in triangles)
{
    int[] tmp = triangle.Split(',').Select(s => int.Parse(s)).ToArray();

    int xa = tmp[0];
    int ya = tmp[1];
    int xb = tmp[2];
    int yb = tmp[3];
    int xc = tmp[4];
    int yc = tmp[5];

    if (IsSameSide(xa, ya, xb, yb, xc, yc, xo, yo)
        && IsSameSide(xa, ya, xc, yc, xb, yb, xo, yo)
        && IsSameSide(xb, yb, xc, yc, xa, ya, xo, yo))
    {
        count++;
    }
}

return count;

发表于 分类于 ， Disqus：

题目本身是问，分母不超过一百万的最简真分数的集合中包含多少元素？

考虑分数 n/d, 其中n 和 d 是正整数。如果 n < d 并且最大公约数 HCF(n,d)=1, 它被称作一个最简真分数。
如果我们将d ≤ 8的最简真分数按照大小的升序列出来，我们得到：
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5 , 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可知该集合中共有21个元素。
d ≤ 1,000,000的最简真分数集合中包含多少个元素？

如果写代码就是遍历d，然后针对每个d求1到d-1中有多少个数与d互质（互质才能是最简真分数），求和。

假设我们有一个函数能够得到互质数的个数，那么这个题目很容易解决，代码如下： 

1
2
3
4
5
6
7
8
long count = 0;
for (int d = 2; d <= 1000000; d++)
{
    long thisCount = Utils.GetCoprimeCount(d);
    count += thisCount;
}

return count;

现在关键问题是，给定一个数n，如何求出1到n-1中，有多少个数与之互质。
前几天刚在《什么是数学》这本书中看完欧拉函数，这就用上了。
欧拉函数描述了这个问题的解：
$$
\varphi(x)=x(1-1/p_1)(1-1/p_2)(1-1/p_3)(1-1/p_4)\cdots(1-1/p_n)
$$
其中$$p_1, p_2, \ldots, p_n$$为x的所有质因数
又$$
x={p_1}^{k_1} + {p_2}^{k_2} + \cdots + {p_n}^{k_n}
$$
所以，$$\varphi(x)=\prod_{i=1}^n (p_i-1)*{p_i}^{k_i-1}$$

开始写代码实现欧拉函数求互质数的个数： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int GetCoprimeCount(int n)
{
    int ret = 1;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            n /= i;
            ret *= i - 1;
            while (n % i == 0)
            {
                n /= i;
                ret *= i;
            }
        }
    }
    if (n > 1)
    {
        ret *= n - 1;
    }

    return ret;
}

简单解释两点，
if (n % i == 0)里面的ret *= i - 1;相当于$$\prod_{i=1}^n (p_i-1){p_i}^{k_i-1}$$里面的$$(p_i-1)$$，while里面的ret \= i;相当于$$p_i$$，整个while循环就相当于$${p_i}^{k_i-1}$$
后面的if是判断，如果n > 1，那么剩余的n肯定是质数，ret *= n - 1;就相当于$$p_i-1$$，与之对应的$$k_i$$是1。

综合起来，就能在短短的几秒钟里面得到答案了。

发表于 分类于 ， Disqus：

关于字符串操作的问题，有一个普适的方法，从后往前来处理字符串。因为我们往往会开一个足够大的缓冲区去放置替换后的字符串，从后往前遍历操作，不用考虑正在被操作的字符被覆盖。

我们需要扫描两次字符串。第一次的目的是统计有多少个空格，这样我们就能确定替换之后的字符串的长度了；第二次从后往前，将空格替换成%20，如果是非空格字符，我们直接拷贝原始的字符就好了。

使用C#来模拟操作这个字符串：

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
public static string ReplaceSpaces(string s)
{
    int spaceCount = 0;
    int newLength;
    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == ' ')
        {
            spaceCount++;
        }
    }

    newLength = s.Length + 2 * spaceCount;
    char[] newString = new char[newLength];
    for (int i = s.Length - 1; i >= 0; i--)
    {
        if (s[i] == ' ')
        {
            newString[newLength - 1] = '0';
            newString[newLength - 2] = '2';
            newString[newLength - 3] = '%';
            newLength -= 3;
        }
        else
        {
            newString[newLength - 1] = s[i];
            newLength--;
        }
    }

    return new string(newString);
}

发表于 分类于 ， Disqus：

给定两个字符串，写一个方法，判断一个字符串是否可以由另一个字符串变换字符顺序得到？

和大多数面试题一样，你往往可以和面试官交流，把一些有可能出现不同理解的地方都弄清楚。比如大小写敏感啊，空白字符算一个字符吗等等。
我们假定大小写敏感，空白字符也算为前提，进行分析。

首先，如果两个字符串的长度不一样，可以直接返回false了。
解法一，将两个字符串排序，然后对比一下。如果一样，说明一个字符串可以由另外一个字符串变换顺序得到。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static bool IsPermutation(string s1, string s2)
{
    if (s1.Length != s2.Length)
    {
        return false;
    }

    return Sort(s1).Equals(Sort(s2));
}

private static string Sort(string s)
{
    char[] chars = s.ToCharArray();
    Array.Sort(chars);
    return new string(chars);
}

然而，这个方法不高效，但是简单易懂。下面给出一个更高效的解法：计算每个字符的个数。

实现上可能有一点点区别，遍历第一个字符串，统计每个字符有多少个，遍历第二个字符串，对统计好的数据做减法。最后，如果两个字符串的每个字符的个数相等，那么数组每项为零。反之，至少有不为零的项。（我们假定只出现ASCII码0-127这些字符）

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 bool IsPermutation(string s1, string s2)
{
    if (s1.Length != s2.Length)
    {
        return false;
    }

    int[] letters = new int[128];
    for (int i = 0; i < s1.Length; i++)
    {
        letters[s1[i]]++;
    }

    for (int i = 0; i < s2.Length; i++)
    {
        letters[s2[i]]--;
    }

    for (int i = 0; i < letters.Length; i++)
    {
        if (letters[i] != 0)
        {
            return false;
        }
    }

    return true;
}

发表于 分类于 ， Disqus：

这个题几乎不需要什么算法，很简单，但是可以花2分钟考察一下面试者到底会不会写代码，如果不会，可以节省面试官很多时间。

下面用C#仿照传统的C来实现反转字符串，思路就是从头开始，把前面的字符和后面的字符兑换，对换到中间的时候结束。 

1
2
3
4
5
6
7
8
9
10
11
12
public static string Reverse(string text)
{
    char[] cArray = text.ToCharArray();
    for (int i = 0; i < cArray.Length / 2; i++)
    {
        char tmp = cArray[i];
        cArray[i] = cArray[cArray.Length - i - 1];
        cArray[cArray.Length - i - 1] = tmp;
    }

    return new string(cArray);
}

当然，C#完成这件事只需要一行代码：

1
2
3
4
public static string Reverse(string text)
{
    return new string(text.ToCharArray().Reverse().ToArray());
}