Posted on

完成了Leetcode网站Array中的

完成了Leetcode网站Array中的Easy部分

对于这些题目的总结：

– 如果需要频繁比较数据，可以考虑将原数据排序后再进行算法操作

– 求和、求差操作不依赖数据顺序，有时候很好用 268. Missing Number

– 要特别注意数组边界数据的处理（26. Remove Duplicates from Sorted Array）

– 顺序操作、控制范围和求和是Array（数组）常规操作，但可能低效。如果善于运用高级一些的数据结构，如HashSet（217. Contains Duplicate）HashMap等，可以显著提高效率

– Java库中提供了很多例如排序查找的功能，善于利用事半功倍，例如：

  • Collections.rotate(List<?> list, distance) 189. Rotate Array （但是类型之间的转换可能会牺牲一些效率）

  • Arrays.binarySearch(int nums[], int target)，如果这个target不存在，假设它应该插入的位置是pos，那么这个函数就返回-pos-1; 35. Search Insert Position

Posted on

After years of worki

After years of working in the IT area, I step back to learn some basic skills like programming. These days I am learning Java in MOOC websites like coursera/edx/xuetangx, and will learn Python in a few days later on.

Java 8 has a lot of built in data structure and algorithms like sorting. And today, I did a simple measure on the merge sort(Arrays.sort()) and parallel sort(Arrays.parallelSort()). Here is the time needed in mill-seconds based on the number of the element (double[]) in this array, from which we can see:

– The performance of merge sort on small data volume (<100,000) is stable and even better than the parallel sort.

– The benefit of parallel sort shows when the volume exceeds 500,000

– The parallel sort is as twice better as the merge sort if the records is more than 5,000,000

– The parallel sort takes more heap space because Java will throw ‘out of memory space’ exception when the record number reach ‘100000000’. While the merge sort works in this case and take 12594 mills.

Posted on

对任意输入的正整数N，编写C程序求N!的尾部连续0的个数

一个算法题：对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18！＝6402373705728000，尾部连续0的个数是3。 分析：要出现末尾的0，必须乘数因子中有2和5，所以应该选取因子2和5数目较少的那个，因为阶乘是连续的，因子中第一个出现的是2而且出现2的速度远远大于5。所以，只要统计因子中5的数目，然后将这些数目加起来即可。 实现： import java.lang.*; import java.math.*; public class Factorial { public static void main(String[] args) { System.out.println(getTailZeros(Integer.parseInt(args[0])) + " " + factorial(BigInteger.valueOf(Integer.parseInt(args[0])))); } public static BigInteger factorial (BigInteger bigInteger) { BigInteger fact = BigInteger.ONE; for( BigInteger i = BigInteger.ONE;i.compareTo(bigInteger)<=0;i=i.add(BigInteger.ONE)) fact = fact.multiply(i); return fact; } //Count the amount of factor 5 for an int public static int countFactor5(int i) { if (i%5!=0) return 0; else return countFactor5(i/5)+1; } //Sum al the amount of factor 5 for all the factors public static int getTailZeros(int i) { int zeros = 0; for (int c=1; c <= i; c++) { zeros += countFactor5(c); } return zeros; } } 测试：编译 javac Factorial.java; 运行 java Factorial 100 结果： 24 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Posted on

利用Java中BigInteger类实现大数阶乘算法

利用Java中BigInteger类实现大数阶乘算法 很早以前在大学ACM编程中发现了BigInteger，这个类可以实现大数字的一些简单数学运算。正好现在做个算法题可以用到，就利用这个类写个简单的阶乘算法。 一、递归实现 public static BigInteger factorial (BigInteger i) { if (i.compareTo(BigInteger.ONE)==0) return BigInteger.ONE; return permutation(i.subtract(BigInteger.ONE)).multiply(i); } 递归写起来比较简单，但是当数字大时（例如10000）就会遇到java.lang.StackOverflowError. 二、迭代实现 public static BigInteger factorial (BigInteger bigInteger) { BigInteger fact = BigInteger.ONE; for( BigInteger i = BigInteger.ONE;i.compareTo(bigInteger)<=0;i=i.add(BigInteger.ONE)) fact = fact.multiply(i); return fact; } 迭代实现的版本更加清晰和便于理解，而且当数字大时不会出现StackOverflowError异常，所以应该是个更好的解决方案。 2010/6/23 10:06