牛客网《剑指Offer》66题 题解
-
字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
dfs， 但是牛客网有些尴尬，list的顺序还得保障，所以结果得sort一下。为了防止重复，用了set。
class Solution: def Permutation(self, ss): if not ss: return [] res = set() def dfs(res, ss, s): if not ss: res.add(s) for i in range(len(ss)): s = s + ss[i] dfs(res, ss[:i] + ss[i + 1:], s) s = s[:-1] dfs(res, ss, '') return sorted(list(res))当然，这只是简单得写法。高级得用swap实现，详情见STL中得permutation经典算法。
-
链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
先求链表长度n，然后输出第n-k节点。注意k>n的情况。
# -*- 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 n = 0 p = head while p: n += 1 p = p.next if k > n: return None t = n - k p = head for _ in range(t): p = p.next return p
-
跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
，斐波那契数列的变体。
class Solution: def jumpFloor(self, number): # write code here a, b = 1, 1 for i in range(number): a, b = b, a + b return a
-
变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
数学推导：，
，因而有。
class Solution: def jumpFloorII(self, number): # write code here return 2 ** (number-1)
-
不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
也就是用二进制的加法，二进制位相加用异或，进位用与并左移一位。
class Solution { public: int Add(int num1, int num2) { int tmp; while(num2 != 0){ tmp = num1 ^ num2; num2 = (num1 & num2) << 1; num1 = tmp; } return num1; } };
上述的实现有些技巧，主要利用c++整数逸出会变0解决的情况，而python则没有逸出的概念，所以我们要与上0xffffffff。
class Solution(object): def getSum(self, a, b): """ :type a: int :type b: int :rtype: int """ # 32 bits integer max MAX = 0x7FFFFFFF # 32 bits interger min MIN = 0x80000000 # mask to get last 32 bits mask = 0xFFFFFFFF while b != 0: # ^ get different bits and & gets double 1s, << moves carry a, b = (a ^ b) & mask, ((a & b) << 1) & mask # if a is negative, get a's 32 bits complement positive first # then get 32-bit positive's Python complement negative return a if a <= MAX else ~(a ^ mask)
-
替换空格
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class Solution: # s 源字符串 def replaceSpace(self, s): # write code here import re s = re.sub(' ', '%20', s) return s
-
顺序针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 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.
class Solution: # matrix类型为二维列表，需要返回列表 def printMatrix(self, matrix): # write code here return matrix and list(matrix.pop(0)) + self.printMatrix(list(zip(*matrix))[::-1])
-
二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
类似二叉搜索树，从右上角开始依次左、下遍历，或者从左下角开始依次上、右遍历。
class Solution: # array 二维列表 def Find(self, target, array): # write code here m, n = len(array), len(array[0]) i, j = 0, n - 1 while i < m and j >= 0: if array[i][j] == target: return True elif array[i][j] < target: i += 1 else: j -= 1 return False
-
包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
同时维护一个最小栈。
class Solution: def __init__(self): self.stack = [] self.minstack = [] def push(self, node): # write code here self.stack.append(node) if not self.minstack: self.minstack.append(node) elif node < self.minstack[-1]: self.minstack.append(node) else: self.minstack.append(self.minstack[-1]) def pop(self): # write code here self.stack.pop() self.minstack.pop() def top(self): # write code here return self.stack[-1] def min(self): # write code here return self.minstack[-1]
-
重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
class Solution: def reConstructBinaryTree(self, preorder, inorder): """ :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """ if inorder: id = inorder.index(preorder.pop(0)) root = TreeNode(inorder[id]) root.left = self.reConstructBinaryTree(preorder, inorder[:id]) root.right = self.reConstructBinaryTree(preorder, inorder[id+1:]) return root
-
用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
一个in栈，一个out栈，in栈用于直接push，out栈用于逆向pop in 栈中的元素。
class Solution: def __init__(self): self.instack = [] self.outstack = [] def push(self, node): self.instack.append(node) def pop(self): if not self.outstack: while self.instack: self.outstack.append(self.instack.pop()) return self.outstack.pop()
-
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
二分查找的变体，采用左闭右开的写法，维持l是最小值。
class Solution: def minNumberInRotateArray(self, rotateArray): if not rotateArray: return 0 l, h = 0, len(rotateArray) - 1 while l < h: m = (l + h) // 2 if rotateArray[m] > rotateArray[h]: l = m + 1 else: h = m return rotateArray[l]
-
斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
用a, b 两个变量记录前后两个斐波那契数，c记录第几个。(注意n=0, 0)
class Solution: def Fibonacci(self, n): a, b = 0, 1 c = 0 while c < n: b, a, c = a, a + b, c + 1 return a
-
矩阵覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
还是斐波那契的变体形式，不想写递推了，直接递归实现。不过python会超时，所以改用java拉。
public class Solution { public int RectCover(int target) { if(target==0) return 0; else if(target==1) return 1; else if(target==2) return 2; else return RectCover(target-1)+RectCover(target-2); } }
-
二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
先求出二进制，然后不同向右移位，统计最低位为1的数量。
class Solution: def NumberOf1(self, n): return sum([(n >> i & 1) for i in range(0, 32)])
-
数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
class Solution: def Power(self, base, exponent): return base ** exponent当然有高深的解法，也就是==>快速幂.(https://www.cnblogs.com/CXCXCXC/p/4641812.html)
class Solution: def Power(self, base, exponent): ans = 1 while exponent: if exponent & 1: ans *= base base *= base exponent >>= 1 return ans这种再牛客网上提交会超时，毕竟python，时间限制的严。但是这确实是O(log n)的解法。
主要思想是分解exponent，如base=a, exponent=11,，也就是说
也就是不停判断exponent的最低一位，a则不停翻倍，实现a=>a2=>a3 ，如果b的最低位是1就乘上去呗。
-
调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
类似冒泡算法，前偶后奇数就交换：
class Solution: def reOrderArray(self, array): n = len(array) for i in range(n): for j in range(n-1, i, -1): if array[j] & 1 and not array[j - 1] & 1: array[j], array[j-1] = array[j-1], array[j]当然最简单的还是耗空间的解法，遍历楼。
-
反转链表
输入一个链表，反转链表后，输出链表的所有元素。
链表经典题型拉。三个指针拉，pre, cur, pos。cur.next = pre是关键。
class Solution: # 返回ListNode def ReverseList(self, pHead): pre = None while pHead: pos = pHead.next pHead.next = pre pre
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！