没什么可说的, 改进方法就是加一个标志位防止有序后重复遍历. 由于需要遍历两次, 所以时间复杂度O(N^2)
外层从0开始默认outer是最小数的下标, 内存从outer+1位置开始遍历, 不稳定, 如{ 3, 3, 3, 2 }, 当比较最后一个4时, 是第一个3和2交换, 从而不稳定. 内外层遍历两次, 时间复杂度O(N^2)
插入排序选择排序冒泡排序有浪费许多比较的次数
归并排序快的是因为小范围合并为大范围时, 有序可以同过外排方式
小组和为大组时, 组内有序没有浪费, 永远是组与组之间的比较
迄今为止, 除了在一些特殊的情况下, 还没人能够从理论上分析希尔排序的效率, 有各种各样基于实验的评估, 估计它的时间级从O(N^(3/2))
到O(N^(7/6))
递归公式同归并排序, 由于需要记录分隔点, 所以额外空间复杂度O(logN), 快排做不到稳定性, 因为partition过程做不到稳定
基础类型很长时, 使用快排, 因为基础数据类型不要求稳定
复合数据类型长度很长时, 使用归并排序, 复合数据类型要求稳定
任何数据类型的数组长度很短(<60)时, 使用插入排序
非基于比较的排序, 与被排序的样本的实际数据状况有很大关系, 所以实际中并不经常使用
简单桶排序: 一个桶统计一个数, 大体思路同计数排序, 如果数据是期望平均分布的,则每个桶中的元素平均个数为N/M, 最后一个for循环时间复杂度M*N/M
, 所以总的时间复杂度O(N), 空间复杂度O(M+N). 头结点处理的挺漂亮, 其实就是计数排序.
桶排序的时间复杂度就可以近似认为是O(N)的, 就是桶越多, 时间效率就越高, 而桶越多, 空间却就越大, 由此可见时间和空间是一个矛盾的两个方面
时间复杂度先遍历数组求最大值最小值O(N), 然后加入桶O(N), 再累加桶O(M), 最后遍历原始数组O(N), 所以总的时间复杂度O(M+N), 当M=N时时间复杂度O(N), 空间复杂度O(N+K), M为数字的范围, 稳定
其实利用计数排序的稳定性原理
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
O(M * logN)
假设按照升序排序的数组在预先未知的某个点上进行了旋转
在一个数组中, 每一个数左边比当前数小的数累加起来, 叫做这个数组的小和. 求一个数字的小和. 如[1, 3, 4, 2, 5]小和为16
在一个数组中, 左边的数如果比右边的数大, 则这两个数构成一个逆序对, 请打印所有逆序对
给定一个数组arr, 和一个数num, 请把小于num的数放在数组的左边, 等于num的数放在数组的中间, 大于num的数放在数组的右边, 要求额外空间复杂度O(1), 时间复杂度O(N)
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
给定一个数组, 求排序之后相邻两数的最大差值, 要求时间复杂度O(N), 且要求使用非基于比较的排序
如何可以得到数据流中排序后的中位数
(1) 当天结束后手里 有 stock. 可能保持前一天的状态, 也可能是今天卖出的. cash
(2) 当天结束后手里 没有 stock. 可能保持前一天的状态, 也可能是买入了. hold
给定一个数组arr, 该数组无序, 但每个值均为正数, 再给定一个正数k. 求arr的所有子数组中元素累加和为k的最长子数组
给定一个数组arr, 数组有正有负, 和一个整数aim, 求在arr中, 累加和等于aim的最长子数组的长度
数组中都是整数, 有奇数有偶数, 求奇数与偶数个数相等的最长子数组
数组中含有0, 1, 2, 求子数组中含有1的数量和含有2的数量相等的最长子数组是多少
给定一个数组arr, 可以任意把arr分成很多不相容的子数组. 求: 分出来的子数组中, 异或和为0的子数组最多是多少
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边, 窗口每次向右滑一个位置. 如果数组长度为n, 窗口大小为w, 则一共产生n-w+1个窗口的最大值. 实现一个函数. 输入: 整型数组arr, 窗口大小为w. 输出: 一个长度为n-w+1的数组res, res[i]表示每一种窗口状态下的数组
解决数组中所有数, 左边距离它最近比它小/大的数, 右边距离它最近比它小/大的数. 要求O(N)
给定一个整型正方形矩阵matrix, 把该矩阵调整成顺时针转换90度的样子. 额外空间复杂度O(1)
给定一个矩阵matrix, 按照"之"字形方式打印这个矩阵
给定一个由N*M的整数型矩阵matrix和一个整数K, matrix的每一行和每一列都是排好序的. 实现一个函数, 判断K是否在matrix中. 要求时间复杂度O(N+M), 额外空间复杂度O(1)
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
一个矩阵中只有0和1两种值, 每个位置都可以和自己的上行左右四个位置相连, 如果有一片1连在一起, 这个部分叫做一个岛, 求一个矩阵中有多少个岛
实现一个特殊的栈, 在实现栈的基本功能的基础上, 再实现返回栈中的最小元素的操作. 要求: 1. pop, push, getMin操作的时间复杂度都是O(1); 2. 设计的栈类型可以使用现成的栈结构
逆序栈, 不能申请额外的数据结构, 只能使用递归函数
输入一个链表, 输出该链表中倒数第k个结点
将单向链表按某值划分成左边小, 中间相等, 右边大的形式
输入一个复杂链表(每个节点中有节点值, 以及两个指针, 一个指向下一个节点, 另一个特殊指针指向任意一个节点), 返回结果为复制后复杂链表的head. (注意, 输出结果中请不要返回参数中的节点引用, 否则判题程序会直接返回空)
curCopy->next = (next !=
nullptr
算法1: 哈希表, 边遍历变查找, 使用set容器和find函数
算法2: 使用快慢指针, 快慢指针相遇后, 快指针从head从重新开始遍历, 一次走一个节点
x为环前面的路程(黑色部分), a为环入口到相遇点的路程(蓝色部分, 假设顺时针走), c为环的长度()(蓝色+红色部分).
即环前面的路程 = 数个环的长度 (为可能为0) + c - a
c-a是相遇点后, 环后面部分的路程(红色部分)
所以, 可以让一个指针从起点A开始走, 让一个指针从相遇点B开始继续往后走
2个指针速度一样, 那么, 当从原点的指针走到环入口点的时候(此时刚好走了x)
从相遇点开始走的那个指针也一定刚好到达环入口点, 所以2者会相遇, 且恰好相遇在环的入口点
实现一个函数, 如果两个链表相交, 返回相交的第一个结点, 如果不相交返回nullptr. 如果链表1长度N, 链表2长度M, 要求时间复杂度O(M+N), 额外空间复杂度O(1)
(1) loop1=loop2时, 第二中情况. 转化到两个无环链表, 找第一相交节点
后继: 该节点中序遍历的下一个节点
前驱: 该结点中序遍历的前一个节点
一个二叉搜索树具有如下特征
目前版本只有先序方式的序列化与反列化
算法: 使用string字符串没有结束字符, 分隔后找不到结尾, 故统一每个节点后的分隔符为叹号. 反序列化的关键在于string的分隔, string的find使用方法是关键, 使用了string::npos
要求: 时间复杂度低于O(N), N为这颗树的节点个数
输入一颗二叉树的根节点和一个整数, 打印出二叉树中结点值的和为输入整数的所有路径. 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径.
输入二叉树先序遍历和中序遍历结果, 重建二叉树
给定彼此独立的两颗树头结点分别为t1和t2, 判断t1中是否有与t2树拓扑结构完全相同的子树
给定彼此独立的两颗树头结点分别为t1和t2, 判断t1树是否包含t2树全部的拓扑结构
给定一课二叉树的头结点head, 以及这颗树中的两个节点o1和o2, 返回o1和o2的最近公共祖先节点
给定一个非空二叉树,返回其最大路径和。
以每个节点作为头结点的树都是平衡树则整颗树平衡.
给定一棵二叉树的头节点head, 请返回最大搜索二叉子树的大小
二叉树中, 一个节点可以往上走和往下走, 那么从节点A总能走到节点B. 节点A走到节点B的距离为: A走到B最短路径上的节点个数. 求一棵二叉树上的最远距离
一个公司的上下节关系是一棵多叉树, 这个公司要举办晚会, 作为组织者已经摸清了大家的心理: 一个员工的直接上级如果到场, 这个员工肯定不会来. 每个员工都有一个活跃度的值, 决定谁来你会给这个员工发邀请函, 怎么让舞会的气氛最活跃? 返回最大的活跃值
matrix[1] = {1 , 5}, 表示1这个员工的直接上级为1(他自己是这个公司的最大boss), 1这个员工自己的活跃度为5
为了让晚会活跃度最大, 应该让1不来, 0和2来. 最后返回活跃度为10
哈希函数可以打乱输入规律
特征: (1)与输入规律无关; (2)输出结果模m, 结果0~m-1均匀分布
急需1000个哈希函数(相对独立), 可以通过1个哈希函数来获得
比如哈希函数h, 会得到2^64范围, 16字节字符串, 得到结果分为高8位h1与低8位h2
哈希表: 利用哈希函数做一N桶, 在桶中挂一些链. 哈希表的增删改查可以理解成时间复杂度O(1), 但实际不是, 有扩容代价, 哈希表扩容, 离线扩容
100T大文件, 每行是一个字符串, 打印所有重复的字符串. 思路: 通过哈希分流
问: 处理大文件按行读是否有很快的读取工具
把每一行作为文本读出来, 利用哈希函数计算一个哈希code, 然后模1000, 模的结果是多少就存放在多少号的机器上. 相同的文本一定会分配到一台机器上, 如果有重复的文本一定会来到一台机器上, 出现的不同字符串(相同字符串算一种)
不安全网页的黑名单包含100亿个黑名单网页, 每个网页的URL最多占用64B. 现在想要实现一个网页过滤系统, 利用该系统可以根据URL判断该网页是否在黑名单上, 设计该系统
要求: 该系统允许有万分之一以下的判断失误率; 使用的额外空间不超过30GB
思路1: 先前如大文件, 有些浪费空间, 还可以继续优化吗
思路2: 如果把黑名单中的所有URL通过数据库或哈希表保存下来, 就可以对每条URL进行查询, 但是每个URL有64B, 数量100亿个, 所以至少需要640GB空间, 不满足要求
准备一个长度为m的bit类型数组bitMap, 准备k个彼此独立的哈希函数(计算结果独立), 这些函数输出值域大于或等于m, 使用这k个哈希函数对一个url进行计算. 对每一结果都对m取余, 然后再bitMap中想应位置1. 按照同样方法处理所有黑名单中的对象, 遇到已经为1的位置保持不变
黑名单中样本的个数为100亿个, 记为n; 失误率不能超过0.001%, 记为p; 每个样本的大小为64B, 这个信息不会影响布隆过滤器的大小, 只和选择哈希函数有关, 一本的哈希函数都可以接受64B的输入对象, 所以使用布隆过滤器还有一个好处是不用顾忌单个样本的大小, 它丝毫不能影响布隆过滤器的大小
数据迁移代价很低, 同时可以完成负载均衡
通过虚拟节点, 路由表映射虚拟节点
设计一种结果, 在该结构中有如下三个功能: insert(key)将某个key加入到该结构, 做到不重复加入. delete(key): 将原本在结构中的某个key移除. getRandom(): 等概率随机返回结构中的任何一个key
给定一个没有重复的整型数组arr, 初始认为arr中每一个数都各自是一个单独的集合. 设计一种结构, 提供isSameSet查询是否处于一个集合与unionSet合并集合. 要求: 如果调用isSameSet与unionSet的总次数逼近或者超过O(N), 做到单次调用isSameSet或unionSet方法的平均时间复杂度为O(1)
假设矩阵很大, 并有多个cpu, 怎么把这道题目分解. 设计一个分治的思路, 多任务并行的算法. 一个矩阵切四块, 各自块信息算好之后, 能不能合并正确的岛数; 或者设计一种思路, 可切任意块, 各自块算好之后合并正确的岛数, 关键在于岛的边界信息如何合并
如何避免重复, 以及合并完的部分不重复 --> 并查集
如图, 把矩阵按中间红色部分分为两块, 左边有岛A, B, 右边有岛C, D共4个岛, 合并
最终一共4-1-1=2个岛, 查找是否在一个集合可使用并查集
每组数据一行, 为待编码的字符串. 保证字符串长度小于等于1000. 求这个字符串最短编码的长度
给定的字符串里面, 找出最长的对称字符串(可以跳过部分字符)
打印一个字符串的全部子序列, 包括空字符串
输入一个字符串(输入一个字符串,长度不超过9, 可能有字符重复, 字符只包括大小写字母), 按字典序打印出该字符串中字符的所有排列.
给定一个包含大写字母和小写字母的字符串, 找到通过这些字母构造成的最长的回文串. 在构造过程中, 请注意区分大小写. 比如"Aa"不能当做一个回文字符串
(cnt/2)*2
来取每个字符的个数(除法取整出现奇数次与偶数次的区别了), 每个字符都会取偶数个, 不论字符出现多少次. 由于前面都是取偶数个字符,
最后当res<str.size()
表示可以再在中间添加一个出现过奇数次的字符
实现字典树, 包含以下四个主要功能
一个字符串类型的数组arr1, 另一个字符串类型的数组arr2,
(2)arr2中有哪些字符串, 是作为arr1中某个字符串前缀出现的, 打印出来
(3)arr2中有哪些字符, 是作为arr1中某个字符串前缀出现的. 请打印arr2中出现次数最大的前缀
给定一个数组, 求子数组的最大异或和
给定两个字符串str和match, 长度分别为N和M. 实现一个算法, 如果字符串str中含有子串match, 则返回match在str中的开始位置, 不含有则返回-1
把一个字符串调整为大字符串, 在这个大字符串中要求包含两个原始串
要求: 大字符串生成时只能在原始串后面添加字符串, 添加长度最短, 包含两个原始串, 开头位置不能相同, 并且大串最短
确定一个字符串不是某一字符串重复得到的. 如字符串由字符串123得到
给定一个字符串str, 返回str中最长回文子串的长度
(1) i不在回文在回文右边界, 暴力扩
(4) i在回文半径内, i的对称点i'的回文半径当前回文左边界重合, 两边不确定, 暴力扩
只能够向字符串最后添加字符, 怎么能够让字符串整体都变成回文串. 要求添加字符最少
给定一个字符串str, 找到str中最长的回文子串
一块金条切成两半, 需要花费和长度数值一样的铜板. 如长度为20的金条, 不管切成长度多大的两半, 都需要花费20个铜板. 一群人想分整块金条, 怎么分最省铜板?
如果先把金条分成10和50, 花费60, 在把长度50的金条分成20和30, 花费50, 一共花费110
如果先把金条分成30和30, 花费60, 在把长度30的金条分成10和20, 花费30, 一共花费90
给定两个整数w和k, w代表拥有的初始资金, k代表最多可做k个项目. 再给定两个长度为N的正数数字cost[]和profits[], 代表一共有N个项目, cost[i]和profits[i]分别表示第i号项目的启动资金与做完后的利润(注意是利润, 如果一个项目启动资金为10, 利润为4, 代表该项目的最终收入为14). 一次只能做一个项目,
并且手里拥有自己大于或等于某个项目的启动资金时, 才能做这个项目. 该如何选择做项目, 可以使最终的受益最大
说明: 每做完一个项目, 马上获得的收益, 可以支持你去做下
一些项目要占用一个会议室宣讲, 会议室不能同时容纳两个项目的宣讲. 给你每一个项目开始的时间和结束的时间(给你一个数组, 里面是一个个具体的项目), 安排宣讲的日程.
要求会议室进行的宣讲的场次最多. 返回这个最多的宣讲场次.
依赖顺序逆着回去就是计算顺序
母牛每年生一只母牛, 新出生的母牛成长三年后也能每年生一只母牛, 假设不会死.
求N年后, 母牛的数量
如果每只母牛只能活10年, 求N年后母牛的数量
所有动态规划都是从暴力版本优化而来, 空间换时间傻白甜问题
有些方法改不出动态规划, 如汉诺塔, 因为没有重复计算
暴力递归改动态规划, 哪些问题可以改, 哪些问题不可以改
面试过程中没见过的动态规划都是从暴力递归修改而来
汉诺塔, 要求打印所有步骤, 有后效性问题, 所以改不出动态规划
用一种机制, 把递归过程中的用到的数据做一个缓存记录下来, 再用到数据时, 不递归而是直接从缓存中拿取数据, 记忆化搜索放法
递归展开过程中有重复状态, 而且重复状态与到达它的路径无关, 无后效性问题
一个二维数组, 二维数组中的每个数都是正数, 要求从左上角走到右下角, 每一步只能向右或者向下. 沿途经过的数字要累加起来. 要求返回最小的路径和
一个数组arr, 和一个整数aim. 如果可以任意选择arr中的数字, 能不能累加得到aim, 返回true或者false
给定两个数组w和v, 两个数组长度相等, w[i]表示第i件商品的重量, v[i]表示第i件商品的价值. 再给定一个整数bag, 要求你挑选商品的重量加起来一定不能超过bag, 返回满足这个条件下, 你能获得的最大价值
面试官: 如果我给你 2GB 的内存, 并且给你 20 亿个 int 型整数, 让你来找出次数出现最多的数, 你会怎么做?
小秋: (嗯?怎么感觉和之前的那道判断一个数是否出现在这 40 亿个整数中有点一样?可是, 如果还是采用 bitmap 算法的话, 好像无法统计一个数出现的次数, 只能判断一个数是否存在) , 我可以采用哈希表来统计, 把这个数作为 key, 把这个数出现的次数作为 value, 之后我再遍历哈希表哪个数出现最多的次数最多就可以了.
面试官: 你可以算下你这个方法需要花费多少内存吗?
小秋: key 和 value 都是 int 型整数, 一个 int 型占用 4B 的内存, 所以哈希表的一条记录需要占用 8B, 最坏的情况下, 这 20 亿个数都是不同的数, 大概会占用 16GB 的内存.
面试官:你的分析是对的, 然而我给你的只有 2GB 内存.
小秋: (感觉这道题有点相似, 不过不知为啥, 没啥思路, 这下凉凉) , 目前没有更好的方法.
面试官: 按照你那个方法的话, 最多只能记录大概 2 亿多条不同的记录, 2 亿多条不同的记录, 大概是 1.6GB 的内存.
小秋: (嗯?面试官说这话是在提示我?) 我有点思路了, 我可以把这 20 亿个数存放在不同的文件, 然后再来筛选.
面试题:可以具体说说吗?
小秋:刚才你说, 我的那个方法, 最多只能记录大概 2 亿多条的不同记录, 那么我可以把这 20 亿个数映射到不同的文件中去, 例如, 数值在 0 至 2亿之间的存放在文件1中, 数值在2亿至4亿之间的存放在文件2中…., 由于 int 型整数大概有 42 亿个不同的数, 所以我可以把他们映射到 21 个文件中去. 显然, 相同的数一定会在同一个文件中,
我们这个时候就可以用我的那个方法, 统计每个文件中出现次数最多的数, 然后再从这些数中再次选出最多的数, 就可以了.
面试官:嗯, 这个方法确实不错, 不过, 如果我给的这 20 亿个数数值比较集中的话, 例如都处于 1~ 之间, 那么你都会把他们全部映射到同一个文件中, 你有优化思路吗?
小秋:那我可以先把每个数先做哈希函数映射, 根据哈希函数得到的哈希值, 再把他们存放到对应的文件中, 如果哈希函数设计到好的话, 那么这些数就会分布的比较平均. 数字过于集中可以直接在内存中统计
面试官:那如果我把 20 亿个数加到 40 亿个数呢?
小秋:最开始用21个文件是因为整型范围是42以内, 给40个整数还是再42亿以内, 还是可以用21个文件解决
面试官:那如果我给的这 40 亿个数中数值都是一样的, 那么你的哈希表中, 某个 key 的 value 存放的数值就会是 40 亿, 然而 int 的最大数值是 21 亿左右, 那么就会出现溢出, 你该怎么办?
小秋: (那我把 int 改为 long 不就得了, 虽然会占用更多的内存, 那我可以把文件分多几份呗, 不过, 这应该不是面试官想要的答案) , 我可以把 value 初始值赋值为 负21亿, 这样, 如果 value 的数值是 21 亿的话, 就代表某个 key 出现了 42 亿次了。
面试官:如果把 40 亿增加到 80 亿呢?
小秋: (我靠, 这变本加厉啊) ………我知道了, 我可以一边遍历一遍判断啊, 如果我在统计的过程中, 发现某个 key 出现的次数超过了 40 亿次, 那么, 就不可能再有另外一个 key 出现的次数比它多了, 那我直接把这个 key 返回就搞定了。
统计二进制中1的个数与判断是否是2的倍数
1.按下述格式,从键盘输入一个整数加法表达式:操作数1+操作数2,
然后计算并输出表达式的计算结果,形式如下:操作数1+操作数2=计算结果。(课本62)
2.输入两个整形数并打印,如果用户不慎输入了非法字符,那么程序
提示“输入数据类型错误”。(课本68页)
3.已知三角形的三边长a,b,c,要求编写程序,从键盘输入a,b,
c的值,计算并输出三角形的面积(注意不存在的情况)。(第三章习题)
4.编程从键盘输入圆的半径r,计算并输出圆的周长和面积。(第三章
5.任意从键盘输入一个三位整数,要求正确分离它的个位,十位和百
位数,并分别在屏幕上输出。(课本82)
6.写一个函数实现统计一个输入的整形数的位数。
7.编程计算方程ax*x+bx+c=0的根,a,b,c由键盘输入,只是用主函
数来实现。(课本83页,但需综合考虑)
8.编写三个函数,分别在b*b-4*a*c大于0、小于0、等于0时进行
调用,并输出结果,在主函数中读入a、b、c的值。
9.从键盘输入你和你朋友的年龄,编程判断谁的年龄大,并打印最大
者的年龄。(课本86页)
10.从键盘输入一个年份,判断该年是否是闰年,并输出结果。
11.判断某人是否属于肥胖体型。根据身高与体重因素,医务工作者经
广泛的调查分析给出了以下按“体指数”对肥胖程度的划分:体指
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。