1月刷题记录

二叉树

NC224 从下到上打印二叉树（层序遍历，每一层的结果从后往前放回ans，麻烦的是arraylist转二维数组）

NC195 二叉树的直径（后序遍历，递归返回左右子树中较大的那个再+1，递归过程中不断计算maxpath=Math.max(maxpath,left+right)）

NC191 二叉搜索树的最近公共祖先（后序遍历，递归，费解）

NC123 序列化二叉树（前序遍历，主要是对字符串的操作）

NC84 完全二叉树结点数（可以直接后序遍历计算，如果要用完全二叉树的特性就要递归计算左右子树的高度，满二叉树计算公式：2 ^ heigh-1，总的结点数 = 根节点 + 满二叉树节点个数+ 完全二叉树节点个数）

NC98 判断t1树中是否有与t2树完全相同的子树（先找到相等的root，再递归计算这两棵子树是否每个结点都相等）

NC223 从中序与后序遍历序列构造二叉树（画图找下标）

NC193 二叉树的前序遍历

NC192 二叉树的后序遍历

NC150 二叉树的个数 （动态规划。对于每一个根i他都是由左边子树（1, 2, …, i - 1)和右边子树（i + 1, i + 2, …, n)组成的。因此他的个数肯定是两个子树情况的积。最后n个根，加起来）

NC162 二叉树中和为某一值的路径(三) （先序遍历，全局变量res）

NC248 左叶子之和（dfs，多传一个isLeft用于记录走了左边）

NC169 修剪叶子（dfs，发现左/右儿子且它是叶节点就修建，即返回空）

动态规划

NC17 最长回文子串（dp[i][i]定义为A[I]到A[j]是否为回文子串，是1，否0，对于对角线上方的部分，从下到上，从左到右遍历）

字符串

NC141 判断是否为回文字符串（头尾配对逐个判断）

NC56 回文数字（int转字符串Integer.toString(x)）

链表

NC96 判断一个表是否为回文结构（先找到链表的中点，再把链表的后半部分进行反转）

NC78 反转链表（递归和迭代，熟练掌握）

NC21 链表内指定区间反转（在head前面加一个dummynode，截断left和right进行反转链表再接回去）

NC50 链表中的节点每k个一组翻转（递归做法，a是头结点，b是从head开始走k步指向的结点，用一个reverse函数反转a到b，a后面接上 下一次递归的结果，b作为头结点，最后返回newHead）

NC33 合并两个排序的链表（把merge定义为，输入两个listnode，返回较小的那个结点，base case是当有一个listnode为空，只能返回另一个listnode。递归比较list1和list2指向的值，哪个小就继续merger下一个结点）

NC4 判断链表中是否有环（经典快慢指针）

NC66 两个链表的第一个公共结点（交替走，会相遇）

leetcode 142. 环形链表 II（先用快慢指针找到第一次的相遇点，然后其中一个指针回到head，另一个指针不动两个指针同速往前走，它们会再次相遇在环形链表的入口点）

NC51 合并k个已排序的链表（利用了小根堆的性质，先把每条链表的第一个结点放进小根堆，再逐个弹出，每次弹出结点都把它的下一位放进小根堆中）

NC2 重排链表 （找到中点，切成两条链表（快慢指针），反转第二条链表，合并两条链表）

NC53 删除链表的倒数第n个节点（快慢指针，加dummy结点）

NC40 两个链表生成相加链表（先反转链表，再相加，注意最高位可能还有一个进位，得到结果后反转回来）

NC70 单链表的排序（归并排序，找到链表中点并断开成两条链表，对左右两条链表继续递归，返回合并两条有序链表的结果）

NC25 删除有序链表中重复的元素-I（双指针）

NC186 两两交换链表的节点（类似NC50）

NC207 排序奇升偶降链表（分为奇链表和偶链表，反转偶链表，两条链表归并）

JZ6 从尾到头打印链表（可以先反转链表）

NC211 旋转链表（）

NC24 删除有序链表中重复的元素-II（pre、cur、tmp）

NC69 链表中倒数最后k个结点（快慢指针）

NC133 链表的奇偶重排（NC207差不多思路）

NC23 划分链表（新建两个链表接收大于x和小于x的结点，最后连起来）

NC244 对链表进行插入排序（遍历链表，找错的结点tmp并放回正确位置）

DFS

NC138 矩阵最长递增路径（）

NC226 被围绕的区域（最外层的’O’先标记为’A’，能和最外层直接相连的’O’也标记为’A’，之后遍历整个矩阵，把’O’变为’X’, 把’A’变为’O’）

排序

NC140 排序（用了插入排序，遍历数组，每个数都和前面的数比较，把小的数交换到前面 一直移到合适的位置上去）

数组

NC73 数组中出现次数超过一半的数字（先排序，取中间数）

NC61 两数之和（哈希表）

NC166 连续子数组的最大和(二)（在原有dp基础上记录max，还要记录当前len，不断更新maxlen和maxend，最后进行输出）

leetcode 15. 三数之和 （先排序，两步去重）

NC22 合并两个有序的数组（归并排序，为了能不额外创建数组，A数组后面有多余空间，所以从后往前进行归并）

NC37 合并区间（[a,b][c,d]可以合并的情况有两种，a<c<b<d,a<c<d<b）

NC107 寻找峰值（例外情况有：只输入一个数 直接返回0，峰值在最左侧和最右侧）

NC77 调整数组顺序使奇数位于偶数前面(一)（两个数组去存再合并）

碎碎念

1月要过完啦~~本命年终于要过去咯，希望新年顺顺利利

总结

以上是生活随笔为你收集整理的1月刷题记录的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。