刷题总结

LeetCode

剑指Offer

问题

统计大写字母出现顺序，并且排序 | &&字符串变形题
有n个长方形，每个的长宽为x,y，从下往上堆，要求上面的长宽小于下面的长宽，求最多可以堆几层 |&&
手写一个随机选择算法的变种 | &&排序变形题
一个循环列表进行是否为空判断 | 没看懂
给定一个整数数组，需要将所有数打乱顺序后重新排列（以String拼接的方式），问这样拼出的数最小是多少？| &数组变形题
数据流的中位数剑指Offer63 |&&&重点题型
- 动态数组求中位数
判断大小端，int的大端转小端 |&&&重点题型
S1中去除S2中出现过的元素 | &&变形题

求数组中a[i]&a[j]的最大值（i!=j）
设计敏感词汇过滤功能

trie树，讲了讲结构，说了下在Java里可以用HashMap实现
- 设计word中的单词拼写检查算法。
  
  谈到了字典树，hash等常用的字符串数据结构，也谈到了单词特征提取和词性标注等nlp的知识，期间写了编辑距离的代码。
给一个文件怎么统计里面的所有ASCII码 | 看答案记住就行了
设计一个短链接服务，短信中的短网址点开之后变成完整的url，完整的url转成短网址发送到用户短信中。| 看答案记住就行了
手写文件读入 | 看答案记住就行了
名人定义：所有人都认识TA，但是TA不认识任何其他人 | && 朋友圈变形题
a [i] [j] = 1, i 认识 j
a [i] [j] = 0, i 不认识 j
a [i] [i] 置空
给定n*n的二维数组，有多少个名人？具体都是谁？
淘宝无限深度树设计？SQL语句（递归）搜索这个树？如何删除某一个节点？| 看答案记住就行了
15个优惠，10个两两互斥条件，求最大优惠（dfs+剪枝）| & 难题
阿里商品组合问题：GG，没做出来，后来仔细一想是DFS+剪枝 |& 难题
背包问题，容量很大，不能在内存中存下怎么办 |& 难题

解决方法：搜索+剪枝
一个字符串数组，字符串为数字字符串“12345”或者是非数字字符串“aadfa"，从该字符串数组中的数字字符串中拼接出一个数字最大的字符串 |&& 数组变形题
给定一个单词数组(String[] wordArray)，一段文本数组(String[] text)，找到文本数组中包含该单词数组全部单词的最小文本长度，如果不符合条件返回空 |&& 数组变形题
一个string数组，和一个长的string，问长的字符串是否是由数组中字符串组成的，可以重复使用 |&& 数组变形题
给一个字符串str，一个字符串数组，用数组中的字符串自由组合，去匹配字符串，可以重复使用，求能匹配的最大长度
- 举了例子说如果关键字里有abcd，abcx，abcy是不是匹配的时候会重复计算很多次，我说那一个用前缀树优化吧
O(N)实现把一个数组中所有的奇数全部移动到偶数前。直接写了个类似快排的partion算法。| && 排序变形题
把1-n的数字转换成字符串，按字典序排序，求排第k位的数字 |&&& 第k大重点变形题
一个数组中间的任何一个数和左右两边不等，求波峰id 题目可能抄错了
二分法找峰值 |&& 二分变形题
利用0到9，a到z大小写都算上，生成一个6位的随机密码，怎么实现？ | 看答案记住就行了
- 我给出用Random，这样的随机性能能保证吗？有没有其他思路？如果改一下，6个数字不能重复呢？后来我提到用蓄水池算法，不知道对不对
约瑟夫环问题 | 看答案记住就行了
给定一个无序数组，给定一个区间查询
- O(1)返回区间元素的总和；Map；
- 现在需要对某一个元素进行更新，请问能否用O(logn)的时间更新1中的Map，这种属于一点更新，区间查询，线段树

设计一个微信红包功能，n个红包，分成m份，手写代码 | 看答案记住就行了

排序 / 查找算法

堆排序相关 12 &&&
- 建堆的时间复杂度？
  - 建堆有两种方法，自顶像下建堆也就是像堆排序那样的时间复杂度是nlogn，而如果采用筛选法建堆，那么时间复杂度应该是O(n)，而不是nlogn
- 最大堆中求前k个最大值的时间复杂度？
- 堆排序是内排序还是外排序？
- 堆排序可以做成外排序吗？
- 最大堆怎么实现？
快速排序相关 10 &&&
- 实现过程，复杂度？
- 快速排序、冒泡排序的区别
- 快排与归并的比较？如果要排序的数组中有大量重复元素的话怎么优化算法？
- 快排是稳定的吗？
- 快排排对象的时候有什么问题？
- 快速排序除了枢纽的随即选取优化方法以外？还有其他的吗？
二分查找相关 8 &&&
- 二分查询的时间复杂度是多少，为什么是logn
  
  回答一次操作将规模减少到一半，所以是logn，面试官不太满意，我又说了master公式，感觉他还是不满意，最后这个问题过了，不知道怎么回答比较好
- 递归/非递归实现
随便说一个排序算法 7 &&&
- Java里内置的是用什么排序方法？
- 插入排序 2
- 基数排序（大数据）
- 冒泡排序
归并排序（内部、外部） 2 &&&

二分排序（二路归并排序）
有一系列字符，包括英文字幕大小写，还有数字，标点符号等等，用什么排序方法比较好？

解答：因为只是字符且字符种类是一定的，所以可以用计数排序，也就是桶排序，记录每个字符的数量然后，时间复杂度O(n),空间复杂度O(1)，认为字符种类数量是一个常数。

数组 / 矩阵

求n数组中最大的k个数 8 &&&
- n个数找最小的k个数
  - 以上除了用堆以外，还可以怎么优化？用快排的变形,时间复杂度是多少
  - 两种情况：N很大的时候用堆存前k大的数，N较小的时候用类似快排的方法（平均复杂度O(n)）
  - 最大 / 最小堆如何构建？最大堆的性质（是一种完全二叉树），如何判断一个树是不是完全二叉树，是不是堆？
  - 变种：海量数据（int范围），数据会有增删，每次查询的K值不同，设计数据存储方法
    
    我给的方法是分段存，段内有序
- 给定大小为n的数组，找出第K小的元素
  - 上述问题，内存只能存1/3的数据怎么办
两数之和问题 4 &&&
- 无序数组：哈希表
- 有序数组,判断是否存在两个数之和等于一个常数,尽可能优化双指针
- 复杂度如何？能否降低？
- 一个有序数组，找到两数相加为给定值的所有可能，时间复杂度尽可能低
- 三数之和
打印矩阵元素 4 &&&
- 对角线打印矩阵元素
- 一个n*n的矩阵，按副对角线打印
- 非递归实现螺旋矩阵输出
- 顺时针打印矩阵
数组顺时针旋转90度 2 &&&
数组的子序列问题 3 &&&
- 求数组的最大子序列和 3
- 最长公共子序列LCS
- 最长递增（上升）子序列开始结束位置 2
- 给一个数组，找出所有的严格递增的序列个数
- 求数组中连续k个数的和的最大值（最大连续子数组和Maximum SubArray）
股票买卖问题 3 &&&
- 第一种问法：不限次数，一天只能买或卖或什么都不干
- 第二种问法：只能买进一次、卖出一次
旋转数组问题 2 &&&
- 旋转数组的二分查找
  
  https://blog.csdn.net/bjweimengshu/article/details/90826510
- 旋转数组求最小值
只出现一次的数字 4 &&&
- 一个数组，里面的数字都是成对出现的（有两个一样的），只有一个只出现了一次，有什么方法可以找出这个单独出现的数？
  
  LeetCode 136
- LeetCode 137
- LeetCode 260
- 推广：有多个数的数组，只有一个元素出现1次，其余出现2次。推广：一个N次，其他M次
给一个长度为n的，值的范围为0到n-1的数组，判断是否有重复的元素出现 &&
1~n n 个数字，选取n-1个数字放入到一个数组中，求数组中缺少的数字 &&
LeetCode 42 雨水收集问题 3 &&
给出一个n*n数字矩阵，寻找一条最长上升路径，每个位置只能向上下左右四个位置移动 &&
二维数组行列均是递增的，查找某一个target &&
在一个数组中，统计出现频率最高的元素 LeetCode &&

注意：有一个前提条件是频率最高的元素超过一半
数组A和数组B，求 A并B - A交B &&
- 1000-10000个有序数组，找并集，数组长度存在不一致的情况，请讲思路？
- 两个有序数组找并集
区间覆盖：例如 [1 3] [2 5] [3 6]能否覆盖[2 6] &
矩阵搜索 &
一个一维整数数组，前半段是递增，后半段也是递增，但是后半段的最大值小于前半段的最小值，找出数组中的最小值 &&
两个排好序的数组，合并成一个有序数组，重复元素只出现一次
一个数组，排序使奇数在前偶数在后，奇数之间不需要有序
输入一个数组和一个整数，数组的长度、数组元素的范围、整数的范围都是1~20000，求数组中的某几项加起来等于整数的可能性组合数？
四个注意点：数组未排序、可能有相同数、多个数相加也可以不局限于两项相加、情况总数。
例如输入：10 5 3 7 5和15
先描述一下思路，然后写。
海岛面积

给一个矩阵，0表示海水，相连的1表示海岛，上下左右表示相连。
00011
11011
10001
（1）求最大海岛面积。
（2）求最大海岛面积和对应海岛的所有坐标。
（3）求所有海岛的所有坐标，按海岛分。
每小题讲思路，最后写第二题。
给定一个list A和listB找出A中存在、B中不存在的数

（TreeSet存B，然后比较A的数是否在set中，TreeSet红黑树，查找效率还可以，但是需要额外内存）

不借助额外内存呢？（排序B，二分查）

还有更简单的吗？（异或运算，O（mn））
给两个数组（长度可能不等），要求循环输出，如
A=1,2,3
B=A,B,C,D,
就要输出1A2B3C1D2A3B...

字符串

字符串反转 2 &&&
- how are you变 you are how
  
  解答：先反转所有字符，再反转每个单词
括号匹配 &&&
- 给一个字符串，只包含小、中、大括号，判断是否合法(如“{()}”和“()[]”合法，“([})”不合法)，leetcode 20
  解法：栈
- 扩展1：如果能匹配的不止大括号小括号，还有自己定义的符号呢
- 扩展2：如果括号之间有优先级呢
- 扩展3：相同的括号不能超过指定数目呢
字符串匹配 &&&
- 给一个字符串pattern，和一个字符串，返回是否匹配abba my ha ha my
- 给定一个字符串集合，然后输入一个查询串问查询串是否可以由这个字符串集合的某些字符串构成 , 可以重复使用字符串集合中的字符串
  
  如：字符串集合ab, xy, cd, 查询串为abxy , 返回true
  
  如：字符串集合ab, xy, cd, 查询串为xyab , 返回true
  
  如：字符串集合ab, xy, cd, 查询串为xyabxy , 返回true
判断回文字符串 &&&
最长不含重复字符的子字符串 2 &&&
剑指offer 48
解法：滑动窗口、多重循环

把字符串转换成数字 2 &&&
- 转换成int型
求两个字符串的最长公共子串。 &&&
去掉字符串开头和末尾的空格 &&&
给一个字符串数组，统计每一个字符串出现的次数，要求不能用set,map.时间复杂度O(n) &&
求一个字符串中第一个不重复字符。 &&&
给你三个string s1，s2和s3,判断s3能不能由s1和s2组成，s1和s2内部元素相对位置不能变，比如a 和bc,可以组成的有abc bac bca（动态规划）&&
假如有n个字符串，要求匹配一个模式串p，问哪些字符串里面出现了p，用什么数据结构维护（trie树）&

栈 / 队列

最小栈，以O(1)时间复杂度取得最小值的栈，要求有pop push getMin方法 3 &
栈实现队列 &&&
队列实现栈 &&&
利用栈判断分隔符是否匹配 &&　　
https://www.cnblogs.com/ysocean/p/7911910.html
颠倒栈中元素（栈的逆置）
手写循环队列

链表

链表的环 9 &&&
- 判断链表是否有环 6
- 如何找出有环的单向链表的环入口位置？ 3
链表反转相关 7 &&&
- 链表反转
- 链表每两个节点反转
- 每隔k个元素反转一下
相交链表问题 6 &&&
- 给出两个单链表的头节点，求他们的公共子节点
- 两个链表，判断是否相交，找出相交的第一个点
  - 上述问题，链表可能有环，需要考虑几种情况？
有一个长度未知的链表，怎么找这个链表的中点 3 &&&

解答：快慢指针
自己实现一个链表 2 &&&
合并两条有序链表 2 &&&

换一种问法：给定两有序(递增)链表，合并为单调非递减链表，要求额外空间复杂度O(1)
链表排序相关 2 &&&
- 链表排序
- k个链表排成一条值递增的有序链表
双链表的插入和删除、查找方法 2 &&
- 双向链表中插入一个节点
删除单链表中所有值相同的节点 2 &&
- 例如：1->2->2->3->4,返回1->3->4
有一个单链表，奇数位是升序的，偶数位是降序的，要求进行给它进行排序 2 &
1->200->10->120->30->8->88->4
1->4->8->10->30->88->120->200

解答：用一个栈来装入偶数位，然后遍历奇数位与这个栈进行，循环比较链表结点与栈顶的大小，并进行合并就行了
输入两个链表，每个链表代表一个数，对这两个链表进行加法运算，输出的和也是一个链表形式，比如1->2->3->4, 2->3->7,对这两个链表进行加操作，1234+237=1471，输出1->4->7->1
- LeetCode 2 两数相加
- LeetCode 445 两数相加II
倒着打印链表（为什么用递归比用栈差？）

二叉树

二叉树的遍历 15 &&&
- 二叉树的前序遍历（递归/非递归） 6

二叉树的中序遍历（递归/非递归） 6 &&&
- 给一个二叉搜索树和一个数，输出这个数的中序遍历的序号
二叉树的后序遍历（递归/非递归） 6 &&&
- 二叉树的层次遍历 3
BFS
- DFS &&&

节点路径问题 7 &&
- 树节点之间的最大距离 / 二叉树的最长路径
- 两个叶子节点之间路径和的最大值：每次计算左右子树最大值和当前结点的和，和max比较，返回最长路径
- 求二叉树是否存在和为N的路径：时间复杂度？ O(N)
二叉树的祖先问题 4 &&
- 假设有平衡二叉树s，有2个叶子结点，请设计函数查找并返回最近公共祖先
- 二叉树中两个节点的最近公共父节点
- 最近公共祖先（不是搜索树） 2
二叉树的镜像 4 &&
- 递归实现/非递归实现
输入两棵二叉树A和B，问B是不是A的子树 2 &&
二叉搜索树转双向链表 2
判断树对称 &&
- 判断树对称不用递归用栈怎么做？
求一个二叉树的高度 &&
通过一个数组构造二叉树 &&
- 平衡二叉树
- 二叉查找树
由后序遍历和中序遍历构造二叉树 &&

https://jingyan.baidu.com/article/cdddd41cb8d79753ca00e144.html
给了个二叉树结构TreeNode,比传统的多了个引用 TreeNode next,要求像层次遍历那样,左边的节点的next指向右边,最右边的节点next指向null,要求空间O(1)
Z字形打印二叉树
判断一个二叉树是否是二叉搜索树
一棵二叉树，从右侧往左看，打印所有能看到的节点

数字与位运算

不用额外空间交换AB的值

解答：位运算
素数计算： 3

这里有一种特殊的算法，叫做 素数筛法
- 打印101~202之间的所有素数并统计个数
- 输出100以内的素数，考虑效率
- 已知1-100个素数，求1-10000的素数
数字反转问题 2
- 整数反转 LeetCode 7
- 翻转一个long类型数字。例如输入123456L，输出654321L。
  
  Leetcode翻转integer的变种。考察能否正确处理溢出的情况。
代码实现整数N的平方根，不考虑四舍五入取平方根 2
大数相加 / 相减 2
1,2,3,4组成的不重复三位数，都用代码写出来
统计1到n中所有数中1的出现次数

LeetCode 233
N！中0的个数
判断一个数是否对称
红蓝两种球，总共N个， N>2, 排列组合，连续3个颜色一样是非法的，求合法的排列数量
把九亿三千零五万五千三百转化为对应的数字
输入一个double，要求返回与它最接近的.49或.99的数字。例如12.77返回12.99，11.02返回10.99，12.61返回12.49。
写一段代码不使用'/'完成除法操作，考虑所有情况
手写进制转换
等差数列第x,y,z 项的值是y,z,x求(x+y)项和(z+y)项的差

海量数据

海量数据寻找TopK &&&
- 十亿个IP，获得访问次数最多的十个 2
- 有10个文件，每个文件大概有10G，求里面最大的100个数
- 从4亿qq号码中，统计出出现次数top 10的号码
- 100万个数中找top100
- 五个单词，在一个长文本中查找是否存在
50亿url找到重复的及数量 &&&
给10亿个int整数，问哪个数字只出现了一次
大文件统计每个字符串的词频
两个大文件求在其中一个文件的数据
海量数据排序

16G的文件储存的是一个数组，要求只用1G内存把他们排好序。
给两个文件a,b a大小为3t, b大小为2t，a中存储的是id 和 name ，b中存储的是id和title，计算机内存2g，要求用最快的方法找出a和b的id重合的部分，输出文件c，c中存储的是id,name,title。

智力题

一个五升桶，一个三升桶，怎么倒出四升水，水可以无限量使用 2
4个瓶盖换1瓶酒，要喝150瓶酒，他自己最少买多少瓶？
10个人编号1-10，一女一男排列，女为奇数男为偶数，第一个女生4岁，男生比前一个女生大两岁，女生比前一个男生大一岁，问第十个人多少岁？
喝汽水问题， 2个空瓶换一瓶汽水，1元1瓶，可以买多少瓶汽水问题，(刚好看过，通过借一瓶来最后再多喝一瓶）
100个硬币，有一个坏的，怎么快速找到，时间复杂度

把100个硬币平均分成三份，分别是：33，33，34，把两堆33个放在天平上称。
一个环形圈，有一个机场起点，一架飞机的油最多飞半圈，飞机之间可以互相加油(用自己的油给别人加)，当飞机没油时就坠毁，求问最少需要多少架飞机可以让一架飞机飞一圈(当时回答4架，面试官说3架，让再想想，没想出来。。。)
25匹马，五条赛道。每条赛道跑一匹马，只能知道名次，不能知道速度，怎么找出前一二三名，用几次？
十个箱子1000个球，怎么放球可以实现通过箱子组合出1~1000个球
2n个人围成一圈，两两握手，没有交叉，一共多少种握手方式
糖与盐的智力题
50个红球和50个蓝球，分布在两个杯子里。现在随机选一个杯子取球，问怎样分布使得取到红球的概率最大？

解答：一个罐子放一个红球，另一个罐子放49个红球和50个蓝球。
概率应该是最高了，接近75%

现选一个罐子，两个罐子被选中概率各为50%
如果取到只有一个红球罐子的话，因为只有一个红球，那么这样取到这个红球概率是
50% * 100% = 50%
取到另一个罐子的话，再要取到罐子中红球的概率是49/99，所以这样取到红球的概率是
50%*49/99=49/198

两者相加
50%+49/198=148/198=0.74747近似75%
1000瓶药水，有一瓶有毒，用小白鼠来试药，要求在一次毒发周期内找出毒药，最少需要多少只小白鼠
每天8：30-9：00上班，上班时间10-30分钟，求不迟到的概率
一个农夫有一些数目的牛，他把这些牛的一半加半头分给了儿子，把剩下的一半加半头分给了妻子，把剩下的一半加半头分给了女儿，最后把剩下的一半加半头分给了乡亲们，牛刚好分完，请问一共多少牛，然后每人都分了几头牛？

解答：设置x,y,z,w，然后解方程，四个等式四个量，解出来即可。这种方法比较数学一点，貌似这个题目是有规律的。等比数列的性质。
有100个乒乓球，你和另一个人轮流拿去，每次拿取的数目必须不少于1个，也必须不多于5个，如果你先拿，那你第一次拿多少个，然接下来怎么拿才能保证你会拿到第100个球？

解法：第一次拿4个，剩下96个会被6整除，所以接下来你只要保证和上一次对手拿取的数目的和为6即可。
1000个苹果，10个框，苹果只能整筐的卖，问怎么放置苹果，当顾客买N个苹果的时候，能满足要求？

这就是10位2进制数，是否可以表示0~1000内的任一实数问题；
3000 根萝卜在A地，A地到B地1000公里，有一个骆驼，最多可以驼1000根萝卜，但是每走一公里就要吃掉一根萝卜，求使用这个骆驼运送这些萝卜到B地后，最多可以剩余到少萝卜

多线程

5个线程分别计算一个数组的和，主线程汇总结果
怎么写多线程
有三个线程ABC分别向一个数组中写入a，l，i，要求最终的写入结果形如alialiali...写入次数由A线程决定。
三个线程A,B,C,A线程输出A，B线程输出B，C线程输出C，如何控制这三个线程使得程序循环输出ABCABCABC...
死锁
两个线程打印1.2.3.4打印到100怎么实现？

这里刚开始说的是加锁用生产者消费者来做，后来说了semaphore，感觉后面的才是面试官想要的答案。
手写场景题：考察countDownLatch，FutureTask等

设计

单例模式 9 &&&
- 线程安全的效率最高的单例模式怎么写？
实现一个LRU缓存队列 LeetCode146 9
- 实现一个带过期时间t的LRU
设计HashMap 4
- 自己手写一个hashmap
- 设计一个元素数量固定的hash表（超过容量，需要将最早加入的元素删除），使用链式存储，支持增删查都是O(1)复杂度。
- 设计一个hashmap，设计扩容方式，讨论了增删数据和扩容的并发性
实现生产者消费者模式 4 &&&
- 用阻塞队列实现
- 用数组实现
- 用wait和notify模拟生产者消费者模式 2
- 多个生产者和消费者的情况如何实现？
实现一个阻塞队列，考虑到多线程并发的情况，要求有put,get,isEmpty, isFull方法
实现一个迭代器类，有两个方法，一个是next，一个是peek(这一题首先可以用java的迭代器，然后要注意获取第一个元素，存到一个变量，后面peek方法要用，还有一些细节要处理不赘述)
实现一个四则运算计算器
通过内存的计数器
实现一个限流器
限制请求在每秒1000次以下
- 解决方法：维护一个计数器就行了，注意一下同步的问题。当计数器小于一千的时候自增并返回true，否则返回false。
  然后用一个线程来每隔1秒就执行一次清零操作。

数据库SQL

左连接
join
t_subject
——————————
c_id
c_student_uid 学生uid
c_teacher_uid 教师uid
c_subject_uid 科目uid
c_score 分数
平均分排名前三的学生uid和平均分数
给这个SQL语句建索引怎么建？
学生表、课程表、成绩表。1）查每个学生的平均成绩和学号；2）查询总分大于500分的学生的姓名和总分。
Sql，一个考试成绩明细表，字段有id，class_name，user_name,score，找出考试分数大于90分的人数最多的班级
数据库两张表求在其中一个表的数据
两种写法实现查询ID在A表但不在B表
实现两个数据库表内联查询的计算方法，select * from a, b where a.key1 == b.key2, 一直让优化，最终的方法是把两个表按key分段排序，一段一段加入内存，排序，然后类似归并两个指针从头扫，遇到相等的查出来；
写sql，Table T Sid：学号 Cid：课程编号 score：成绩，q1：查询平均成绩大于60分的同学的学号和平均成绩 q2：查询所有课程成绩小于60的同学的学号
每一条数据有ID和分数两项，要求用ID可以查到分数，能查询给定分数区间的id列表。用B+树，类似数据库索引。