Posts

题目描述：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1) i c } m l p a o s r s f } f } t u u F n n F o c c o r i } v v f } r v v f } r u 3 m f a a o e m a a o e n 1 a r r r t a r r r t d S x n u x u a o S . r c s i i } } i } r S c s i c s r t l u c e u u f e f n u u u u u n i u b o t r m i l b r m i r m o t A u u r n c s c s A r n r s n i r n r e = u c e c u s u r e = e = u o r t n n n r u u r u m r n n n m n a t I r r { r r m a t I t m y = 0 n { e r r e y n { a { ( = = t n e e n = 2 = t = x _ . t n n t ( . ( 0 0 m t t c _ 0 m m c n i < > u i a u : { n = + r n n x r 0 = s r : ( r [ i u e i e I { i m n [ , n n t I t t { n c , ] t u ) ] r s ) r u e m n ) t I + n I i t n ) t { { 算法思想：第一种解法比较常规，第二种解法比较巧妙。每次比较当前和之前的值大小，然后存最大的值。 ...

题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 i c } m l p a o s r s f } f } t u / u F n 快 n F o c 排 c o r i } v v v v w } r p l v v w } n r u 3 t f a a a a h e a p e a a h [ e n 0 o r r r r i t r a t r r i l t d S p n l u t r l e u a o K . r n s e i e i } i } r i t t l r e w } n w } n f r t l ( c e u t n n f f n t i e e i h [ h [ t n i u _ o t m a d d i i t m f g l i l i r ] o t u u s r e n i i A o i p t h e l e l i l n i n n r t = x d n e i n s i r n o t f e r f e l g = e o : t n = e d n n d t n r n = = t i t e h f n = n = x e d d e a d a ( = l g ] l f t t t [ = [ n . x e x r e y _ n l < e h e t ] e { I = ] 0 c p ! = x t x ( [ e r f t = f m n o a = > < n n l f i r t t + = p t 0 u r i = = = u : e t g i - n = ] n t m m n m m f I h g < = [ < n , t i i i d p i i p s i t n t h r 1 [ _ t n n e a n n a [ n I I t r 1 i r l - i K K x r K d r 0 o n n i g i e m m o t e t . u ] { g h g f i i 1 n - - - i - x i . t h t h t n n ( t t < t ] t ] K K & 1 1 1 i 1 + i m [ : n o o i I & & = u { { n { 1 n n n & & I = m ( ( K t n s & & ] ] n n t 0 , n n ) , [ [ ) u u _ r l { s m m i e t s s l g f a , , e h t r f t ] [ t s s t ] I , t t I < n a a n > = t e r r : = ] n t t t d , , I t e { ) n e m e e t m p n n , p d d _ { ) ) { r i g h t I n : I n t ) I n t { 算法思想：利用快速排序划分的思想，每一次划分就会有一个数字位于以数组从小到达排列的的最终位置index；最后index=K就完成了。 ...

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 i c } m l p a o s r s f } t u F n F o c o r g } v f } v f } i } r u 2 m u a o a o f e n 9 o a r r r r t d S r r k u a o e d p r h r i } } k k i } e p r r t l T r e a f e e f y r e n i u h n i t s i l y i i t o t a . n u h n h s : n h = n u k n i n c t r M a h e h a k = t r e o H o ( n a n s a a I h s e ( n y n a u " p h s { s n a h y n " ! l n n - { M h h t s M i n - { f t 为 9 = a M M ? h a = l 为 9 N 无 9 p a a M p 无 9 u > 效 9 [ . p p = a [ k { 效 9 m 数 I k . . p k 数 ( 0 组 n e u u n . ] 组 _ " t y p p i k ! " e ) s d d l e ) n l : . a a y > : s c t t s e I o e e n [ n n V V { . I { t t a a c n ] a l l o t ( i u u u ] ) n e e n ) s ( ( t ( h 1 / r a , 2 ) s h f { I { M o n a r t p K [ e { r y ] : ! + r 1 ) , f o r K e y : r ) 算法思想：某个数字出现的次数大于数组长度的一半，意思就是它出现的次数比其他所有数字出现的次数和还要多。因此我们可以在遍历数组的时候记录两个值：1. 数组中的数字;2. 次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。最后再判断它是否符合条件。 ...

题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列 例如输入字符串abc, 则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。 i c } m l p a o s r s f } f } f } t u u u F n n n F o c 去 c 字 c o r l f 重 v f } r 符 v i } } u 2 p e u i a o e 串 f a f n 8 e t l s r r t 特 u r e d S r l S u 定 l b l a o m t _ w r i i } r 区 l t e l p s f } t l u e p a e f n 间 _ e g e r e o i u t m e p s i 的 p m i t i r o t a p r ( u n a r 字 e p n n { n i t : m a l r r b e 符 r : d t i i } o i [ u r t b r e r s 串 m [ = a ( f n o C t r : e [ s e u 排 u C = t " i n h a : B g i u a l 列 t h a 排 n i { ( a t o i ] l k t a a e : 列 s t f t _ r i [ o n t t r n [ - b S e u e a o C l . = i a d C - e w m l m s c n h . = = o c h - g a p l p : t ( a = < n t - a \ i p . _ . e a r e a f ( e r ( n ( s p s S r r a t n r a a r 1 a d . a w e w t ] r c r d r l r ] c a . r a r a r : t u [ s r { t t < r p m p i = e e { e e : = e a e : A u A n t r n r ) n t t t g A e ] d [ a ] " d t ( a ( ) r m , ] C r ) e i t i r p h r 递 = { m , i , { a , b { a 归 p o y e r 之 A , b n b ( b g a 后 r e ( e s e i c 输 r b g a g ) g n t 出 a e i r i i : e y g n r n n r ( i ) : ) : I ] a n n , r : t 0 t r e , , b [ b m e 0 e 字 p 字 e e g . g 符 , 符 n n i . i 串 串 d d n < n 交 b 恢 : : : e , 换 e 复 n g t I I d e i e n n ] n n m t t ) d : p ) , : . b c e i e o n ) g u d i n B : { n t o + ) o I 1 l n , t { ) e n { d : e n d ) 算法思想：首先，求所有可能出现在第一个位置的字符， 其次，把第一个字符和其后面的字符一一交换。如下图所示，分别把第一个字符a和后面的b、c等字符交换的情形。 接着，固定第一个字符，求后面所有字符的排列。这个时候我们仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换 ...

题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 i c } m / l p 中 a o 序 s r 遍 s v v f } f } t 历 a a u u ， F r r n n F 节 o c c o 点 r h l c r i } c i } } c u 互 2 e a c o e c f o f o n 指 7 a s o n t o n e n d S d t n v u n r v l l v a o : N v e r v o r e a h l s r l l e t l T o e r n e o e r s e a e / o a a r i u r d r t r t t t t a s 前 o s s t o t e e t S h t u S N d t { 一 t t t S n i e : T u e S = r u o N 个 ? N N u o N T w b a u = n b d = o 节 . o o b n o r o L d b L e d 点 l d d L d e W i L n i r e 和 e e e i { e e a s i i s = o 当 f ? s ? N y t s l t = o = 前 t . = t o L ( t ( t 节 r ( d i r ( { r n r 点 = i r r e s o _ o i o （ g o o ? t o o l o r l h o o ( t r t t o a t t t _ ) o ? { o s ? o . t t = . r t l ） N r o : e 互 o r i o T f 指 d o g t r t ， e o h : e ) 然 t t T e 后 ) r N 到 e o 下 e d 一 N e 个 o ? d ) e ? { ) T r e e N o d e ? { 算法思想：在二叉搜索树中，左子结点的值总是小于父结点的值，右子节点的值总是大于父结点的值。因此我们在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子节点的指针调整为链表中指向后一个结点的指针。 因为中序遍历是按照从小到大的顺序遍历二叉搜索树，所以我们用中序遍历树中的每一个节点得到的正好是要求的排好序的。遍历过程如下： 每次遍历节点的左孩子、右孩子，把左孩子指向转换链表的尾节点，并把末尾指针的右孩子指向自己。右孩子指向节点的右孩子。如果没有右孩子就返回。这一过程可以用递归实现。 ...

题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。要求编写函数复制这个复杂链表。 i p } c } m u l p b a o L l s r i i p p p p } s f } f } f } f } t s c u u u u u / u / u / u t b b b b F n 复 n 复 n 分 n F N c l l l l o c 制 c 制 c 离 c o o l i i i i s s s r v r 主 v l w } r 随 v l w } r 两 v v v i } w } r u d a c c c c e e e 2 c a e 链 c a e h e 机 c a e h e 个 p a a a f h e n e s l l l 6 o r t o r t i t 指 o r t i t 链 a r r r i t d s v v v i f f f S p u p l u 针 p l u 表 r p l u a U a a a n . . . o y p p p r y p p e l p p p p p r y p p e l i } p r t p p p N p p p p e p p p p r t t C r r r i v n s l C n N N H e C C C N N n S N H e f N n i N C C o C C N N C C N N n i i o t a e i u o = = = e o e p t l l l o o i o e p t o t o l l d l l o o p l l o o o l m v n s ( l x b t m p x d a N o o o d d p b d a N p d p i d o o e o o d d N o o d d p n s p a e i _ t l i p c c p t e d o p n n n e e H l e d o p N p e H o e n n n n e e o n n e e C l l x b = i o l o o a ( d C e e e ? e i d C o C e n e e ! e e ? d e e ? l e : t l v = n n e p p r _ = = e l . . . . = a n = = e l d l = a ( = H N = H N . = e N N . = o x : i a v g x y y t o v n s n d g o e o d _ e o e o n o o n n L I n l a n { L N S i h h h ! n a e i e p ! ( h h ! n ? n p ! h a d n a d e p ! d d e p e i n C g : l i = i e i t e e e = e l x b x N _ e e = e . e C h e d e i d e x N = e e x N H s t o : l s x b i a a a t l t o a a s ? l e a : : l t o ? t o e t m I n t t l o d d d n = = i d h d d n = i . o a d = = d n . = d a N p C n i N ( i n : i = n = e e i b s n d C C { = e i n = e d o l o t l o h n ( l C p g ? a l p l i e : o o p p ? l e p ? ! d e m ) d e g p C o N p p . d N i b ? m m C N p . x C p . e x p e a ( ) o { m o N = C n : { o n l . C p p l o C n { t l C n L l { ( d p m p d o l e d g i n o l l o d l e o l e { i e _ ) ) p l e d n o x C e n e m e e n e o x = n o x s x l e ! e i n t o ! ! g x p x x e ? n t e n t t L h e x . ? l e m . = t l L L N . e p N e N i e x L v . p n = e i i o n N N o N o s a L i a n l e n x s s d e o o d o d t d i s l e e x i p L t t e x d d e d e N : s t x x t l N i N N t e e ? e ? o t N t L o s o o ? ? . ? d C N o i { d t d d . . n . e o o d s e N e e n n e n ? m d e t ? o ? ? e e x e p e ( N . d x x t x l ? 0 o s e = = t t t e ) ) d i ? x e b ) n n L ? l i i i ) i l l s n t C g N o ? C o m . o d p C n m e l o e p ? e m x l ) x p t e L l x i e L s x i t L s C N i t o o s N m d t o p e N d l o e e { d x e { L i { s t N o d e { 算法思想：思想是在原来的链表每个节点后面都复制了一个同样的节点，再修改其指针，最后把偶数节点都抽出来，作为新的复杂链表。 ...

题目描述：输入一棵二叉树和一个整数， 打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 i c } m l p a o s r s f } f } t u u F n n F o c c o r v l p p i } v p i } i } i } u 2 t a e a r p f a a f f f n 5 r r t t i a r t d S e h n t r h r r r a o e r p H t h o r p . o p o p o i } t l V e a e ( H o e a a o a o a o f i u a s t l r e t t t p t t t t t o t l h p e l u h p ? h ? h ? p n i S = e s p = r e . H . H . a r o u = r ) e = n = n l e r e l t e n m [ ( r d e l i l e h s ( [ [ r ( n p ( f p g p f . . { _ I I o _ i a r t e h e t r a n n o l t o r t r e p r t t t r h o ! ( ( = d p o ] ] , o { s t = r ! r = u e o ] ( o ! o = o c n t ( ) & t . n o o n e d : ) r : v i t n t i ( ( e a l ? i ? l 0 p T s T l . l . , a r , r ) { l r & t e e e { i & h e p e f g ) N a N t h r o t o , t o = d h d , o = e , e & t ? ? r & ? s , n , e r . u _ ) _ s e r m , s i n r , g { : e p h s a p t I : t a n h t = t i , h = ) n s , o u s n { u m u i t ) m l ) [ { [ I n t ] ] , _ p a t h s : [ I n t ] , _ s u m : I n t ) { 算法思想：由于路径是从根结点出发到叶结点， 也就是说路径总是以根结点为起始点，因此我们首先需要遍历根结点。在树的前序、中序、后序三种遍历方式中，只有前序遍历是首先访问根结点的。 ...

题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。 i c } m l p a o s r s f } t u F n F o c o r v v w } r u 4 a a a h e n 7 d r r i t d S d l u a o S n n e l l n n r t l u 1 2 e e 1 2 n i u m n t t o t ( = = 2 = = n n i _ s c 1 o a b ! u a s c n a = m r u a : r m r { 0 = y r I y n { n = t 1 , ( _ ^ n 1 b n : 2 & I n n 2 t ) ) 1 I n t { 算法思想：位运算模拟加法。 ...

题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。 i c } m l p a o s r s f } t u F n F o c o r i } l v w } v w } v i } v i } r u 2 i f e a h a h a f a f e n 4 s t r i r i r r t d S P n l l i i u a o o . r r i e i j e i } j l l r r r t l s c e o f e > e i < i n i u t o t o = n + = j + f f g g o t O u u t [ = n = t 0 t h l h l n i r n r 0 i i < [ r t e t e o d t n = ] 1 j e 1 = { = n f n e l ] t = = t r = f n < e u t i - { ( = a [ n < r r s t i & _ l l r n u P r 1 s & 0 s e o - r e o u P n e n o o f s e { o r : t 1 o a t s i - t l O t g [ & { s r O h I l 1 & { e d r t n e ] e d t n i r e ] ( r , = < n ( _ = , A l r l 0 e i r e n ) a n { y : - ( n I 1 [ n i t { . ) . . j ] ) B , o o j l - { i ) 算法思想：通过举例子分析，寻找规律，先判断根结点的整颗树是否满足二叉搜索树左小右大的规律，再判断各个子树是否同样满足这种规律。子问题和问题本身是等价的，所以使用递归即可实现子树的判断。 ...

题目描述：从上往下打印出二叉树的每个节点，同层节点从左至右打印。 i c } m l p a o s r s f } t u F n F o c o r v q w } u 2 p a u h n 3 r r e i d S i u l a o n q e e l p i } i } t l t u . e r f f i u T e a ! t i o t r u p q n n n n i e e p u n t e q e q o e : e e e ( w u w u n N n u w n R e R e o [ d e R e o u o u { d T ( . o w o e o e e r r i o R t . t . ( e o s t o ? a ? a _ e o E o . p . p N t m = t l p r p r o ) p ? e e i e o d t q . f n g n o e y u v t d h d t ? e a ( t ( : ] { u l ! n n e = e ! e T = . ? w = w r r ? n R R e [ e i o n o e T m 0 l o i o N r o ) t l t o e v { ? ? d e e . { . e N F l r ? o i e i ) d r f g e s t h { ] t ) t ( ( ) ) ) 算法思想：题目实际上就是二叉树的层序遍历，如上图，我们借助队列来存储节点来实现层序遍历的效果，具体操作： ...