没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源讲义互联网常见算法笔试题分类总结.pdf

互联网常见算法笔试题分类总结.pdf

剑指offer

需积分: 10 5 下载量 7 浏览量 2020-12-20 20:36:45 上传评论收藏 8.29MB PDF 举报

温馨提示

试读

63页

互联网常见算法笔试题分类总结，欢迎下载，全是干货。

资源推荐

资源详情

资源评论

排序算法

冒泡排序

原理(升序)

进行第一次遍历，比较相邻元素，如果左侧元素大于右侧元素，则交换位置，这样遍历一次之后，

就可以找出最大值处于数组最末端；

进行第二次遍历，执行同样的比较，不包括最后一个元素，第二大的数就会处于数组倒数第二个位

置；

以此类推，遍历len(nums)次，就可以对整个数组排序完毕。

复杂度

最坏时间复杂度：$0(N^2)$

最优时间复杂度：$O(N)$

平均时间复杂度：$O(N^2)$

空间复杂度：$O(1)$

python code

import numpy as np

np.random.seed(5)

nums = np.random.randint(0, 100, size=20, )

print(nums)

sort_nums = np.sort(nums)

print(sort_nums)

选择排序

原理（升序）

第一次遍历，在未排序序列中找到最小元素，存放到排序序列的起始位置。

第二次遍历，从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾

重复第二步，直到所有元素均排序完毕。

复杂度

最坏时间复杂度：$O(N^2)$

最优时间复杂度：$O(N^2)$

平均时间复杂度：$O(N^2)$

额外空间复杂度：$O(1)$

python code

插入排序

原理（升序）

遍历整个序列，每拿到一个值就将其与其前面的序列中所有值挨个比较，将其插入到适当位置

复杂度

最坏时间复杂度： $O(N^2)$

最优时间复杂度： $O(N)$

平均时间复杂度： $O(N^2)$

额外空间复杂度： $O(1)$

python code

def bubble_sort(nums):

 for j in range(len(nums)-1, 0, -1):

   for i in range(j):

     if nums[i] > nums[i+1]:

       nums[i], nums[i+1] = nums[i+1], nums[i]

 return nums

print(bubble_sort(nums))

assert all(bubble_sort(nums)==sort_nums)

def select_sort(nums):

 for j in range(len(nums)-1):

   min_index = j

   for i in range(j+1, len(nums)):

     if nums[i] < nums[min_index]:

       min_index = i

   nums[min_index], nums[j] = nums[j], nums[min_index]

 return nums

print(select_sort(nums))

assert all(select_sort(nums)==sort_nums)

希尔排序

归并排序

快速排序

原理

快速排序的主要原理包含二分法（分治）和递归

每次选定一个基准值，将当前数组依据与基准值的大小关系分成两个子数组

递归地对两个子数组执行同样的操作

递归结束的条件是当前数组仅剩一个元素或者0个元素

最终排序后的数组=[小于基准值的数组] + [基准值] + [大于基准值的数组]

复杂度

最坏时间复杂度: $O(N^2)$

最优时间复杂度: $O(NlogN)$

平均时间复杂度: $O(NlogN)$

额外空间复杂度: $O(logN)$

堆排序

计数排序

def insert_sort(nums):

 for j in range(len(nums)):

   for i in range(j):

     if nums[j] < nums[i]:

       nums[i], nums[j] = nums[j], nums[i]

 return nums

print(insert_sort(nums))

assert all(insert_sort(nums)==sort_nums)

def quick_sort(nums):

 if len(nums)<=1:

   return nums

 else:

   pivot = nums[0]

   more = []

   less = []

   for i in range(1, len(nums)):

     if nums[i] > pivot:

       more.append(nums[i])

     else:

       less.append(nums[i])

   return quick_sort(less) + [pivot] + quick_sort(more)

 

print(quick_sort(nums))

assert all(quick_sort(nums)==sort_nums)

桶排序

基数排序

数组

【剑指Oﬀer】1. 二维数组中的查找

题目

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排

序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路

循环迭代查找的时间复杂度是O(n^2)，最优化的方式是从左下或者右上开始搜索，因为数组本身

是从左到右依次增大，从上到下依次增大。

从右上开始搜索，如果数组中的数比该数要大，那么向左移动一位，如果数组中的数比该数小，向

下移动一位。

【剑指Oﬀer】6. 旋转数组的最小数字

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路

class Solution:

 # array 二维列表

 def Find(self, target, array):

   # write code here

   raw = len(array)

   col = len(array[0])

   i = 0

   j = col - 1

   while i < raw and j >= 0:

     if array[i][j] > target:

       j -= 1

     elif array[i][j] < target:

       i += 1

     else:

       return True

   return False

原数组非递减，也就是说右侧的元素一定大于等于左侧元素，如下图：

但是旋转后就变成了这样：

二分查找：其输入是一个有序的元素列表（必须是有序的），解决思路是：观察 left、mid、right

三个指针对应的元素的大小关系，然后移动指针。

本题是一个变相的二分查找，解决思路同样是：观察 left、mid、right 三个指针对应的元素的大小

关系，然后移动指针。

如果left<=mid是正常情况，说明最小值在右半个数组内。

如果mid<=right也是正常情况，说明最小值在左半个数组内。

一直二分，循环直至将left和right区间内的元素为空。

【剑指Oﬀer】13. 调整数组顺序使奇数位于偶数前面

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，

所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

解题思路一

新建两个数组分别存放奇数和偶数

class Solution:

 def minNumberInRotateArray(self, rotateArray):

   if len(rotateArray) == 0:

     return 0

   # write code here

   left = 0

   right = len(rotateArray) - 1

   while (right - left != 1):

     mid = (left + right) / 2

     if rotateArray[left] <= rotateArray[mid]:

       left = mid

     elif rotateArray[mid] <= rotateArray[right]:

       right = mid

   return rotateArray[right]

剩余62页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

NickBlog

粉丝: 3w+
资源: 4

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

互联网常见算法笔试题分类总结.pdf

人工智能算法岗笔试题（截图）.pdf

C、C++各大公司面试笔试题

常见C++笔试题目整理（含答案）.docx

C++面试题笔试题C++ 数据结构算法笔试题资料合集.zip

Java笔试题及答案..pdf

嵌入式笔试题汇总1.pdf

人民银行笔试真题计算机总结.pdf

京东2018秋招算法工程师笔试题及答案.pdf

信息技术部笔试题.doc.pdf

2021年前端笔试题汇总 PDF.pdf

android笔试题及答案.pdf

嵌入式C语言笔试题及答案.pdf

java面试笔试题大汇总.pdf

数据结构与算法笔试题考点分析.doc

(完整版)hadoop常见笔试题答案.pdf

硬件工程师笔试题附答案.pdf

滴滴出行2017秋招算法岗笔试真题汇总.pdf

2022年SQL数据库经典面试题笔试题 (2).pdf

xx嵌入式笔试题及答案.pdf

面试知识点总结--java笔试算法题及答案.pdf

超全的嵌入式工程师笔试面试题汇总.zip

2022前端笔试题 - javascript.pdf

Vector Davinci官方帮助配置使用手册（AutoSAR）.pdf

c++入门，核心，提高讲义笔记

离散数学及其应用 第八版 奇数编号练习答案.pdf

数字图像处理 冈萨雷斯 课后习题

科研伦理与学术规范 期末考试2 （40题）.pdf

最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理.emmx

最新资源

离散数学及其应用第八版奇数编号练习答案.pdf

数字图像处理冈萨雷斯课后习题

科研伦理与学术规范期末考试2 （40题）.pdf

最值得收藏的考研线性代数全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理.emmx