[关闭]
@knight 2016-09-09T01:52:55.000000Z 字数 23100 阅读 8709

剑指offfer编程题(python版)

python

动态规划

和为s的两个数字

  1. # 依次遍历第一个找到的两个数就是乘积最小的一个
  2. # 设置两个指针，初始为第一个low和最后一个hight， low只能加， hight只能减
  3. # -*- coding:utf-8 -*-
  4. class Solution:
  5.     def FindNumbersWithSum(self, array, tsum):
  6.         if not array:  # 数组为空返回[]
  7.             return []
  8.         low = 0
  9.         hight = len(array)-1
  10.         while low < hight:
  11.             tmp_sum = array[low]+array[hight]
  12.             if tmp_sum > tsum: # 当前和大于tsum，那么需要减值
  13.                 hight -= 1
  14.             elif tmp_sum < tsum:
  15.                 low += 1
  16.             else:
  17.                 return [array[low], array[hight]]
  18.         return []
  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def FindNumbersWithSum(self, array, tsum):
  4.         # 和为s的两个数字
  5.         ret = []
  6.         for i, num in enumerate(array):
  7.             tmp = tsum - num
  8.             if tmp in array[i+1:]:
  9.                 ret.append((num*tmp, num, tmp))
  10.         if not ret:
  11.             return ret
  12.         tmp_ret = min(ret) #默认(num*tmp, num, tmp) num*tmp作为关键码求最小
  13.         return tmp_ret[1:]

和为s的连续正数序列

考虑两个数ｓｍａｌｌ和ｂｉｇ分别表示当前最小值和最大值。初始设置为１，２．如果从ｓｍａｌｌ到ｂｉｇ序列的和大于ｓ，我们可以从序列中去掉较小值，否则增加ｂｉｇ值。

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def FindContinuousSequence(self, tsum):
  4.         if tsum < 3:  # 验证至少2个数
  5.             return []
  6.         small, big = 1, 2
  7.         middle = (1+tsum)>>1  # 最大值--终止条件
  8.         cur_sum = small + big
  9.         ret = []
  10.         while small < middle:
  11.             if cur_sum == tsum:
  12.                 ret.append(range(small, big+1))
  13.             while cur_sum > tsum and small < middle: # 当前和大于tsum，减小small
  14.                 cur_sum -= small
  15.                 small += 1
  16.                 if cur_sum == tsum:
  17.                     ret.append(range(small, big+1))
  18.             big += 1
  19.             cur_sum += big
  20.         return ret

连续子数组和最大

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def FindGreatestSumOfSubArray(self, array):
  4.         if not array: # 数组为空返回0
  5.             return 0
  6.         dp = [float('-inf')]  # 初始值负无穷
  7.         for i,n in enumerate(array):
  8.             if dp[i] <= 0:   # dp[i]前面最大的连续数组和，如果小于等于0，那么加上当前值只会更小，更新dp[i+1]=n
  9.                 dp.append(n)
  10.             else:
  11.                 dp.append(dp[i]+n)  # 当前值为0，且前面连续最大和为正，说明加上当前数一定大于之前和
  12.         return max(dp)

数组与矩阵

构建乘法数组

给定一个数组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]。不能使用除法。

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def multiply(self, A):
  4.         first = [1]
  5.         second = [1]
  6.         for i in range(1, len(A)):
  7.             first.append(first[i-1]*A[i-1]) # 依次保存中间的计算值
  8.             second.append(second[i-1]*A[-i])
  9.         B = []
  10.         for i in range(0, len(A)):
  11.             B.append(first[i]*second[-(i+1)])
  12.         return B

不用加减乘除做加法

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def Add(self, num1, num2):
  4.         # 使用sum函数
  5.         return sum([num1, num2])

孩子们的游戏（约瑟夫环）

1） 开始有n个人，从0数到m-1，m-1下标的这个人出列，下一次有n-1个人，从0数到m-1，m-1下标出列，。。下一个出列的下标 = （当前下标 + m-1）%当前人数

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def LastRemaining_Solution(self, n, m):
  4.         if n < 1 or m < 1:
  5.             return -1
  6.         last = 0
  7.         people = range(n)
  8.         i = 0
  9.         for num in range(n,1,-1):
  10.             i = (i+m-1)%num
  11.             people.pop(i)
  12.         return people[-1]

扑克牌顺子

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def IsContinuous(self, numbers):
  4.         if not numbers or len(numbers) != 5:
  5.             return False
  6.         zeros = numbers.count(0)
  7.         gap = 0
  8.         i,j = zeros, zeros+1
  9.         n = len(numbers)
  10.         numbers.sort()
  11.         while j < n:
  12.             if numbers[i]==numbers[j]:
  13.                 return False
  14.             gap += numbers[j] - numbers[i] - 1
  15.             i = j
  16.             j += 1
  17.         return True if gap <= zeros else False
  18.         # write code here

数组中只出现一次的数字

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     # 返回[a,b] 其中ab是出现一次的两个数字
  4.     def FindNumsAppearOnce(self, array):
  5.         ret = []
  6.         for num in array:
  7.             if array.count(num)==1:
  8.                 ret.append(num)
  9.         if len(ret)==2:
  10.             return ret
  11.         return [0,0]
  12.         # write code here

数字在排序数组中出现的次数

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def GetNumberOfK(self, data, k):
  4.         # o(n)解法,笔试编程题一般没问题，想必面试是过不了的，利用数组有序，做二分查找
  5.         return data.count(k)
  7. # log(n)的解法，二分查找在找到ｋ的时候做变形使得满足要求
  8. # -*- coding:utf-8 -*-
  9. class Solution:
  10.     def bisect_first_k(self, data, k, start, end):
  11.         # 找到第一个ｋ
  12.         if start > end:
  13.             return -1
  14.         mid = (start+end)>>1
  15.         if data[mid]==k:
  16.             if mid > 0 and data[mid-1]!=k or mid==0:
  17.                 return mid
  18.             else:
  19.                 end = mid -1
  20.         elif data[mid] > k:
  21.             end = mid - 1
  22.         else:
  23.             start = mid + 1
  24.         return self.bisect_first_k(data, k, start, end)
  26.     def bisect_last_k(self, data, k, start, end):
  27.         # 找到最后一个ｋ
  28.         if start > end:
  29.             return -1
  30.         mid = (start+end)>>1
  31.         if data[mid]==k:
  32.             if mid < len(data)-1 and data[mid + 1] != k or mid ==len(data)-1:
  33.                 return mid
  34.             else:
  35.                 start = mid + 1
  36.         elif data[mid] > k:
  37.             end = mid - 1
  38.         else:
  39.             start = mid + 1
  40.         return self.bisect_last_k(data, k , start, end)
  42.     def GetNumberOfK(self, data, k):
  43.         count = 0
  44.         if data and len(data)>0:
  45.             first = self.bisect_first_k(data, k, 0, len(data)-1)
  46.             last = self.bisect_last_k(data, k, 0, len(data)-1)
  47.             if first > -1 and last > -1:
  48.                 return last - first + 1
  49.         return count
  51.         # write code here

丑数

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

  1. class Solution:
  2.     def GetUglyNumber_Solution(self, index):
  3.         # write code here
  4.         n, m = 0, 0
  5.         k1, k2, k3 = [1], [1], [1]
  6.         while n < index:
  7.             m = min(k1[0], k2[0], k3[0])
  8.             n += 1
  9.             if m in k1:
  10.                 k1.remove(m)
  11.             if m in k2:
  12.                 k2.remove(m)
  13.             if m in k3:
  14.                 k3.remove(m)
  15.             k1.append(m*2)
  16.             k2.append(m*3)
  17.             k3.append(m*5)
  18.         return m

把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def str_cmp(self, s1, s2):  #　定义排序比较规则
  4.         s1, s2 = s1+s2, s2+s1
  5.         return cmp(s1, s2)
  7.     def PrintMinNumber(self, numbers):
  8.         if not numbers:
  9.             return ''
  10.         tmp = map(str, numbers) #　转化为ｓｔｒ
  11.         tmp.sort(self.str_cmp)
  12.         return ''.join(tmp)

整数中１出现的次数

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def NumberOf1Between1AndN_Solution(self, n):
  4.         count = 0
  5.         for i in range(1,n+1):
  6.             count += str(i).count('1')
  7.         return count

最小的ｋ个数

python中堆的使用

python-coolbook-查找最大或最小的ｋ个值

  1. # -*- coding:utf-8 -*-
  2. import heapq
  3. class Solution:
  4.     def GetLeastNumbers_Solution(self, tinput, k):
  5.         if tinput==None or len(tinput)<k:
  6.             return []
  7.         return heapq.nsmallest(k, tinput)
  8.         # write code here

数组中出现次数超过一半的数字

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def MoreThanHalfNum_Solution(self, numbers):
  4.         mid = len(numbers)>>1
  5.         for num in numbers:
  6.             if numbers.count(num) > mid:  # py中的ｃｏｕｎｔ（）使用
  7.                 return num
  8.         return 0

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每个数字

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     # matrix类型为二维列表，需要返回列表
  4.     def printMatrix(self, matrix):
  5.         if not matrix:
  6.             return None
  7.         rows = len(matrix)
  8.         cols = len(matrix[0])
  9.         start = 0
  10.         result = []
  11.         while rows > 2*start and cols > 2*start:
  12.             endx = rows - 1 - start  
  13.             endy = cols - 1 - start
  14.             for i in range(start, endy+1):  # 左到右处理
  15.                 result.append(matrix[start][i])
  16.             if start < endx:　　# 上到下处理
  17.                 for i in range(start+1,endx+1):
  18.                     result.append(matrix[i][endy])
  19.             if start < endx and start < endy:　　＃　右到左处理
  20.                 for i in range(endy-1, start-1, -1):
  21.                     result.append(matrix[endx][i])
  22.             if start < endx-1 and start < endy:　　＃　下到上处理
  23.                 for i in range(endx-1, start, -1):
  24.                     result.append(matrix[i][start])
  25.             start += 1
  26.         return result

旋转数组的最小数字

  1. # -*- coding:utf-8 -*-
  2. # 所有元素都是大于0， 所以零pre=0
  3. class Solution:
  4.     def minNumberInRotateArray(self, rotateArray):
  5.         if len(rotateArray)==0:
  6.             return 0
  7.         pre = 0
  8.         for num in rotateArray:
  9.             if num < pre:
  10.                 return num
  11.             pre = num
  12.         return rotateArray[0] 
  13.         #  有序，输出第一个元素

字符串

　python处理字符串实在是便利。

正则表达式匹配

实现. *　的匹配

  1. # -*- coding:utf-8 -*-
  3. def match_core(s, pat):
  4.     if len(s)==0 and len(pat)==0:  #匹配完成返回True
  5.         return True
  6.     if len(s)>0 and len(pat)==0: #匹配串pat匹配完，而s不为空，说明不匹配
  7.         return False
  8.     if len(pat)>1 and pat[1]=='*':  # pat至少有2个*匹配才有意义
  9.         if len(s)>0 and (s[0]==pat[0] or pat[0]=='.'):  # ab  .*  / ab a*  两种情况统一处理
  10.             return match_core(s[1:], pat) or match_core(s, pat[2:]) or match_core(s[1:], pat[2:])  # *匹配1个保持当前模式/不匹配/移动到下一个状态
  11.         else:  # len(s)==0 s匹配完，看剩下的是否匹配
  12.             return match_core(s, pat[2:])
  13.     if len(s)>0 and (pat[0]=='.' or pat[0]==s[0]):  # 处理非匹配字符和 . 直接处理下一个
  14.         return match_core(s[1:], pat[1:])
  15. class Solution:
  16.     # s, pattern都是字符串
  17.     def match(self, s, pattern):
  18.         return match_core(s, pattern)
  19.         # write code here

字符串转整数

  2. # -*- coding:utf-8 -*-
  3. class Solution:
  4.     def StrToInt(self, s):
  5.         if not s:
  6.             return 0
  7.         str2num = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9, '0':0}
  8.         flag2num = {'-':-1, '+': 1}
  9.         first = s[0]
  10.         if first in ['+', '-']: # 包含符号位的情况
  11.             flag = flag2num[first]
  12.             tmp = 0
  13.             for n in s[1:]:
  14.                 if n not in str2num:
  15.                     return 0
  16.                 tmp = tmp*10 + str2num[n]
  17.             return tmp*flag    
  18.         else:
  19.             tmp = 0
  20.             for n in s:
  21.                 if n not in str2num:
  22.                     return 0
  23.                 tmp = tmp*10 + str2num[n]
  24.             return tmp

翻转单词顺序序列

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def ReverseSentence(self, s):
  4.         return ' '.join(s.split(' ')[::-1])
  5.         # write code here

左旋转字符串

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def LeftRotateString(self, s, n):
  4.         return s[n:] + s[:n]
  5.         # write code here

第一个只出现一次的字符

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def FirstNotRepeatingChar(self, s):
  4.         if not s:
  5.             return -1
  6.         for i, ch in enumerate(s):
  7.             if s.count(ch)==1:
  8.                 return i
  9.         # write code here

字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。

  2. # -*- coding:utf-8 -*-
  3. import itertools
  4. class Solution:
  5.     def Permutation(self, ss):
  6.         # 借助内置的itertools.permutaions求解
  7.         # write code here
  8.         if not ss:
  9.             return ss
  10.         result = []
  11.         k = itertools.permutations(ss)
  12.         for i in k:
  13.             result.append(''.join(i))
  14.         result = list(set(result))
  15.         result.sort()
  16.         return result
  19. # -*- coding:utf-8 -*-
  20. def permuations(n):
  21.     #　全排列的一个实现(二找，一交换，一翻转)
  22.     """
  23.     1. 找到排列中最右一个升序的首位置ｉ，　ｘ＝ai
  24.     2. 找到排列中第ｉ位向右最后一个比ａｉ大的位置，ｊ，　ｙ＝ａｊ
  25.     3. 交换ｘ　ｙ
  26.     4. 把第ｉ＋１位到最后的部分翻转
  27.     ２１５４３－－下一个数是２３１４５
  28.     """
  29.     indices = range(n)
  30.     # n = len(ss)
  31.     yield indices
  32.     while True:
  33.         low_idx = n-1
  34.         while low_idx > 0 and indices[low_idx-1] > indices[low_idx]:　# 找到排列中最右一个升序的首位置
  35.             low_idx -= 1
  36.         if low_idx == 0:
  37.             break
  38.         low_idx -= 1
  39.         high_idx = low_idx + 1
  40.         while high_idx < n and indices[high_idx] > indices[low_idx]:　　#找到排列中第ｉ为向右最右一个比ａｉ大的位置
  41.             high_idx += 1
  42.         high_idx -= 1
  43.         indices[low_idx], indices[high_idx] = indices[high_idx], indices[low_idx]　# 交换
  44.         indices[low_idx+1:] = reversed(indices[low_idx+1:])  #　翻转
  45.         yield indices
  47. class Solution:
  48.     def Permutation(self, ss):
  49.         if not ss:
  50.             return []
  51.         ret_set = set()
  52.         for idx in permuations(len(ss)):
  53.             e = ''.join([ss[i] for i in idx])
  54.             ret_set.add(e)
  55.         return sorted(ret_set)
  56.         # write code here

替换空格

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     # s 源字符串
  4.     def replaceSpace(self, s):
  5.         return s.replace(' ', '%20')

栈和队列

栈的压入、弹出序列

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def IsPopOrder(self, pushV, popV):
  4.         n = len(pushV)
  5.         if not n: return False
  6.         tmp = []
  7.         j = 0
  8.         for val in pushV:
  9.             tmp.append(val)  # 依次入栈
  10.             while j < n and tmp[-1]==popV[j]:  # tmp栈顶值等于popV[j]值 出栈
  11.                 tmp.pop()
  12.                 j += 1
  13.         if tmp:return False
  14.         return True

包含ｍｉｎ函数的栈

定义栈的数据结构，实现一个能够得到栈最小元素的ｍｉｎ函数

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def __init__(self):
  4.         self.stack = []　# 存放数据
  5.         self.stack_min = [] #　存放最小值
  6.     def push(self, node):
  7.         if not self.stack_min:
  8.             self.stack_min.append(node)
  9.         else:
  10.             if self.min() <= node:
  11.                 self.stack_min.append(self.min())
  12.             else:
  13.                 self.stack_min.append(node)
  14.         self.stack.append(node)
  16.         # write code here
  17.     def pop(self):
  18.         if not self.stack:
  19.             return []
  20.         else:
  21.             self.stack_min.pop()
  22.             return self.stack.pop()
  23.         # write code here
  24.     def top(self):
  25.         if not self.stack:
  26.             return []
  27.         return self.stack[-1]
  28.         # write code here
  29.     def min(self):
  30.         if not self.stack_min:
  31.             return []
  32.         else:
  33.             return self.stack_min[-1]
  34.         # write code here

链表

删除链表中重复的结点

  1. # -*- coding:utf-8 -*-
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  6. class Solution:
  7.     def deleteDuplication(self, pHead):
  8.         if not pHead or not pHead.next:
  9.             return pHead
  10.         if pHead.next.val==pHead.val:
  11.             pnode = pHead.next.next
  12.             while pnode and pnode.val == pHead.val:
  13.                 pnode = pnode.next
  14.             return self.deleteDuplication(pnode)
  15.         else:
  16.             # pnode = pHead.next
  17.             pHead.next = self.deleteDuplication(pHead.next)
  18.             return pHead
  21.         # write code here

链表中环的入口结点

  1. # -*- coding:utf-8 -*-
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  6. def meeting_node(pHead):
  7.     if not pHead:
  8.         return None
  9.     pslow = pHead.next
  10.     if not pslow:
  11.         return None
  12.     pfast = pslow.next
  13.     while pslow and pfast:
  14.         if pslow==pfast:
  15.             return pslow
  16.         pslow = pslow.next
  17.         pfast = pfast.next.next
  18.     return None  # 前面没有相遇返回None
  20. class Solution:
  21.     def EntryNodeOfLoop(self, pHead):
  22.         """
  23.         1. 找到环
  24.         2. 计算环中结点个数
  25.         3. 根据环结点个数设置快指针初始
  26.         4. 快慢指针相遇
  27.         """
  28.         pmeet = meeting_node(pHead)
  29.         if not pmeet:
  30.             return None
  31.         node_count = 1 #当前相遇点包含在环中 1
  32.         pnode = pmeet
  33.         while pnode.next != pmeet:  # 遍历一圈计数得到环中结点个数
  34.             pnode = pnode.next
  35.             node_count += 1
  36.         pnode1 = pHead
  37.         for i in range(node_count):  # pnode1 先走node_count
  38.             pnode1 = pnode1.next
  39.         pnode2 = pHead
  40.         while pnode2!=pnode1:  # pnode2 走node_count步之后指向环的入口
  41.             pnode2 = pnode2.next
  42.             pnode1 = pnode1.next
  43.         return pnode1
  44.         # write code here

两个链表的第一个公共结点

  1. # -*- coding:utf-8 -*-
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. def iter_node(root):
  8.     while root:
  9.         yield root
  10.         root = root.next
  12. class Solution:
  13.     def FindFirstCommonNode(self, pHead1, pHead2):
  14.         if not pHead1 or not pHead2:
  15.             return None
  16.         p1 = [node for node in iter_node(pHead1)]
  17.         p2 = [node for node in iter_node(pHead2)]
  18.         ret = None
  19.         while p1 and p2:
  20.             top1 = p1.pop()
  21.             top2 = p2.pop()
  22.             if top1.val == top2.val:
  23.                 ret = top1
  24.                 continue
  25.             else:
  26.                 break
  27.         return ret
  30. #－－－－－－－－－－－－－－－－－－－－
  32. # -*- coding:utf-8 -*-
  33. # class ListNode:
  34. #     def __init__(self, x):
  35. #         self.val = x
  36. #         self.next = None
  38. def iter_node(root):
  39.     while root:
  40.         yield root
  41.         root = root.next
  43. class Solution:
  44.     def FindFirstCommonNode(self, pHead1, pHead2):
  45.         if not pHead1 or not pHead2:
  46.             return None
  47.         p1 = [node.val for node in iter_node(pHead1)]
  48.         for node in iter_node(pHead2):
  49.             if node.val in p1:
  50.                 return node
  51.         return None

二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     def Convert(self, pRootOfTree):
  9.         # 中序遍历
  10.         if not pRootOfTree or (not pRootOfTree.left and not pRootOfTree.right): # 只有一个根结点或空时
  11.             return pRootOfTree
  12.         self.Convert(pRootOfTree.left) #　递归处理左子树
  13.         lt = pRootOfTree.left
  14.         if lt:
  15.             while lt.right:
  16.                 lt = lt.right
  17.             pRootOfTree.left, lt.right = lt, pRootOfTree　# 修改当前根结点的指针
  19.         self.Convert(pRootOfTree.right)　　# 处理右子树
  20.         rt = pRootOfTree.right
  21.         if rt:
  22.             while rt.left:
  23.                 rt = rt.left
  24.             pRootOfTree.right, rt.left = rt, pRootOfTree
  26.         while pRootOfTree.left: #　最左的结点是双链表的第一个结点
  27.             pRootOfTree = pRootOfTree.left
  28.         return pRootOfTree
  30.         # write code here

复杂链表复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

  1. # -*- coding:utf-8 -*-
  2. # class RandomListNode:
  3. #     def __init__(self, x):
  4. #         self.label = x
  5. #         self.next = None
  6. #         self.random = None
  8. # 使用生成器来高效访问
  9. def iter_node(root):
  10.     while root:
  11.         yield root
  12.         root = root.next
  14. class Solution:
  16.     # 返回 RandomListNode
  17.     def Clone(self, pHead):
  18.         mem = dict()  # 保存对象内存地址与下标的对应关系
  19.         for i, node in enumerate(iter_node(pHead)):
  20.             mem[id(node)]=i  # id获取对象的内存地址
  21.         lst = [RandomListNode(node.label) for node in iter_node(pHead)]　# 创建ｌｓｔ保存结点值
  23.         for p, node in zip(iter_node(pHead), lst): #　复制ｎｅｘｔ和ｒａｎｄｏｍ指向
  24.             if p.next:
  25.                 node.next = lst[mem[id(p.next)]]
  26.             if p.random: 
  27.                 node.random = lst[mem[id(p.random)]]
  28.         return lst[0] if lst else None

合并两个排序的链表

  1. # -*- coding:utf-8 -*-
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  6. class Solution:
  7.     # 返回合并后列表
  8.     def Merge(self, pHead1, pHead2):
  9.         if not pHead1: # pHead1 为空返回ｐＨｅａｄ２
  10.             return pHead2
  11.         elif not pHead2:　＃　pHead2 为空返回pHead1
  12.             return pHead1
  13.         else:  # 都不为空，处理第一个元素
  14.             if pHead1.val <= pHead2.val:
  15.                 p = pHead1
  16.                 pHead1 = pHead1.next
  17.             else:
  18.                 p = pHead2
  19.                 pHead2 = pHead2.next
  20.         pnode = p  
  21.         while pHead1 and pHead2:  # 依次处理两个链表
  22.             if pHead1.val <= pHead2.val:
  23.                 pnode.next = pHead1
  24.                 pnode = pHead1
  25.                 pHead1 = pHead1.next
  26.             else:
  27.                 pnode.next = pHead2
  28.                 pnode = pHead2
  29.                 pHead2 = pHead2.next
  30.         ＃处理剩余结点
  31.         if pHead1:
  32.             pnode.next = pHead1
  33.         if pHead2:
  34.             pnode.next = pHead2
  35.         return p

反转链表

  1. # -*- coding:utf-8 -*-
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  6. class Solution:
  7.     # 返回ListNode
  8.     # 非递归版本
  9.     def ReverseList(self, pHead):
  10.         if not pHead or not pHead.next: # 空或者只有一个元素直接返回
  11.             return pHead
  12.         q = None
  13.         p = pHead
  14.         while p:
  15.             tmp = p.next #暂存下一个结点
  16.             p.next = q # 修改当前结点指向
  17.             q = p # 指向返回链表的第一个元素
  18.             p = tmp # 访问下一个
  19.         return q
  20.         # write code here
  22. #　递归版本
  23. # -*- coding:utf-8 -*-
  24. # class ListNode:
  25. #     def __init__(self, x):
  26. #         self.val = x
  27. #         self.next = None
  28. class Solution:
  29.     # 返回ListNode
  30.     def ReverseList(self, pHead):
  31.         if not pHead or not pHead.next:
  32.             return pHead
  33.         else:
  34.             pnode = self.ReverseList(pHead.next) # pnode新表头
  35.             pHead.next.next = pHead # 新表头最后一个结点指向ｐｈｅａｄ
  36.             pHead.next = None　# ｐｈｅａｄ指向None,修改尾指针
  37.             return pnode
  38.         # write code here

链表中倒数第k个结点

  1. # -*- coding:utf-8 -*-
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  6. # 设置间隔为ｋ的两个指针
  7. class Solution:
  8.     def FindKthToTail(self, head, k):
  9.     # 链表k可能大于链表长度，此时返回None
  10.         i = 0
  11.         p = head
  12.         while p and i<k:
  13.             p = p.next
  14.             i += 1
  16.         if i==k:  # k小于等于链表长度，正常处理
  17.             q = head
  18.             while p:
  19.                 q = q.next
  20.                 p = p.next
  21.             return q
  22.         return None
  23.         # write code here

从尾到头打印链表

  1. # -*- coding:utf-8 -*-
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  6. from collections import deque
  7. class Solution:
  8.     # 返回从尾部到头部的列表值序列，例如[1,2,3]
  9.     def printListFromTailToHead(self, listNode):
  10.         if not listNode:
  11.             return []
  12.         tmp = deque()  #　使用队列
  13.         while listNode:
  14.             tmp.appendleft(listNode.val)
  15.             listNode = listNode.next
  16.         return tmp
  17.         # write code here

递归和循环

矩阵覆盖

矩阵覆盖类似与斐波拉契数列

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def rectCover(self, number):
  4.         a = [0, 1, 2] 
  5.         if number<3:
  6.             return a[number]
  7.         for i in xrange(3, number+1):
  8.             a.append(a[i-1]+a[i-2])
  9.         return a[number]

变态跳台阶

动手推导一下：２^(n-1)

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def jumpFloorII(self, number):
  4.         return 2**(number-1)

跳台阶

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def jumpFloor(self, number):
  4.         a = [0,1,2] # 起步不一样
  5.         if number<3:
  6.             return a[number]
  7.         for i in xrange(3, number+1):
  8.             a.append(a[i-1]+a[i-2])
  9.         return a[number]
  10.         # write code here

斐波拉契数列

  1. # -*- coding:utf-8 -*-
  2. # 使用记忆体函数，保存中间值。
  3. from functools import wraps
  5. def memo(func):
  6.     cache = {}
  7.     @wraps(func)
  8.     def wrap(*args):
  9.         if args not in cache:
  10.             cache[args] = func(*args)
  11.         return cache[args]
  12.     return wrap
  14. class Solution:
  15.     @memo
  16.     def Fibonacci(self, n):
  17.         if n==0:
  18.             return 0
  19.         if n<2:
  20.             return 1
  21.         return self.Fibonacci(n-1) + self.Fibonacci(n-2)
  23. # 使用list缓存中间值
  24. class Solution_2:
  25.     def Fibonacci(self, n):
  26.         a = [0, 1, 1]
  27.         if n<3:
  28.             return a[n]
  29.         for i in range(3,n+1):
  30.             a.append(a[i-1]+a[i-2])
  31.         return a[n]

树

序列化二叉树

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

把二叉树打印成多行

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     # 返回二维列表[[1,2],[4,5]]
  9.     def Print(self, pRoot):
  10.         if not pRoot:
  11.             return []
  12.         nodes = [pRoot]
  13.         ret = []
  14.         while nodes:
  15.             cur, nxt = [], [] # 保存每一层结点
  16.             for node in nodes:
  17.                 cur.append(node.val)
  18.                 if node.left:
  19.                     nxt.append(node.left)
  20.                 if node.right:
  21.                     nxt.append(node.right)
  22.             nodes = nxt
  23.             ret.append(cur)
  24.         return ret
  25.         # write code here

按之字形顺序打印二叉树

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     def Print(self, pRoot):
  9.         if not pRoot:
  10.             return []
  11.         nodes = [pRoot]
  12.         flag = True
  13.         ret = []
  14.         while nodes:
  15.             cur, nxt = [], [] #　保存每一层的结点
  16.             for node in nodes:
  17.                 cur.append(node.val)
  18.                 if node.left:
  19.                     nxt.append(node.left)
  20.                 if node.right:
  21.                     nxt.append(node.right)
  22.             nodes = nxt
  23.             if flag:
  24.                 ret.append(cur)
  25.                 flag = False
  26.             else:
  27.                 ret.append(cur[::-1])
  28.                 flag = True
  29.         return ret
  30.         # write code here

对称的二叉树

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

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     def help_func(self, pRoot1, pRoot2):
  9.         if not pRoot1 and not pRoot2:
  10.             return True
  11.         if not pRoot1 or not pRoot2:
  12.             return False
  13.         if pRoot1.val != pRoot2.val:
  14.             return False
  15.         return self.help_func(pRoot1.left, pRoot2.right) and self.help_func(pRoot1.right, pRoot2.left)
  17.     def isSymmetrical(self, pRoot):
  18.         return self.help_func(pRoot, pRoot)
  19.         # write code here

二叉树的下一个结点

考察中序遍历

  1. # -*- coding:utf-8 -*-
  2. # class TreeLinkNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. #         self.next = None  # 指向父节点
  8. class Solution:
  9.     def GetNext(self, pNode):
  10.         # ｐｎｏｄｅ右子树最左的点或者ｐｎｏｄｅ父节点
  11.         if not pNode:
  12.             return None
  13.         elif pNode.right:
  14.             prt = pNode.right
  15.             while prt.left:
  16.                 prt = prt.left
  17.             return prt
  18.         elif pNode.next:            
  19.             parent = pNode.next
  20.             while parent and parent.left!=pNode:
  21.                 parent = parent.next
  22.                 pNode = pNode.next
  23.             return parent if parent else None
  25.         # write code here

平衡二叉树

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     def depth(self, root):
  9.         if not root:
  10.             return 0
  11.         lt = self.depth(root.left)
  12.         rt = self.depth(root.right)
  13.         return max(lt, rt) + 1
  15.     def IsBalanced_Solution(self, pRoot):
  16.     # 递归解法，出现多次遍历同一个结点的情况
  17.         if not pRoot:
  18.             return True
  19.         lt = self.depth(pRoot.left)
  20.         rt = self.depth(pRoot.right)
  21.         if abs(lt-rt) > 1:
  22.             return False
  23.         return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
  24.         # write code here

二叉树深度

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     def TreeDepth(self, pRoot):
  9.     # 递归解
  10.         if not pRoot:
  11.             return 0
  12.         return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1
  13.         # write code here
  15. # 非递归解
  16. # -*- coding:utf-8 -*-
  17. # class TreeNode:
  18. #     def __init__(self, x):
  19. #         self.val = x
  20. #         self.left = None
  21. #         self.right = None
  22. class Solution:
  23.     def Depth(self, root):
  25.         #　层次遍历得到深度
  26.         if not root:
  27.             return 0        
  28.         from collections import deque
  29.         dp = deque()
  30.         layer = 1
  31.         dp.append((root,1))
  32.         while dp:
  33.             node, layer = dp.popleft()
  34.             deep = layer
  35.             if node.left:
  36.                 dp.append((node.left, layer+1))
  37.             if node.right:
  38.                 dp.append((node.right, layer+1))
  39.         return deep
  41.     def TreeDepth(self, pRoot):
  42.         return self.Depth(pRoot)

二叉树中和为某一值的路径

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     # 返回二维列表，内部每个列表表示找到的路径
  9.     def FindPath(self, root, expectNumber):
  10.         if not root:  #　空树　返回空
  11.             return []
  12.         elif root.val > expectNumber: #　当前值大于期望，不存在满足条件路径返回空
  13.             return []
  14.         elif root.val == expectNumber and not root.left and not root.right: #　没有左右子树，当前值等于和，那么返回该结点(即叶子结点)
  15.             return [[root.val]]
  16.         ret = []
  17.         if root.left: ＃　递归处理左子树
  18.             lt = self.FindPath(root.left, expectNumber - root.val)
  19.             for i in lt:
  20.                 i.insert(0, root.val)
  21.                 ret.append(i)
  22.         if root.right:　# 递归处理右子树
  23.             rt = self.FindPath(root.right, expectNumber - root.val)
  24.             for i in rt:
  25.                 i.insert(0, root.val)
  26.                 ret.append(i)
  27.         return ret
  28.         # write code here

二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def VerifySquenceOfBST(self, sequence):
  4.         # 二叉搜索树，左子树值小于根，根小于右子树
  5.         #　后序遍历，左－右－根
  6.         # 找到根结点，根据搜索树的特点划分左右子树
  7.         if not sequence or len(sequence)==0:
  8.             return False
  9.         lenght = len(sequence)
  10.         root = sequence[-1]
  11.         breakindex = 0
  12.         while sequence[breakindex] < root and breakindex < lenght-1:
  13.             breakindex += 1
  14.         for i in range(breakindex,lenght):
  15.             if sequence[i] < root:
  16.                 return False
  17.         left = True
  18.         if breakindex > 0:
  19.             left = self.VerifySquenceOfBST(sequence[:breakindex])
  20.         right = True
  21.         if breakindex < lenght - 1:
  22.             right = self.VerifySquenceOfBST(sequence[breakindex:lenght-1])
  23.         return left and right

从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。层次遍历即可

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. from collections import deque
  8. class Solution:
  9.     # 返回从上到下每个节点值列表，例：[1,2,3]
  10.     # 使用队列
  11.     def PrintFromTopToBottom(self, root):
  12.         if not root:
  13.             return []
  14.         node_queue = deque()
  15.         node_queue.append(root)
  16.         ret = []
  17.         while node_queue:
  18.             first_node = node_queue.popleft() # 队首出队
  19.             ret.append(first_node.val)
  20.             if first_node.left:
  21.                 node_queue.append(first_node.left)
  22.             if first_node.right:
  23.                 node_queue.append(first_node.right)
  24.         return ret
  27. # 使用ｌｉｓｔ
  28. # -*- coding:utf-8 -*-
  29. # class TreeNode:
  30. #     def __init__(self, x):
  31. #         self.val = x
  32. #         self.left = None
  33. #         self.right = None
  34. class Solution:
  35.     # 返回从上到下每个节点值列表，例：[1,2,3]
  36.     def PrintFromTopToBottom(self, root):
  37.         if not root:
  38.             return []
  39.         node_lst, ret = [root], []
  40.         while node_lst:
  41.             ret.append(node_lst[0].val)
  42.             p = node_lst.pop(0)
  43.             if p.left:
  44.                 node_lst.append(p.left)
  45.             if p.right:
  46.                 node_lst.append(p.right)
  47.         return ret

二叉树的镜像

1) 空树返回空　２）层次遍历入队，栈出队。依次交换当前结点的左右子树

递归处理，交换当前结点左右子树，递归处理左右子树

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     # 返回镜像树的根节点
  9.     # 非递归解
  10.     def Mirror(self, root):
  11.         if not root:
  12.             return None
  13.         node_lst = [root]
  14.         while node_lst:
  15.             node = node_lst.pop()　#　默认弹出最后一个
  16.             node.left, node.right = node.right, node.left
  17.             if node.left:
  18.                 node_lst.append(node.left)
  19.             if node.right:
  20.                 node_lst.append(node.right)
  21.         return root
  23. # 递归解
  24. class Solution:
  25.     # 返回镜像树的根节点
  26.     def Mirror(self, root):
  27.         # root is None
  28.         if not root:
  29.             return None
  30.         root.left, root.right = root.right, root.left
  31.         self.Mirror(root.left)
  32.         self.Mirror(root.right)
  33.         return root

树的子结构

查找与根结点值相等的结点，依次判断左右子树是否包含同样结构

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     def DoesTree1HasTree2(self, pRoot1, pRoot2):
  9.         if not pRoot2:　# pRoot2遍历完，说明包含子结构
  10.             return True
  11.         if not pRoot1: # pRoot1遍历完，而pRoot2不为空
  12.             return False
  13.         if pRoot1.val!=pRoot2.val:
  14.             return False
  15.         return self.DoesTree1HasTree2(pRoot1.left, pRoot2.left) and self.DoesTree1HasTree2(pRoot1.right, pRoot2.right)　# 递归处理左右子结构
  18.     def HasSubtree(self, pRoot1, pRoot2):
  19.         if not pRoot1 or not pRoot2:　# 空不是子结构
  20.             return False
  21.         result = False
  22.         if pRoot1.val == pRoot2.val:  #当前结点值相等，判断是否包含子结构
  23.             result = self.DoesTree1HasTree2(pRoot1, pRoot2)　# 
  24.         if not result: #　遍历左子树
  25.             result = self.HasSubtree(pRoot1.left, pRoot2)　# 
  26.         if not result:　# 遍历右子树
  27.             result = self.HasSubtree(pRoot1.right, pRoot2)
  28.         return result

重建二叉树：给出前序和中序

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

数值运算

求１＋２＋３＋...+n(不使用乘除for/while/if/else/switch/case)

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def Sum_Solution(self, n):
  4.         # write code here
  5.         # return (pow(n,2)+n)>>1  利用公式求解
  6.         # return n and self.Sum_Solution(n-1)+n  利用递归求解,注意终止条件
  7.         # return sum(range(1,n+1))  内建公式求解
  8.         return (pow(n,2)+n)>>1

调整数组顺序使奇数位于偶数前面

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def reOrderArray(self, array):
  4.         # write code here
  5.         num1 = []
  6.         num2 = []
  7.         for num in array:
  8.             if num&0x1==0: # 利用位运算判断奇偶
  9.                 num1.append(num)
  10.             else:
  11.                 num2.append(num)
  12.         return num2+num1

数值的整数次方

指数可能正也可能负

  1. # -*- coding:utf-8 -*-
  3. class Solution:
  4.     def Power(self, base, exponent):
  5.         if exponent == 0:
  6.             return 1
  7.         if exponent == 1:
  8.             return base
  9.         exp = abs(exponent)
  10.         result = self.Power(base, exp>>1)  # 处理exp/2的情况
  11.         result *= result
  12.         if (exp & 0x1 == 1): # 最后一位是1还需要* base 奇数个base的情况
  13.             result *= base
  14.         if exponent > 0:
  15.             return result
  16.         return 1/result

二进制中1的个数

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def NumberOf1(self, n):
  4.         # 内建bin转换为二进制统计1的个数,注意处理正负号的情况
  5.         if n==0:
  6.             return 0
  7.         if n>0:
  8.             return bin(n).count('1')
  9.         else:
  10.             return bin(n&0xffffffff).count('1')
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注