CHuiL

判断平衡二叉树

剑指offer

题目描述 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 解法 平衡二叉树要求每一个节点的左右子树深度的差值<=1。所以采用后序遍历的方法，从下往上遍历判断每个子树都否都满足，并且返回每个子树的深度。 代码 bool IsBalanced_Solution(TreeNode* pRoot) { int i; return isBanlance(...

Posted by chl on February 17, 2019

两个链表的第一个公共结点

剑指offer

题目描述 输入两个链表，找出它们的第一个公共结点。 解法 这道题单纯这么描述感觉有歧义。因为可能存在以下两种情况 第一种，如下，从公共节点开始后面的节点都相同，可以先求两链表长度，例如分别为5,6；然后使两链表到达尾部的时间相同，即长的先走m-n（n-m)步，然后每走一步比较一次，找到的就是第一个公共节点。空间复杂度O(1),时间复杂度O(m+n); 下面这种情况显然上面的方法就行不通...

Posted by chl on February 17, 2019

数组中的逆序队

剑指offer

题目描述 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 解法 解法一：很容易想到的就是遍历到每一个数值后在和后面的数字依次比较，统计个数，时间复杂度为O(n^2); 解法二：利用归并排序的思路，因为归并排序在排序的时候是两个子数组（...

Posted by chl on February 17, 2019

连续子数组的最大和

剑指offer

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续...

Posted by chl on February 15, 2019

数据流中的中位数

剑指offer

题目描述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。 解法 题目本身不难理解，就是从不断增加的数据中找出中位数，因此需要有合适的容器和方法来决定插入的操...

Posted by chl on February 15, 2019

剪绳子-动态规划和贪婪算法

剑指offer

题目描述 给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]k[1]…*k[m]可能的最大乘积是多少？ 解法 典型的动态规划问题，将最终最值问题转换为由各个小问题的最值堆叠起来，并且在这个过程中存储各个小问题的最值。 我们可以将这段绳子最大乘积的问题进行转换：先将他切割为两部分，假设切割...

Posted by chl on February 15, 2019

最小的k个数

剑指offer

题目描述 给定一个乱序的整型数组，求这个数组中最小的k个数 解法一 快排序思想，随机取一个数值，然后按大于该数或小于该数分为两部分，然后返回该数在数组中的位置index，判断是否等于k-1；如果等于k-1，则说明此时所求的最小的k个数位于数组前k个； 否则根据k的位置继续寻找index=k-1;时间为O(n)，但是会改变原数组； 解法一代码 vector<int>...

Posted by chl on February 13, 2019

数组中出现次数超过一半的数字

剑指offer

题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 解法 解法一：利用map来存储每个数字出现的次数，然后判断是否超过数组一半来返回； 解法二：基于数组特点，由于有超过数组长度一半的数值，所以该数值出现次数总和大于其他数...

Posted by chl on February 13, 2019

复杂链表的复制

剑指offer

题目描述 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 解法一 首先从链表节点的next开始复制，先获得一条单向链表，在获得单向链表的过程中，使用map来将原链表节点和复制后得到的链表节点建立映射； 接着复制链表节点中的特...

Posted by chl on February 9, 2019

二叉树中和为某一值的路径

剑指offer

题目描述 输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 解法 使用一个辅助栈（向量），来从根开始前序遍历树，将路上的值加起来并进行判断，符合期望值的路径输出；当搜索完一条路径之后（不管是否成功）回溯回父节点时，将原来加入进去的节点弹出...

Posted by chl on January 20, 2019

ABOUT ME

just do it