- 博客(78)
- 收藏
- 关注
RSS订阅原创 最大值与最小值之差小于等于指定值的子数组个数
解题思路首先明确两点： 1、如果子数组arr[i…j]满足条件，那么arr[i…j]中的子数组一定也满足条件。 2、如果子数组arr[i…j]不满足条件，那么包含arr[i…j]的子数组一定也不满足条件。使用两个双端队列qmin和qmax，qmin用来维护子数组arr[i…j]的最小值更新，qmax用来维护子数组arr[i…j]的最大值更新。队头表示的就是子数组arr[i…j]的...
2019-05-26 10:21:30
836
原创 求最大子矩阵的大小
题目描述给定一个整型矩阵map，其中的值只有0,1两种，求全是1 的所有矩阵区域中，最大的矩形区域为1的数量。 例如： 1 1 1 0，其中最大的矩形区域有3个1，所以返回3 例如： 1 0 1 11 1 1 1 1 1 1 0 其中，最大的矩形区域有6个1，所以返回6解题思路如果矩阵的大小为 O(N * M) ， 如何达到时间复杂度为O（ N...
2019-05-26 10:19:07
229
原创 构造数据的MaxTree
题目描述一个数组的MaxTree定义如下： 数组必须没有重复元素。 MaxTree是一棵二叉树， 数组的每一个值对应一个二叉树节点。 包括MaxTree树在内且在其中的每一棵子树上， 值最大的节点都是树的头。 给定一个没有重复元素的数组arr， 写出生成这个数组的MaxTree的函数， 要求如果数组长度为N， 则时间复杂度为O(N)、 额外空间复杂度为O(N)。解题思路解法一...
2019-05-26 10:15:41
229
原创 滑动窗口的最大值
题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个：{[2,3,4],2,6,2,5,1}，{2,[3,4,2],6,2,5,1}，{2,3,[4,2,6],2,5...
2019-05-26 10:10:01
201
原创 汉诺塔问题
题目描述汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？分析如果是初次接触类似的问题，...
2019-05-26 09:55:27
204
原创 用一个栈实现另一个栈的排序
解题思路假设需要被排序的栈为stack申请一个栈helper，当栈stack不为空的时，出栈stack栈顶的元素，标记为cur若helper为空或者stack栈顶的元素大于等于cur，将cur压入helper中，否则将helper中的元素弹出到stack中，直到helper为空或helper栈顶的元素小于等于cur，再将cur压入helper中，如此反复，直到stack为空（此时，helpe...
2019-05-26 09:42:49
107
原创 猫狗队列
题目描述实现一种猫狗队列可以add,pollAll,pollDog,pollCat,isEmpty,isDogEmpty,isCatEmpty要求如下：用户可以调用add方法将cat类或者dog类的实例放入队列中；用户可以调用pollAll方法，将队列中所有的实例按照队列的先后顺序依次弹出；用户可以调用pollDog方法，将队列中dog类的实例按照队列的先后顺序依次弹出；用户可以调...
2019-05-26 09:23:56
110
原创 如何引用递归函数和栈操作逆序一个栈
题目描述一个栈一次压入1,2,3,4,5,那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底位1,2,3,4,5,也就是实现栈中元素的逆序,但是只能用递归函数来实现,不能用其它数据结构解题描述先将栈stack的栈底元素返回并移除,然后依次再压入代码public class ReverseStack{ public void reverse(Stack&...
2019-05-26 09:20:11
116
原创 Mapreduce都能实现哪些Join？
概述在传统数据库（如：MYSQL）中，JOIN操作是非常常见且非常耗时的。而在HADOOP中进行JOIN操作，同样常见且耗时，由于Hadoop的独特设计思想，当进行JOIN操作时，有一些特殊的技巧。本文首先介绍了Hadoop上通常的JOIN实现方法，然后给出了几种针对不同输入数据集的优化方法。常见的join方法介绍假设要进行join的数据分别来自File1和File2.2.1 redu...
2019-05-09 16:50:29
193
原创 YARN与MapReduce V1的对比
分散了jobTracker 的任务。资源管理任务由资源管理器负责，作业启动、运行和监测任务由分布在集群节点上的应用主题负责。这样大大减缓了MapReduce V1中jobTracker 单点瓶颈和单点风险的问题，大大提高了集群的扩展性和可用性。在MapReduce V2中ApplicationMaster是一个用户可定制的部分，因此用户可以针对编程模型编写自己的应用主题程序。这样大大扩展...
2019-05-09 16:35:37
625
原创 YARN的工作原理
YARN的组成部分YARN共有ResourceManager、NodeManager、JobHistoryServer、Containers、Application Master、job、Task、Client组成。Resource Manager: 一个Cluster 只有一个，负责资源调度、资源分配等工作。JobHistory Server: 负责查询job运行进度及元数据管理。no...
2019-05-09 16:32:02
363
原创 Hadoop中小文件过多的问题
问题定义HDFS上的小文件是指文件大小明显小于HDFS上块（block）大小（默认64MB）的文件。在hdfs上大量存储小文件会给hadoop的扩展性和性能带来严重问题。原因首先，在HDFS中，任何一个文件，目录或者block在NameNode节点的内存中均以一个对象表示（元数据）（Every file, directory and block in HDFS is represented ...
2019-05-09 16:15:22
2977
原创 字符串转化的最小操作数
题目描述Given two words word1 and word2, find the minimum number of operations required to convert word1to word2.You have the following 3 operations permitted on a word:Insert a characterDelete a cha...
2019-05-08 20:12:15
1505
原创 hdfs的日常维护
Datanode块扫描器各个datanode运行一个块扫描器，定期检测节点上的所有块，从而在客户端读到坏块之前及时检测和修复坏块。可以依靠DataBlockScanner所维护的块列表依次扫描块，查看是否存在校验和错误。扫描器利用节流机制，来维持datanode的磁盘带宽。默认情况下，扫描器每隔三周就会检测块，以应对可能的磁盘故障，这个周期由dfs.datanode.scan.period.h...
2019-05-06 13:42:48
534
原创 hdfs的安全模式
安全模式的作用hadoop的安全模式即只读模式，是指当前系统中数据块的副本数比较少，在该阶段要对数据块进行复制操作，不允外界对数据块进行修改和删除等操作。Namenode启动时，首先将映像文件（fsimage）载入内存，并执行编辑日志（edits）中的各项操作。一旦在内存中成功建立文件系统元数据的映像，则创建一个新的fsimage文件（这个操作不需要辅助namenode）和一个空的编辑日志。此...
2019-05-06 11:53:39
528
原创 DataNode的工作机制
问题场景：1、集群容量不够，怎么扩容？2、如果有一些datanode宕机，该怎么办？3、datanode明明已启动，但是集群中的可用datanode列表中就是没有，怎么办？以上这类问题的解答，有赖于对datanode工作机制的深刻理解概述Datanode工作职责：存储管理用户的文件块数据定期向NameNode汇报自身所持有的block信息（通过心跳信息上报）（这点很重要，因为...
2019-05-06 11:26:23
152
原创 NameNode工作机制
学习目标：理解namenode的工作机制尤其是元数据管理机制，以增强对HDFS工作原理的理解，及培养hadoop集群运营中“性能调优”、“namenode”故障问题的分析解决能力问题场景：1、集群启动后，可以查看文件，但是上传文件时报错，打开web页面可看到namenode正处于safemode状态，怎么处理？2、Namenode服务器的磁盘故障导致namenode宕机，如何挽救集群及数据？...
2019-05-06 11:23:14
249
原创 Hadoop的机架感知功能
原理默认情况下，hadoop的机架感知是没有被启用的。所以，在通常情况下，hadoop集群的HDFS在选机器的时候，是随机选择的，也就是说，很有可能在写数据时，hadoop将第一块数据block1写到了rack1上，然后随机的选择下将block2写入到了rack2下，此时两个rack之间产生了数据传输的流量，再接下来，在随机的情况下，又将block3重新又写回了rack1，此时，两个rack之间...
2019-04-26 15:33:56
458
原创 hdfs中的复本放置策略
hadoop默认的复本数为：3hadoop的默认布局策略是：在运行客户端的节点上放第1个复本第2个复本放在与第一个不同且随机另外选择的机架中的节点上第3个复本放在与第2个复本放在同一个机架上Hadoop的副本放置策略在可靠性（副本在不同机架）和带宽（只需跨越一个机架）中做了一个很好的平衡。...
2019-04-26 15:29:04
706
原创 hdfs的工作机制
工作机制的学习主要是为加深对分布式系统的理解，以及增强遇到各种问题时的分析解决能力，形成一定的集群运维能力注：很多不是真正理解hadoop技术体系的人会常常觉得HDFS可用于网盘类应用，但实际并非如此。要想将技术准确用在恰当的地方，必须对技术有深刻的理解概述HDFS集群分为两大角色：NameNode、DataNodeNameNode负责管理整个文件系统的元数据DataNode 负责管理...
2019-04-26 15:26:40
329
原创 hdf的基本概念与使用
基本概念首先，它是一个文件系统，用于存储文件，通过统一的命名空间——目录树来定位文件其次，它是分布式的，由很多服务器联合起来实现其功能，集群中的服务器有各自的角色；重要特性如下：（1）HDFS中的文件在物理上是分块存储（block），块的大小可以通过配置参数( dfs.blocksize)来规定，默认大小在hadoop2.x版本中是128M，老版本中是64M（2）HDFS文件系统会给客户...
2019-04-26 15:21:04
4999
原创 haddop环境搭建与配置
下载地址http://archive.cloudera.com/cdh5/cdh/5/建议下载cdh版本，可以帮助解决很多依赖问题，也是工程上常用的版本。配置流程准备Linux环境1.0先将虚拟机的网络模式选为NAT 1.1修改主机名 vi /etc/sysconfig/network NETWORKING=yes HOSTNAME=itcast ###1.2修改...
2019-04-26 15:09:42
266
原创 二叉搜索树中的后序遍历序列
题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。解题思路方法：递归判断序列中是否可以被最后一个值划分因为是二叉搜索树的后序遍历，所以序列中的最后一个值为根节点，且根节点的值大于左子树所有值，小于右子树所有值。代码public class VerifySquenceOfBST { p...
2019-04-26 11:59:25
246
原创 树的子结构
题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）解题思路1、首先设置标志位result = false，因为一旦匹配成功result就设为true，剩下的代码不会执行，如果匹配不成功，默认返回false2、递归思想，如果根节点相同则递归调用DoesTree1HaveTree2（），如果根节点不相同，则判断tree1的左子树和tree2是...
2019-04-26 11:58:06
193
原创 重建二叉树
题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。解题思路方法：递归解决思路：重建二叉树只能通过前序遍历和中序遍历或者中序遍历和后序遍历来实现，因为其原理就是递归实现通过前序遍历中的第一个节点（根节...
2019-04-26 11:56:58
200
原创 二叉树中和为某一值的路径
题目描述输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)解题思路代码public class FindPathWithSum { ArrayList<ArrayList<Integer>> res =...
2019-04-26 11:48:04
228
原创 数据流中的中位数
题目描述如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。解题思路【java】这里讨论两种方法：一：代码复杂：减少不必要插入，提高效率二：代码大大简化：可能有...
2019-04-26 11:45:52
233
原创 序列化二叉树
问题描述请实现两个函数，分别用来序列化和反序列化二叉树思路描述a) 思路一：首先想到的就是这个思路，先计算出二叉树的前序、中序、后序遍历中的两个，将这2个遍历结果作为序列化后的字符串中的主要内容；解析时，拿到这两个遍历结果，重构二叉树即可。（刷题时忘了重构二叉树的思路，就没用这个方法）b) 思路二：根据层序遍历结果，将二叉树序列化为字符串，然后根据层序结果重构二叉树 – 应该借助split...
2019-04-24 11:48:05
148
原创 二叉树的第k个节点
问题描述给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。思路解析二叉搜索树的中序遍历结果是有序的，所以直接中序遍历，然后输出第k个结果就好了。代码public class KthNode { ArrayList<TreeNode> TraversalRes = new ArrayL...
2019-04-24 11:46:11
135
原创 对称的二叉树 – 重点
题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。思路解析思路：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同左子树的右子树和右子树的左子树相同即可，采用递归非递归也可，采用栈或队列存取各级子树根节点代码public class isSymmetrical { boolean isSymmetric...
2019-04-24 11:44:59
104
原创 按之字形顺序打印二叉树
问题描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。解题思路在按层次遍历的基础上，增加方向标记标量，以及实现逆序的代码即可。代码public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { Arra...
2019-04-24 11:42:51
65
原创 把二叉树打印成多行
问题描述从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。解题思路按层次遍历即可代码public static ArrayList<ArrayList<Integer>> traversalByLayer(TreeNode<Integer> pRoot){ ArrayList<ArrayList<Integer>...
2019-04-24 11:41:40
68
原创 复杂链表的复制
题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）解题思路剑指offer中面试题26代码public class CloneRandomList { public RandomListNode Clone...
2019-04-24 09:30:18
96
原创 链表中倒数第k个节点
题目描述输入一个链表，输出该链表中倒数第k个结点。解题思路建立两个指针，一个领先另一个k步，同时前进，前面的指针到头，后面的那个是倒数第k个代码public ListNode FindKthToTail(ListNode head,int k) { if(head==null || k==0) return null; int len=0; ListNode ...
2019-04-23 15:06:37
72
原创 反转链表
public static ListNode reverse(ListNode head){ if (head==null || head.next==null) return head; ListNode last=null; ListNode tmp; while(head!=null){ tmp=head.next; head...
2019-04-23 15:05:12
72
原创 删除链表中重复的节点
题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。解题思路设置两个根节点p1和p2，p1负责更改原链表，p2负责检测并跳过重复的节点。当发现p2与p2的下一个节点值相等时，将p2后移直到p2指向的节点为非重复节点...
2019-04-23 15:03:37
82
原创 找到链表中的第一个公共节点
题目描述输入两个链表，找出它们的第一个公共结点。解题思路在只包含next节点的前提下，如果两个链表有公共节点，那么这两个链表在公共节点之后的所有节点一定是重合的。即他们一定是“Y”字形，而不可能是“X”字形。所以这两个链表的区别就在于公共节点之前，如果两个链表的在公共节点之前的长度相等，且不重合，那么两个头指针同步前进直到两指针相等即可找到第一个公共节点。但是，公共节点之前，如果两个链表...
2019-04-23 15:01:16
421
原创 最大乘积 – 拼多多2018笔试
题目描述解题思路设max1、max2、max3分别为第1大到第3大的数，min1、min2分别为第1小到第2小的数。思路： 如果数组中全是正数：结果为max1max2max3 如果数组中全是负数：结果为max1min1min2 如果数组中有正有负：结果为：max{ max1max2max3,max1min1min2}解题方法：在遍历数组是需要记录第一，第二，第三大，和最小...
2019-04-23 14:59:19
105
原创 扑克牌顺子
题目描述LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张_)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张...
2019-04-23 14:56:08
95
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人