admin 管理员组

文章数量: 887018

找工作

JZ3 数组中重复的数字

描述

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


数据范围：
进阶：时间复杂度 ，空间复杂度

示例1

输入： [2,3,1,0,2,5,3]
返回值：2
说明：2或3都是对的

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:def duplicate(self , numbers: List[int]) -> int:# write code herefor i in numbers:if numbers.count(i)>=2:return ireturn -1

自测结果

运行结果

 

JZ4 二维数组中的查找

描述

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]

]
给定 target = 7，返回 true。
给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 ， 矩阵中的值满足
进阶：空间复杂度 ，时间复杂度 

示例1

输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：true
说明：存在7，返回true

示例2

输入：1,[[2]]
返回值：false

示例3

输入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：false
说明：不存在3，返回false

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param array int整型二维数组 
# @return bool布尔型
#
class Solution:def Find(self , target: int, array: List[List[int]]) -> bool:# write code herefor i in array:if target in i :return Truereturn False

自测结果

 

运行结果

JZ5 替换空格

描述

请实现一个函数，将一个字符串s中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。


数据范围:  。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。

示例1

输入："We Are Happy"
返回值："We%20Are%20Happy"

示例2

输入：" "
返回值："%20"

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串
#
class Solution:def replaceSpace(self , s: str) -> str:# write code hereresults = ''for i in s:if i == " ":results +="%20"else:results +=ireturn results

自测结果

 

运行结果

JZ7 重建二叉树

描述

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

 

提示:

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

3.vin出现的元素均出现在 pre里

4.只需要返回根结点，系统会自动输出整颗树做答案对比

数据范围： ，节点的值 

要求：空间复杂度 ，时间复杂度 

示例1

输入：[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值：{1,2,3,4,#,5,6,#,7,#,#,8}
说明：返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示

 

示例2

输入：[1],[1]
返回值：{1}

示例3

输入：[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值：{1,2,5,3,4,6,7}

代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pre int整型一维数组 
# @param vin int整型一维数组 
# @return TreeNode类
#
class Solution:def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:# write code hereif not pre:return Noneroot = TreeNode(pre[0])tmp = vin.index(pre[0])root.left = self.reConstructBinaryTree(pre[1:tmp+1], vin[:tmp])root.right = self.reConstructBinaryTree(pre[tmp+1:], vin[tmp+1:])return root

自测结果

  运行结果

 

JZ8 二叉树的下一个结点

描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

 

示例

输入:{8,6,10,5,7,9,11},8返回:9

解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来

数据范围：节点数满足  ，节点上的值满足 

要求：空间复杂度  ，时间复杂度 

输入描述：

输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面，用户得到的输入只有一个子树根节点

返回值描述：

返回传入的子树根节点的下一个节点，后台会打印输出这个节点

示例1

输入：{8,6,10,5,7,9,11},8 
返回值：9

示例2

输入：{8,6,10,5,7,9,11},6 
返回值：7

示例3

输入：{1,2,#,#,3,#,4},4 
返回值：1

示例4

输入：{5},5 
返回值："null" 
说明：不存在，后台打印"null"

代码

# -*- 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 hereif pNode.right:rchild = pNode.rightwhile rchild.left:rchild = rchild.leftreturn rchildwhile pNode:if pNode.next:if pNode.next.left == pNode:return pNode.nextpNode = pNode.nextelse:return None

自测结果

 

 运行结果

JZ9 用两个栈实现队列

描述

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素


数据范围：
要求：存储n个元素的空间复杂度为  ，插入与删除的时间复杂度都是

示例1

输入：["PSH1","PSH2","POP","POP"]
返回值：1,2

说明："PSH1":代表将1插入队列尾部 "PSH2":代表将2插入队列尾部 "POP“:代表删除一个元素，先进先出=>返回1 "POP“:代表删除一个元素，先进先出=>返回2

示例2

输入：["PSH2","POP","PSH1","POP"] 
返回值：2,1

代码

版本一

# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.stack1 = []self.stack2 = []def push(self, node):# write code hereself.stack1.append(node)def pop(self):# return xxif len(self.stack2) == 0:while len(self.stack1)!=0:self.stack2.append(self.stack1.pop())value= self.stack2.pop()return value

版本二

# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.stack1 = []self.stack2 = []def push(self, node):# write code hereself.stack1.append(node)def pop(self):# return xxreturn self.stack1.pop(0)

自测结果

运行结果

JZ10 斐波那契数列

描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足  的数列
数据范围： 
要求：空间复杂度  ，时间复杂度 ，本题也有时间复杂度  的解法

输入描述：

一个正整数n

返回值描述：

输出一个正整数。

示例1

输入：4
返回值：3

说明：根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。

示例2

输入：1
返回值：1

示例3

输入：2
返回值：1

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:def Fibonacci(self , n: int) -> int:# write code herea = 1 # n-1b = 1 # n-2c = 1 # n for i in range(3, n+1):c = a+b # fib(n)=fib(n-1)+fib(n-2)b = a   a = c   return c

自测结果

 运行结果

JZ11 旋转数组的最小数字

描述

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。


数据范围：  ，数组中任意元素的值： 

要求：空间复杂度：  ，时间复杂度： 

示例1

输入：[3,4,5,1,2]
返回值：1

示例2

输入：[3,100,200,3]
返回值：3

代码

1.数组为空
2.部分旋转，例如由（1,2,3,4,5）旋转为（3,4,5,1,2），此时只需要遍历数组，找到当前数比前面的数小的数即可。
3.完全旋转，例如由（1,2,3,4,5）旋转为（1,2,3,4,5），此时第一个数最小。
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param rotateArray int整型一维数组 
# @return int整型
#
class Solution:def minNumberInRotateArray(self , rotateArray: List[int]) -> int:# write code hereif len(rotateArray) == 0:return -1for i in range(len(rotateArray)-1):if rotateArray[i] > rotateArray[i+1]:return rotateArray[i+1]return rotateArray[0]

自测结果

 运行结果

JZ12 矩阵中的路径

描述

请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
数据范围： , 

示例1

输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
返回值：true

示例2

输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcb"
返回值：false

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:def hasPath(self , matrix: List[List[str]], word: str) -> bool:# write code hereif len(matrix) == 0:return Falsefor i in range(len(matrix)):for j in range(len(matrix[0])):if self.backtrack(matrix, word,0,i,j):return Truereturn Falsedef backtrack(self, matrix, word, index, i, j):if index == len(word):return Trueif i < 0 or i >= len(matrix) or j < 0 or j >= len(matrix[0]) or (matrix[i][j]!=word[index]):return Falsetemp = matrix[i][j]matrix[i][j] = '*'if (self.backtrack(matrix,word,index+1,i+1,j)or self.backtrack(matrix,word,index+1,i,j+1)or self.backtrack(matrix,word,index+1,i-1,j)or self.backtrack(matrix,word,index+1,i,j-1)):return Truematrix[i][j] = tempreturn False

自测结果

运行结果

JZ13 机器人的运动范围

描述

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


数据范围：， 


进阶：空间复杂度  ，时间复杂度 

示例1

输入： 1,2,3
返回值：3

示例2

输入： 0,1,3 
返回值：1

示例3

输入： 10,1,100
返回值：29

说明： [0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的

示例4

输入： 5,10,10
返回值：21

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param threshold int整型 
# @param rows int整型 
# @param cols int整型 
# @return int整型
#
class Solution:def movingCount(self, threshold, rows, cols):# write code hereself.rows = rowsself.cols = colsself. dict = set()self.dfs(threshold, 0, 0)return len(self.dict)def sum(self, i, j):sum = (i//10)+(i%10)+(j//10)+(j%10)return sumdef dfs(self,threshold, i,j):if (not self.sum(i,j) <= threshold) or (i,j) in self.dict:return self.dict.add((i,j))if i != self.rows-1:self.dfs(threshold, i+1, j)if j != self.cols-1:self.dfs(threshold, i, j+1)

自测结果

 运行结果

JZ14 剪绳子

描述

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。


数据范围：
进阶：空间复杂度 ，时间复杂度 

输入描述：

输入一个数n，意义见题面。

返回值描述：

输出答案。

示例1

输入：8
返回值：18

说明：8 = 2 +3 +3 , 2*3*3=18

示例2

输入：2
返回值：1

说明：m>1，所以切成两段长度是1的绳子

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
#
class Solution:def cutRope(self , number: int) -> int:# write code hereif number < 2:return 0elif number == 2:return 1elif number == 3:return 2else:x = number % 3y = number // 3if x == 0:res=3**yelif x == 1:res=3**(y-1)*4else:res=3**y*2return res

自测结果

 

 运行结果

本文标签： 找工作

版权声明：本文标题：找工作 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687124249h66545.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。