发表于 | 分类于

开幕雷击，老师让我发中文和英文给他改，所以当然要使用LaTex来写一份中文的，然后另一份写英文的。但是试了一下网上介绍的方法，还是没有效果。用TeXstudio编译后，自带的PDF显示器没有显示中文。炸裂。随后万能的网友告诉了我答案百度贴吧。原来生成是成功了的，但是自带的PDF却没有显示，这时候只要在Tex文件里面加上这一句就可以了：\usepackage[fontset=mac]{ctex}。成功！

发表于 | 分类于 ，

面试题20: 表示数值的字符串

题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

解题思路：这个题目用排除法做。

算法：

-*- coding:utf-8 -*-
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
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        if len(s) <= 0:
            return False
        has_point = False
        has_sign = False
        has_e = False
        for i in range(len(s)):
            if s[i] == 'e' or s[i] == 'E':
                if has_e == True:
                    return False
                else:
                    if not s[i+1:]:
                        return False
                    has_e = True
            elif s[i] == '+' or s[i] == '-':
                if has_e:
                    if s[i-1] != 'e' and s[i-1] != 'E':
                        return False
                if i > 0 and s[i-1] != 'e' and s[i-1] != 'E':
                        return False
                has_sign = True
            elif s[i] == '.':
                if has_point or has_e :
                    return False
                else:
                    has_point = True
                    if i > 0 and (s[i-1] == 'e' or s[i-1] == 'E'):
                        return False
            else:
                if s[i] <'0' or s[i] > '9':
                    return False
        return True

算法思路：条件排除主要还是使用if elif else来实现，对所有情况的排除没有先后关系，因为是和前面的状态相关。

面试题 21:调整数组顺序，使奇数在偶数前面

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

解题思路：

算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        def is_even(num):
            return (num & 1) == 0
        left, right = 0, len(array) - 1
        while left < right:
            while not is_even(array[left]):
                left += 1
            while is_even(array[right]):
                right -= 1
            if left < right:
                array[left], array[right] = array[right], array[left]
        return array

发表于 | 分类于 ，

面试题15： 二进制中的1的个数

题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

解题思路：把一个整数减去1之后和原来的整数做位于运算。得到的结果相当于把整数的二进制表示中最右边的1变成0。然后注意python的负数补码是无限的···，所以要先和32位的1做与运算。

代码：

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def NumberOf1(self, n):
        # write code here

        count = 0
        if n < 0:
            n = n & 0xffffffff
        while n:
            count += 1
            n = (n - 1) & n
        return count

代码思路：先处理掉负数死循环的情况（只对python来说），然后用解题思路的做法来计算1的数量。

还有一个要记住的：如果一个整数和1做与运算的结果是1，则表示该整数的最右边一位是1，否则是0。

面试题16: 数值的整数次方

题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0

解题思路：这种题目看似简单，但实际上主要考察的是代码的完整性，之所以觉得简单是因为题目的功能实现简单，但是完整的代码应该考虑到所有可能的输入情况，就是代码的完整性。（有一种情况是错的，底数为0，指数为负数），其他情况有：指数为负数。

-*- coding:utf-8 -*-
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
class Solution:
    def __init__(self):
        self.g_InvalidInput = False
    def Power(self, base, exponent):
        # write code here
        self.g_InvalidInput = False
        if base is 0.0 and exponent < 0:
            g_InvalidInput = True
            return 0.0
        absExponent = exponent
        if exponent < 0:
            absExponent = -exponent
        result = self.PowerWithUnsignedExponent(base, absExponent)
        if(exponent <0):
            result = 1.0/result
        return result
    def PowerWithUnsignedExponent(self, base, exponent):
        if exponent == 0:
            return 1
        if exponent == 1:
            return base
        result = self.PowerWithUnsignedExponent(base, exponent >> 1)
        result *= result
        if exponent & 0x1 == 1:
            result *= base
        return result

算法解析：算法考虑将指数先变成绝对值，在之后根据指数是否是负数来处理。然后主要的实现放到另一个函数中实现。用了递归来加快指数运算。依据如下：

用了右移来取代除以2，用位与运算符代替求余运算符（%）（这个用了如果一个整数和1做与运算的结果是1，则表示该整数的最右边一位是1，否则是0。）

发表于 | 分类于 ，

面试题13: 机器人的运动范围

题目：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

解题思路：回溯体现在迭代中，所以算法肯定是一个迭代的算法，然后，因为统计的是能够达到的格子数量，所以可以为每个格子做一个标记（二维数组），标记为0时表示这个已经是能够达到的格子。，用类属性count统计可达到的格子数量。

代码：

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def __init__(self):
        self.count = 0
    def movingCount(self, threshold, rows, cols):
        # write code here
        arr = [[1 for i in range(cols)] for j in range(rows)]
        self.findway(arr, 0, 0, threshold)
        return self.count
    def findway(self, arr, i, j, k):
        if i < 0 or j < 0 or i >= len(arr) or j >= len(arr[0]):
            return
        tmpi = list(map(int, list(str(i))))
        tmpj = list(map(int, list(str(j))))
        if sum(tmpi) + sum(tmpj) > k or arr[i][j] != 1:
            return
        arr[i][j] = 0
        self.count += 1
        self.findway(arr, i + 1, j, k)
        self.findway(arr, i - 1, j, k)
        self.findway(arr, i, j + 1, k)
        self.findway(arr, i, j - 1, k)

代码思路：arr和count写在迭代外面，是global的值。list(map(int, list(str(i))))这个的意思是，先将字符串转换成str的list，然后用一个map将这些str转成int，然后在生成list。每个findway里面有四个迭代函数，表示向上下左右进行搜索。

面试题14:剪绳子

题目：给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

解题思路：这题可以用贪婪算法来求解。原因如下：

算法：

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def cutRope(self, number):
        # write code here
        if number<2:
            return 0
        if number == 2:
            return 1
        if number ==3:
            return 2
        timesOf3 = number//3
        if number - timesOf3*3 == 1:
            timesOf3 -= 1
        timesOf2 = (number - timesOf3*3)//2
        return pow(3,timesOf3)*pow(2,timesOf2)

算法思路：就是先写出最简单的情况，然后尽量使得3的数量最多，当最后一段可以为4时，就让它为4，而不是3和1。最后就是n个3和m个2。

发表于 | 分类于 ，

面试题11: 旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路：使用二分查找法，一般情况下，这个最小值将数组分成两个部分。二分法有三个很重要的指针，左指针，右指针和中间的指针。这里可以分成三种情况，数组没有真正旋转、数值的左指针和右指针以及中间的指针指向的数字相等、正常二分法情况。数组没有真正旋转的话，直接返回第一个；相等的话就只能一个个找；二分法就二分法地找。二分法的核心是缩小寻找的范围，而缩小寻找的范围的条件又是数组不能有重复的数字。所以这里才会主要分成两种情况，一种就是可以使用二分法的，另一种就是不能分成二分法的。

-*- coding:utf-8 -*-
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
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0
        left = 0
        right = len(rotateArray)-1
        mid = 0
        while(rotateArray[left] >= rotateArray[right]):
            if right-left == 1:
                mid = right
                break
            mid = (left+right)//2
            if rotateArray[right] == rotateArray[left] and rotateArray[right] == rotateArray[mid]:
                return self.MinOrder(rotateArray,left,right)
            if rotateArray[mid] >= rotateArray[left]:
                left = mid
            else:
                right =mid
        return rotateArray[mid]
    def MinOrder(self, num, left, right):
        result = num[left]
        for i in num[left+1:right]:
            if i<result:
                result =i
        return result

算法思路：让mid等于0是让算法简洁，输出逻辑和二分法保持一致。while循环保证是满足二分法的（或者相等的情况）。二分法就是逼近的思想，让两个指针一直在两边，然后往最小值靠。

面试题12:矩阵中的路径

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路：回溯法体现在递归中，回溯就是一个探索路径的过程，探索的顺序是自定的，就像触手一样伸出去，就像深度遍历一样，知道找到一条可行的路径或者根本就不存在符合的条件的路径为止。

-*- coding:utf-8 -*-
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
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        # 将矩阵转成二维数组表示
        x = [list(matrix[i*cols:(i+1)*cols]) for i in range(rows)]
        for i in range(rows):
            for j in range(cols):
                self._dict = {}
                if self.dfs(x, i, j, path):
                    return True
        return False
    def dfs(self, matrix, i, j, p):#四个if语句中i,j边界判断保证了不越界，return保证了去掉不匹配的结果
        if matrix[i][j] == p[0]:
            if not p[1:]:#出口，路径中所有字母都找到
                return True
            matrix[i][j] = ''#先置为空，递归后再改回来，保证了不发生重复
            if i > 0 and self.dfs(matrix, i-1, j, p[1:]):#向上寻找，回溯体现在递归中
                return True
            if i < len(matrix)-1 and self.dfs(matrix, i+1, j ,p[1:]):#向下寻找
                return True
            if j > 0 and self.dfs(matrix, i, j-1, p[1:]):#向左寻找
                return True
            if j < len(matrix[0])-1 and self.dfs(matrix, i, j+1, p[1:]):#向右寻找
                return True
            matrix[i][j] = p[0]
            return False
        else:
            return False

代码思路：首先将矩阵转成二维数组表示，方便后续的遍历。在遍历的过程中要避免数组越界的情况，回溯体现在递归中。

这里有一个小细节：就是not p[1:],这里不能用p[1:] == None ,因为这样会报string下标溢出的错，因为这个情况下，p只剩下最后一位了，p[1:]是不存在的， 后者的写法就溢出了。

发表于 | 分类于 ，

面试题9:用两个栈实现队列

题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

解题思路：Push操作的话其实队列和栈的逻辑是一样的，入口就是第一个stack，主要是pop的话要实现队列的先进先出的逻辑，所以要将stack中已有的node依次pop然后马上push到stack2中。

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def __init__(self):
        self.stack = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack.append(node)
    def pop(self):
        # return xx
        if self.stack2:
            return self.stack2.pop()
        while self.stack:
            self.stack2.append(self.stack.pop())
        return self.stack2.pop() if self.stack2 else None

代码思路：没有什么特殊的情况需要考虑的，就是初始化的时候要生成两个队列。

面试题10:斐波那契数列

题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

解题思路：这是一题用来驳斥递归效率的题目，这题不能简单地使用递归的做法，因为重复的计算太多，浪费太多的计算资源。我们用递归树来分析一下这个复杂度：

可以发现很多的节点是重复的，并且重复的节点数随着n的增大而急剧增大。动态规划就是用来存储这些值来重复加以利用，所以时间上缩短了，但是空间上可能变大？递归问题是从上往下，而动态规划是从下往上。递归问题是从大问题推到小问题，而动态规划是先考虑小问题再考虑大问题。

1
2
3
4
5
6
7
class Solution:
    def fib(self, N: int) -> int:
        a,b = 0,1
        while N:
            a,b  = b,a+b
            N -=1
        return a

算法思路：就是从下往上。

题目二：青蛙跳台阶

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级台阶共需要多少种跳法。

解题思路：这种题目就是要看出它的本质了，感觉有点像知识迁移能力题。

当n=1，有一种跳法

当n=2，一次跳一个跳两次，一次跳两个跳一次，共两种跳法

当n>=2时，n个台阶，设有F（n）种跳法

（1）若第一次选择跳1个台阶，那么剩下的n-1个台阶有F(n-1)种跳法
（2）若第一次选中跳2个台阶，那么剩下的n-2个台阶有F(n-2)种跳法

所以当有n个台阶时 F(n) = F(n-1)+F(n-2)种跳法。

此问题可以归结为斐波那契数列问题（需要注意的是斐波那契数列的第二项是1，此问题当n=2时是2）

引用：https://blog.csdn.net/kuangsonghan/article/details/81414628

发表于 | 分类于 ，

面试题7:重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题思路：这题的大问题和小问题都是一样的，都是先找出根结点，然后再对左边的节点和右边的节点分别进行处理。所以使用递归的方法。

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre or not tin:
            return None
        index = tin.index(pre[0])
        left = tin[:index]
        right = tin[index+1:]
        root = TreeNode(tin[index])
        root.left = self.reConstructBinaryTree(pre[1:1+len(left)],left)
        root.right = self.reConstructBinaryTree(pre[-len(right):],right)
        return root

代码思路：首先构造树的结点类，然后就是用递归的思想去做了，递归出口就是当pre和tin为空。

面试题8:二叉树的下一个节点

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解题思路：这个要分情况讨论，大致可以分成三种情况。一种是二叉树不存在的情况，一种是当前指向的点存在右子树，最后一种是当前指向的点不存在右子树，但是有父节点，当这个指向的点是它的父节点的左节点时，就返回它的父节点，否则将这个指向移到它的父节点，进行下一个循环。

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class TreeLinkNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None
         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if pNode == None:
            return None
        if pNode.right != None:
            pNode = pNode.right
            while pNode.left != None:
                  pNode = pNode.left
            return pNode
        while pNode.next != None:
            proot = pNode.next
            if(proot.left == pNode):
                return proot
            pNode = proot
        return None

代码思路：首先排除特殊情况（不存在二叉树），然后就按解题思路中的情况依次写下来。

发表于 | 分类于 ，

面试题5:替换空格

题目：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

解题思路：遍历替换的时间复杂度为$O(n^2)$,所以简单的遍历肯定是行不通的。在python的解法中有两种，一种是直接使用$replace()$但是要注意，这个不能直接修改原数组，所以要写另一个变量来引用。另一种解法是用正则表达式，我不是很熟悉，但是后者的运行时间比前者要来得短，本着越短越好的原则，我们用后一种方法。

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        import re
        ret = re.compile(' ')
        k = ret.sub('%20', s)
        return k

算法思路：就两步，一个是compile，另一个是sub。暂时没理解是啥意思。

面试题6:从尾到头打印链表

题目：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

解题思路：可以额外使用一个栈来实现，先入后出。

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        out = []
        re_out = []
        while listNode != None:
                out.append(listNode.val)
                listNode = listNode.next
        while out :
            re_out.append(out.pop())
        return re_out

算法思路：这里不用考虑额外情况，当空时，输出自然为空。所以直接先将链表装入链中，然后再把链pop出来，导入re_out中，返回即可。

发表于 | 分类于 ，

面试题4: 二维数组中的查找

题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路：还是一样，我们考虑的是要复杂度越小越好，所以打消遍历整个数组的念头吧。我们可以通过比较选取的点和我们要找的点的大小关系，来排除候选的点（排除一整行或者是一整列），直到找到目标或者无候选点。这个遍历的起始位置只能选择矩阵的左下角或者右上角，只有这样才能排除候选点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def searchMatrix(self, matrix, target):
        # an empty matrix obviously does not contain `target` (make this check
        # because we want to cache `width` for efficiency's sake)
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False

        # cache these, as they won't change.
        height = len(matrix)
        width = len(matrix[0])

        # start our "pointer" in the bottom-left
        row = height-1
        col = 0

        while col < width and row >= 0:
            if matrix[row][col] > target:
                row -= 1
            elif matrix[row][col] < target:
                col += 1
            else: # found it
                return True
        
        return False

代码思路：还是一样，先排除一下异常的情况，行数(len(matrix))和列数(len(matrix[0]))都不能为零。然后就是按照大小关系去排除（移动）了。

形象的过程可以看：leetcode

发表于 | 分类于 ，

一.面试题3：数组中重复的数字

题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

解题思路：所有的题目都是冲着复杂度越小越好的目标去的，所以空间复杂度就应该是O（1），而时间复杂度就应该是O（n）。这题本身就有点可以投巧的点，就是长度为n，而且所有数字都在0～n-1的范围内，所以在没有重复数字的情况下，应该是数组的每个下标都与它对应的值相等。因此下面的算法思路就是遍历整个数组，尽量让所有的数都在其应该的位置（即下标值等于对应值），而实现这一步的做法就是交换两个数的位置。若发现要交换的两个数相等时，就发现了一个重复的数字了。

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if numbers == None or len(numbers) <= 0:
            return False
        for i in range(len(numbers)):
            if numbers[i] < 0 or numbers[i] > len(numbers)-1:
                return False
        for i in range(len(numbers)):
            while numbers[i] != i :
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True
                a = numbers[i]
                numbers[i] = numbers[a]
                numbers[a] = a
        return False

代码思路：首先排除一些异常的情况，也就是前面两段：排除输入的数组为空以及数组长度等于或小于零的情况，排除数组的值超出限定范围的情况。然后就是主体部分，直接遍历整个数组，这里就不多赘述啦，看解题思路。

——————————————————————————————————————————————————

题目二：不修改数组找出重复的数字

题目：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

解题思路：这一题有两种做法，一种是二分法， 另一种是快慢指针。我这里先讲讲快慢指针的做法吧，感觉这个做法挺常看到的。尤其是在数组这类题中。快慢指针的做法里面有一个很关键的概念：环。

要理解快慢指针的问题的话，有几个关键的问题需要理解：1.slow和fast为什么会在环中相遇时，多走的n步满足n%c==0? 2.为什么finder和slow相遇在入口？

回答：1.首先假设，起点到环的入口长度为m，环的周长为c，在fast和slow相遇时slow走了n步。则fast走了2n步，fast比slow多走了n步。首先走的n步是m+（在环上走的长度），剩余的n步就是一直在绕圈了，所以才会得出那个结论。2.fast和slow相遇时，slow在环中行进的距离是n-m，其中n%c==0。这时我们再让slow前进m步——也就是在环中走了n步了（此时finder也走了m步，到了环的入口）。而n%c==0即slow在环里面走的距离是环的周长的整数倍，就回到了环的入口了，而入口就是重复的数字。

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findDuplicate(self, nums: List[int]) -> int:
    slow=0
    fast=0
    while(1):
        slow=nums[slow]
        fast=nums[nums[fast]]
        if(slow==fast):
            break
    find=0
    while(1):
        find=nums[find]
        slow=nums[slow]
        if(find==slow):
            return find

代码思路：首先第一个循环是找出fast和slow相遇的位置，然后第二个循环是找出环的入口位置。注：这里没有写特殊情况的处理，可能是测试的例子里面没有包括吧，在leetcode跑过了。在第一个循环中要注意，循环条件是不能写成while slow != fast 的因为初始条件是slow==fast=0的，所以两个指针就启动不了了。

注：这两题的前提假设都是不同的，如果使用第二小题的思路去解第一小题的话会出现问题，因为环在开始的时候就出现了，这就直接默认了数组第一个是重复数字，但显然这个结论是错误的。