• 高精度运算(4题)
Big Integer Addition
public String addStrings(String num1, String num2) {
// write your code here
String res = "";
int carry = 0;
for (int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0; i--, j--) {
int sum = carry;
sum += i >= 0 ? num1.charAt(i) - '0' : 0;
sum += j >= 0 ? num2.charAt(j) - '0' : 0;
res = sum % 10 + res;
carry = sum / 10;
}
if (carry > 0) {
res = carry + res;
}
return res;
}
View Code
Big Integer multiplication
public String multiply(String num1, String num2) {
// write your code here
int l1 = num1.length();
int l2 = num2.length();
int[] res = new int[l1 + l2 + 1];
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
res[i + j] += (num1.charAt(l1 - 1 - i) - '0') * (num2.charAt(l2 - 1 - j) - '0');
}
}
for (int i = 0; i < l1 + l2; i++) {
res[i + 1] += res[i] / 10;
res[i] = res[i] % 10;
}
int i = l1 + l2;
while (res[i] == 0 && i >= 1) {
i--;
}
String str = "";
while (i >= 0) {
str += res[i--];
}
return str;
}
View Code
Add Binary
public String addBinary(String a, String b)
{
String res = "";
int carry = 0;
for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; j--, i--) {
int sum = carry;
sum += i >= 0 ? (a.charAt(i) - '0') : 0;
sum += j >= 0 ? (b.charAt(j) - '0') : 0;
res = sum % 2 + res;
carry = sum / 2;
}
if (carry > 0) {
res = carry + res;
}
return res;
}
View Code
Add Two Numbers
public ListNode addLists(ListNode l1, ListNode l2)
{
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int carry = 0;
for (ListNode i = l1, j = l2; i != null || j != null;) {
int sum = carry;
sum += i != null ? i.val : 0;
sum += j != null ? j.val : 0;
tail.next = new ListNode(sum % 10);
tail = tail.next;
i = i == null ? i : i.next;
j = j == null ? j : j.next;
carry = sum / 10;
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return dummy.next;
}
View Code
• 快速幂(1题)
Pow(x, n)
public double myPow(double x, int n)
{
if (n < 0) {
x = 1 / x;
n = -n;
}
double res = 1, temp = x;
while (n != 0) {
if (n % 2 == 1) {
res *= temp;
}
n /= 2;
temp = temp * temp;
}
return res;
}
View Code
public double myPow(double x, int m)
{
long n = m;
if (n < 0) {
x = 1 / x;
n = -n;
}
double res = 1, temp = x;
while (n != 0) {
if (n % 2 == 1) {
res *= temp;
}
n /= 2;
temp = temp * temp;
}
return res;
}
View Code