
剑指offer
井底的笨鸟
Stay hungry,stay foolish.
展开
-
链表——删除排序链表的重复结点(一个都不保留)
题目:删除排序链表中的所有重复结点,只留下没有重复过的那些结点。For example,Given1->2->3->3->4->4->5, return1->2->5.Given1->1->1->2->3, return2->3.思路:设置三个指针 ppre,pcur,pnext,pcur始终指向链表中一个数字第一次出现....转载 2016-05-09 15:36:22 · 660 阅读 · 0 评论 -
回溯法——八皇后问题 n-queens
题目描述一个8*8的棋盘上有八个皇后,使她们互相不能攻击(即两个皇后不能出现在同一行,同一列,或同一对角线上)。package TraceBack;public class 八皇后问题 { public static void main(String[] args) { // TODO 自动生成的方法存根 int []data原创 2016-05-28 21:09:04 · 503 阅读 · 0 评论 -
回溯法——正方体的八个顶点
题目描述:将1--8这八个整数放在正方体的八个顶点上,要求相对的两面上四个数之和相等。求所有放法。package TraceBack;public class 正方体的八个顶点 { public static void main(String[] args) { // TODO 自动生成的方法存根 int data[]={1,2,3,4,5,6,7,8}原创 2016-05-28 20:51:09 · 2880 阅读 · 0 评论 -
String、动态规划——正则表达式匹配
题目描述:请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配。直接贴代码!public class Solution { public b原创 2016-05-12 17:42:34 · 1793 阅读 · 0 评论 -
树——二叉搜索树化为双向链表
题目描述输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。public class Solution { public TreeNode Convert(TreeNode root) { if(root == null) return null; if(r原创 2016-06-14 15:00:47 · 337 阅读 · 0 评论 -
链表——复杂链表的复制
题目:在复杂链表中,每个节点除了一个next引用外还有一个random引用指向链表中的任意结点或者null,实现函数复制该链表。方法一:HashMap存储结点对信息第一步:(遍历原链表一次)不考虑random引用,将原链表作为单链表进行复制,并用HashMap将结点的配对信息存储;第二步:(第二次遍历原链表)设置复制链表上的每个random结点;总的时间复杂度为O(N)原创 2016-05-09 12:36:06 · 763 阅读 · 0 评论 -
链表——反转链表
了解反转链表的通法:遍历一遍链表,利用一个辅助指针ne,存储遍历过程中当前指针cur指向的下一个元素,然后将当前节点元素的指针反转后,利用已经存储的指针往后面继续遍历。源代码如下: public ListNode reverseList(ListNode head) { if(head==null) return head; Lis原创 2016-05-09 22:04:39 · 444 阅读 · 0 评论 -
滑动窗口的最大值
题目描述给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,原创 2016-06-16 17:15:47 · 491 阅读 · 0 评论 -
归并排序应用——数组中的逆序对 and 计算数组的小和
题目描述在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。public class Solution { public int InversePairs(int [] array) { if(array == null||array.length < 2) retu原创 2016-06-16 16:10:50 · 445 阅读 · 0 评论 -
single-number、single-number2,数组中只出现一次的数字
题目描述:single-number1一个数组中除了一个数字外,其余数字均出现两次,找出只出现一次的数字。要求线性复杂度方法:两个相同的数字异或得0,一个数字和0异或结果是它本身。public class Solution { public int singleNumber(int[] nums) { int num=0; fo...原创 2016-05-27 20:17:00 · 1801 阅读 · 0 评论 -
链表——判断链表是否有环以及环的入口结点 两个链表的节点
思路:首先,判断链表是否有环,方法为快慢指针(prear每次走两步,pfront每次走一步),若有环则总有相交的时候;其次,找出环包含的节点数;最后,再次遍历链表,找出环的入口结点;代码如下:/*** Definition for singly-linked list.* class ListNode {* int val;* Li...原创 2016-05-09 13:01:30 · 484 阅读 · 0 评论 -
位运算——二进制中1的个数相关题目
题目描述输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。如果一个整数不为0,那么这个整数至少有一位是1。如果我们把这个整数减1,那么原来处在整数最右边的1就会变为0,原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。举个例子:一个二进制数1100,从右边数起第三位是处于最右边的一个1。减去1后,第三位变成0,原创 2016-06-12 20:47:16 · 401 阅读 · 0 评论 -
String——反转单词顺序VS左旋字符串
题目一:反转单词顺序String.split(String regex)根据给定正则表达式的匹配拆分此字符串。 该方法的作用就像是使用给定的表达式和限制参数 0 来调用两参数 split 方法。因此,所得数组中不包括结尾空字符串。例如,字符串 "boo:and:foo" 使用这些表达式可生成以下结果: Regex结果:{ "boo", "and", "foo"原创 2016-05-12 16:16:13 · 685 阅读 · 0 评论 -
数组——蛇形矩阵、螺旋矩阵
????????????????????start,start???????????????????start*2import java.util.*;public class Solution { public ArrayList spiralOrder(int[][] matrix) { ArrayList array=new ArrayList();原创 2016-05-17 13:23:40 · 965 阅读 · 0 评论 -
和为s的连续正整数数列 and 未排序正数数组中和为s的最长子数组长度
题目一:输入一个正整数s,打印出所有和为s的连续正整数序列(至少有两个数)。两个下标small和big,可以看出small递增到s/2即可。import java.util.ArrayList;public class Solution { public ArrayList > FindContinuousSequence(int sum) { Arra原创 2016-07-23 22:20:51 · 498 阅读 · 0 评论 -
二分查找——旋转数组的最小数字
题目描述把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。import java.util.ArrayList;public class Solution {原创 2016-07-22 09:44:22 · 787 阅读 · 0 评论 -
二分查找——数字在排序数组中出现的次数
两次二分查找找到该数字的左右边界。public class Solution { public int GetNumberOfK(int [] array , int k) { if(array == null||array.length == 0) return 0; //找左边界 int left=0;原创 2016-06-14 14:31:20 · 784 阅读 · 0 评论 -
树——二叉树中和为某一值的路径and求二叉树深度
题目:path-sum例如:给定二叉树头结点root 和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1return true, 因为原创 2016-05-10 20:12:53 · 313 阅读 · 0 评论 -
BFS、DFS——机器人的运动范围
题目描述地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?public class Sol原创 2016-05-29 14:20:07 · 3856 阅读 · 0 评论 -
DFS——矩阵中的路径
题目描述请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符原创 2016-05-29 13:48:05 · 883 阅读 · 0 评论 -
把字符串转换成整数
题目描述将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。考虑首位有正负号和字符串中可能有错误字符的可能。public int StrToInt(String str) { if(str == null||str.length() == 0) return 0; char[] ch=str.toCharArray原创 2016-06-15 14:18:09 · 365 阅读 · 0 评论 -
树——二叉树中序遍历的下一个节点
题目描述给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。分析二叉树的下一个节点,一共有以下情况: 1.二叉树为空,则返回空; 2.节点右孩子存在,则设置一个指针从该节点的右孩子出发,一直沿着指向左子结点的指针找到的叶子节点即为下一个节点; 3.节点不是根节点。如果该节点是其父节点的左孩子,原创 2016-06-15 13:57:57 · 1705 阅读 · 0 评论 -
数组——二维数组的查找
题目:在一个二维数组上,每一行从左到右递增,每一列从上到下递增,高效的查找二维数组中是否有所要查找的数字target。For example,Consider the following matrix:[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]Given target =3, ret原创 2016-05-16 20:47:14 · 283 阅读 · 0 评论 -
基于partition——最小的K个数、数组中出现次数超过一半的数字
题目一:最小的K个数解法一:基于partition,O(N)的算法,并且会修改输入的数组,不适用于海量数据,因为数据可能不能一次性读入内存; public void swap(int[] data,int i,int j) { int temp=data[i]; data[i]=data[j]; data[j]=temp; } public int ...原创 2016-05-16 16:16:12 · 528 阅读 · 0 评论 -
String——表示数值的字符串
题目描述请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。方法一:利用检测异常的try,catch语句public boolean isNumeric(char[] str) {原创 2016-05-12 16:34:14 · 800 阅读 · 1 评论 -
String——第一个只出现一次的字符
方法:判断字符串字频,用hashmap public int FirstNotRepeatingChar(String str) { if(str == null||str.length()==0) return -1; int []count=new int[256]; for(int i=0;i<str.length()原创 2016-05-12 16:01:06 · 532 阅读 · 0 评论 -
树——对称的二叉树
题目:判断一棵二叉树是否对称判断两棵二叉树是否相同:public boolean isSameTree(TreeNode p, TreeNode q) { if(p == null && q == null) return true; if(p == null || q == null) return原创 2016-05-11 16:34:55 · 297 阅读 · 0 评论 -
树——二叉树的镜像
题目:输入一个二叉树,输出它的镜像; 方法:交换该二叉树左右结点,再递归其左右子树即可。代码如下:public class Solution { public void Mirror(TreeNode root) { if(root==null) return ; if(root.left==null&&root.原创 2016-05-11 16:31:49 · 293 阅读 · 0 评论 -
树——按“之”字形打印二叉树(层序遍历变型)
题目描述请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。思路:用两个stack依次保存相邻的两层。代码如下:*public class TreeNode { int val = 0; TreeNode left = null; TreeNode righ原创 2016-05-11 10:41:33 · 1530 阅读 · 0 评论 -
树——由中序和前序,中序和后序序列重建二叉树
题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。一、由前序和中序重构代码如下:/** * Definition for binary tree * public class TreeNode原创 2016-05-11 14:58:12 · 697 阅读 · 0 评论 -
回溯法——字符串的全排列
题目:输出一个字符串的全排列,且重复的排列不重复输出。注:经典回溯法题目,八皇后问题,正方体的八个顶点,电话号码对应英文单词等都是一种算法;代码如下:public class TraceBack { public static void main(String []argc) { String str="abbc"; char[...原创 2016-05-09 09:29:05 · 1482 阅读 · 0 评论 -
链表——(循环和递归)合并两个排序链表
题目:合并两个递增排序链表,使新链表仍然按照递增排序。方法一:基于递归的方法,链表first和链表second各有m和n个结点,新链表的头结点为两个链表中头结点较小的一个,当找到该头结点时(假设为first的头结点),仍需对first的m-1个结点和second的n个结点合并。可以看出,子问题和原问题相同,因此可以利用递归解决。代码如下:/** * Definit原创 2016-05-09 16:45:30 · 3887 阅读 · 0 评论 -
String——替换空格
方法一:使用String的replaceAll方法。public class Solution { public String replaceSpace(StringBuffer str) { String string=str.toString(); return string.replaceAll(" ","%20"); }}方原创 2016-05-12 15:39:50 · 670 阅读 · 0 评论 -
调整数组顺序使奇数位于偶数前面
题目描述输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。若题目没有要求相对位置不变,则设置两个指针first和second,当first<second时分别从前和后查找奇数和偶数,交换即可。但这里要求相对奇数偶数间顺序不能改变。方法如下: public v...原创 2016-06-15 10:40:24 · 344 阅读 · 0 评论 -
约瑟夫环问题
题目描述0,1,2------n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字,求剩下的最后一个数字。解法一:用链表模拟圆环import java.util.*;public class Solution { public int LastRemaining_Solution(int n, int m) { if(n<1||原创 2016-06-14 22:41:41 · 327 阅读 · 0 评论 -
丑数
题目描述把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。多读两边代码就懂了。public class Solution { public int GetUglyNumber_Solution(int index) { if(in原创 2016-06-14 21:10:25 · 306 阅读 · 0 评论 -
把数组排成最小的数
题目描述输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。解题思路: * 先将整型数组转换成String数组,然后将String数组排序,最后将排好序的字符串数组拼接出来。关键就是制定排序规则。 * 排序规则如下: * 若ab > ba 则 a >原创 2016-06-14 15:05:48 · 284 阅读 · 0 评论 -
栈的压入弹出序列
题目描述输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。【思路】借用一个辅助的栈,遍历压栈顺序,先讲第一个放入栈中,这里是1,然后判断栈顶元素是不是出栈顺序的第一个元素,这原创 2016-06-14 14:27:36 · 274 阅读 · 0 评论 -
1-n整数中1出现的次数
题目描述求1到n的整数中,各个位置上的1出现的次数。主要思路:设定整数点(如1、10、100等等)作为位置点i(对应n的各位、十位、百位等等),分别对每个数位上有多少包含1的点进行分析 根据设定的整数位置,对n进行分割,分为两部分,高位n/i,低位n%i 当i表示百位,且百位对应的数>=2,如n=31456,i=100,则a=314,b=56,此时百位为1的次数有a/10+1=32原创 2016-06-14 14:24:27 · 493 阅读 · 0 评论 -
树——判断是否为平衡二叉树
题目:balanced-binary-tree判断一棵二叉树是否为平衡二叉树,即二叉树的每个结点的两棵子树的高度差不大于一。后序遍历二叉树,每遍历一个节点判断时候满足平衡条件,并存储该节点深度。/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * ...原创 2016-05-10 20:52:17 · 369 阅读 · 0 评论