代皓 Blog

要么庸俗要么孤独.

从头到尾打印链表

题目输入一个链表，从尾到头打印链表每个节点的值分析最容易想到的就是进行链表的翻转，但是这样会改变原始的输入，可能不满足要求。链表从后先输出，就是先进后出的思想，那么读取一个入栈一个，最后依次弹出，就可以满足要求。代码 /** * public class ListNode { * int val; * ListNode next...

Posted by DH on August 4, 2017

二维数组中的查找

题目在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。分析直接举例：查找7的过程：总结三句话：从右往左，从上往下，先列后行。从图中我们可以看。首选用7和9比较，就排除了最后一列，接着7和8比较，排除倒数第二列，7和2比较，说明7只可能出...

Posted by DH on August 3, 2017

iOS的内存管理机制

概述在iOS开发中主要有量类型的对象，一种是值类型（int、float、strict等基本数据类型），一种就是OC对象，其中值类型是存储在栈上，操作系统会自己管理， OC对象类型存在堆上，是需要我们进行管理的。 iOS的内存管理也就是引用计数。每一个OC对象内部都有一个整数（4个字节）来存储该对象被引用的次数，称之为引用计数器。如果引用计数器是0，该对象被回收，如果不是0，不回收。...

Posted by DH on August 3, 2017

OC对象和Core Foundation对象之间的转换

OC对象和Core Foundation对象 Core Foundation对象主要用于C语言编写的Core Foundation框架中，他是一组C语言的接口，主要为iOS应用提供基本的数据管理和服务功能。主要管理的数据包括：（1）数组集合等群体数据（2）程序包（3）字符串（4）时间日期（5）原始数据块提供的服务主要包括：（1）偏好管理（2）线程和RunLo...

Posted by DH on August 2, 2017

详解递归时栈的调用

递归与栈之前很多算法都是用递归解决的，也知道递归的是对栈的调用，但是并没有仔细的了解具体是怎么工作的，乘着上一篇文章也用了递归，就根据上一篇文章中的算法，详细的看看栈中是怎么变化的，因为是自己画图，有不严谨的地方，请联系我，感谢！函数调用，栈中要做什么？函数调用是指一个函数在函数体内调用另一个函数，那么这个过程中，会做些什么呢？（1）运行时系统，将调用者的所有实参和...

Posted by DH on August 1, 2017

序列化二叉树

题目请实现两个函数，分别用来序列化和反序列化二叉树分析要确定一颗二叉树，可以用前序遍历和中序遍历唯一确定，因此可以把一颗二叉树序列化成前序和中序遍历，反序列化时，根据前序和中序重构。但是，这有两个缺点：（1）二叉树不能有数值相同的节点；（2）必须将二叉树全部读入内存才能进行反序列化。我们可以从根节点开始遍历，反序列化在根节点读出来之前就可以开始。这样就不用...

Posted by DH on August 1, 2017

二叉搜索树的第k个结点

题目给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。分析二叉搜索树（二叉排序树）的满足：（1）左子树上的节点小于根节点，右子树的节点大于根节点，他的左右子树也分别是二叉排序树。这颗二叉搜索树的中序遍历是： 2，3，4，5，6，7 因此，排好序之后，我们想输出第几...

Posted by DH on August 1, 2017

按之字形顺序打印二叉树

题目请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。分析如图的二叉树：按照题目的要求输出的结果是： 1 3 2 4 5 6 7 15 14 13 12 11 10 9 8 可以发现奇数行是按照从左往右的顺序输出的，偶数行是按照...

Posted by DH on July 27, 2017

把二叉树打印成多行

题目从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。分析如下图示，输出的结果应该是： 8 6 10 5 7 9 11 这个和层序遍历不一样的就是，我们需要记录这个数到底来自哪一行。我们可以使用两个队列。第一个队列记录当前正在被遍历的这一行的节点，遍历一个节点时，将他的左右孩子（也就是下一层）存在第二个队列中，因...

Posted by DH on July 27, 2017

对称的二叉树

题目请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的分析首先看下图：所谓对称二叉树，就是二叉树和他的镜像完全一样，如图1 我们看看图一的前序遍历（根-左-右）是8657675，而如果采用对称前序遍历算法，也就是根右左，得到的结果也是8657675 但是第二颗树，6和9不一样第三棵树，遍历结果一样，...

Posted by DH on July 26, 2017