简介
记录下刷的题目思路，以及题目的总结，基本都是面试高频题目,面试pdd面过bfs，百度的面过字符串全排列
| 题号 | 标题 | 类型 | 思路 |
|---|---|---|---|
| 3 | 数组中重复的数字 | 数组 | 1刷和2刷都是用字典，题解有萝卜坑的思路非常巧妙 |
| 4 | 二维数组的查找 | 数组 | 1刷和2刷都是用二分查找，时间复杂都是O(MlogN)，题解有螃蟹步思路时间复杂度O(M+N) |
| 5 | 替换空格 | 字符串\数组 | 用python熟悉下api，C++空间复杂度上还可以再优化从O(N)到O(1) |
| 6 | 从尾到头打印链表 | 链表\数组 | 遍历链表保存到数组，然后用reverse或者用个temp把头尾调换下时间复杂度O(N),空间复杂度O(N) |
| 7 | 重建二叉树 | 树 | 确定前序中的左子树的范围和右子树的范围，中序的左子树的范围和右子树的范围，递归即可，ps:同样的c++实现，使用算法自带库find和迭代速度快好多，pps:可以利用空间换时间，先把中序的节点对应的下标用字典保存下来，然后前序的根节点对应中序的根节点位置可以从字典获取 |
| 9 | 用两个栈实现队列 | 队列\栈 | 栈1负责入栈,栈2负责出栈，栈2为空的时候就把栈1的元素push到栈2即可 |
| 10-1 | 斐波那契数列 | 找规律 | 解题方法很多，dp或者递归，粗暴一点直接申请n+1内存dp下去，节省内存可以按照题意，直接定义三个变量fn，fn-1，fn-2然后计算即可,https://leetcode.cn/submissions/detail/144093951/ |
| 10-2 | 青蛙跳台阶问题 | 找规律 | 同10-1 https://leetcode.cn/submissions/detail/144097948/ |
| 11 | 旋转数组的最小数字 | 二分查找 | 注意数组可能有相同的值，PS：二分判断的时候if条件顺序改变会影响耗时 https://leetcode.cn/submissions/detail/144108336/ |
| 12 | 矩阵中的路径 | bfs/dfs | 注意使用mask记录访问会超时,用个临时字符改变board，dfs完成后再复原https://leetcode.cn/submissions/detail/145286677/ |
| 13 | 机器人的运动范围 | bfs/dfs | 先根据下标生成mask可到达矩阵，使用bfs从（0，0）开始遍历mask即可 https://leetcode.cn/submissions/detail/145294634/ |
| 14-1 | 剪绳子 | dp | 1：用动态规划的方法，dp记录长度为i的绳子可以剪出的最好的乘机。dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j)); j为当前剪去1到i-1的长度，i-j为剩下的不剪，dp[i-j]为剩下长度的最优剪。https://leetcode.cn/submissions/detail/145801646/。2：参考评论区的大佬直接用数学方法https://leetcode.cn/submissions/detail/145794940/ |
| 14-2 | 剪绳子-2 | dp | pow不支持大数 https://leetcode.cn/submissions/detail/145806143/ |
| 15 | 二进制中1的个数 | 数组/位 | 循环判断二进制串是否包含1 https://leetcode.cn/submissions/detail/145807473/ |
| 16 | 数值的整数次方 | 递归 | 注意n为-2147483648取正会超范围。用long临时保存下，递归就可以https://leetcode.cn/submissions/detail/145860526/ |
| 17 | 打印从1到最大的n位数 | 大数/数组 | 题目没有设计大数的用例，所以最简单的解法会ac，但是也要会写针对特别大的数字的解法（n=100）。先初始化‘000‘（n=3)模拟加法即可(001, 002, 003, 004),然后将字符串转为数字（题目要求int，一般大数问题直接返回vector） https://leetcode.cn/submissions/detail/145860526/ |
| 18 | 删除链表的节点 | 链表 | 申请两个临时的节点，pre和prepre，也就是保存节点的前节点和前前节点。判断前节点的next的val是否和val相等。最后返回前前节点的next的next即可 https://leetcode.cn/submissions/detail/145992046/ |
| 21 | 调整数组顺序使奇数位于偶数前面 | 双指针/数组 | https://leetcode.cn/submissions/detail/146100227/ |
| 22 | 链表中倒数第k个节点 | 双指针/链表 | 定义两个节点n1, n2, n1先走k步，然后n1,n2同时走，n1为空停止，n2就是倒数第k个节点 https://leetcode.cn/submissions/detail/146102919/ |
| 24 | 反转链表 | 双指针/链表 | https://leetcode.cn/submissions/detail/146104743/ |
| 25 | 合并两个排序的链表 | 链表 | 不用额外申请节点，直接inplace的改变next指针即可 https://leetcode.cn/submissions/detail/146110438/ |
| 26 | 树的子结构 | 树 | 树皆可递归，两个树的节点的值相同的时候，判断各自的左子树和右子树的值是否相同。https://leetcode.cn/submissions/detail/146251803/ |
| 27 | 二叉树的镜像 | 树 | 树皆可递归，递归交换每个节点的左右子树即可。https://leetcode.cn/submissions/detail/146257430/ |
| 28 | 对称的二叉树 | 树 | 树皆可递归，递归判断根节点的左子树和右子树的值，以及左子树的左子树和右子树的右子树的值是否相同。https://leetcode.cn/submissions/detail/146260752/ |
| 29 | 顺时针打印矩阵 | 数组 | https://leetcode.cn/submissions/detail/146266645/ |
| 30 | 包含min函数的栈 | 栈 | 使用两个栈，一个栈s1保存push的数据，一个栈s2保存非递增的数据（要push的值比栈上的top值要小的时候才push进去,s1栈上pop的值与s2栈的top值相同的时候才pop。https://leetcode.cn/submissions/detail/146266645/ |
| 31 | 栈的压入、弹出序列 | 栈 | 使用栈模拟，pushed数据直接push进栈，当栈顶数据与poped相同时弹出，pushed遍历完判断栈是否为空。https://leetcode.cn/submissions/detail/146342940/ |
| 32-1 | 从上到下打印二叉树 | 树/bfs | https://leetcode.cn/submissions/detail/146610135/ |
| 32-2 | 从上到下打印二叉树-2 | 树/bfs | 用一个变量记录每层的个数，然后用bfs就行https://leetcode.cn/submissions/detail/146905023/ |
| 32-3 | 从上到下打印二叉树-3 | 树/bfs | 再加个reverse的flag初始化为false，当push_back一层后就置为true,然后把下一层的节点顺序reverse下即可，reverse再置为false。https://leetcode.cn/submissions/detail/147433681/ |
| 33 | 二叉搜索树的后序遍历序列 | 树 | 和7重建二叉树一样的思路，后序是左右根，先找到左子树和右子树的范围，遍历到第一个大于根节点的地方就是右子树开始的地方，然后递归划分，最后划分到只有一个节点return True，那么在什么情况下return False：也就是找到右子树开始的地方，接着往下遍历到根节点，只要有小于根节点就return False https://leetcode.cn/submissions/detail/147449346/ |
| 34 | 二叉树中和为某一值的路径 | 树 | 递归 https://leetcode.cn/submissions/detail/147770994/ |
| 35 | 复杂链表的复制 | 链表 | 使用两个map（都是map<Node*, Node*>），一个保存old到new（复制新申请的内存)的映射dict1,一个保存new到old radom地址的映射dict2，新的链表的next指针在遍历的过程就赋值，新的节点random指针。使用dict2可以知道 old的地址，通过dict1知道new地址，这个就是新的节点的random指针的指向 https://leetcode.cn/submissions/detail/149003325/ |
| 36 | 二叉搜索树与双向链表 | 树/链表 | 第一：二叉搜索树的中序遍历，正好是排序的链表，把处理链表的一些指针操作像打印链表放到inorder(root->left)和inorder(root->right)中间，https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/ |
| 37 | 序列化二叉树 | 树/bfs | 第一可以去看时间分布的答案里超过100%(牛逼)，第二，序列化和反序列化都用bfs思想 https://leetcode.cn/submissions/detail/150370545/ |
| 38 | 字符串的全排列 | 组合与排列 | 题解:https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/solution/sheng-cheng-zu-he-dui-xiang-de-suan-fa-by-bugger-r/ https://leetcode.cn/submissions/detail/127179252/ |
| 39 | 数组中出现次数超过一半的数字 | 数组 | 1刷后看题解的莫尔投票思路：https://leetcode.cn/submissions/detail/150733833/ |
| 40 | 最小的k个数 | 堆/快排 | 堆:c++有make_heap的api建堆https://leetcode.cn/submissions/detail/150743747/ 快排思路:https://leetcode.cn/submissions/detail/151156621/ |
| 41 | 数据流中的中位数 | 堆 | 利用两个大根堆，左堆保存更小的一半，右堆保存更大的一半的负数(小的数的取反后会再堆顶),https://leetcode.cn/submissions/detail/151183513/ |
| 42 | 连续子数组的最大和 | 动态规划 | https://leetcode.cn/submissions/detail/152124524/ |
| 43 | 1~n整数中1出现的次数 | 规律 | 把数字的位数分离出来，当前数字<0的时候，1的个数=高位数字x当前的base(百位还是千位还是个位)，当前的数字等于1，1的个数=高位数字x当前的base+低位数字+1,当数字>1的时候，1的个数=（高位数字+1)x当前的base https://leetcode.cn/submissions/detail/152145566/ 题目很难理清思路，也很难想到思路，但是只要理清了，代码还是很好写的 |
| 44 | 数字序列中的某一位的数字 | 规律 | 1刷毫无思路，看了解题区大佬的思路，佩服，过了2个月二刷，其实分为3步就可以了，第一:找到这个数有几位(是几百，几千，还是几万)，确定的有多少位后，第二步是确定x位数中的第几个(确定是万数中的第几个数字)，第三步是确定这个数字的中第某位数字(是万位，还是千位，还是百位)。https://leetcode.cn/submissions/detail/152275248/ |
| 45 | 把数组排成最小的数 | 数组 | 先把数字转成字符串，然后按照字符串排序，但是这样，3和30两个数字会组成330并不是最小的，所以需要自定义排序函数,把两个字符串a,b，拼成ab和ba然后返回更小的就可以https://leetcode.cn/submissions/detail/152294552/ |
| 46 | 把数字翻译成字符串 | 递归/动态规划 | dfs(12258)=dfs(2258) + dfs(258); dfs(2258) = dfs(258) + dfs(58); dfs(258) = dfs(58) + dfs(8). dfs(58) = dfs(5)终止条件只有1个字符，dfs(58)=1, dfs(258)=1 + 1=2, dfs(2258)=2+1=3, dfs(12258)=3+2=5。中间的dfs(258)可以优化下保存下来，dfs(2258)和dfs(12258)都用到.https://leetcode.cn/submissions/detail/153171986/ |
| 47 | 礼物的最大值 | 动态规划 | 原地动态规划即可 https://leetcode.cn/submissions/detail/153183943/ |
| 48 | 最长不含重复字符的子字符串 | 数组/字符串 | 注意重复的字符是否在未重复字符串的中间还是再两端，https://leetcode.cn/submissions/detail/153578456/ |
| 49 | 丑数 | 动态规划 | k神的思路，使用三个索引a,b,c，求得2a,3b,5c最小的值，然后最小值对应的索引+1.返回dp[n-1];刷题的时候尽量用栈数组，vector数组更耗时 https://leetcode.cn/submissions/detail/154055063/ |
| 50 | 第一个只出现一次的字符 | 数组 | 用两个数组分别保存字符的出现的次数mask，以及字符的索引idx，然后遍历mask，找到mask中的次数等于1的字符对应的索引。返回最小的索引即可。https://leetcode.cn/submissions/detail/154066960/ |
| 51 | 数组中的逆序对 | 归并排序 | 先写个归并排序，然后再判断两个数字大小的时候计数下逆序对，ex：[5,7], [3,4]两部分，i=0，num1=5, j=0, num2=3。这时的逆序对+=(左边数组的右边界-左边数组当前数字的下标)=2.也就是(5>3, 7>3)。然后j++, (5>4, 7>4) https://leetcode.cn/submissions/detail/154559009/ |
| 52 | 两个链表的第一个公共节点 | 链表 | 方法很多，方法1：可以先算法两个链表的长度，然后让长的链表先走n步(n为两个链表的差值),然后让两个链表同时走， 方法2：a,b链表同时走，某个链表为空的时候，遍历另一个链表的头节点，继续往下走（挺巧妙的) https://leetcode.cn/submissions/detail/154630943/ |
| 53-1 | 在排序数组中查找数字 | 二分查找 | 一般有排序就是二分法，最原始的方法就是写两个二分，查找左边界和右边界。优化：把target的值+1，然后也变成查找左边界。https://leetcode.cn/submissions/detail/154879604/ |
| 53-2 | 0~n-1中缺失的数字 | 二分查找 | 排好序的数组 https://leetcode.cn/submissions/detail/155611860/ |
| 54 | 二叉搜索树的第K大节点 | 树/递归 | https://leetcode.cn/submissions/detail/155643380/ |
| 55-1 | 二叉树的深度 | 树/递归 | https://leetcode.cn/submissions/detail/156454329/ |
| 55-2 | 平衡二叉树 | 树/递归 | https://leetcode.cn/submissions/detail/156471720/ |
| 56-1 | 数组中数字出现的次数 | 二刷也没有思路 | |
| 56-2 | 数组中数字出现的次数 II | 数组 | 统计二进制位数上的数字出现的次数，出现3次的话，该位对3取余则为0。https://leetcode.cn/submissions/detail/156939869/ |
| 57 | 和为s的两个数字 | 双指针 | https://leetcode.cn/submissions/detail/156939869/ |
| 57-2 | 和为s的连续正数序列 | 数组 | https://leetcode.cn/submissions/detail/157423803/ |
| 58-1 | 翻转单词顺序 | 字符串 | https://leetcode.cn/submissions/detail/157435192/ |
| 58-2 | 左旋转字符串 | 字符串 | https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/ |
| 59-1 | 滑动窗口的最大值 | 单调队列 | https://leetcode.cn/submissions/detail/157975584/ |
| 59-2 | 队列的最大值 | 单调队列 | https://leetcode.cn/submissions/detail/158957693/ |
| 60 | n个骰子的点数 | 递归 | https://leetcode.cn/submissions/detail/160751960/ |
| 61 | 扑克牌中的顺子 | 数组 | https://leetcode.cn/submissions/detail/161477518/ |
| 62 | 圆圈中最后剩下的数字 | 递归 | 方法1：用列表模拟，动态调整列表，方法2：从活着的人的id往前推(amazing) |
| 63 | 股票的最大利润 | 动态规划 | https://leetcode.cn/submissions/detail/162745479/ |
| 64 | 求1+2+…+n | 递归&逻辑运算 | 巧妙的用到与的运算，妈的这种题，不刷到死也想不出来，https://leetcode.cn/submissions/detail/161482149/ |
| 65 | 不用加减乘除做加法 | 逻辑运算 | 用到与和异或运算，https://leetcode.cn/submissions/detail/166464038/ |
| 66 | 构建乘积数组 | 数组 | 构建前缀乘和后缀乘数组，然后遍历相乘 https://leetcode.cn/submissions/detail/166481344/ |
| 67 | 把字符串转换成整数 | 字符串 | 编译器分析token的感觉，注意下INT_MAX和INT_MIN的情况即可 https://leetcode.cn/submissions/detail/166509636/ |
| 68 | 二叉搜索树的最近公共祖先 | 树/递归 | 用递归思路就比较简单，搜索树左小右大情况判断，然后递归左子树或者右子树 |
| 69 | 二叉树的最近公共祖先 | dfs/bfs | https://leetcode.cn/submissions/detail/172276604/ |
评论 (0)
