韶关做网站的公司,快印店网站建设84wzjs,网站建设面试表,云南品牌网站开发leetcode-剑指offer-11.面试题3-数组中的重复数字2.面试题04-二维数组中的查找3.面试题05-替换空格4.面试题06-从尾到头打印链表5.面试题07-重建二叉树6.面试题09-两个堆栈实现队列7.面试题10-1-斐波那契数列8.面试题10-2-青蛙跳台阶问题9.面试题11-旋转数组的最小数字10.面试题…
leetcode-剑指offer-11.面试题3-数组中的重复数字2.面试题04-二维数组中的查找3.面试题05-替换空格4.面试题06-从尾到头打印链表5.面试题07-重建二叉树6.面试题09-两个堆栈实现队列7.面试题10-1-斐波那契数列8.面试题10-2-青蛙跳台阶问题9.面试题11-旋转数组的最小数字10.面试题12-矩阵中的路径本系列博文为题库刷题笔记仅在督促自己刷题如有不详之处请参考leetcode官网https://leetcode-cn.com/problemset/lcof/编程语言为python
1.面试题3-数组中的重复数字
在一个长度为n的数组里所有的数字都在0-n-1的范围内数组中某些数字是重复了的但是不知道有几个数字是重复了的也不知道每个数组的重复次数。请找出数组中任意一个重复的数字 hash表存储遍历过的数字如果表中已经存在直接返回。
class Solution(object):def findRepeatNumber(self, nums)::type nums: List[int]:rtype: intvis_has{}for val in nums:if vis_has.get(val): #访问字典的键值都用这个方法return valelse:vis_has[val]Trueleetcode 287.寻找重复数字 给定一个包含n1个整数的数组其中数字都在1-n之间可知至少存在一个重复数字。假设只存在一个重复整数找出这个重复的数。 要求 不能更改原数组假设数组是只读的。 只能使用额外的 O(1) 的空间。–不能用hash表 时间复杂度小于 O(n2) 。–暴力法的时间复杂度是o(n2) 数组中只有一个重复的数字但它可能不止重复出现一次。 –弗洛伊德兔子乌龟。如果有重复数字那么就会有至少两个索引指向相同的数字这就是链表中成环的条件。检验链表入环节点就是重复的数字。 vinums[i],指向下一个索引
class Solution(object):def findDuplicate(self, nums)::type nums: List[int]:rtype: inttnums[0]rnums[0]while True:tnums[t]rnums[nums[r]]if tr:breakrnums[0]while t!r:tnums[t]rnums[r]return t2.面试题04-二维数组中的查找
在一个nm的二维数组中每一行都按照从左往右递增的顺序每一行都按从左到右递增顺序排序每一列都按照从上到下递增顺序排列完成在二维数组中查找指定数在返回true,不在返回false.与leetcode240一致 思路1:暴力搜索忽略有序条件时间复杂度o(nm) 思路2:线性查找从数组的右上角开始搜索
nums[0][n-1]target: return truenums[0][n-1]target: 去更大的区域查找,行坐标加1nums[0][n-1]taget: 去更小的区域查找列坐标减1 直至行列索引不符合条件时间复杂度o(nm)
class Solution(object):def findNumberIn2DArray(self, matrix, target)::type matrix: List[List[int]]:type target: int:rtype: boolmlen(matrix)if m0:return Falsenlen(matrix[0])i,j0,n-1while(-1im and -1jn):if matrix[i][j]target:return Trueelif matrix[i][j]target:i1else:j-1return False3.面试题05-替换空格
请实现一个函数把字符串中的空格替换成“%20”。 考察的是字符串可变不可变转义字符的输出 直接想法新建一个res_str遍历原字符串按要求复制一份。–python操作十分方便
class Solution(object):def replaceSpace(self, s)::type s: str:rtype: strres_strfor char in s:if char :res_str%20else:res_strcharreturn res_str4.面试题06-从尾到头打印链表
输入一个链表的头节点从尾到头反过来返回每个节点的值用数组返回。 思路1先将链表反转然后打印输出就可以了。
class Solution(object):def reversePrint(self, head)::type head: ListNode:rtype: List[int]if headNone:return []pre_nodeNonecur_nodeheadwhile(cur_node):next_nodecur_node.nextcur_node.nextpre_nodepre_nodecur_nodecur_nodenext_noderes[]new_nodepre_nodewhile(new_node):res.append(new_node.val)new_nodenew_node.nextreturn res思路2将链表正序输出将结果res逆序输出就好。
class Solution(object):def reversePrint(self, head)::type head: ListNode:rtype: List[int]if headNone:return []res[]cur_nodeheadwhile(cur_node):res.append(cur_node.val)cur_nodecur_node.nextreturn res[::-1]5.面试题07-重建二叉树
leetcode 105:从前序与中序遍历序列构二叉树
6.面试题09-两个堆栈实现队列
用两个堆栈实现一个队列。请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入整数和在队列头部删除整数若队列中没有元素deleteHead操作返回-1
堆栈先进后出队列先进先出 方案1: 两个栈 主栈存队列。需要添加元素时将原有的所有元素押入辅助栈将元素押入栈底然后将辅助栈的元素押回主栈。删除元素直接弹出栈顶元素 辅助栈辅助主栈实现存元素操作这个思路主要保证先存入的元素在栈顶。
class CQueue(object):def __init__(self):self.main_stack[]self.help_stack[]def appendTail(self, value)::type value: int:rtype: Noneif self.main_stack[]:self.main_stack.append(value)else:while(self.main_stack):self.help_stack.append(self.main_stack.pop())self.main_stack.append(value)while(self.help_stack):self.main_stack.append(self.help_stack.pop())def deleteHead(self)::rtype: intif self.main_stack[]:return -1return self.main_stack.pop()4024ms 17.3MB
方案1主要费时在添加一个新元素的时候需要移动主栈内的所有元素然后将所有元素押回来保证最先存入的元素在主栈顶。 改进方案 插入元素维护一个主堆栈每次加元素往堆栈顶添加元素就可以了 删除元素维护一个辅助堆栈需要弹出元素时将主栈的元素弹入辅助栈那么第一个入主栈的元素将出现在辅助栈顶直接将其弹出。重点此时不需要将剩余元素弹回主栈因为下一次删除操作对象还是在辅助栈栈顶。所以弹出操作检查辅助栈是否为空为空将主栈中元素弹入辅助栈中弹出辅助栈栈顶即可。时间快了3倍数。
class CQueue(object):def __init__(self):self.main_stack[]self.help_stack[]def appendTail(self, value)::type value: int:rtype: Noneself.main_stack.append(value)def deleteHead(self)::rtype: intif self.main_stack[] and self.help_stack[]:return -1if self.help_stack[]:while(self.main_stack):self.help_stack.append(self.main_stack.pop())return self.help_stack.pop()1816ms 17.4MB
7.面试题10-1-斐波那契数列
写一个函数求输入n的斐波那契数列的第n项。 答案需要取模 1e971000000007如计算初始结果为1000000008请返回 1。
class Solution(object):def fib(self, n)::type n: int:rtype: intif n0:return 0if n1:return 1prepre_f0pre_f1f0for i in range(2,n1): fpre_fprepre_fprepre_fpre_fpre_ffreturn f%(10**97)循环求余法用于解决大数越界问题python可以不用考虑大数越界问题。
8.面试题10-2-青蛙跳台阶问题
一只青蛙一次可以跳一阶台阶也可以跳2阶台阶。求该青蛙跳上一个n阶台阶总共有多少总跳法。
答案需要取模 1e971000000007如计算初始结果为1000000008请返回 1。
f(i)表示跳到第i个台阶的方法数它可以由i-1个台阶跳上来也可以从i-2个台阶跳上来。所以这两种方式所拥有的方法数相加就是跳上第i阶台阶有的方法数即f(i)f(i−1)f(i−2)f(i)f(i-1)f(i-2)f(i)f(i−1)f(i−2)。看到这个表达式不就是斐波那契数列么再求一次斐波那契数列就好了唯一的区别就是初始条件prepre_f应该初始化为1pre_f初始化为1。
class Solution(object):def numWays(self, n)::type n: int:rtype: intif n0:return 1if n1:return 1prepre_f1pre_f1for i in range(2,n1):fpre_fprepre_fprepre_fpre_fpre_ffreturn f%(10**97)9.面试题11-旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。输入一个递增排序的数组的一个旋转输出旋转数组的最小元素。例如数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转该数组的最小值为1。
思路1:暴力找一个数组最小o(n)
class Solution(object):def minArray(self, numbers)::type numbers: List[int]:rtype: intnlen(numbers)resfloat(INF)for val in numbers:resmin(res,val)return res思路2:二分查找初始化l0rlen(numbers)用中点mid(lr)//2将数组分成两个部分。判断是否两边都有序旋转点在无序的那一边
class Solution(object):def minArray(self, numbers)::type numbers: List[int]:rtype: intnlen(numbers)if n0:return Nonel,r0,n-1while(lr):mid(lr)//2if numbers[mid]numbers[r]: # 右边无序旋转点在右边numbers[mid]比右端点都大最小肯定不是它lmid1elif numbers[mid]numbers[r]: # 右边有序最小可能是numbers[mid]rmidelse:r-1return numbers[r]10.面试题12-矩阵中的路径
请设计一个函数用来判断在一个矩阵是否存在一条包含某字符串所有字符的路径。路径可以总矩阵的任意一个格子开始每一步可以在矩阵中向左、向右、向上、向下移动一格。如果一条路径经过了某一格子那么该路径不能再次进入该格子。
dfs递归遍历。以每个位子开始寻找该匹配的字符串。有一个visted矩阵用于记录哪些格子已经遍历过了: 保护现场和恢复现场的问题
class Solution(object):def exist(self, board, word)::type board: List[List[str]]:type word: str:rtype: boolmlen(board)if m0:return Falsenlen(board[0])visted[]visted[[False]*n for _ in range(m)]def dfs(string,i,j):if len(string)1 and string[0]board[i][j]:return Trueif string[0]board[i][j]:visted[i][j]Trueif i-1-1 and visted[i-1][j]False:if dfs(string[1:],i-1,j):return Trueif i1m and visted[i1][j]False:if dfs(string[1:],i1,j):return Trueif j-1-1 and visted[i][j-1]False:if dfs(string[1:],i,j-1):return Trueif j1n and visted[i][j1]False:if dfs(string[1:],i,j1):return Truevisted[i][j]Falsereturn Falsefor i in range(m):for j in range(n):if dfs(word,i,j):return Truereturn False
