代皓 Blog

要么庸俗要么孤独.

包含min函数的栈

题目定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。分析栈的特点是先进后出，所以要求min的时间复杂度是1，就必须将最小的元素时刻放在栈顶，那么我们考虑每次压栈的时候，将当前要压栈的元素和栈中所有元素进行比较，最小的放在栈顶。这样是可以满足min函数的要求，但是这个数据结构就不是栈了，因为不能保证先进后出。那么我们考虑在栈中设置一个变量保存最小...

Posted by DH on May 3, 2017

树的子结构—递归

题目输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）分析（1）在tree1中寻找tree2的根节点，如果找到了，就接着往下匹配左右节点，如果没有找到，就直接返回false，表示匹配失败；（2）加入tree1的某个节点和tree2的根节点相等，但是左右子树并不相同，并不能说明tree2就不是tree1的子结构，应该继续往下寻找；...

Posted by DH on May 2, 2017

操作给定的二叉树，将其变换为源二叉树的镜像。

题目操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 ...

Posted by DH on May 2, 2017

合并两个排序列表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

题目输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。分析如果我们按照一般的思路去思考，不用递归的话，就是从两个链表的开头往后比较，数值小的放到新的链表中，然后又从链表的开头进行比较。这样知道其中某一个链表的所有元素被遍历完，另一个没有被遍历完的链表的剩余部分一定是有序的，并且比新的链表的中的节点的值大，所以直接接在新的链表...

Posted by DH on April 28, 2017

链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点

题目输入一个链表，输出该链表中倒数第k个结点。分析链表采用非连续地址存储，所以节点中都会存储下一个节点的信息，有的链表还会同时存储上一个节点和下一个节点的信息。因此链表相比于数组来说，输出指定位置的元素并不那么容易。需要进行遍历操作，这是无法逃脱的。这个题，我们首先要考虑：（1）链表为空时，直接返回null；（2）k的值<1的时候，也不正确；（3）...

Posted by DH on April 27, 2017

反转链表

输入一个链表，反转链表后，输出链表的所有元素。

题目输入一个链表，反转链表后，输出链表的所有元素。分析首先这个题要看清楚，是反转链表再进行输出，而不是将链表反向输出。所以第一件要做的就是将链表反转。假如首先我们只考虑两个节点的反转，只需要将head.next指向之前的节点就行了。但是假如有三个节点，加入第二个是当前的head的节点，我们将head.next指向之前的节点，前两个节点的顺序交换了，但是第三个节点和第...

Posted by DH on April 27, 2017

iOS 使用AFNetworking传递复杂的POST参数（数组、键值对）

需求项目要进行一个购物车价格的计算，需要从客户端传递用户购物车中商品的信息，包括ID和数量，同时涉及到优惠码。一般我们用AFNetworking传递参数都是使用如下代码： // 取得管理者 AFHTTPRequestOperationManager *manager = [AFHTTPRequestOperationManager manager]; // 取...

Posted by DH on April 27, 2017

调整数组顺序使奇数位于偶数前面

题目输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。分析有两种考虑方法，一种是空间换时间，一种是时间换空间。空间换时间空间换时间。思路是，遍历原数组，遇到是奇数的就加入到新的数组中，并且要设置一个标志位一直指向新数组中待插入的那一位。然后，...

Posted by DH on April 26, 2017