import java.util.Arrays; /** * 最早是在陈利人老师的微博看到这道题: * #面试题#An array with n elements which is K most sorted,就是每个element的初始位置和它最终的排序后的位置的距离不超过常数K * 设计一个排序算法。It should be faster than O(n*lgn)。 * * 英文原题是: * Given an array of n elements, where each element is at most k away from its targ ... http://zhedahht.blog.163.com/blog/static/254111742007376431815/ http://blog.csdn.net/yysdsyl/article/details/4226630 import java.util.ArrayList; import java.util.List; public class LongestCommonSubsequence { /** * Q 56 最长公共子序列 * 如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。 ... public class DeleteNode_O1_Time { /** * Q 60 在O(1)时间删除链表结点 * 给定链表的头指针和一个结点指针(!!),在O(1)时间删除该结点 * * Assume the list is: * head->...->nodeToDelete->mNode->nNode->...->tail * you have already the point of 'nodeToDelete' in hand.So what you need to do is: * ... import java.util.ArrayList; import java.util.List; import java.util.Stack; /* * Q 57 用两个栈实现队列 */ public class QueueImplementByTwoStacks { private Stack<Integer> stack1; private Stack<Integer> stack2; QueueImplementByTwoStacks(){ stack1=new Stack<Integer&g ... public class LeftRotateString { /** * Q 26 左旋转字符串 * 题目:定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。 * 如把字符串abcdef左旋转2位得到字符串cdefab。 * 请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。 */ public static void main(String[] args) { String data = 'abcdef'; String re = leftRotate ... import java.util.Stack; public class ReverseStackRecursive { /** * Q 66.颠倒栈。 * 题目:用递归颠倒一个栈。例如输入栈{1,2,3,4,5},1在栈顶。 * 颠倒之后的栈为{5,4,3,2,1},5处在栈顶。 *1. Pop the top element *2. Reverse the remaining stack *3. Add the top element to the bottom of the remaining stack */ public ... import java.util.Arrays; import java.util.Random; import ljn.help.Helper; public class OddBeforeEven { /** * Q 54 调整数组顺序使奇数位于偶数前面 * 输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶? ... public class DeleteSpecificChars { /** * Q 63 在字符串中删除特定的字符 * 输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。 * 例如,输入”They are students.”和”aeiou”,则删除之后的第一个字符串变成”Thy r stdnts.” */ public static void main(String[] args) { String strSource='They are students'; String strDelete=' ... package com.ljn.base; import java.util.Arrays; import java.util.Random; public class ContinuousPoker { /** * Q67 扑克牌的顺子 从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。 * 2-10为数字本身,A为1,J为11,Q?? ... import java.util.Arrays; import java.util.Comparator; public class MinNumFromIntArray { /** * Q68输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。 * 例如输入数组{32, 321},则输出这两个能排成的最小数字32132。请给出解决问题的算法,并证明该算法。 */ public static void main(String[] args) { int[][] val={ {32,321},//32132 ... public class MinOfShiftedArray { /** * Q69 旋转数组的最小元素 * 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。 * 例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。 */ public static void main(String[] args) { int[][] a={ {1,2,3,4,5}, {2,3,4,5,1}, {3,4,5,1 ... public class ProbabilityOfDice { /** * Q67 n个骰子的点数 * 把n个骰子扔在地上,所有骰子朝上一面的点数之和为S。输入n,打印出S的所有可能的值出现的概率。 * 在以下求解过程中,我们把骰子看作是有序的。 * 例如当n=2时,我们认为(1,2)和(2,1)是两种不同的情况 */ private static int MAX=6; public static void main(String[] args) { int n=2; printProbabilityOfDice(n);//so ... public class Power { /** *Q71-数值的整数次方 *实现函数double Power(double base, int exponent),求base的exponent次方。不需要考虑溢出。 */ private static boolean InvalidInput=false; public static void main(String[] args) { double result=power(3,15); System.out.println(result); } public static d ... public class LongestSymmtricalLength { /* * Q75题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。 * 比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。 */ public static void main(String[] args) { String[] strs={ 'google', 'elgoog', 'agollloge', ' ... import java.util.LinkedList; import java.util.List; import ljn.help.*; public class BTreeLowestParentOfTwoNodes { public static void main(String[] args) { /* * node data is stored in leverOrder.'0' represents null node. * e.g. * int[] data={1,8,7,9,2,0,0,0,0,4,7}; * the ... public class OcuppyMoreThanHalf { /** * Q74 数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字 * two solutions: * 1.O(n) * see <beauty of coding>--每次删除两个不同的数字,不改变数组的特性 * 2.O(nlogn) * 排序。中间那个元素就是所求 */ public static void main(String[] args) { int[] a={4,3,4,2,4,5,4,4}; int re ... public class FirstShowOnlyOnceElement { /**Q17.在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b * 1.int[] count:count[i]表示i对应字符出现的次数 * 2.将26个英文字母映射:a-z <--> 0-25 * 3.假设全部字母都是小写 */ public static void main(String[] args) { String str='abaccdeff'; int index=find(str); ... 思路来自:http://zhedahht.blog.163.com/blog/static/25411174201011445550396/ import ljn.help.*; public class HasSubtree { /**Q50. * 输入两棵二叉树A和B,判断树B是不是A的子结构。 例如,下图中的两棵树A和B,由于A中有一部分子树的结构和B是一样的,因此B就是A的子结构。 1 8 ... public class PrintMatrixClockwisely { /** * Q51.输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 例如:如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1, ... 思路来自:http://zhedahht.blog.163.com/blog/static/2541117420116135376632/ 写了个java版的 public class GreatestLeftRightDiff { /** * Q61.在数组中,数字减去它右边(注意是右边)的数字得到一个数对之差。 * 求所有数对之差的最大值。例如在数 ... public class MaxCatenate { /* * Q.37 有n 个长为m+1 的字符串,如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配,则两个字符串可以联接, * 问这n 个字符串最多可以连成一个多长的字符串,如果出现循环,则返回错误。 */ public static void main(String[] args){ String[] text = new String[]{ 'abcd', ... the idea is from:http://blog.csdn.net/zhanxinhang/article/details/6731134 public class MaxSubMatrix { /**see http://blog.csdn.net/zhanxinhang/article/details/6731134 * Q35 求一个矩阵中最大的二维矩阵 ( 元素和最大 ). 如 : 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0 中最大的是 : 4 5 5 3 three solutions: 1.brutalFind:calc ... import java.util.Arrays; public class MinSumASumB { /** * Q32.有两个序列a,b,大小都为n,序列元素的值任意整数,无序. * * 要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。 * 例如: * int[] a = {100,99,98,1,2,3}; * int[] b = {1, 2, 3, 4,5,40}; * * 求解思路: * 当前数组a和数组b的和之差为 A = sum(a) - sum(b) a的第i个 ... import java.util.ArrayList; import java.util.List; import java.util.Stack; public class CombinationToSum { /* 第21 题 2010 年中兴面试题 编程求解: 输入两个整数 n 和 m ,从数列 1 , 2 , 3.......n 中随意取几个数 , 使其和等于 m , 要求将其中所有的可能组合列出来 . * two solutions * permutation01:Recursion.easy to write and read-->p ... //use recursion public static void mirrorHelp1(Node node){ if(node==null)return; swapChild(node); mirrorHelp1(node.getLeft()); mirrorHelp1(node.getRight()); } //use no recursion but stack public static void mirrorHelp2(Node node){ if(node==null)return; Stack<Node> st ... two cursors. Make the first cursor go K steps first. /* * 第 13 题:题目:输入一个单向链表,输出该链表中倒数第 k 个节点 */ public void displayKthItemsBackWard(ListNode head,int k){ ListNode p1=head,p2=head; while(--k>0){ p1=p1.next; } while(p1.next!=null){ p1=p1.next; p2=p2.next; } Sy ... public class LinkListTest { /** * we deal with two main missions: * * A. * 1.we create two joined-List(both have no loop) * 2.whether list1 and list2 join * 3.print the joinPoint * * B. * 1.create loop in list1 by itself * 2.whether the list has loop * 3.pri ... public class UglyNumber { /** * 64.查找第N个丑数 具体思路可参考 [url] http://zhedahht.blog.163.com/blog/static/2541117420094245366965/[/url] * 题目:我们把只包含因子 2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。 */ public static void main(String[] args) { ... import java.util.Arrays; import java.util.Random; public class MinKElement { /** * 5.最小的K个元素 * I would like to use MaxHeap. * using QuickSort is also OK */ public static void main(String[] args) { MinKElement mke=new MinKElement(); int[] a={1,2,3,4,5,6,7,8}; int k=4 ... import java.util.ArrayList; import java.util.List; public class BSTreeToLinkedList { /* 把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=1 */ public static void main(String[] args) { BSTreeT ... |
|
来自: 昵称19774237 > 《待分类》