微软2020.11.24日~2021.3.20日面试算法题溯源

[afatcoder]

本issue的目的是「注明每道题目的来源」

若您想查看汇总好的题目，

您可以在README的微软下查看最终数据

您也可以在https://codetop.cc 更方便的查询

公司	链接	日期	题目描述
微软	https://www.nowcoder.com/discuss/570397	2020.11.24	记得有一个格雷码的算法题
微软	https://www.nowcoder.com/discuss/570397	2020.11.24	单向链表里面判定有没有环
微软	https://www.nowcoder.com/discuss/570397	2020.11.24	一个matrix（m行n列），从[0,0]开始，只能向右或者向下走，求走到[m-1, n-1]有多少种方法。一开始用dp写了个空间复杂度为O(mn)的，然后让优化到O(n)，最后follow-up问了一下如果matrix里面有障碍物怎么算
微软	https://www.nowcoder.com/discuss/570397	2020.11.24	单向链表里面判定有没有环
微软	https://www.nowcoder.com/discuss/570397	2020.11.24	找一个String里面最长的Substring，要求里面不能有重复字符
微软	https://www.nowcoder.com/discuss/571275	2020.11.13	字典树
微软	https://www.nowcoder.com/discuss/571275	2020.11.13	实现哈希表
微软	https://www.nowcoder.com/discuss/571275	2020.11.18	写了一道题，大概意思就是给定一个字符串'aaabbbccc{{a}b{c}}'然后可替换的部分'a: [d, e], c: [f], dbf: [x], ebf: [y]'最后返回所有可能生成的字符串
微软	https://www.nowcoder.com/discuss/573606	2020.12.01	merge two sorted list，力扣原题
微软	https://www.nowcoder.com/discuss/573606	2020.12.01	树节点增加父节点指针，输入一个树节点，求中序遍历中的下一个节点
微软	https://www.nowcoder.com/discuss/573606	2020.12.01	给一个数组，找局部峰值。能不能更快？
微软	https://www.nowcoder.com/discuss/573606	2020.12.01	力扣原题，在旋转了的sorted list里找最小值
微软	https://www.nowcoder.com/discuss/573675	2020.12.01	代码题：写堆排序
微软	https://www.nowcoder.com/discuss/573675	2020.12.01	有序数组找到num[i]=i的那个。进阶：数组可能有重复值。用二分法做了一下
微软	https://www.nowcoder.com/discuss/572085	2020.12.14	一面leetcode 297       准hard
微软	https://www.nowcoder.com/discuss/572085	2020.12.14	二面leetcode 1358     准hard
微软	https://www.nowcoder.com/discuss/572085	2020.12.14	三面leetcode 4               hard
微软	https://www.nowcoder.com/discuss/580025	2020.12.16	极其传统的一句话把单词调转
微软	https://www.nowcoder.com/discuss/580025	2020.12.16	开根号
微软	https://www.nowcoder.com/discuss/580025	2020.12.16	LRU
微软	https://www.nowcoder.com/discuss/580025	2020.12.16	复制带随机指针的链表，
微软	https://www.nowcoder.com/discuss/580025	2020.12.16	判断数独是否有解，
微软	https://www.nowcoder.com/discuss/581796	2020.12.22	算法：一道全排列的题
微软	https://www.nowcoder.com/discuss/581796	2020.12.22	String2Double
微软	https://www.nowcoder.com/discuss/581796	2020.12.22	二叉树的序列化和反序列化：
微软	https://www.nowcoder.com/discuss/581796	2020.12.22	实现strtok
微软	https://www.nowcoder.com/discuss/582688	2020.12.23	Return the top k large numbers in an array
微软	https://www.nowcoder.com/discuss/582688	2020.12.23	Give the Chinese representation of a number
微软	https://www.nowcoder.com/discuss/582688	2020.12.23	calculate the ‘Qi’ of a point on a Go board (dfs).
微软	https://www.nowcoder.com/discuss/587631	2021.01.11	有一个数组元素[a0, a1 ...]，从数组中找出连续的数组和为最大
微软	https://www.nowcoder.com/discuss/587631	2021.01.11	有一个数组元素[a0, a1 ...]无重复元素。从数组里面找出所有可能的组合加和是n
微软	https://www.nowcoder.com/discuss/587631	2021.01.11	有一个数组，从数组中找出连续数组乘积最大。
微软	https://www.nowcoder.com/discuss/587631	2021.01.11	假设有两个整数a，b. 那么a/b有可能除尽和除不尽。如果除尽，找出循环的单节
微软	https://www.nowcoder.com/discuss/587631	2021.01.11	假设一个数组只有"a"和“b”两种string 组成。如何重新安排数组，使得最多有3个a相邻，3个b相邻。如果不能安排，返回None
微软	https://www.nowcoder.com/discuss/587631	2021.01.11	假设有a，b两个int，转成二进制后 c = a | b. 假设从0->1, 1->0理解为一个action。最少需要多少个action计算c = a|b？
微软	https://www.nowcoder.com/discuss/587631	2021.01.11	之字型二叉树广度优先遍历
微软	https://www.nowcoder.com/discuss/587631	2021.01.11	如何实现a/b。a和b是string，返回double
微软	https://www.nowcoder.com/discuss/594503	2021.02.05	手撕字典序数组还原成正常排序
微软	https://www.nowcoder.com/discuss/594503	2021.02.05	两个非常大的稀疏矩阵做点乘，以及后序拓展
微软	https://www.nowcoder.com/discuss/594503	2021.02.05	手写堆排序
微软	https://www.nowcoder.com/discuss/594503	2021.02.05	反转链表
微软	https://www.nowcoder.com/discuss/594503	2021.02.05	链表判断有无环
微软	https://www.nowcoder.com/discuss/594503	2021.02.05	八皇后
微软	https://www.nowcoder.com/discuss/594503	2021.02.05	二叉树最近公共祖先
微软	https://www.nowcoder.com/discuss/594503	2021.02.05	链表排序（我用的归并）
微软	https://www.nowcoder.com/discuss/595449	2021.02.02	1.手撕lca 先写了个递归版，然后写非递归
微软	https://www.nowcoder.com/discuss/595449	2021.02.02	给定一个按照字典序排列的string字符串数组，每个字符串表示一个int，要求按照string对应的int大小重新排序
微软	https://www.nowcoder.com/discuss/595449	2021.02.02	给定入栈序列和出栈序列，判断出栈序列是否合法
微软	https://www.nowcoder.com/discuss/595449	2021.02.02	1.反转链表
微软	https://www.nowcoder.com/discuss/595449	2021.02.02	2.8皇后
微软	https://www.nowcoder.com/discuss/595449	2021.02.02	3.二叉树序列化 反序列化
微软	https://www.nowcoder.com/discuss/595449	2021.02.02	4.（口述思路,约给5min时间)一辆汽车，从0要开到n，路线上分布着kk个加油站
微软	https://www.nowcoder.com/discuss/595449	2021.02.02	1.dp题 数组中找k个不重叠的子数组和最大
微软	https://www.nowcoder.com/discuss/601221	2021.02.09	输出该串字符串的全排列（完全相同的字符串算一个），同时需要满足条件『相邻字符不能相同』
微软	https://www.nowcoder.com/discuss/601221	2021.02.09	给定一个二维矩阵，包括0和非0，把0所在的行和列都置为0
微软	https://www.nowcoder.com/discuss/601221	2021.02.09	算法题：跳台阶，两个参数（n级台阶，最多迈k步）
微软	https://www.nowcoder.com/discuss/612895	2021.03.13	1.    找峰值。是否可以优化时间复杂度，写一些测试的例子。
微软	https://www.nowcoder.com/discuss/612895	2021.03.13	2 .    旋转数组的最小值。
微软	https://www.nowcoder.com/discuss/612895	2021.03.13	1. 有效数独
微软	https://www.nowcoder.com/discuss/612895	2021.03.13	2. 两个单链表的交点
微软	https://www.nowcoder.com/discuss/612895	2021.03.13	做题，找链表的最中间n个节点。
微软	https://www.nowcoder.com/discuss/614091	2021.03.16	删除链表中的倒数第 n 个节点
微软	https://www.nowcoder.com/discuss/614091	2021.03.16	两个无序链表中找第 k 大元素，忘记怎么写 priority_queue 的比较函数了，自己写了堆的 down 和 up 函数
微软	https://www.nowcoder.com/discuss/615719	2021.03.16	求第K大
微软	https://www.nowcoder.com/discuss/615719	2021.03.16	给MxN矩阵，每个矩阵有非负值，求从一点到另一点最小路径，要求只能往小于当前值的坐标走，第一问最小路径的定义为经过的步数（BFS），第二问定义为经过格子值的总和（DFS），第三问为中间有k个障碍不能走，有去除一个障碍的机会，求最短路径
微软	https://www.nowcoder.com/discuss/619269	2021.03.20	给一个字符串，仅由空格和单词组成，只要不是空格就是单词的一部分，把单词的顺序全部反转，并保留原来的两个单词之间的空格长度
微软	https://www.nowcoder.com/discuss/619269	2021.03.20	. 给两个数组表示rank的分数，比如[6, 3, 5], [8, 4, 6]这两个，每一个代表给每个下标的page的一个打分，但是最终结果不关心打分的分数，只关心这一组page里的排名大小是否相同。写一个函数判断这两个数组代表的排名是否相同
微软	https://www.nowcoder.com/discuss/619269	2021.03.20	找到其中最长的回文子串