41、数组

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        if s is None:
            return ""
        alist = list(s.split(" "))
        return " ".join(alist[::-1])

解题思路：列表的翻转

42、数组

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

# -*- coding:utf-8 -*-
class Solution:
    def IsContinuous(self, numbers):
        # write code here
        if len(numbers) == 0:
            return False
        numbers = sorted(numbers)
        count_0 = 0

        for i in range(0,len(numbers)-1):
            if numbers[i] == 0:
                count_0 += 1
            else:
                delta = numbers[i+1] - numbers[i]
                if delta < 1:
                    return False
                elif delta > 1:
                    count_0 = count_0 - delta + 1
                    if count_0 < 0:
                        return False
        return True

解题思路：大小王可以视作0，然后把数组排序。从头开始读数组，统计0的个数，然后读后面的数字，相邻两个数字之间如有间隔差值，则用0的个数来填补，如果后面的数字本来就是连续的则肯定ok，如果中间有不连续且刚好能被0填补，则也是顺子。

43、环、数组

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

# -*- coding:utf-8 -*- （140ms、5724k）
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n == 0 or m == 0:
            return -1
        a = [i for i in range(n)]
        while (len(a) > 1):
            r = int((m - 1) % len(a))
            a.remove(a[r])
            a = a[r:] + a[:r]
        return a[0]

解题思路：我自己的解法就是找到，删除，调整数组。速度有点慢

另一种就是只保存删除的索引，效率较高：

class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n < 1:
            return -1
        con = list(range(n))
        final = -1
        start = 0
        while con:
            k = (start + m - 1) % n
            final = con.pop(k)
            n -= 1
            start = k
        return final

44、加法

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

# -*- coding:utf-8 -*-
class Solution:
    def Sum_Solution(self, n):
        ans = n
        temp = ans and self.Sum_Solution(n-1)
        ans = ans + temp
        return ans

解题思路：递归。注意 python 的写法。当and和or等短路运算符，用作普通值而不是布尔值时，短路运算符的返回值是最后一次评估的参数。也就是说下面的句子中，如果ans为0，则temp为0， 如果ans不为0， 则temp就是递归了之后的值。

通过位运算的方法：

首先看十进制是如何做的： 5+7=12，三步走

第一步：相加各位的值，不算进位，得到2。

第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。

第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。

同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111

第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。

第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111) << 1。

第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010) << 1。 继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。

public class Solution {
    public int Add(int num1,int num2) {
        while (num2!=0) {
            int temp = num1^num2;
            num2 = (num1&num2)<<1;
            num1 = temp;
        }
        return num1;
    }
}

# -*- coding:utf-8 -*-
class Solution:
    def Add(self, a, b):
        while(b):
            a, b = (a^b) & 0xFFFFFFFF,((a&b)<<1) & 0xFFFFFFFF
        return a if a<=0x7FFFFFFF else ~(a^0xFFFFFFFF)

补充一下python位运算：

x >> y # 返回 x 向右移 y 位得到的结果

x << y # 返回 x 向左移 y 位得到的结果

x & y # 与操作，xy对应的每一位，只有都为1时才为1

x | y # 或操作，xy对应的每一位，只有都为0时才为0

~x # 按位取反操作，x的每一位如果为0则变为1，如果为1则变为0，从十进制来看，结果是 -x - 1（例如，~8 = -9）

x ^ y # 异或运算，xy对应的每一位，数字不同则为1，数字相同则为0

45、字符串

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

# -*- coding:utf-8 -*-
class Solution:
    def StrToInt(self, s):
        # write code here
        minus = 1
        number = 0
        if not s:
            return number
        if s[0] == '+':
            if len(s) > 1:
                s = s[1:]
            else:
                return 0
        elif s[0] == '-':
            minus = -1
            if len(s) > 1:
                s = s[1:]
            else:
                return 0
        for i in range(0, len(s)):
            if '0' <= s[i] <= '9':
                number = number * 10 + ord(s[i]) - ord('0')
            else:
                return 0
        return number * minus

解题思路：记得ord(‘0’)=48,ord(‘a’)=97,ord(‘A’)=65

46、数组

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        dis = {}
        for i in list(numbers):
            if i not in dis:
                dis[i] = 1
            else:
                dis[i] += 1
        j = 0
        for i in dis:
            if dis[i] == 1:
                continue
            elif dis[i] > 1:
                j = i
                break
        if j == 0:
            return False 
        else:
            duplication[0] = j
        return True

解题思路：hash表

47、数组

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

class Solution:
def multiply(self, A):
    ifnot A:
        return []
    b = [1] * len(A)
    for i in range(1,len(A)):
        b[i] = b[i] * A[i-1]
    tmp = 1
    for i in range(len(A)-2,1,-1):
        tmp = tmp * A[i+1]
        b[i] = b[i] *tmp
    return b

解题思路：将乘积分为两部分。

48、字符串匹配

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

# -*- coding:utf-8 -*-
class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # 如果s与pattern都为空，则True
        if len(s) == 0 and len(pattern) == 0:
            return True
        # 如果s不为空，而pattern为空，则False
        elif len(s) != 0 and len(pattern) == 0:
            return False
        # 如果s为空，而pattern不为空，则需要判断
        elif len(s) == 0 and len(pattern) != 0:
            # pattern中的第二个字符为*，则pattern后移两位继续比较
            if len(pattern) > 1 and pattern[1] == '*':
                return self.match(s, pattern[2:])
            else:
                return False
        # s与pattern都不为空的情况
        else:
            # pattern的第二个字符为*的情况
            if len(pattern) > 1 and pattern[1] == '*':
                # s与pattern的第一个元素不同，则s不变，pattern后移两位，相当于pattern前两位当成空
                if s[0] != pattern[0] and pattern[0] != '.':
                    return self.match(s, pattern[2:])
                else:
                    # 如果s[0]与pattern[0]相同，且pattern[1]为*，这个时候有三种情况
                    # pattern后移2个，s不变；相当于把pattern前两位当成空，匹配后面的
                    # pattern后移2个，s后移1个；相当于pattern前两位与s[0]匹配
                    # pattern不变，s后移1个；相当于pattern前两位，与s中的多位进行匹配，因为*可以匹配多位
                    return self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern)
            # pattern第二个字符不为*的情况
            else:
                if s[0] == pattern[0] or pattern[0] == '.':
                    return self.match(s[1:], pattern[1:])
                else:
                    return False

49、类似字符串匹配

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

# -*- coding:utf-8 -*-
class Solution:
    # s字符串
    def isNumeric(self, s):
        # 标记符号、小数点、e是否出现过
        sign = False
        decimal = False
        has_e = False
        for i in range(len(s)):
            if s[i] == 'e' or s[i] == 'E':
                if i == len(s) - 1:
                    return False  # E后面必须跟数字，E不可以在字符串结尾
                if has_e:
                    return False  # 不可以出现两个E
                has_e = True
            elif s[i] == '+' or s[i] == '-':
                if sign and (s[i-1] != 'e' and s[i-1] != 'E'):
                    return False  # 如果是第二次出现符号，符号必须跟在E之后
                if (not sign) and (i > 0) and (s[i-1] != 'e' and s[i-1] != 'E'):
                    return False  # 如果第一次出现符号，且不是在开头出现，则必须紧跟在E之后
                sign = True
            elif s[i] == '.':
                if has_e or decimal:
                    return False  # E后面不能出现小数点，或小数点不能出现两次
                decimal = True
            elif s[i] < '0' or s[i] > '9':
                return False  # 不合法字符
        return True

50、hash

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

class Solution:
    def __init__(self):
        self.stream = []
        self.counter = {}
    # 返回对应char
    def FirstAppearingOnce(self):
        for c in self.stream:
            if self.counter[c] == 1:
                return c
        return '#'
    def Insert(self, char):
        if char in self.counter:
            self.counter[char] += 1
        else:
            self.counter[char] = 1
        self.stream.append(char)

51、环、链表

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead:
            return None
        slow = pHead
        fast = pHead
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow2 = pHead
                while slow2 != slow:
                    slow = slow.next
                    slow2 = slow2.next
                return slow

解题思路：快慢指针法，当slow与fast相遇时，slow走过的就是环的长度。

52、链表

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if (not pHead) or (not pHead.next):
            return pHead
        head = ListNode(0)
        head.next = pHead
        pre = head
        last = head.next
        while last:
            if last.next and last.val == last.next.val:
                while last.next and last.val == last.next.val:
                    last = last.next
                pre.next = last.next
                last = last.next
            else:
                pre = pre.next
                last = last.next
        return head.next    

解题思路：注意构建新的链表。

53、树

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

# -*- coding:utf-8 -*-
# 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 not pNode:
            return None
        if pNode.right != None:
            r = pNode.right
            while r and r.left != None:
                r = r.left
        elif pNode.next != None:
            if pNode.left == None:
                if pNode.next.left == pNode:
                    r = pNode.next
                elif pNode.next.next.left != pNode.next:
                    return None
                else:
                    r = pNode.next.next
            else:
                r = pNode.next
        else:
            r = None
        return r

解题思路：要考虑多种情况

54、树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        if not pRoot:
            return True
        else:
            return self.check(pRoot.left, pRoot.right)
    def check(self, left, right):
        if (not left) and (not right):
            return True
        elif not(left and right):
            return False
        if left.val != right.val:
            return False
        return self.check(left.left, right.right) and self.check(right.left, left.right)

解题思路：递归加判断。

55、树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        stack = [pRoot]
        res = []
        while stack:
            tmp = []
            for i in range(len(stack)):
                t = stack.pop(0)
                tmp.append(t.val)
                if t.left != None:
                    stack.append(t.left)
                if t.right != None:
                    stack.append(t.right)
            res.append(tmp)
        for i in range(len(res)):
            if i & 1 == 1:
                res[i] = res[i][::-1]
        return res

解题思路：先层次遍历，再转换。

56、树

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        stack = [pRoot]
        res = []
        while stack:
            tmp = []
            for i in range(len(stack)):
                t = stack.pop(0)
                tmp.append(t.val)
                if t.left != None:
                    stack.append(t.left)
                if t.right != None:
                    stack.append(t.right)
            res.append(tmp)
        return res

解题思路：就是层次遍历。

57、树

请实现两个函数，分别用来序列化和反序列化二叉树

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.flag = -1
    def Serialize(self, root):
        # write code here
        if not root:
            return '#,'
        return str(root.val)+','+self.Serialize(root.left)+self.Serialize(root.right)
    def Deserialize(self, s):
        # write code here
        self.flag += 1
        l = s.split(',')
        if self.flag >= len(s):
            return None
        root = None
        if l[self.flag] != '#':
            root = TreeNode(int(l[self.flag]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root

解题思路：递归前序遍历二叉树，对每个节点的孩子如果遇到空就以#来代替，最终得到一个字符串。读取字符串，当前字符作为根，下一个字符作为当前的左孩子，依此递归进行前序遍历，恢复树结构。

58、二叉排序树

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def __init__(self):
        self.cur = 0
    def KthNode(self, pRoot, k):
        # write code here
        if k <= 0:
            return None
        if pRoot == None:
            return None
        left_val = self.KthNode(pRoot.left,k)
        if left_val:
            return left_val
        self.cur += 1
        if self.cur == k:
            return pRoot
        right_val = self.KthNode(pRoot.right, k)
        if right_val:
            return right_val
        return None

解题思路：递归左子树，并判断有无返回节点。如果有，停止递归，返回所要返回的节点；当左子树没有返回节点时，判断当前的根节点是不是第k个遍历到的值（即第k大）。如果是，则返回该节点，停止递归；当左子树和根节点都没有返回节点时，递归右子树，并判断有无返回节点。如果有，停止递归，返回所要返回的节点。

59、堆

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.arr=[]
    def Insert(self, num):
        self.arr.append(num)
        self.arr.sort()
    def GetMedian(self,fuck):
        length=len(self.arr)
        return self.arr[length//2] if length%2==1 else (self.arr[length//2]+self.arr[length//2-1])/2.0

这是一般人的思想，另一种是考虑用堆；

import math
import heapq

class Solution:
    nums = []
    def Insert(self, num):
        heapq.heappush(self.nums, num)

    def GetMedian(self):
        mid = math.ceil(len(self.nums)/2)
        return (heapq.nlargest(mid, self.nums)[-1] + heapq.nsmallest(mid, self.nums)[-1])/2.0

60、数组

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size <= 0:
            return []
        left = 0
        right = size - 1
        res = []
        while right <= len(num) - 1:
            tmp = num[left:right+1]
            m = max(tmp)
            res.append(m)
            left += 1
            right += 1
        return res

61、递归、回溯、匹配

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

class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        if not matrix and rows <= 0 and cols <= 0 and path == None:
            return False
        # 模拟的字符矩阵
        markmatrix = [0] * (rows * cols)
        pathlength = 0
        # 从第一个开始递归，当然第一二个字符可能并不位于字符串之上，所以有这样一个双层循环找起点用的，一旦找到第一个符合的字符串，就开始进入递归，
        # 返回的第一个return Ture就直接跳出循环了。
        for row in range(rows):
            for col in range(cols):
                if self.hasPathCore(matrix, rows, cols, row, col, path, pathlength, markmatrix):
                    return True
        return False
    def hasPathCore(self, matrix, rows, cols, row, col, path, pathlength, markmatrix):
        # 说明已经找到该路径，可以返回True
        if len(path) == pathlength:
            return True
        hasPath = False
        if row >= 0 and row < rows and col >= 0 and col < cols and matrix[row * cols + col] == path[pathlength] and not \
                markmatrix[row * cols + col]:
            pathlength += 1
            markmatrix[row * cols + col] = True
            # 进行该值上下左右的递归
            hasPath = self.hasPathCore(matrix, rows, cols, row - 1, col, path, pathlength, markmatrix) \
                      or self.hasPathCore(matrix, rows, cols, row, col - 1, path, pathlength, markmatrix) \
                      or self.hasPathCore(matrix, rows, cols, row + 1, col, path, pathlength, markmatrix) \
                      or self.hasPathCore(matrix, rows, cols, row, col + 1, path, pathlength, markmatrix)
            # 对标记矩阵进行布尔值标记
            if not hasPath:
                pathlength -= 1
                markmatrix[row * cols + col] = False
        return hasPath

62、递归、回溯

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

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        markmatrix = [False] * (rows * cols)
        count = self.GetNum(threshold, rows, cols, 0, 0, markmatrix)
        return count
    def GetNum(self, threshold, rows, cols, row, col, markmatrix):
        count = 0
        if self.GetSum(threshold, rows, cols, row, col, markmatrix):
            markmatrix[row * cols + col] = True
            count = 1 + self.GetNum(threshold, rows, cols, row - 1, col, markmatrix) + \
                    self.GetNum(threshold, rows, cols, row, col - 1, markmatrix) + \
                    self.GetNum(threshold, rows, cols, row + 1, col, markmatrix) + \
                    self.GetNum(threshold, rows, cols, row, col + 1, markmatrix)
        return count
    def GetSum(self, threshold, rows, cols, row, col, markmatrix):
        if row >= 0 and row < rows and col >= 0 and col < cols and self.getDigit(row) + self.getDigit(
                col) <= threshold and not markmatrix[row * cols + col]:
            return True
        return False
    def getDigit(self, number):
        sumNum = 0
        while number > 0:
            sumNum += number % 10
            number = number // 10
        return sumNum

解题思路：回溯法，递归，注意判断条件。