bylijinnan
- 浏览: 787555 次
- 性别:
- 来自: 深圳
-
最新评论
-
萨琳娜啊：
Java读源码之Netty深入剖析网盘地址：https://p ...
Netty源码学习-FileRegion -
飞天奔月：
写得有趣 ^_^
那一年你定义了一个接口 -
GoldRoger：
第二个方法很好
java-判断一个自然数是否是某个数的平方。当然不能使用开方运算 -
bylijinnan：
<script>alert("close ...
自己动手实现Java Validation -
paul920531：
39行有个bug:"int j=new Random ...
java-蓄水池抽样-要求从N个元素中随机的抽取k个元素，其中N无法确定
文章列表
public class ReverseWords {
/**
* 题目：颠倒一个句子中的词的顺序。比如： I am a student颠倒后变成：student a am I.词以空格分隔。
* 要求：
* 1.实现速度最快,移动最少
* 2.不能使用String的方法如split,indexOf等等。
* 解答：两次翻转。
*/
public static void main(String[] args) {
String str=" ^busy living, or busy dying! $ "; ...
import java.util.LinkedList;
public class CreateBSTfromSortedArray {
/**
* 题目:给定一个排序数组，如何构造一个二叉排序树
* 递归
*/
public static void main(String[] args) {
int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
CreateBSTfromSortedArray bst = new CreateBSTfromSortedArray();
Node root = bst ...
java-谷歌面试题-设计方便提取中数的数据结构
- 博客分类：
- 面试题
网上找了一下这道题的解答，但都是提供思路，没有提供具体实现。其中使用大小堆这个思路看似简单，但实现起来要考虑很多。
以下分别用排序数组和大小堆来实现。
使用大小堆：
import java.util.Arrays;
public class MedianInHeap {
/**
* 题目：设计方便提取中数的数据结构
* 设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。
* 1. 使用排序数组存储。
* 插入数字时，在O(logn)时间内找到要插入的位置，在O(n)时间里移动元素并将新数字插入到合适的位置。
* 获得 ...
这道题的具体思路请参看 何海涛的微博：http://weibo.com/zhedahht
import java.math.BigInteger;
import java.util.Arrays;
public class CreateBFromATencent {
/**
* 题目：输入一个数组A[1,2,...n]，求输入B，使得数组B中的第i个数字B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[N-1].
* 要求
* 1.不得使用除法
* 2.不得新建变量--how?
* see http://weibo.c ...
java-给定两个已排序序列，找出共同的元素。
- 博客分类：
- 面试题
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CommonItemInTwoSortedArray {
/**
* 题目：给定两个已排序序列，找出共同的元素。
* 1.定义两个指针分别指向序列的开始。
* 如果指向的两个元素相等，则找到一个相同的元素；如果不等，则将指向较小元素的指针向前移动。
* 重复执行上面的步骤，直到有一个指针指向序列尾端。
* 2.如果数组大小差得很多，就遍历小的，然后在大的里二分查找
...
public class SearchInShiftedArray {
/**
* 题目：给定一个固定长度的数组，将递增整数序列写入这个数组。当写到数组尾部时，返回数组开始重新写，并覆盖先前写过的数。
* 请在这个特殊数组中找出给定的整数。
* 解答：
* 其实就是“旋转数组”。旋转数组的最小元素见http://bylijinnan.iteye.com/blog/1431531
* 采用类似二分查找的策略。首先比较a[0]和a[N/2]，如果a[0] < a[N/2]，则说明a[0,1,...,N/2]为递增子序列，否则另一部分是递增子序列。
...
蓄水池抽样（Reservoir Sampling）
相关证明可看这个链接：http://www.cnblogs.com/HappyAngel/archive/2011/02/07/1949762.html
以下为上面这个链接的两个截图：
import java.util.Arrays;
import java.util.Random;
public class ReservoirSampling {
/**
* 题目：给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。
* 如何才能从这个无穷尽的流中随机的选取100 ...
import java.util.ArrayList;
import java.util.List;
public class KickOutBadGuys {
/**
* 题目：13个坏人和13个好人站成一圈，数到7就从圈里面踢出一个来，要求把所有坏人都给踢出来，所有好人都留在圈里。请找出初始时坏人站的位置。
* Maybe you can find out the mathematical rule behind the question.
* But we try to figure it out in Java.
* It's easy t ...
public class SquareRoot {
/**
* 题目：判断一个自然数是否是某个数的平方。当然不能使用开方运算
* 方法1.squareRoot0 二分查找
* 方法2.squareRoot1
* 考虑等差数列 1 3 5 7 9...发现
* 1^2=1
* 2^2=1+3
* 3^2=1+3+5
* ...
* 因此，N-1-3-5...若刚好可减至0，则N是某正整数的平方
*/
public static void main(String[] args) {
for(int i=0; ...
BigIntegerAddition.add见http://bylijinnan.iteye.com/blog/1463337
public class FactorialInAddition {
/**
*题目：求100的阶乘-100！(即100*99*98*...*2*1)
*方法：用加法代替乘法，加法的加数用字符串表示
*/
public static void main(String[] args) {
for(int i=1;i<=100;i++){
System.out.println(factorial(i));
} ...
public class DeleteExtraSpace {
/**
* 题目：给定字符串，删除开始和结尾处的空格，并将中间的多个连续的空格合并成一个。
* 方法1.用已有的String类的trim和replaceAll方法
* 方法2.全部用正则表达式，这个我不熟
* 方法3.“重新发明轮子”，从头遍历一次
*/
public static void main(String[] args) {
String[] strs={
"",
" ",
"a&qu ...
public class MyDiv {
/**
* 题目：编程实现两个正整数的除法，当然不能用除法操作符。
* 方法1：除数不断乘以2，直到最接近被除数
* 方法2：二分查找
* 扩展题目：如何求出a%b的值，要求不能使用除法和求模运算！
* 解答：在上面求出商(假设为c)之后，a%b=a-(b*c);
*/
private static boolean INVALID_INPUT;
public static void main(String[] args) {
int x=24;
for(int y=1 ...
java实现两个大数相加，可能存在溢出。
- 博客分类：
- 面试题
import java.math.BigInteger;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class BigIntegerAddition {
/**
* 题目：java实现两个大数相加，可能存在溢出。
* 如123456789 + 987654321 返回 1111111110
* 1.直接用BigInteger
* 2.模拟手算加法，进位相加（暂时没有考虑负数的情况）
*/
public static void main(S ...
1024! 末尾有多少个0？
- 博客分类：
- 算法与数据结构
public class CountZerosInFactorial {
/**
* 题目：1024! 末尾有多少个0？
* 参看《编程之美》
* 解答：
末尾0的个数取决于乘法中因子2和5的个数。显然乘法中因子2的个数大于5的个数，所以我们只需统计因子5的个数。
是5的倍数的数有： 1024 / 5 = 204个
是25的倍数的数有：1024 / 25 = 40个
是125的倍数的数有：1024 / 125 = 8个
是625的倍数的数有：1024 / 625 = 1个
所以1024! 中总共有204+40+8+1=253 ...
在排序数组中，找出给定数字的出现次数
- 博客分类：
- 算法与数据结构
public class CountTimesInSortedArray {
/**
* 题目：在排序数组中，找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。
* 解法：使用二分查找的方法分别找出给定数字的开始和结束位置，最坏情况下时间复杂度为O(logn)
*/
public static void main(String[] args) {
int[] data={0,1,2,2,3,3,3,4,4,4,4,5};
for(int target:data){
int time=times(dat ...