二维数组中的查找
Q: 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
A: 从左上或者右下开始查找。从右上开始查找：如果数组中的数比这个整数大，向左移动一位，如果数组中的数比这个数小，向下移动一位。
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if array == []:
return False
num_row = len(array)
num_col = len(array[0])
i = num_col - 1
j = 0
while i >= 0 and j < num_row:
if array[j][i] > target:
i -= 1
elif array[j][i] < target:
j += 1
else:
return True
替换空格
Q: 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
A: 1. 先计算最终需要给出的长度，然后建立两个指针p1,p2，p1指向原始字符串的末尾，p2指向替换后的字符串的末尾。同时移动p1,p2, 将p1指的内容逐个复制到p2, 当p1遇到空格时，在p2处插入 %20， p1向前移动一个位置，p2向前移动3个位置，当p1和p2位置重合时，全部替换完成。
2. python中可以利用append() [O(1)]，新建list，一次遍历，碰到空格就添加 %20，否则就添加原始字符串s内容。
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
if not isinstance(s, str) or len(s) <= 0 or s == None:
return ''
spaceNum = 0
for i in s:
if i == " ":
spaceNum += 1
newStrLen = len(s) + spaceNum * 2
newStr = newStrLen * [None]
indexOfOriginal, indexOfNew = len(s) - 1, newStrLen - 1
while indexOfNew >= 0 and indexOfOriginal <= indexOfNew:
if s[indexOfOriginal] == ' ':
newStr[indexOfNew - 2: indexOfNew + 1] = ['%', '2', '0']
indexOfNew -= 3
indexOfOriginal -= 1
else:
newStr[indexOfNew] = s[indexOfOriginal]
indexOfNew -= 1
indexOfOriginal -= 1
return ''.join(newStr)
从尾到头打印链表
Q: 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
A: 从头到尾遍历链表，并用一个栈存储每个节点的值，之后出栈输出，用insert()，一直在index=0的位置插入遍历的值。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
if not listNode:
return []
result =[]
while listNode:
result.insert(0, listNode.val)
listNode = listNode.next
return result
重建二叉树
Q: 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
A: 利用二叉树前序遍历和中序遍历的特点，前序遍历的第一个值一定为根节点，对应于中序遍历中间的一个点，在中序遍历中，该点左侧的值为根节点的左子树，右侧的值为根节点的右子树。这时可以利用递归，取前序遍历的[1:i+1]和中序遍历的[:i]作为对应的左子树继续上一个过程，取前序遍历的[i+1:]和中序遍历的[i+1:]对应与右子树继续上一个过程，重建二叉树。
# -*- coding:utf-8 -*-
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 and not tin:
return None
root = TreeNode(pre[0])
if set(pre) != set(tin):
return None
i = tin.index(pre[0])
root.left = self.reConstructBinaryTree(pre[1:i+1],tin[:i])
root.right = self.reConstructBinaryTree(pre[i+1:], tin[i+1:])
return root
用两个栈实现队列
Q: 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
A: 两个栈stack1和stack2， push的时候直接push进stack1，pop时需要判断stack1和stack2中的情况。如果stack2不为空的话，直接从stack2中pop，如果stack2为空，把stack1中的值push到stack2中，然后再pop stack2中的值。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
# write code here
self.stack1.append(node)
def pop(self):
# return xx
if len(self.stack1) == 0 and len(self.stack2) == 0:
return
elif len(self.stack2) == 0:
while len(self.stack1) > 0:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
旋转数组的最小数字
Q: 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
A: 二分查找的变形，旋转数组的首元素肯定不小于旋转数组的尾元素，找一个中间点，如果中间点比首元素大，说明最小数字在中间点后面，如果中间点比尾元素小，说明最小数字在中间点前面。然后循环。 但是在一次循环中，首元素小于尾元素，说明该数组是排序的，首元素就是最小数字，如果出现首元素、尾元素、中间值三者相等，则只能在此区域中顺序查找。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
front = 0
rear = len(rotateArray) - 1
minVal = rotateArray[0]
if rotateArray[front] < rotateArray[rear]:
return rotateArray[front]
else:
while (rear - front) > 1:
mid = (front + rear) // 2
if rotateArray[mid] >= rotateArray[front]:
front = mid
elif rotateArray[mid] <= rotateArray[rear]:
rear = mid
elif rotateArray[front] == rotateArray[rear] == rotateArray[mid]:
for i in range(1, len(rotateArray)):
if rotateArray[i] < minVal:
minVal = rotateArray[i]
rear = i
minVal = rotateArray[rear]
return minVal
斐波那契数列
Q: 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
A: 不使用递归实现数列，需要把前面两个数字存入在一个数组中,实际一直在更新。
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
tempArray = [0,1]
if n >= 2:
for i in range(2, n+1):
tempArray[i%2] = tempArray[0] + tempArray[1]
return tempArray[n%2]
跳台阶
Q: 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
A: 斐波那契数列的变形， (递推公式)
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
tempArray = [1, 2]
if number >= 3:
for i in range(3, number+1):
tempArray[(i+1)%2] = tempArray[0] + tempArray[1]
return tempArray[(number + 1)%2]
变态跳台阶
Q: 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
A: 斐波那契数列的变形。 (递推求解)
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
ans = 1
if number >= 2:
for i in range(number-1):
ans = ans * 2
return ans
矩形覆盖
Q: 我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形，总共有多少种方法？
A: 依然是斐波那契数列的变形。代码参考跳台阶。
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
tempArray = [1,2]
if number >= 3:
for i in range(3,number+1):
tempArray[(i+1)%2] = tempArray[0] + tempArray[1]
return tempArray[(number+1)%2]
二进制中1的个数
Q: 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
A: 每个非零整数n和n-1进行按位与运算，整数n的二进制中，最右边的1就会变成0，利用循环，计算经过几次运算二进制变成0，就有几个1。
class Solution:
def NumberOf1(self, n):
# write code here
count = 0
if n < 0:
n = n & 0xffffffff
while n != 0:
count += 1
n = (n - 1) & n
return count
数值的整数次方
Q: 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
A: 如果用常规的算法，要注意：1.指数为负数的时候，2.底数为零且指数为负数的时候，这种情况的时候，不能直接通过底数==0来判断，计算机内表示小数有误差，只能判断他们的差的绝对值是不是在一个很小的范围内。 所以用递归好一点。 利用右移一位实现除2运算，用&1 运算，判断是否为奇数，能提高效率。
class Solution:
def Power(self, base, exponent):
# write code here
try:
ret = self.power_value(base, abs(exponent))
if exponent < 0:
return 1.0 / ret
except ZeroDivisionError:
print('Error: base is zero')
else:
return ret
def power_value(self,base, exponent):
if exponent == 0:
return 1
if exponent == 1:
return base
ret = self.power_value(base, exponent >> 1)
ret *= ret
if exponent & 1 == 1:
ret *= base
return ret
调整数组顺序使奇数位于偶数前面
Q: 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
A: 函数的扩展功能。把函数中的判断条件拿出来，写成一个函数。奇数位于偶数前面的情况，类似于快排，头尾各设置一个指针，头指针为奇数则后移，尾指针为偶数则前移。但是快排不稳定，会打破相对位置。所以用python可以一行搞定： lambda大法。
class Solution:
def reOrderArray(self, array):
# write code here
return sorted(array,key=lambda c:c%2,reverse=True)
链表中倒数第k个结点
Q: 输入一个链表，输出该链表中倒数第k个结点。
A: 设置两个指针指向头节点，第一个指针向前走k-1步，走到第k个结点，此时，第二个指针和第一个指针同时移动，当第一个指针到尾节点的时候，第二个指针指向倒数第k个结点，注意链表为空，k为0，k大于链表的长度的情况
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
if head == None or k <= 0:
return None
pAhead = head
pBhead = None
for i in range(k-1):
if pAhead.next != None:
pAhead = pAhead.next
else:
return None
pBhead = head
while pAhead.next != None:
pAhead = pAhead.next
pBhead = pBhead.next
return pBhead
反转链表
Q: 输入一个链表，反转链表后，输出新链表的表头。
A: 主要注意当头结点为空或者整个链表只有一个结点时，翻转后的链表断裂，返回的翻转之后的头节点不是原来的尾节点。所以需要一个翻转后的头节点，一个指向当前结点的指针，两个分别指向当前结点的前后结点的指针，防止断裂。也可以使用递归。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
pReversedHead = None
pNode = pHead
pPrev = None
while pNode != None:
pNext = pNode.next
if pNext == None:
pReversedHead = pNode
pNode.next = pPrev
pPrev = pNode
pNode = pNext
return pReversedHead
合并两个排序的链表
Q: 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
A: 每个链表建立一个指针，合并时，比较头节点大小，小的作为合并后链表的头节点，再比较剩余部分和另一个链表的头节点，取小的，然后一直循环此过程。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
if pHead1 == None:
return pHead2
if pHead2 == None:
return pHead1
pMergeHead = None
if pHead1.val < pHead2.val:
pMergeHead = pHead1
pMergeHead.next = self.Merge(pHead1.next,pHead2)
else:
pMergeHead = pHead2
pMergeHead.next = self.Merge(pHead1,pHead2.next)
return pMergeHead
树的子结构
Q: 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
A: 在树A中查找和树B根节点一致的值，然后判断树A中以该节点为根节点的子树，是不是和树B有相同的结构。可以通过递归实现。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
result = False
if pRoot1 != None and pRoot2 != None:
if pRoot1.val == pRoot2.val:
result = self.DoesTree1haveTree2(pRoot1,pRoot2)
if not result:
result = self.HasSubtree(pRoot1.left,pRoot2)
if not result:
result = self.HasSubtree(pRoot1.right,pRoot2)
return result
def DoesTree1haveTree2(self,pRoot1,pRoot2):
if pRoot2 == None:
return True
if pRoot1 == None:
return False
if pRoot1.val != pRoot2.val:
return False
return self.DoesTree1haveTree2(pRoot1.left, pRoot2.left) and self.DoesTree1haveTree2(pRoot1.right, pRoot2.right)
二叉树的镜像
Q:操作给定的二叉树，将其变换为源二叉树的镜像。
A: 先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的子节点，当交换完所有非叶节点的左右子节点后，得到树的镜像。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
if root == None:
return
if root.left == None and root.right == None:
return root
ptemp = root.left
root.left = root.right
root.right = ptemp
self.Mirror(root.left)
self.Mirror(root.right)
顺时针打印矩阵
Q: 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： [[1 2 3 4], [5 6 7 8], [9 10 11 12], [13 14 15 16]] 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
A: 首先判断每一圈开始时的坐标点，是否小于行数的一半且小于列数的一半。打印的时候从左到右打印，从上到下打印(至少两行)，从右到左打印(至少两行两列)，从下到上打印四种情况(至少三行两列)。除了从左到右打印一定发生，其他三种情况都要判断发生条件。
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
if not matrix:
return []
rows = len(matrix)
columns = len(matrix[0])
start = 0
result = []
while rows > start * 2 and columns > start * 2:
self.PrintMatrixInCircle(matrix, columns, rows, start,result)
start += 1
return result
def PrintMatrixInCircle(self, matrix, columns, rows,start,result):
endX = columns - 1 - start
endY = rows - 1 - start
# 从左到右打印一行
for i in range(start, endX+1):
#number = matrix[start][i]
result.append(matrix[start][i])
# 从上到下打印一行
if start < endY:
for i in range(start+1, endY+1):
#number = matrix[i][endX]
result.append(matrix[i][endX])
# 从右到左打印一行
if start < endX and start < endY:
for i in range(endX-1, start-1, -1):
#number = matrix[endY][i]
result.append(matrix[endY][i])
# 从下到上打印一行
if start < endX and start < endY-1:
for i in range(endY-1, start, -1):
#number = matrix[i][start]
result.append(matrix[i][start])
包含min函数的栈
Q: 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））
A: 建立一个辅助栈，每次都把最小值压入辅助栈，这样辅助栈的栈顶一直是最小元素。当数据栈中，最小值被弹出时，同时弹出辅助栈的栈顶元素。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, node):
# write code here
self.stack.append(node)
if self.minStack == [] or node < self.min():
self.minStack.append(node)
else:
temp = self.min()
self.minStack.append(temp)
def pop(self):
# write code here
if self.stack == None or self.minStack == None:
return None
self.minStack.pop()
self.stack.pop()
def top(self):
# write code here
return self.stack[-1]
def min(self):
# write code here
return self.minStack[-1]
栈的压入、弹出序列
Q: 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
A: 建立一个辅助栈，把push序列的数字依次压入辅助栈，每次压入后，比较辅助栈的栈顶元素和pop序列的首元素是否相等，相等的话，就推出pop序列的首元素和辅助栈的栈顶元素，若最后辅助栈为空，则push序列可以对应于pop序列。
# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
if pushV == [] or popV == []:
return False
stack = []
for i in pushV:
stack.append(i)
while len(stack) and stack[-1] == popV[0]:
stack.pop()
popV.pop(0)
if len(stack):
return False
else:
return True
从上往下打印二叉树
Q: 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
A: 引入一个队列，每次打印一个节点的时候，如果该节点有子节点，则把该节点的子节点放到一个队列的末尾，取出队列头部的最早进入队列的节点。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if root is None:
return []
queue = []
result = []
queue.append(root)
while len(queue) > 0:
currentRoot = queue.pop(0)
result.append(currentRoot.val)
if currentRoot.left:
queue.append(currentRoot.left)
if currentRoot.right:
queue.append(currentRoot.right)
return result
二叉搜索树的后序遍历序列
Q: 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
A: 根据后序遍历的特点，尾元素一定是根节点，同时小于尾元素的值时左子树，大于尾元素的值时右子树。且序列前半部分小于尾元素，后半部分大于尾元素，可以将序列划分为左子树序列和右子树序列，然后递归。
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if sequence == []:
return False
length = len(sequence)
root = sequence[-1]
for i in range(length):
if sequence[i] > root:
break
for j in range(i, length):
if sequence[j] < root:
return False
left = True
if i > 0:
left = self.VerifySquenceOfBST(sequence[:i])
right = True
if j < length - 1:
right = self.VerifySquenceOfBST(sequence[i:length-1])
return left and right
二叉树中和为某一值的路径
Q: 输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
A: 用前序遍历的方式访问二叉树的节点，当访问到一个节点时，将该节点加到路径中，并累加节点的值。直到访问到符合要求的节点或者访问到叶节点，然后递归访问该节点的父节点，在函数退出时要删除当前节点，并减去当前节点的值。实际上是一个出栈和入栈的过程。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
if not root or root.val > expectNumber:
return []
if not root.left and not root.right and root.val == expectNumber:
return [[root.val]]
else:
expectNumber -= root.val
left = self.FindPath(root.left,expectNumber)
right = self.FindPath(root.right,expectNumber)
result = [[root.val]+i for i in left]
for i in right:
result.append([root.val]+i)
return sorted(result, key=lambda x:-len(x))
复杂链表的复制
Q: 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
A: 复制原始链表的每个结点，将复制的结点链接在其原始结点的后面，然后将复制后的链表中的复制结点的random指针，指向被复制结点的random指针指向结点的下一个结点，最后拆分链表，拆分成原始链表结点组成的新链表和复制结点组成的复制链表。
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
return None
pNode = pHead
while pNode:
pClone = RandomListNode(pNode.label)
pClone.next = pNode.next
pNode.next = pClone
pNode = pClone.next
pNode = pHead
while pNode:
pClone = pNode.next
if pNode.random != None:
pClone.random = pNode.random.next
pNode = pClone.next
pNode = pHead
pCloneHead = pCloneNode = pNode.next
pNode.next = pCloneHead.next
pNode = pNode.next
while pNode:
pCloneNode.next = pNode.next
pCloneNode = pCloneNode.next
pNode.next = pCloneNode.next
pNode = pNode.next
return pCloneHead
二叉搜索树与双向链表
Q: 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
A: 左右子树分治，中序遍历，递归实现。根据二叉搜索树的的特点，根节点的左边连接左子树最右边的节点，根节点的右边连接右子树最左边的节点。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Convert(self, pRootOfTree):
# write code here
if not pRootOfTree:
return None
if not pRootOfTree.left and not pRootOfTree.right:
return pRootOfTree
self.Convert(pRootOfTree.left)
left = pRootOfTree.left
if left:
while left.right:
left = left.right
pRootOfTree.left = left
left.right = pRootOfTree
self.Convert(pRootOfTree.right)
right = pRootOfTree.right
if right:
while right.left:
right = right.left
pRootOfTree.right = right
right.left = pRootOfTree
while pRootOfTree.left:
pRootOfTree = pRootOfTree.left
return pRootOfTree
字符串的排列
Q: 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
A: 固定第一个元素，求出后面所有字符的排列，重新固定第一个元素，再求后面字符的排列，依次换第一个元素，典型递归问题。
# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
# write code here
if not ss:
return []
if len(ss) == 1:
return list(ss)
charList = list(ss)
charList.sort()
pStr = []
for i in range(0,len(charList)):
if i > 0 and charList[i] == charList[i-1]:
continue
temp = self.Permutation(''.join(charList[:i])+''.join(charList[i+1:]))
for j in temp:
pStr.append(charList[i] + j)
return pStr
数组中出现次数超过一半的数字
Q: 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0
A: 第一种思路：出现次数超过一半的数字，一定位于数组中间的位置，找到数组中间位置的数字，然后再顺序检索这个数字的出现次数是否超过一半；第二种思路：出现次数超过一半的数，它的出现次数比其他所有数字出现次数的总和还要多，保存两个值，数组中的数字和它的出现次数。如果下一个数字等于该数字，那么出现次数加一，如果不相等，次数减一，当次数为0时，保存下一个数字，并重置出现次数为1，我们要找的数字就是最后一次把次数重置为1的时候，保存的数字。最后要检查得到的元素出现次数是否超过一半。
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
length = len(numbers)
if not numbers:
return 0
result = numbers[0]
times = 1
for i in range(1,length):
if times == 0:
result = numbers[i]
times = 1
elif numbers[i] == result:
times += 1
else:
times -= 1
if not self.CheckNoreThanHalf(numbers,length,result):
return 0
return result
def CheckNoreThanHalf(self, numbers,length,number):
times = 0
for i in range(length):
if numbers[i] == number:
times += 1
if times*2 <= length:
return False
return True
最小的k个数
Q: 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
A: 第一种思路：基于划分的方法，使比第k个数字小的数都位于数组的左边，大的位于数组右边。第二种思路：基于二叉树或堆。首先把前k个数字构建一个堆，从第k+1个数字开始遍历，遍历到的元素如果小于堆的最大元素，则交换，继续遍历到结束，最后剩下的就是最小的k个数。
# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if not tinput or k > len(tinput):
return []
tinput = self.quick_sort(tinput)
return tinput[:k]
def quick_sort(self,lst):
if not lst:
return []
pivot = lst[0]
left = self.quick_sort([x for x in lst[1: ] if x < pivot])
right = self.quick_sort([x for x in lst[1: ] if x >= pivot])
return left + [pivot] + right
连续数组的最大和
Q: HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
A: 对于连续子数组，可以用一个数值来存储当前的和，如果当前和小于0，那么在进行到下一个元素时，直接把当前和赋值为下一个元素，如果当前和大于0，则累加下一个元素，同时用一个链表存储最大值并随时更新。
# -*- coding:utf-8 -*-
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
if not array:
return 0
cur_sum = 0
max_sum = array[0]
for i in range(len(array)):
if cur_sum <= 0:
cur_sum = array[i]
else:
cur_sum += array[i]
if cur_sum > max_sum:
max_sum = cur_sum
return max_sum
整数中1出现的次数
Q: 求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1-13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
A: 第一种思路：累加1-n中每个整数中1出现的次数，每次通过对10取余，判断整数的个位是否为1，如果数字大于10，则除以10以后，再通过取余计算判断各位是否为1.第二种思路： 数学规律
设定整数点（如1、10、100等等）作为位置点m（对应n的各位、十位、百位等等），分别对每个数位上有多少包含1的点进行分析。
- 根据设定的整数位置，对n进行分割，分为两部分，高位n//m，低位n%m
- 当i表示百位，且百位对应的数>=2,如n=31456,m=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a/10+1)*100个点的百位为1
- 当i表示百位，且百位对应的数为1，如n=31156,m=100，则a=311,b=56，此时百位对应的就是1，则共有a/10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a/10*100）+(b+1)，这些点百位对应为1
- 当i表示百位，且百位对应的数为0,如n=31056,m=100，则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0~30）
- 综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%10==1)，需要增加局部点b+1
- 之所以补8，是因为当百位为0，则a/10==(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
count=0
for i in range(1,n+1):
while i:
if i%10==1:
count+=1
i=i/10
return count
# 数学规律
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
count, m =0, 1
while m <= n:
count += (n // m + 8) // 10 * m + (n // m % 10 == 1) * (n % m + 1)
m*=10
return count
把数组排成最小的数
Q: 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
A: 将数组中的数字全部转换成字符串存储在一个新的数组中，然后比较每两个数字串的拼接的mn和nm的大小，如果mn小于nm，则m更小，反之n更小。然后把小的数放入一个新的列表中输出。
# -*- coding:utf-8 -*-
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if not numbers:
return ''
str_num = [str(m) for m in numbers]
for i in range(len(numbers)-1):
for j in range(i+1,len(numbers)):
if str_num[i] + str_num[j] > str_num[j] + str_num[i]:
str_num[i],str_num[j] = str_num[j] ,str_num[i]
return ''.join(str_num)
丑数
Q: 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
A: 建立一个长度为n的数组保存N个丑数，在这N个数中，某个位置要求的丑数一定是前面某个丑数乘以2、3或者5得到的结果。分别记录乘以2能得到的最大丑数, 乘以3以后能得到的最大丑数
, 乘以5以后能得到的最大丑数
. 那么下一个丑数一定是这三个最大丑数中最小的那个。因为是按照顺序存放的丑数，所以对于乘以2来说，肯定存在一个丑数
, 排在它之前的每一个丑数乘以2得到的结果都会小于已有的最大丑数，己住该丑数的位置，每次生成新的丑数时，更新它。对于乘以3或者5，同理。
# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if not index:
return 0
ugly_number = [1]*index
next_index = 1
index2 = 0
index3 = 0
index5 = 0
while next_index < index:
minValue = min(ugly_number[index2]*2, ugly_number[index3]*3,ugly_number[index5]*5)
ugly_number[next_index] = minValue
while ugly_number[index2]*2 <= ugly_number[next_index]:
index2 += 1
while ugly_number[index3]*3 <= ugly_number[next_index]:
index3 += 1
while ugly_number[index5]*5 <= ugly_number[next_index]:
index5 += 1
next_index += 1
return ugly_number[-1]
第一个只出现一次的字符
Q: 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
A: 先遍历一遍字符串，用一个hash表存放每个出现的字符和字符出现的次数。在遍历一遍字符串，找到hash值等于1的即可。
# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
if not s:
return -1
store = {}
lis = list(s)
for i in lis:
if i not in store.keys():
store[i] = 0
store[i] += 1
for i in lis:
if store[i] == 1:
return s.index(i)
return -1
数组中的逆序对
Q: 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
A: 先将原序列排序，然后从排完序的数组中取出最小的，它在原数组中的位置表示有多少比它大的数在它前面，每取出一个在原数组中删除该元素，保证后面取出的元素在原数组中是最小的，这样其位置才能表示有多少比它大的数在它前面，即逆序对数。或者用归并排序。(这道题在牛客上 用python怎么做都超时。。)
class Solution:
def InversePairs(self, data):
# write code here
count = 0
copy = []
for i in data:
copy.append(i)
copy.sort()
for i in range(len(copy)):
count += data.index(copy[i])
data.remove(copy[i])
return count%1000000007
count = 0
class Solution:
def InversePairs(self, data):
global count
def MergeSort(lists):
global count
if len(lists) <= 1:
return lists
num = int( len(lists)/2 )
left = MergeSort(lists[:num])
right = MergeSort(lists[num:])
r, l=0, 0
result=[]
while l<len(left) and r<len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
count += len(left)-l
print 'count: ', count
result += right[r:]
result += left[l:]
return result
MergeSort(data)
return count%1000000007
两个链表的第一个公共节点
Q: 输入两个链表，找出它们的第一个公共结点。
A: 首先依次遍历两个链表，记录两个链表的长度m和n，假设m>n，就先让长的链表走m-n个节点，然后两个链表同时遍历，遍历到相同节点的时候停止即可。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
if not pHead1 or not pHead2:
return None
p1,p2 = pHead1,pHead2
len1 = len2 = 0
while p1:
len1 += 1
p1 = p1.next
while p2:
len2 += 1
p2 = p2.next
if len1 > len2:
while len1 - len2:
pHead1 = pHead1.next
len1 -= 1
else:
while len2 - len1:
pHead2 = pHead2.next
len2 -= 1
while pHead1 and pHead2:
if pHead1 is pHead2:
return pHead1
pHead1 = pHead1.next
pHead2 = pHead2.next
return None
数字在排序数组中出现的次数
Q: 统计一个数字在排序数组中出现的次数。
A: 有序数组的元素查找，可以考虑二分查找。找到该数字在数组中第一次出现的位置和最后一次出现的位置即可。
# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
if not data:
return 0
if self.GetLastK(data, k) == -1 and self.GetFirstK(data, k) == -1:
return 0
return self.GetLastK(data, k) - self.GetFirstK(data, k) + 1
def GetFirstK(self, data, k):
low = 0
high = len(data) - 1
while low <= high:
mid = (low + high) // 2
if data[mid] < k:
low = mid + 1
elif data[mid] > k:
high = mid - 1
else:
if mid == low or data[mid - 1] != k: #当到list[0]或不为k的时候跳出函数
return mid
else:
high = mid - 1
return -1
def GetLastK(self, data, k):
low = 0
high = len(data) - 1
while low <= high:
mid = (low + high) // 2
if data[mid] > k:
high = mid - 1
elif data[mid] < k:
low = mid + 1
else:
if mid == high or data[mid + 1] != k:
return mid
else:
low = mid + 1
return -1
二叉树的深度
Q: 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
A: 利用递归，如果一个树只有一个节点，那么深度为1，如果存在左子树和右子树，深度为左右子树中深度较深的加1
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def TreeDepth(self, pRoot):
# write code here
if not pRoot:
return 0
return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right)) + 1
平衡二叉树
Q: 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
A: 递归，在遍历每个节点的时候，记录它的深度，就可以一边遍历一边判断。
# -*- 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 = True
def IsBalanced_Solution(self, pRoot):
# write code here
self.getDepth(pRoot)
return self.flag
def getDepth(self, root):
if not root:
return 0
left = self.getDepth(root.left) + 1
right = self.getDepth(root.right) + 1
if abs(left - right) > 1:
self.flag = False
return left if left > right else right
数组中只出现一次的数字
Q: 一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
A: 第一种思路用hashmap，把数组所有的数字转成字符串存到hashmap中，直接找出次数为1 的值。第二种思路是分成两个数组进行异或。位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。 当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
hashmap = {}
for i in array:
if str(i) in hashmap:
hashmap[str(i)] += 1
else:
hashmap[str(i)] = 1
result = []
for k in hashmap.keys():
if hashmap[k] == 1:
result.append(int(k))
return result
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
if array == None:
return []
xor = 0
for i in array:
xor ^= i
idxOf1 = self.getFirstIdx(xor)
num1 = num2 = 0
for j in range(len(array)):
if self.IsBit(array[j], idxOf1):
num1 ^= array[j]
else:
num2 ^= array[j]
return [num1, num2]
def getFirstIdx(self, num):
idx = 0
while num & 1 == 0 and idx <= 32:
idx += 1
num = num >> 1
return idx
def IsBit(self, num, indexBit):
num = num >> indexBit
return num & 1
和为s的连续正数序列
Q: 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
A: 设定两个指针分别指向数字1和数字2，并设为small和big，求和，如果大于s，则删除small并把small加1，如果小于s，则把big加1，并加入和中。如果等于目标值，就输出small到big的序列，同时把big加1，并加入和中，继续之前操作。
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
small, big,res = 1, 2, []
csum = small + big
while small < big:
if csum > tsum:
csum -= small
small += 1
else:
if csum == tsum:
res.append([i for i in range(small,big+1)])
big += 1
csum += big
return res
和为s的两个数字
Q: 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
A: 两个指针，一个指向起点，一个指向终点，然后对两个数字求和，如果大于s，则前移后一个指针，如果小于s，则把前一个指针后移。
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
if not array or not tsum:
return []
start = 0
end = len(array) - 1
while start < end:
csum = array[start] + array[end]
if csum < tsum:
start += 1
elif csum > tsum:
end -= 1
else:
return [array[start],array[end]]
return []
左旋转字符串
Q: 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
A: 首先翻转输入的任何字符串，然后根据左旋转个数n，用字符串长度len减去旋转字符个数n，求得新字符串在哪一位旋转，然后分别旋转前[:len-n]子串和[len-n:]子串，然后拼接。
# -*- coding:utf-8 -*-
class Solution:
def LeftRotateString(self, s, n):
# write code here
if len(s) <= 0 or n < 0 or len(s) < n:
return ''
lis = list(s)
self.Reverse(lis)
length = len(s)
pivot = length - n
frontlist = self.Reverse(lis[:pivot])
behindlist = self.Reverse(lis[pivot:])
res = ''.join(frontlist) + ''.join(behindlist)
return res
def Reverse(self,lis):
if not lis or len(lis) <= 0:
return ''
start = 0
end = len(lis) - 1
while start < end:
lis[start], lis[end] = lis[end], lis[start]
start += 1
end -= 1
return lis
翻转单词顺序列
Q: 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
A: 首先把输入的字符串完全翻转，从前往后依次遍历新字符串，遇到空格，就把空格前的字符串翻转，添加空格，继续遍历，遍历到结尾的时候，因为最后一个字符串后没有空格，所以最后要再翻转它。
# -*- coding:utf-8 -*-
class Solution:
def ReverseSentence(self, s):
# write code here
if not s or len(s) <= 0:
return ''
lis = list(s)
lis = self.Reverse(lis)
start = 0
end = 0
res = ''
lisTmp = []
while end < len(s):
if end == len(s) - 1:
lisTmp.append(self.Reverse(lis[start:]))
break
if lis[start] == ' ':
start += 1
end += 1
lisTmp.append(' ')
elif lis[end] == ' ':
lisTmp.append(self.Reverse(lis[start:end]))
start = end
else:
end += 1
for i in lisTmp:
res += ''.join(i)
return res
def Reverse(self,lis):
if not lis or len(lis) <= 0:
return ''
start = 0
end = len(lis) - 1
while start < end:
lis[start], lis[end] = lis[end], lis[start]
start += 1
end -= 1
return lis
扑克牌顺子
Q: 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。
A: 把这5张牌组成的顺子看成数组，所以先对数组排序，然后求出大小王 即0的个数，然后除去0之外的数字，求出在数组中的数字间隔，然后比较间隔和0的个数，如果出现成对的，肯定不是顺子，再求间隔的时候需要鉴别。
# -*- coding:utf-8 -*-
class Solution:
def IsContinuous(self, numbers):
# write code here
if not numbers or len(numbers) == 0:
return False
transdict = {'A':1,'J':11,'Q':12,'K':13}
for i in range(len(numbers)):
if numbers[i] in transdict.keys():
numbers[i] = transdict[numbers[i]]
numbers = sorted(numbers)
number_0 = 0
number_gap = 0
i = 0
while i < len(numbers) and numbers[i] == 0:
number_0 += 1
i += 1
front = number_0
behind = front + 1
while behind < len(numbers):
if numbers[front] == numbers[behind]:
return False
number_gap += numbers[behind] - numbers[front] - 1
front = behind
behind += 1
return False if number_gap > number_0 else True
孩子们的游戏(圆圈中最后剩下的数)
Q: 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
A: 约瑟夫环问题，可以直接模拟。也可以用递推公式。推导过程
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n < 1 or m < 1:
return -1
con = range(n)
start = 0
end = -1
while con:
k = (start + m - 1) % n
end = con.pop(k)
n -= 1
start = k
return end
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n < 1 or m < 1:
return -1
idx = 0
for i in range(1,n+1):
idx = (idx + m ) % i
return idx
求1+2+3+...+n
Q: 求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
A: 利用两个函数，一个函数充当递归函数的角色，另一个函数处理终止递归的情况，如果对n连续两次做去反运算，那么非零的n转换为True，0转换为False。利用这一特性终止递归。还可以利用python中的and特性，a and b，a为False，返回a，a为True，就返回b
# -*- coding:utf-8 -*-
class Solution:
def Sum_Solution(self, n):
# write code here
return self.sumN(n)
def sum0(self, n):
return 0
def sumN(self,n):
fun = {False:self.sum0,True: self.sumN}
return n + fun[not not n](n - 1)
# -*- coding:utf-8 -*-
class Solution:
def Sum_Solution(self, n):
# write code here
return n and self.Sum_Solution(n - 1) + n
不用加减乘除做加法
Q: 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
A: 两个数异或：相当于每一位相加，而不考虑进位；两个数相与，并左移一位：相当于求得进位；将上述两步的结果相加。注意：在使用Python实现的过程中，对于正整数是没有问题的，但是对于负数，会出现死循环情况。因为在Python中，对于超出32位的大整数，会自动进行大整数的转变，这就导致了在右移位过程中，不会出现移到了0的情况，也就会造成了死循环。已经知道了右移过程中大整数的自动转化，导致变不成0，那么只需要在移动的过程中加一下判断就行了。一个int可表示的无符号整数为4294967295，对应的有符号为-1。因此最后我们可以判断符号位是否为1。
# -*- coding:utf-8 -*-
class Solution:
def Add(self, num1, num2):
# write code here
while num2 != 0:
temp = num1 ^ num2
num2 = (num1 & num2) << 1
num1 = temp & 0xFFFFFFFF
return num1 if num1 >> 31 == 0 else num1 - 4294967296
把字符串转换成整数
Q: 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
A: 主要是区分输入和合法性，比如输入一个None，输入一个空字符串 “ ”，或者输入的字符串中含有“+”或者“-”，或者输入的字符串中含有除去“+”“-” 数字的非数字字符。
# -*- coding:utf-8 -*-
class Solution:
def StrToInt(self, s):
# write code here
flag = False
if not s or len(s) < 1:
return 0
num = []
numdict = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
for i in s:
if i in numdict.keys():
num.append(numdict[i])
elif i == '+' or i == '-':
continue
else:
return 0
ans = 0
if len(num) == 1 and num[0] == 0:
flag = True
return 0
for i in num:
ans = ans*10 + i
if s[0] == '-':
ans = 0 - ans
return ans
数组中重复的数字
Q: 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
A: 长度为n的数组里，所有数字的范围都在[0,n-1]中。查重的话，可以首先对数组进行排序，然后遍历数组查找重复的数字，事件复杂度为O(nlogn)，或者建立一个哈希表，这样在O(n)的时间内查找到，但是需要O(n)的额外空间。因为数字在[0,n-1]中，如果数字没有重复，那么数组排序后数字i 将出现在index为i 的位置。存在重复的话，位置i 出现的数字就可能不是i。所以可以重排数组，从头到尾扫描所有数字，如果位置i 的数字不是i，就和位置i 的数字交换，交换后还不是，就继续交换，直到位置i 的数字为i。 如果在交换过程中，需要交换的数字，在相应位置已经存在，则该数字为重复数字，记录该数字，然后继续扫描。
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
if not numbers or len(numbers) < 0:
return False
for i in numbers:
if i < 0 or 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
else:
idx = numbers[i]
numbers[i],numbers[idx] = numbers[idx],numbers[i]
return False
构建乘积数组
Q: 给定一个数组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]。不能使用除法。
A: 把B[i]分成两部分， 一部分是A[0,...,i-1]的连乘，记为C[i]，一部分是A[i+1,...,n-1]的连乘，记为D[i]，所以，C[i]=C[i-1] * A[i-1]， D[i]=D[i+1] * A[i+1]。
[图片上传失败...(image-f0759a-1564241743119)]
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
if not A or len(A) <= 0:
return
length = len(A)
lis = [1] * length
for i in range(1,length):
lis[i] = lis[i-1] * A[i-1]
temp = 1
for i in range(length-2,-1,-1):
temp = temp * A[i+1]
lis[i] *= temp
return lis
正则表达式匹配
Q: 请实现一个函数用来匹配包括'.'和'* '的正则表达式。模式中的字符'.'表示任意一个字符，而'* '表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab* ac* a"匹配，但是与"aa.a"和"ab*a"均不匹配。
A:
'''
解这题需要把题意仔细研究清楚，反正我试了好多次才明白的。
首先，考虑特殊情况：
1>两个字符串都为空，返回true
2>当第一个字符串不空，而第二个字符串空了，返回false（因为这样，就无法
匹配成功了,而如果第一个字符串空了，第二个字符串非空，还是可能匹配成
功的，比如第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次，
所以有可能匹配成功）
之后就开始匹配第一个字符，这里有两种可能：匹配成功或匹配失败。但考虑到pattern
下一个字符可能是‘*’， 这里我们分两种情况讨论：pattern下一个字符为‘*’或
不为‘*’：
1>pattern下一个字符不为‘*’：这种情况比较简单，直接匹配当前字符。如果
匹配成功，继续匹配下一个；如果匹配失败，直接返回false。注意这里的
“匹配成功”，除了两个字符相同的情况外，还有一种情况，就是pattern的
当前字符为‘.’,同时str的当前字符不为‘\0’。
2>pattern下一个字符为‘*’时，稍微复杂一些，因为‘*’可以代表0个或多个。
这里把这些情况都考虑到：
a>当‘*’匹配0个字符时，str当前字符不变，pattern当前字符后移两位，
跳过这个‘*’符号；
b>当‘*’匹配1个或多个时，str当前字符移向下一个，pattern当前字符
不变。（这里匹配1个或多个可以看成一种情况，因为：当匹配一个时，
由于str移到了下一个字符，而pattern字符不变，就回到了上边的情况a；
当匹配多于一个字符时，相当于从str的下一个字符继续开始匹配）
之后再写代码就很简单了。
'''
# -*- 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
表示数值的字符串
Q: 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
A: 表示数值的字符串遵循模式 或者
，其中A为整数部分，B为小数部分，C为指数部分。首先尽可能多的扫描0-9的数位，也是就A的部分，如果遇到小数点，则开始扫描B部分，如果遇到e或者E，则开始扫描指数C部分。
# -*- coding:utf-8 -*-
class Solution:
# s字符串
def isNumeric(self, s):
# write code here
if len(s) <= 0:
return False
# 分别标记是否出现过正负号、小数点、e，因为这几个需要特殊考虑
has_sign = False
has_point = False
has_e = False
for i in range(len(s)):
# 对于e的情况
if s[i] == 'E' or s[i] == 'e':
# 不同出现两个e
if has_e:
return False
# e不能出现在最后面，因为e后面要接数字
else:
has_e = True
if i == len(s) -1:
return False
# 对于符号位的情况
elif s[i] == '+' or s[i] == '-':
# 如果前面已经出现过了符号位，那么这个符号位，必须是跟在e后面的
if has_sign:
if s[i-1] != 'e' and s[i-1] != 'E':
return False
# 如果这是第一次出现符号位，而且出现的位置不是字符串第一个位置，那么就只能出现在e后面
else:
has_sign = True
if i > 0 and s[i-1] != 'e' and s[i-1] != 'E':
return False
# 对于小数点的情况
elif s[i] == '.':
# 小数点不能出现两次；而且如果已经出现过e了，那么就不能再出现小数点，因为e后面只能是整数
if has_point or has_e:
return False
# 如果是第一次出现小数点，如果前面出现过e，那么还是不能出现小数点
else:
has_point = True
if i > 0 and (s[i-1] == 'e' or s[i-1] == 'E'):
return False
else:
# 其他字符必须是‘0’到‘9’之间的
if s[i] < '0' or s[i] > '9':
return False
return True
字符流中第一个不重复的字符
Q: 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
A: 使用两个辅助空间，一个dict存储当前出现的字符以及字符出现的次数，list存储当前出现的字符，然后依次比较list的第一个字符和dict中出现的次数，如果为1，则输出，不为1，则弹出该字符，继续比较下一个。
# -*- coding:utf-8 -*-
class Solution:
# init
def __init__(self):
self.dic = {}
self.lis = []
# 返回对应char
def FirstAppearingOnce(self):
# write code here
while len(self.lis) > 0 and self.dic[self.lis[0]] == 2:
self.lis.pop(0)
if len(self.lis) == 0:
return '#'
else:
return self.lis[0]
def Insert(self, char):
# write code here
if char not in self.dic.keys():
self.dic[char] = 1
self.lis.append(char)
elif self.dic[char]:
self.dic[char] = 2
链表中环的入口结点
Q: 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
A: 首先设置两个快慢指针，移动两个指针，如果相遇，则存在环，然后从相遇的地方设置一个指针向后遍历并计数，回到开始的位置时，计数就是环中的结点数n，最后设置两个指针，一个先走n步，另一个再移动，两个指针每次移动一步，相遇的结点为入口。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
meetNode = self.MeetNode(pHead)
if not meetNode:
return None
loop = 1
flag = meetNode
while flag.next != meetNode:
loop += 1
flag = flag.next
fast = pHead
for i in range(loop):
fast = fast.next
slow = pHead
while fast != slow:
fast = fast.next
slow = slow.next
return fast
def MeetNode(self, head):
if not head:
return None
slow = head.next
if slow == None:
return None
fast = slow.next
while fast:
if slow == fast:
return slow
slow = slow.next
fast = fast.next.next
删除链表中重复的结点
Q: 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
A: 第一步是确定删除的参数。当然这个函数需要输入待删除链表的头结点。头结点可能与后面的结点重复，也就是说头结点也可能被删除，所以在链表头添加一个结点。接下来我们从头遍历整个链表。如果当前结点的值与下一个结点的值相同，那么它们就是重复的结点，都可以被删除。为了保证删除之后的链表仍然是相连的而没有中间断开，我们要把当前的前一个结点和与当前结点的值不重复的结点相连。我们要确保前一个结点要始终与下一个没有重复的结点连接在一起。
# -*- 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 pHead is None or pHead.next is None:
return pHead
first = ListNode(-1)
first.next = pHead
last = first
while pHead and pHead.next:
if pHead.val == pHead.next.val:
val = pHead.val
while pHead and val == pHead.val:
pHead = pHead.next
last.next = pHead
else:
last = pHead
pHead = pHead.next
return first.next
二叉树的下一个结点
Q: 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
A: 三种情况：当前节点有右子树的话，当前节点的下一个结点是右子树中的最左子节点；当前节点无右子树但是是父节点的左子节点，下一个节点是当前结点的父节点；当前节点无右子树而且是父节点的右子节点，则一直向上遍历，直到找到最靠近的一个祖先节点pNode，pNode是其父节点的左子节点，那么输入节点的下一个结点就是pNode的父节点。
# -*- 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 pNode is None:
return
pNext = None
if pNode.right:
pNode = pNode.right
while pNode.left:
pNode = pNode.left
pNext = pNode
else:
if pNode.next and pNode.next.left == pNode:
pNext = pNode.next
elif pNode.next and pNode.next.right == pNode:
pNode = pNode.next
while pNode.next and pNode.next.right == pNode:
pNode = pNode.next
# 遍历终止时当前节点有父节点, 说明当前节点是父节点的左子节点, 输入节点的下一个结点为当前节点的父节点
# 反之终止时当前节点没有父节点, 说明当前节点在位于根节点的右子树, 没有下一个结点
if pNode.next:
pNext = pNode.next
return pNext
对称的二叉树
Q: 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
A: 把叶子节点的None结点加入到遍历中，按照前序遍历的方式遍历二叉树，存入一个序列中，然后按照和前序遍历对应的先父节点，然后右节点，最后左结点遍历二叉树，存入一个序列中，如果两个序列相等，则对称。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetrical(self, pRoot):
# write code here
return self.selfIsSym(pRoot,pRoot)
def selfIsSym(self,root1,root2):
if root1 == root2 and root2 == None:
return True
if root1 == None or root2 == None:
return False
if root1.val != root2.val:
return False
return self.selfIsSym(root1.left, root2.right) and self.selfIsSym(root1.right,root2.left)
按之字形顺序打印二叉树
Q: 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
A: 按之字形顺序打印二叉树需要两个栈。我们在打印某一行节点时，把下一层的子节点保存到相应的栈里。如果当前打印的奇数层，则先保存左子节点再保存右子节点到第一个栈里；如果当前打印的是偶数层，则先保存右子节点再保存左子节点到第二个栈里。
# -*- 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 []
result,nodes = [],[pRoot]
right = True
while nodes:
curStack, nextStack = [],[]
if right:
for node in nodes:
curStack.append(node.val)
if node.left:
nextStack.append(node.left)
if node.right:
nextStack.append(node.right)
else:
for node in nodes:
curStack.append(node.val)
if node.right:
nextStack.append(node.right)
if node.left:
nextStack.append(node.left)
nextStack.reverse()
right = not right
result.append(curStack)
nodes = nextStack
return result
把二叉树打印成多行
Q: 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
A: 两个队列，首先把当前层的节点存入队列1中，然后遍历队列1，遍历时，如果有左子树或者右子树，依次存入队列2，然后遍历队列2.
# -*- 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 pRoot is None:
return []
nodes,res = [pRoot],[]
while nodes:
curStack, nextStack = [],[]
for node in nodes:
curStack.append(node.val)
if node.left:
nextStack.append(node.left)
if node.right:
nextStack.append(node.right)
res.append(curStack)
nodes = nextStack
return res
序列化二叉树
Q: 请实现两个函数，分别用来序列化和反序列化二叉树
A: 二叉树的序列化，通过前序遍历二叉树输出节点，然后碰到左子节点和右子节点为None的时候，输出一个特殊字符。对于反序列化，就是通过输入的序列构建二叉树，针对前序遍历，可以先设置一个指针，先指向序列的开头，然后把指针位置的数字转化成节点，当遇到特殊字符时或者超出序列长度时，对应节点为none。然后继续遍历。
# -*- 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
二叉搜索树的第k个结点
Q: 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
A: 中序遍历，输出第k个结点。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回对应节点TreeNode
def KthNode(self, pRoot, k):
# write code here
if not pRoot or not k:
return
res = []
def traverse(node):
if len(res) >= k or not node:
return
traverse(node.left)
res.append(node)
traverse(node.right)
traverse(pRoot)
if len(res) < k:
return
return res[k-1]
数据流中的中位数
Q: 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
A: 构建一个最大堆，一个最小堆，分别存储比中位数小的数和大的数。当两个堆的总数为偶数时，把数字存入最大堆，然后重排最大堆，如果最大堆堆顶的数字大于最小堆堆顶的数字，则交换，然后重排两个堆。此时两个堆总数为奇数，输出最大堆堆顶的数字；当两个堆总数为奇数时，把数字存入最小堆，重排最小堆，如果最大堆堆顶数字大于最小堆堆顶的数字，则交换，重排两个堆，此时两堆总是为偶数，输出两堆堆顶的数字的平均值。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.left = []
self.right = []
self.count = 0
def Insert(self, num):
if self.count & 1 == 0:
self.left.append(num)
else:
self.right.append(num)
self.count += 1
def GetMedian(self, x):
if self.count == 1:
return self.left[0]
self.MaxHeap(self.left)
self.MinHeap(self.right)
if self.left[0] > self.right[0]:
self.left[0], self.right[0] = self.right[0], self.left[0]
self.MaxHeap(self.left)
self.MinHeap(self.right)
if self.count & 1 == 0:
return (self.left[0] + self.right[0])/2.0
else:
return self.left[0]
def MaxHeap(self, alist):
length = len(alist)
if alist == None or length <= 0:
return
if length == 1:
return alist
for i in range(length//2-1, -1, -1):
k = i; temp = alist[k]; heap = False
while not heap and 2*k < length-1:
index = 2*k+1
if index < length - 1:
if alist[index] < alist[index + 1]: index += 1
if temp >= alist[index]: heap = True
else:
alist[k] = alist[index]
k = index
alist[k] = temp
def MinHeap(self, alist):
length = len(alist)
if alist == None or length <= 0:
return
if length == 1:
return alist
for i in range(length//2-1, -1, -1):
k = i; temp = alist[k]; heap = False
while not heap and 2 * k < length - 1:
index = 2 * k+1
if index < length - 1:
if alist[index] > alist[index + 1]: index += 1
if temp <= alist[index]:
heap = True
else:
alist[k] = alist[index]
k = index
alist[k] = temp
滑动窗口的最大值
Q: 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
A: 滑动窗口应当是队列，但为了得到滑动窗口的最大值，队列序可以从两端删除元素，因此使用双端队列。对新来的元素k，将其与双端队列中的元素相比较，前面比k小的，直接移出队列（因为不再可能成为后面滑动窗口的最大值了!）,前面比k大的X，比较两者下标，判断X是否已不在窗口之内，不在了，直接移出队列，队列的第一个元素是滑动窗口中的最大值。
# -*- coding:utf-8 -*-
class Solution:
def maxInWindows(self, num, size):
# write code here
if not num or size <= 0:
return []
deque = []
if len(num) >= size:
index = []
for i in range(size):
while len(index) > 0 and num[i] > num[index[-1]]:
index.pop()
index.append(i)
for i in range(size, len(num)):
deque.append(num[index[0]])
while len(index) > 0 and num[i] >= num[index[-1]]:
index.pop()
if len(index) > 0 and index[0] <= i - size:
index.pop(0)
index.append(i)
deque.append(num[index[0]])
return deque
矩阵中的路径
Q: 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
A: 回溯法。任选一个格子作为路径的起点。假设矩阵中某个格子的字符为ch并且这个格子将对应于路径上的第i个字符。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子外，其他各自都有4个相邻的格子。重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。
class Solution:
def hasPath(self, matrix, rows, cols, path):
if matrix == None or rows < 1 or cols < 1 or path == None:
return False
visited = [0] * (rows * cols)
pathLength = 0
for row in range(rows):
for col in range(cols):
if self.hasPathCore(matrix, rows, cols, row, col, path, pathLength, visited):
return True
return False
def hasPathCore(self, matrix, rows, cols, row, col, path, pathLength, visited):
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 \
visited[row * cols + col]:
pathLength += 1
visited[row * cols + col] = True
hasPath = self.hasPathCore(matrix, rows, cols, row, col - 1, path, pathLength, visited) or \
self.hasPathCore(matrix, rows, cols, row - 1, col, path, pathLength, visited) or \
self.hasPathCore(matrix, rows, cols, row, col + 1, path, pathLength, visited) or \
self.hasPathCore(matrix, rows, cols, row + 1, col, path, pathLength, visited)
if not hasPath:
pathLength -= 1
visited[row * cols + col] = False
return hasPath
机器人的运动范围
Q: 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
A: 把方格看成一个m*n的矩阵，从（0，0）开始移动。当准备进入坐标(i, j)是，通过检查坐标的数位来判断机器人能否进入。如果能进入的话，接着判断四个相邻的格子。
# -*- coding:utf-8 -*-
class Solution:
def movingCount(self, threshold, rows, cols):
visited = [False] * (rows * cols)
count = self.movingCountCore(threshold, rows, cols, 0, 0, visited)
return count
def movingCountCore(self, threshold, rows, cols, row, col, visited):
count = 0
if self.check(threshold, rows, cols, row, col, visited):
visited[row * cols + col] = True
count = 1 + self.movingCountCore(threshold, rows, cols, row-1, col, visited) + \
self.movingCountCore(threshold, rows, cols, row+1, col, visited) + \
self.movingCountCore(threshold, rows, cols, row, col-1, visited) + \
self.movingCountCore(threshold, rows, cols, row, col+1, visited)
return count
def check(self, threshold, rows, cols, row, col, visited):
if row >= 0 and row < rows and col >= 0 and col < cols and self.getDigitSum(row) + self.getDigitSum(col) <= threshold and not visited[row * cols + col]:
return True
return False
def getDigitSum(self, number):
sum = 0
while number > 0:
sum += (number % 10)
number = number // 10
return sum
网友评论