代皓 Blog

要么庸俗要么孤独.

二叉树的下一个结点

题目给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。分析借用网上的一个图片：我们按照当前节点是否含有右子树进行分类分析： -思考一如果当前节点有右子树，那么按照中序遍历“左-根-右”的顺序，我们只要找到当前节点右子树的最左节点就是下一个节点。 -思考二 ...

Posted by DH on July 26, 2017

链表中环的入口结点

题目一个链表中包含环，请找出该链表的环的入口结点。分析一这个题目应该有蛮多解法的。第一种是利用hashset,那么hashset有什么特点呢？说道hashset第一反应就应该是不能插入重复的元素。因此，我们从头开始插入，假如有环的话，插入就会失败，这个时候就是第一个重复的元素，也就是环的开头。代码 /* public class ListNode { ...

Posted by DH on July 25, 2017

表示数值的字符串

题目请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。分析网上有很多自己去一步步匹配的，但是我觉得既然Java提供了正则表达式匹配，那么写好正则表达式就好了。那么我们一步...

Posted by DH on July 25, 2017

字符流中第一个不重复的字符

题目请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。输出描述如果当前字符流没有存在出现一次的字符，返回#字符分析最容易想到的就是用hashmap，key是对应的char,value是出现的次数，每次读...

Posted by DH on July 25, 2017

删除链表中重复的结点

– layout: post title: 删除链表中重复的结点 subtitle: date: 2017-07-25 author: DH header-img: img/post-bg-alibaba.jpg catalog: true tags: - 算法 - 剑指offer — 题目在一个排序的链表中，存在重复的结点...

Posted by 代皓 Blog on July 25, 2017

构建乘积数组

题目给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]A[i+1]…A[n-1]。不能使用除法。分析由于不能使用除法，只能够使用乘法。 B[i]就是下图每一行的乘积。先计算下三角的乘积，再计算上三角。代码 import java.util.ArrayList; public ...

Posted by DH on July 24, 2017

数组中重复的数字

题目在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。分析（1）直接想到的可以使用hashmap，遍历一次，时间复杂度是O(n)，空间复杂度是O(n); ...

Posted by DH on July 24, 2017

把字符串转换成整数

题目将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0 分析其实这个不涉及到算法，主要是对输入的合法性的检查和转化过程中，是否越界或者溢出。具体来说，有如下要求：（1）输入是否为null （2）输入字符串的长度是够为0 （3）输入的字符串的第一个字符是-、+或者没有正负号（4）Java的正数的最大值...

Posted by DH on July 23, 2017

不用加减乘除做加法

题目写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。分析不能使用加减乘除，就只剩下移位操作可以使用了。十进制的5+7的计算方式：（1）相加各数位的值，不进行进位，结果是2；（2）看是否有进位，这一步的到10，加入是0，就没有进位；（3）2+10 = 12 扩展到二进制： 5的二进制101；7的二进制111. （1）不进位...

Posted by DH on July 23, 2017

求1+2+3+...+n

题目求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。分析不能使用乘除也还好，可以用加减，效果一样的。但是不能使用循环和判断就比较蛋疼了。要解决这个题必须要使用判断语句，不然根本不知道从哪里跳出，位移运算，也找不到规律，在运算符中，还能做判断的也就是”或” 还有 &&...

Posted by DH on July 21, 2017