代皓 Blog

要么庸俗要么孤独.

iOS中内存分配

概述在iOS的内存中，主要包括如下的几个部分：代码区、常量区、全局静态区（已初始化全局静态数据和未初始化全局静态区）、堆区、栈区。他们在内存中的大致分布如下：各分区存储的数据类型代码区代码区顾名思义就是存储代码的，这个区域主要存储的是代码的二进制文件，为了防止程序被篡改，这一部分只允许读不允许写。而这个区域中包括了操作代码和备操作的对象（对象的地址）。如果是立即数，...

Posted by DH on August 11, 2017

8种排序算法的比较

概述之前把8种排序算法复习了一遍，来进行一个总结。内容如下图：时间复杂度直接插入排序：平均情况是O(n2),最好情况是O(n),当数组是正序时，只需要与最后一个关键码进行比较，不需要移动，最坏情况是倒叙，要比较n-1次还要移动，为O(n2); 希尔排序：平均情况是O(n1.3)，我也不知道这是怎么算出来的，在网上找了一下证明，数学公式推倒，就没深入了，有时间再研究一下。最好...

Posted by DH on August 11, 2017

链表中倒数第k个结点

题目输入一个链表，输出该链表中倒数第k个结点。分析一我最开始的想法就是使用栈，先把全部的节点压入栈内，那么最后一个节点一定在栈顶，那么我弹出K个就好，最后一个就是结果。这个方法是可以通过牛客网的测试的，但是感觉利用了额外的空间，不一定是最好的。代码一 // 方法一 public ListNode FindKthToTail1(ListNode head,int...

Posted by DH on August 10, 2017

反转链表

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

Posted by DH on August 10, 2017

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

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

Posted by DH on August 9, 2017

数值的整数次方

题目给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。方法一最容易想到的就是循环，每次循环的时候乘以底数。这个过程很简单，要注意的是底数为0的时候，直接返回0，底数为0同时指数为负数的时候，会出现错误，没有意义，可以返回0或者-1.当底数不为0，指数小于0的时候，可以先去指数的绝对值，按照指数为正数的方法去计算...

Posted by DH on August 9, 2017

iOS多线程、线程安全和线程间通信

多线程的概念一个运行着的程序叫做一个进程，一个进程至少包含一个线程，线程是程序的执行流。在iOS中程序一旦启动就有一个线程一直运行，这个线程叫主线程。主线程是其他所有线程的父线程。系统中的所有县城共享进程的地址空间，所以能够自由的访问进程的空间变量。多线程访问的变量称之为“共享变量”。共享变量主要是“全局变量”和“静态变量”。各个线程都有自己的栈，线程不能访问其他线程的的栈内变...

Posted by DH on August 9, 2017

跳台阶

题目一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析才开始感觉有点懵，就看一下规律，当台阶只有一级台阶，f(1)=1，当台阶有2级，f(2)=2，当台阶有3级，f(3) = 3,f(4) = 5,依次类推，发现是个斐波拉切数列。那么，为什么会是这样呢？假设要跳到6，有两种，一种是从5跳到5，这个时候，跳到6的方式就是f(5)，另...

Posted by DH on August 8, 2017

矩形覆盖

题目我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？分析这个题的比较难以下手，首先找一下规律，n=1，只有一种，n=2，是一个正方形，可以讲小矩形横着放或者竖着放：当n=3，假如第三个小矩形恰好能够竖直放下，这个时候，就相当于只考虑第一个和第二个小矩形怎么放，也就是怎么用小矩形去填充一个正...

Posted by DH on August 8, 2017

变态跳台阶

题目一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析最后一节台阶是必须上的，之前的n-1个台阶每一个都有两种情况，上或者不上，因此从第一个开始，2*2……2,共有n-1个2相乘。 Java中实现2的n-1次方，要用到库函数math.pow(2,n)。加入不允许用库函数，就要用位移运算，而位移运算的效率还要...

Posted by DH on August 8, 2017