代皓 Blog

要么庸俗要么孤独.

二进制中1的个数

题目输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。方法一最容易想到的就是每次去判断二进制的最右边一位是不是1，然后右移一位，直到整个数的二进制变为0。那么要怎么判断最后一位是不是0呢，只需要和1进行与操作。这个方法对于整数直接有效，但是负数的话，因为符号位是1，右移的时候最高位会补1，那么这个数永远不会为0，无法退出，进入死循环，我们可以直接将负数变...

Posted by DH on August 8, 2017

二叉树的非递归和递归遍历

代码没什么可以说的，代码很简单。 // 递归前序遍历 public void preOrder1(TreeNode root){ if (root != null) { System.out.println(root.val); preOrder1(root.left); preOrder1(root.right); } } // 前序遍历非递归 ...

Posted by DH on August 8, 2017

排序算法之基数排序

基数排序

思想基数排序首先按照个位数的值进行装桶，个位数的相同的数装进一个桶，然后从第0个桶开始取，取到第9个桶，将数组重新装进数组，在按照这种方式对十位、百位，直到最高位进行操作。例子例子如下图所示：代码 package test; import java.util.Arrays; public class RadixSort { public static void...

Posted by DH on August 7, 2017

排序算法之快速排序

思想快速排序是排序算法中比较有名的一个，他的主要思想是，用一趟排序找到一个数，将数组分组两个部分，左边的部分都比这个数大，右边的部分都比这个数小。然后再分别对左右两边的数组进行此种操作，直到被分割的数组长度是1，整个数组就达到了有序。例子一般，我们选择数组的第一个数作为基准进行比较，左边的比这个数小，右边的比这个数大。例子，如下图所示，开始从右边扫描，直到一个数比基准数小...

Posted by DH on August 6, 2017

排序算法之堆排序

思想堆排序在排序算法中属于比较难的一个了，首先阐明一些概念。堆的实质是一颗完全二叉树，假如一颗二叉树的层数的h,那么这可二叉树的h-1层都是满二叉树。假如堆中的父节点的值<子节点的值，这个堆叫做小根堆假如堆中的父节点的值>子节点的值，这个堆交大根堆。而数组与堆的对应是顺序对应，堆就是顺序存储的二叉树，如下图所示：堆排序的主要步骤是; 将数组Array...

Posted by DH on August 6, 2017

排序算法之归并排序

思想归并排序的中心思想是分值。把两个已经排序的文件合并成一个更大的已排序的文件。算法包括两个部分，一个部分是拆分，将数组拆分成包含k个元素和n-k个元素的两个数组的过程。这个过程每一次都将数组折半拆分。另一部分是合并，将已排序的小数组合并成排序的大数组。下面看图就明白这个过程：例子如上图所示。分析时间复杂度：O(nlogn); 总时间=分解时间+解决问题...

Posted by DH on August 5, 2017

用两个栈实现队列

题目用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。分析栈的特点是“先进后出”，队列的特点是“先进先出”。在插入的时候，先将第一个元素压入栈的栈底，后面的元素依次压入栈顶，最后一个压入的元素在栈顶。而出栈的时候，必须从栈顶开始出栈，也就是最先入栈的元素最后出栈。这时，我们将所有元素{1，2，3，4，5}压入栈1，从栈底到栈顶...

Posted by DH on August 4, 2017

替换空格

题目请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。分析最容易想到的就是从头开始遍历字符串，遇到空格，就把空格后面的内容后移两位，并插入%20.由于会重复的移动，所以时间复杂度是O(n2) 如果我们从后面开始遍历呢？先计算出字符串中的空格，知道最终字符串的长度，然后...

Posted by DH on August 4, 2017

旋转数组的最小数字

题目把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。分析分析这个题目，其实不用看什么数组的旋转的描述，感觉上没有多少意义，实际要做的就是对这个...

Posted by DH on August 4, 2017

斐波拉切数列

题目大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39 分析斐波拉切数列简单的说就是0，1，1，2，3，5，8……，简单的说就是后一项是前两项的和，很容易想到使用递归。既简单又方便，几行代码就搞定了。于是有了如下的代码： public class Solution { public int Fibonacci(int...

Posted by DH on August 4, 2017