告别2008
-----
作别昨日昨天
避人避情避责
胜命胜运胜天
决心冲开这巨网
不记望
以后会是如何
只要避人海
莫问谁错
苍生中很多
欲望若能降
你会更快乐
今天看到一道题目,关于两个n位十进制数的加法问题,不禁想起了n久前在一次华为的面试中被问起两个50位的整数相乘的问题。唉,一个小小的问题,说起来虽然简单,实际做的时候却有很多细节要注意,我平时还是空想大于实干了。
不曾想到,这段代码,来来回回居然花了几个小时的时间。
//(#)NBitDecimalIntegerAlgorithm.java
public class NBitDecimalIntegerAlgorithm {
/**
* addition
*
* @param a the first addend
* @param b the second addend
*
* @return the sum
*/
public static int[] addAB(int[] a, int[] b) {
int maxLength = a.length;
if (a.length < b.length) {
maxLength = b.length;
}
int[] integerA = new int[maxLength];
int[] integerB = new int[maxLength];
for (int i = 0; i < a.length; i++) {
integerA[i] = a[i];
}
for (int i = 0; i < b.length; i++) {
integerB[i] = b[i];
}
int[] sum = new int[maxLength + 1];
int carry = 0;
for (int i = 0; i < maxLength; i++) {
int tempSum = integerA[i] + integerB[i] + carry;
int remainder = tempSum % 10;
carry = tempSum / 10;
sum[i] = remainder;
}
sum[sum.length - 1] = carry;
return sum;
}
/**
* multiplication
*
* @param a the first factor
* @param b the second factor
*
* @return the product
*/
public static int[] multiplyAB(int[] a, int[] b) {
int[] sumProduct = new int[a.length + 1];
for (int i = 0; i < b.length; i++) {
int[] product = multiplyAB(a, b[i], i);
sumProduct = addAB(sumProduct, product);
}
return sumProduct;
}
public static String parseStr(int[] v) {
String str = "";
for (int i = v.length; i > 0; i--) {
if (v[i - 1] != 0 || !str.equals("")) {
str += v[i - 1];
}
}
return str;
}
private static int[] multiplyAB(int[] a, int b, int bIndex) {
int[] product = new int[a.length + 1 + bIndex];
int carry = 0;
for (int i = 0; i < a.length; i++) {
int tempProduct = a[i] * b + carry;
int remainder = tempProduct % 10;
carry = tempProduct / 10;
product[bIndex + i] = remainder;
}
product[bIndex + a.length] = carry;
return product;
}
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 3, 5}; //3501987654321
int[] b = {1, 2, 3, 4, 5, 6, 7, 8, 9}; //987654321
int[] s = addAB(a, b);
int[] p = multiplyAB(a, b);
System.out.println(parseStr(a));
System.out.println(parseStr(b));
System.out.println(parseStr(s));
System.out.println(parseStr(p));
}
}
public abstract class Orange {
protected String taste;
protected String name;
public String getTaste() {
return taste;
}
public String getName() {
return name;
}
}
public class MandarinOrange extends Orange {
public MandarinOrange() {
this.name = "Mandarin Orange";
this.taste = "delicious";
}
}
public class FunnyOrange extends Orange {
public FunnyOrange() {
this.name = "Funny Orange";
this.taste = "funny";
}
}
public abstract class Soil {
abstract public Orange harvestOrange();
public void printInvolvedParameter() {
Orange org = this.harvestOrange();
System.out.println("Species:" + org.getName());
System.out.println("Tastes:" + org.getTaste());
}
}
public class HuaiNanSoil extends Soil {
@Override
public Orange harvestOrange() {
return new MandarinOrange();
}
}
public class HuaiBeiSoil extends Soil {
@Override
public Orange harvestOrange() {
return new FunnyOrange();
}
}
public class TestFactoryMethodPattern {
public static void main(String[] args) {
Soil soil = new HuaiNanSoil();
soil.printInvolvedParameter();
System.out.println("----------");
soil = new HuaiBeiSoil();
soil.printInvolvedParameter();
}
}
public abstract class MyAbstractClass {
public static String myProperty1;
public static String myProperty2;
abstract public void myMethod1();
abstract public void myMethod2();
}
public interface MyInterface {
String myProperty1 = null;
String myProperty2 = null;
void myMethod1();
void myMethod2();
}
public class MyConcreteClass1 extends MyAbstractClass {
public void myMethod1() {
System.out.println("MyConcreteClass1 myMethod1");
}
public void myMethod2() {
System.out.println("MyConcreteClass1 myMethod2");
}
}
public class MyConcreteClass2 implements MyInterface {
public void myMethod1() {
System.out.println("MyConcreteClass2 myMethod1");
}
public void myMethod2() {
System.out.println("MyConcreteClass2 myMethod2");
}
}