机试刷题（常见）-北京尧图网络

1、数组中的最长连续子序列给定无序数组arr返回其中最长的连续序列的长度(要求值连续位置可以不连续,例如 3,4,5,6为连续的自然数Python# # 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 # # max increasing subsequence # param arr int整型一维数组 the array # return int整型 # class Solution: def MLS(self , arr: List[int]) - int: # write code here r 0 arr set(arr) for num in arr: if num - 1 in arr: # 如果 num - 1 在数组中那么 num 一定不是最长子序列的 head所以跳过这个数 continue cur_num num cur_len 1 while cur_num 1 in arr: cur_num 1 cur_len 1 r max(r, cur_len) return rGolang使用 Go 的话解题思路就不一样了因为 Go 里边没有内置类似集合这种数据结构进行处理之前最好是先排序再进行处理。package main import ( fmt sort ) /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * max increasing subsequence * param arr int整型一维数组 the array * return int整型 */ func MLS(arr []int) int { // write code here if len(arr) 0 { return 0 } sort.Ints(arr) max : 1 count : 1 for i : 1; i len(arr); i { if arr[i] -1 arr[i-1] { count max maxs(max, count) }else if arr[i] arr[i-1] { continue } else { count 1 } } return max } func maxs(x, y int) int { if x y { return x } return y } func main() { arr : []int{4, 3, 1, 5} max : MLS(arr) fmt.Println(max) }2、最长无重复子数组给定一个长度为n的数组arr返回arr的最长无重复元素子数组的长度无重复指的是所有数字都不相同。子数组是连续的比如[1,3,5,7,9]的子数组有[1,3][3,5,7]等等但是[1,3,7]不是子数组。Python# # 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 # # # param arr int整型一维数组 the array # return int整型 # class Solution: def maxLength(self , arr: List[int]) - int: # write code here maxlen 0 stack [] for num in arr: if num in stack: # 如果新的数在 stack 里边那么将 num 及 num 之前的数都删除确保 stack 是子数组且无重复元素 stack stack[stack.index(num) 1:] stack.append(num) maxlen max(maxlen,len(stack)) return maxlenGolangpackage main /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param arr int整型一维数组 the array * return int整型 */ func maxLength( arr []int ) int { // write code here if len(arr) 0 { return 0 } maxLen : 0 var tmpArr []int for _, a : range arr { index : findIndex(tmpArr, a) if index ! -1 { tmpArr tmpArr[index1:] } tmpArr append(tmpArr, a) maxLen max(len(tmpArr), maxLen) } return maxLen } func findIndex(arr []int, x int) int { for index, i : range arr { if i x { return index } } return -1 } func max(x, y int) int { if x y { return x } return y }3、判断链表中是否有环下面的解法主要是利用有环链表的特点如果有环快慢指针终究会在某个节点相遇。Python# class ListNode: # def __init__(self, x): # self.val x # self.next None # # # param head ListNode类 # return bool布尔型 # class Solution: def hasCycle(self , head: ListNode) - bool: if not head: return False s head t head while t and t.next: # 当快节点还可以继续往下走的时候 s s.next # 慢节点往下走一步 t t.next.next # 快节点往下走两步 if s t: # 如果在某个时候有碰到 return True # 表示有环 return FalseGolangpackage main import fmt type ListNode struct { val int Next *ListNode } func hasCycle( head *ListNode ) bool { slow : head fast : head if slow nil || slow.Next nil { return false } for { slow slow.Next fast fast.Next if fast nil { // 只需要判断快指针是否到末尾快指针没到末尾的话慢指针肯定没到末尾 return false } fast fast.Next if fast nil { return false } if fast slow { // 快慢指针相遇有环 return true } } } func InitListNode(head *ListNode) *ListNode { head ListNode{} head.Next ListNode{ val: 3, Next: nil, } node1 : head.Next node1.Next ListNode{ val: 2, Next: nil, } node2 : node1.Next node2.Next ListNode{ val: 0, Next: nil, } node3 : node2.Next node3.Next ListNode{ val: -4, Next: nil, } node3.Next node1 return head } func main() { var head *ListNode head InitListNode(head) isCycle : hasCycle(head) fmt.Println(isCycle) // true }4、合并两个排序的链表输入两个递增的链表单个链表的长度为n合并这两个链表并使新链表中的节点仍然是递增排序的。链表一直是我的软肋下次有疑惑可以多看看这个例子了。Python# class ListNode: # def __init__(self, x): # self.val x # self.next None # # 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 # # # param pHead1 ListNode类 # param pHead2 ListNode类 # return ListNode类 # class Solution: def Merge(self , pHead1: ListNode, pHead2: ListNode) - ListNode: # write code here if not pHead1: return pHead2 if not pHead2: return pHead1 v_head ListNode(-1) # 由于 tmp 的指针在循环过程中不断变化所以需要创建虚拟 head 节点来记住真正 head 节点的位置 tmp v_head # tmp 作为临时链表节点会不断切换 head while pHead1 and pHead2: # 每次将数值更小的链表的头结点追加到 tmp 链表 if pHead1.val pHead2.val: tmp.next pHead1 pHead1 pHead1.next else: tmp.next pHead2 pHead2 pHead2.next tmp tmp.next # 每次追加完节点后重置临时链表的头到新追加的节点 # 到这里的时候其中一个链表已经遍历完毕将另外一个链表直接追加到 tmp 链表后面 if pHead1 is None: tmp.next pHead2 else: tmp.next pHead1 # 虚拟节点的下一个节点才是真正的合并链表的 head return v_head.nextGolangpackage main type ListNode struct{ Val int Next *ListNode } /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param pHead1 ListNode类 * param pHead2 ListNode类 * return ListNode类 */ func Merge( pHead1 *ListNode , pHead2 *ListNode ) *ListNode { // write code here if pHead1 nil { return pHead2 } if pHead2 nil { return pHead1 } v_head : ListNode{} tmp : v_head for pHead1 ! nil pHead2 ! nil { if pHead1.Val pHead2.Val { tmp.Next pHead1 pHead1 pHead1.Next } else { tmp.Next pHead2 pHead2 pHead2.Next } tmp tmp.Next } if pHead1 ! nil { tmp.Next pHead1 } if pHead2 ! nil { tmp.Next pHead2 } return v_head.Next }5、连续子数组的最大和输入一个长度为n的整型数组array数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。Python# # 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 # # # param array int整型一维数组 # return int整型 # # -*- coding:utf-8 -*- class Solution: def FindGreatestSumOfSubArray(self, array): # write code here if not array: return 0 s 0 m array[0] # 初始默认最大值就是第一个元素 for i in array: s i if s m: # 如果某个时候的 sum 大于 max则重置 max 的值 m s if s 0: # 如果某个时候的 sum 比初始的 s 0 还小 s 0 # 则从后续元素开始重新查找最大值的子数组 return mGolangpackage main import ( bufio fmt os strconv ) func main() { var num int fmt.Scan(num) var arr []int scanner : bufio.NewScanner(os.Stdin) for scanner.Scan() { tmp, _ : strconv.Atoi(scanner.Text()) arr append(arr, tmp) } s : 0 m : arr[0] for _, v : range arr { s v if s m { m s } if s 0 { s 0 } } fmt.Println(m) }6、最大数给定一个长度为n的数组nums数组由一些非负整数组成现需要将他们进行排列并拼接每个数不可拆分使得最后的结果最大返回值需要是string类型否则可能会溢出。这里其实就是简单的冒泡排序就行只不过是要把更大的数排到更靠前边。# # 最大数 # param nums int整型一维数组 # return string字符串 # class Solution: def solve(self , nums ): nums [str(x) for x in nums] for i in range(len(nums)): for j in range(len(nums)-i-1): a str(nums[j]) b str(nums[j1]) # 每次把相邻的两个字符串正反拼接转成整数比较大小后确认是否交换位置 if int(.join([b, a])) int(.join([a, b])): nums[j], nums[j1] nums[j1], nums[j] if nums[0] 0: return 0 return .join(nums)7、链表的奇偶重排给定一个单链表请设定一个函数将链表的奇数位节点和偶数位节点分别放在一起重排后输出。注意是节点的编号而非节点的数值。解题思路对于原始链表每个节点都是奇数节点或偶数节点。头节点是奇数节点头节点的后一个节点是偶数节点相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表然后将偶数链表连接在奇数链表之后合并后的链表即为结果链表。Python# class ListNode: # def __init__(self, x): # self.val x # self.next None # # 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 # # # param head ListNode类 # return ListNode类 # class Solution: def oddEvenList(self , head: ListNode) - ListNode: # write code here if not head: return head odd head even head.next even_head even # 记住偶链表的头因为最后要将偶链表拼接到奇链表的末尾 while even and even.next: odd.next even.next # 奇链表 odd odd.next even.next odd.next # 偶链表 even even.next odd.next even_head # 将奇偶链表前后连起来 return headGolangpackage main import . nc_tools /* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param head ListNode类 * return ListNode类 */ func oddEvenList( head *ListNode ) *ListNode { // write code here if head nil || head.Next nil { return head } odd : head even : head.Next evenHead : head.Next for even ! nil even.Next ! nil{ odd.Next even.Next odd odd.Next even.Next odd.Next even even.Next } odd.Next evenHead return head }8、买卖股票的最好时机假设你有一个数组prices长度为n其中prices[i]是股票在第i天的价格请根据这个价格数组返回买卖股票能获得的最大收益1.你可以买入一次股票和卖出一次股票并非每天都可以买入或卖出一次总共只能买入和卖出一次且买入必须在卖出的前面的某一天2.如果不能获取到任何利润请返回03.假设买入卖出均无手续费Python贪心算法每第 i 天都计算一下如果当天卖出的话所能获得的最大收益。# # 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 # # # param prices int整型一维数组 # return int整型 # class Solution: def maxProfit(self , prices: List[int]) - int: # write code here if not prices: return 0 max_profit 0 min_price prices[0] for price in prices: min_price min(min_price, price) # 第 i 天及之前的最低价格 max_profit max(max_profit, price - min_price) # 第 i 天卖出的话所能获得的最大收益 return max_profitGolangpackage main import ( bufio fmt os strconv strings ) func main() { var num int fmt.Scan(num) var intArr []int var line string reader : bufio.NewReader(os.Stdin) line, _ reader.ReadString(\n) line strings.TrimSpace(line) arr : strings.Split(line, ) for _, v : range arr { tmp, _ : strconv.Atoi(v) intArr append(intArr, tmp) } minPrice : intArr[0] maxProfit : 0 for _, price : range intArr { minPrice min(minPrice, price) maxProfit max(maxProfit, price-minPrice) } fmt.Println(maxProfit) } func min(x, y int) int { if x y { return y } return x } func max(x, y int) int { if x y { return x } return y }9、最长公共前缀给你一个大小为 n 的字符串数组 strs 其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀返回这个公共前缀。哈哈我的第一想法竟然是 os.path.commonprefix(strs)而且还通过了用例这就比较尴尬了# # 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 # # # param strs string字符串一维数组 # return string字符串 # class Solution: def longestCommonPrefix(self , strs: List[str]) - str: # write code here import os return os.path.commonprefix(strs)不过题目显然是想让我们自己写Python# # 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 # # # param strs string字符串一维数组 # return string字符串 # class Solution: def longestCommonPrefix(self , strs: List[str]) - str: # write code here if not strs: return min_len min([len(x) for x in strs]) common_prefix for i in range(min_len): if len(set([x[i] for x in strs])) 1: common_prefix strs[0][i] else: break return common_prefixGolangpackage main /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param strs string字符串一维数组 * return string字符串 */ func longestCommonPrefix(strs []string) string { // write code here if len(strs) 0 { return } if len(strs) 1 { return strs[0] } minLen : len(strs[0]) for _, str : range strs { if len(str) minLen { minLen len(str) } } commonPrefix : for i : 0; i minLen; i { ch : strs[0][i] for _, v : range strs { if v[i] ! ch { return commonPrefix } } commonPrefix string(ch) } return commonPrefix }10、链表环入口输入分为2段第一段是入环前的链表部分第二段是链表环的部分后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表。这个也需要先判断环Python# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def EntryNodeOfLoop(self, pHead): # write code here fast pHead slow pHead if slow is None or slow.next is None: return None while fast and slow: slow slow.next fast fast.next if fast is None: return None fast fast.next if fast is None: return None if slow fast: break slow pHead if slow fast: return slow while slow ! fast: slow slow.next fast fast.next return slowGolangpackage main func EntryNodeOfLoop(pHead *ListNode) *ListNode { slow : pHead fast : pHead if slow nil || slow.Next nil { return nil } for { slow slow.Next fast fast.Next if fast nil { return nil } fast fast.Next if fast nil { return nil } if fast slow { break } } slow pHead if slow fast { return slow } for { fast fast.Next slow slow.Next if fast slow { return slow } } }

机试刷题（常见）

相关推荐

多叉树的运算

2021年wordpress国内最好用的网站优化插件

DFS非递归实现搜索图中两顶点间的所有路径

更多资讯

个人电工证怎样补办 2026河南最新政策教你一步到位

江西电工证真伪查询怎么查？上岗必备证书别被坑了

住建部电工证图片高清查询 2026河南最新政策怎么走？

房县电工证报考流程全攻略：上岗必备怎么避开中介坑

孟津电工证哪里办？郑州报考避坑指南全攻略

济南电工证啥时候考的？考前押题助你少走弯路

今日更新

电工证考试及格线你知道多少？值不值得考

南通电工证发证单位考前押题怎么搞？工地太忙根本没时间复习考试

黄陵县高低压电工证怎么考？上岗必备全流程避坑指南

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？